Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 1,021

ОПТИМИЗАЦИЯ СХЕМ АЛГОРИТМОВ СТОХАСТИЧЕСКОГО ПОИСКА С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ НЕЧЕТКОГО УПРАВЛЕНИЯ

Корнеев А.М. 1 Бузина О.П. 1 Суханов А.В. 1
1 ФГБОУ ВО «Липецкий государственный технический университет»
Настоящая работа посвящена развитию методов нечёткой логики применительно к оптимизации схем алгоритмов стохастического поиска. В качестве объектов исследования выступают схемы алгоритмов стохастической оптимизации на основе метода имитации отжига, в частности схемы Больцмана и Коши, которые признаны одними из самых эффективных для случая оптимизации многоэкстремальных функций. Вариативность расчетных параметров алгоритмов при построении структур схем стохастического поиска актуализирует исследования в данной области с использованием методов нечеткого управления; это актуально, например, для случаев, когда расчетные параметры алгоритмов в системах со сложной иерархией варьируются в зависимости от решаемых в процессе управления задач. Одна из таких задач – оптимизация значений координат кусочно-линейных деформационных диаграмм и параметров химического состава в системе управления процессом структуризации чугунных сплавов. Целью настоящего исследования является оптимальная модификация схем алгоритмов стохастического поиска методом имитации отжига (simulated annealing) применительно к решению данной прикладной задачи. В качестве инструмента интеллектуальной поддержки при выборе численных параметров алгоритмов оптимизации в разработанной системе принятия решений использован метод нечеткого управления Такаги и Сугено. Авторами предложена база правил для осуществления нечёткого управления, а также функции принадлежности, необходимые для осуществления нечёткого вывода. В статье показано, каким образом метод нечёткого управления Такаги и Сугено помогает осуществить интеллектуальную поддержку в системе принятия решений при построении модифицированных схем алгоритмов стохастического поиска. С применением описанных в статье методик разработана автоматизированная система интеллектуальной поддержки принятия решений процессов, участвующих в формировании оптимального химического состава чугунных сплавов.
нечёткая логика
стохастический поиск
метод имитации отжига
случайная величина
функция распределения
схема алгоритма
1. Корнеев А.М., Суханов А.В. Исследование точности и скорости сходимости алгоритмов стохастической оптимизации функций на многомерном пространстве // Вестник АГТУ. Серия: управление, вычислительная техника и информатика. 2018. № 3. С. 26–37.
2. Ingber L. Simulated Annealing: Practice versus theory. Mathematical and Computer Modelling. 1993. Vol. 18 (11). P. 29–57.
3. Zhigljavsky A., Zilinskas A. Stochastic Global Optimization. Berlin: Springer. 2008. 262 p.
4. Корнеев А.М., Суханов А.В. Структура системы принятия решений по управлению процессом формирования химического состава отливок из чугуна // Современная наука: актуальные проблемы теории и практики. Серия «Естественные и технические науки». 2018. № 6. С. 73–77.
5. Щербина О.А. Метаэвристические алгоритмы для задач комбинаторной оптимизации (обзор) // Таврический вестник информатики и математики. 2014. № 1 (24). С. 56–72.
6. Грибанова Е.Б. Стохастический алгоритм поиска // Прикладная информатика. Journal of applied informatics. 2017. № 2 (68). С. 130–134.
7. Альбакасов А.И., Гарькина И.А., Данилов А.М., Королев Е.В. Оптимизация систем со сложной иерархией // Вестник гражданских инженеров. 2012. № 2. С. 324–327.
8. Корнеев А.М., Бузина О.П., Суханов А.В., Галай И.Г. Интеллектуальная поддержка принятия решений в системе управления процессом формирования оптимального химического состава отливок из чугуна // Современные наукоемкие технологии. 2018. № 7. С. 37–42.
9. Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by simulated annealing. Science. 1983. Vol. 220. P. 671–680.
10. Тихомиров А.С. О быстрых вариантах алгоритма отжига (simulated annealing) // Стохастическая оптимизация в информатике. 2009. Т. 46. № 3. С. 379–394.
11. Takagi Т., Sugeno M., Fuzzy Identification of Systems and Its Applications to Modeling and Control, IEEE Transactions on Systems, Man and Cybernetics. 1985. vol. 15. P. 116–132.

Для решения задач оптимизации в настоящее время разработаны многочисленные методы стохастического поиска, основанные на марковских случайных процессах [1, 2]. В частности, одними из самых эффективных методов для случая оптимизации многоэкстремальной целевой функции являются метаэвристические: метод имитации отжига, являющийся примером метода Монте-Карло; эволюционные алгоритмы, моделирующие процессы естественного отбора; муравьиный алгоритм и многие другие [3]. Метаэвристические методы позволяют находить оптимальные решения для задач, являющихся трудноразрешимыми с точки зрения прямого аналитического исследования [4]. Во многом именно поэтому данные методы являются эффективными и популярными современными инструментами для решения широкого круга оптимизационных задач [5].

Одно из важнейших достоинств данных методов заключается в том, что правильная реализация (модификация с учётом решаемой задачи) метаэвристического алгоритма позволяет обеспечить нахождение близкого к оптимальному решения за разумное время или малое число итераций [1, 6]. Такая гибкость в организации схем стохастического поиска актуализирует исследования в области оптимизации схем алгоритмов случайного поиска с использованием методов нечеткого управления: например для случаев, когда расчетные параметры алгоритмов в системах со сложной иерархией варьируются в зависимости от решаемых в процессе управления задач [7].

Цель исследования: оптимальная модификация схем алгоритмов стохастического поиска методом имитации отжига (simulated annealing) применительно к решению отдельной прикладной задачи – поиска оптимальных значений координат опорных точек кусочно-линейных диаграмм деформирования, необходимых для проведения вычислительных экспериментов в автоматизированной системе принятия решений по управлению процессом формирования химического состава отливок из чугуна. Для принятия решений в автоматизированной системе используются методы нечеткого управления. Принципы работы системы принятия решений в системе управления процессом формирования оптимального химического состава отливок из чугуна подробно рассмотрены в работе [8].

В работе [9] S. Kirkpatrick предложил метод случайного поиска глобального минимума функции, называемый simulated annealing (метод имитации отжига). Киркпатрик сформулировал метод для условий наличия явных ограничений на изменяемые параметры [2]. Метод эффективно определяет минимум заданной для x функции f(x). При этом переменная x определена на некотором дискретном или непрерывном пространстве Ω. Элементы данного пространства представлены как состояния мнимой системы, под энергией которой понимаются значения самой функции E = f(x). Под температурой понимают параметр системы T, который уменьшается со временем. Основное его предназначение – «тушение» алгоритма для случая, когда не заданы иные условия остановки работы алгоритма. Параметр T соответствует каждому состоянию системы x. Каждое следующее состояние системы генерируется с использованием заданной функции G(x, T), являющейся вероятностным распределением. Функция G(x, T) генерирует случайный элемент из пространства Ω при известных x и T. В новое состояние x' = G(x, T) система переходит с вероятностью p(ΔE, T), в ином случае состояние x' генерируется снова на новом шаге алгоритма. Величина ΔE определяется как изменение энергии системы, а величина p(ΔE, T) является вероятностью принятия нового состояния.

Поиск глобального минимума целевой функции f : Rn осуществляется на некотором собственном подмножестве метрического пространства Rn:

f(x1, ..., xn) > min, x∈Ω, Ω∈Rn,

где подмножество Ω определяется ограничениями в виде q(x) = 0, q : Rn.

В качестве функции, задающей вероятность принятия нового состояния, выбирается либо точное значение

korneev01.wmf,

либо приближенное значение

korneev02.wmf.

Последняя формула используется с условием p(ΔE, T) > 1 в случае ΔE < 0, и тогда вероятность перехода в новое состояние p(ΔE, T) считается равной 1. Поиск минимума целевой функции завершается при уменьшении значения параметра T до некоторого заданного уровня Tend. Таким образом, схема метода отжига задается следующими параметрами: законом изменения параметра T(k), где k – номер шага; порождающим семейством вероятностных распределений G(x, T); функцией вероятности перехода системы в новое состояние p(ΔE, T).

Одной из самых распространенных схем метода simulated annealing является схема Больцмана. В данной схеме изменение параметра T алгоритма задается формулой

korneev03.wmf, korneev04.wmf.

Если T принять за дисперсию, x – за математическое ожидание, то плотность вероятностных распределений выбирается как семейство нормальных распределений, задаваемых функцией

korneev05.wmf,

где D – размерность метрического пространства состояний.

Другой распространенной схемой метода имитации отжига является схема Коши. В данной схеме изменение параметра T алгоритма задается формулой

korneev06.wmf, korneev07.wmf.

При данной схеме не будет иметь место отсутствие гарантии нахождения оптимума, поскольку здесь использованы нормированные распределения Коши с плотностью, заданной уравнением

korneev08.wmf.

Данные схемы допускают модификации А, Б и В, подробно описанные в работах [1, 10].

Данные схемы алгоритмов стохастического поиска используются для оптимизации значений координат кусочно-линейных деформационных диаграмм и параметров химического состава в системе управления процессом структуризации чугунных сплавов [4, 8]. Выбор альтернатив решений при оптимизации значений координат кусочно-линейных деформационных диаграмм (ξ1, ..., ξ28) в системе управления представлен в табл. 1. Выбор альтернатив решений при оптимизации значений содержания химических элементов в сплаве чугунов (ξ1, ..., ξ14) представлен в табл. 2.

Таблица 1

Выбор алгоритма оптимизации параметров

Размерность области

стохастического поиска

Оптимизируемые параметры Ξ

Модификация алгоритма

оптимизации

1 ≤ D ≤ 8

ξ15, ξ16, ξ22, ξ23

Схема Больцмана модификации А

ξ1, ξ2, ξ8, ξ9

Схема Больцмана модификации А

8 < D ≤ 20

ξ15, ξ16, ξ17, ξ18, ξ19, ξ22, ξ23, ξ24, ξ25, ξ26

Схема Коши модификации А, Б или В

ξ1, ξ2, ξ3, ξ4, ξ5, ξ8, ξ9, ξ10, ξ11, ξ12

20 < D ≤ 28

ξ15, …, ξ28

ξ1, …, ξ14

Сверхбыстрый поиск

Таблица 2

Выбор алгоритма оптимизации параметров при оптимизации значений содержания химических элементов в сплаве

Размерность области

стохастического поиска

Оптимизируемые параметры Ξ

Модификация алгоритма

оптимизации

1 ≤ D ≤ 6

ξ1, ξ2

Схема Больцмана модификации А, Б или В

ξ3, ξ4

Схема Коши модификации А, Б или В

ξ5, ξ6

Сверхбыстрый поиск

6 < D ≤ 10

ξ1, …, ξ3

Схема Коши модификации А, Б или В

ξ4, …, ξ6

ξ7, ..., ξ10

Сверхбыстрый поиск или алгоритм Ксин Яо

10 < D ≤ 14

ξ1, …, ξ5

Схема Коши модификации А, Б или В

ξ6, …, ξ10

ξ11, …, ξ14

Алгоритм Ксин Яо

Схема принятия решения при выборе модификации алгоритма оптимизации параметров множества Ξ представлен на рис. 1.

korneev1.tif

Рис. 1. Схема принятия решения при выборе модификации алгоритма оптимизации

В качестве инструмента интеллектуальной поддержки при выборе численных параметров алгоритмов оптимизации коэффициентов характеристических диаграмм в разработанной системе принятия решений применяется метод нечеткого управления Такаги и Сугено [11]. Данный метод применяется здесь для определения коэффициента χ, влияющего на скорость сходимости алгоритма поиска: korneev09.wmf для схемы Больцмана и korneev10.wmf для схемы Коши.

В системе принятия решений [8] сигнал, подающийся на вход модуля нечеткого управления [4], имеет вид korneev11.wmf, где x1 – значение размерности области стохастического поиска (D), x2 – значение, характеризующее сложность композиционной структуры чугунного сплава, – количество фаз в матрице сплава (графиты, феррит, аустенит и др.). korneev12.wmf и korneev13.wmf могут принимать следующие значения:

– малое: korneev14.wmf, korneev15.wmf;

– среднее: korneev16.wmf, korneev17.wmf;

– большое: korneev18.wmf, korneev19.wmf.

База правил модуля записывается в виде:

R(1) : ЕСЛИ (x1 малое И x2 малое) ТОГДА y1 = 0,5 + 0,045x1 + 0,11x2,

R(2) : ЕСЛИ (x1 малое И x2 среднее) ТОГДА y2 = 0,5 + 0,025x1 + 0,063x2,

R(3) : ЕСЛИ (x1 малое И x2 большое) ТОГДА y3 = 0,51 + 0,02x1 + 0,005x2,

R(4) : ЕСЛИ (x1 среднее И x2 малое) ТОГДА y4 = 0,55 + 0,02x1 + 0,01x2,

R(5) : ЕСЛИ (x1 среднее И x2 среднее) ТОГДА y5 = 0,55 + 0,021x1 + 0,015x2,

R(6) : ЕСЛИ (x1 среднее И x2 большое) ТОГДА y6 = 0,56 + 0,017x1 + 0,005x2,

R(7) : ЕСЛИ (x1 большое И x2 малое) ТОГДА y7 = 0,53 + 0,017x1 + 0,008x2,

R(8) : ЕСЛИ (x1 большое И x2 среднее) ТОГДА y8 = 0,53 + 0,018x1 + 0,007x2,

R(9) : ЕСЛИ (x1 большое И x2 большое) ТОГДА y9 = 0,6 + 0,017x1 + 0,006x2.

Правила нечеткого вывода для значений korneev20.wmf и korneev21.wmf вектора входного сигнала представлены на рис. 2.

korneev2a.tif korneev2b.tif

а) б)

Рис. 2. Функции принадлежности для значений вектора входного сигнала: а – для параметра korneev22.wmf , б – для параметра korneev23.wmf

korneev3.tif

Рис. 3. Приближение значений коэффициентов ξ1 (xC), ξ3 (xMn), ξ4 (xP), ξ5 (xS) к оптимальным

Выходной сигнал модуля korneev24.wmf определяется здесь следующим образом. Для правил R(k), k = 2,…,9 рассчитывается

korneev25.wmf, korneev26.wmf,

где korneev27.wmf, korneev28.wmf – результаты нечеткого вывода (рис. 2, а, б).

Выходной сигнал модуля нечеткого управления Такаги – Сугено тогда будет иметь вид

korneev29.wmf.

Для анализа предложенного способа модификаций проведения вычислительных экспериментов написана программа для ЭВМ, позволяющая осуществлять интеллектуальную поддержку принятия решений при формировании химического состава отливок из чугуна [8]. Один из модулей программы позволяет анализировать зависимости между расчетными параметрами алгоритма и основными характеристиками его работы – точности и скорости сходимости к оптимальным значениям. Основные результаты такого анализа приведены в работе [1]. Графически приближение точек ξ1(xC), ξ3 ( xMn), ξ4 ( xP), ξ5 ( xS) (каждая десятая итерация) для чугуна марки ЧХ1 к найденному оптимальному значению проиллюстрировано на рис. 3 (в процессе оптимизации была выбрана схема Больцмана).

Выводы

Таким образом, метод нечёткого управления Такаги и Сугено помогает осуществить интеллектуальную поддержку в системе принятия решений при построении модифицированных схем алгоритмов стохастического поиска посредством автоматического расчета параметров алгоритмов в зависимости от размерности пространства поиска или количества оптимизируемых величин. С применением описанного метода разработана автоматизированная система интеллектуальной поддержки принятия решений процессов, участвующих в формировании оптимального химического состава чугунных сплавов.


Библиографическая ссылка

Корнеев А.М., Бузина О.П., Суханов А.В. ОПТИМИЗАЦИЯ СХЕМ АЛГОРИТМОВ СТОХАСТИЧЕСКОГО ПОИСКА С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ НЕЧЕТКОГО УПРАВЛЕНИЯ // Современные наукоемкие технологии. – 2018. – № 10. – С. 65-70;
URL: http://top-technologies.ru/ru/article/view?id=37196 (дата обращения: 17.06.2021).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074