ИССЛЕДОВАНИЕ ТОЧНОСТИ И СКОРОСТИ СХОДИМОСТИ АЛГОРИТМОВ СТОХАСТИЧЕСКОЙ ОПТИМИЗАЦИИ ФУНКЦИЙ НА МНОГОМЕРНОМ ПРОСТРАНСТВЕ
Авторы:
1.
Липецкий государственный технический университет
(доктор технических наук, доцент; профессор кафедры общей механики)
2.
Липецкий государственный технический университет
Тип:
Статья
Страницы:
с 26
по 37
Статус:
Опубликован
Получено:
05.07.2018
Одобрено:
25.07.2018
Опубликовано:
25.07.2018
Классификаторы:
ВАК 05.12.2013 Системы, сети и устройства телекоммуникаций
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 519.853.4
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 519.853.4
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
Язык материала:
русский
Ключевые слова:
стохастическая оптимизация, метод имитации отжига, схема Больцмана, схема Коши, точность, сходимость, экстремум
Аннотация (русский):
Целью настоящей работы является анализ точности вычислений и величины временных затрат на поиск оптимальных значений для функций нескольких переменных с помощью алгоритмов стохастической оптимизации на основе метода имитации отжига. Для проведения исследования сотрудниками кафедры общей механики Липецкого государственного технического университета создано программное обеспечение, реализующее алгоритмы поиска экстремальных значений для функций нескольких переменных. Функциональное назначение программного обеспечения - интеллектуальная поддержка принятия решений при формировании химических составов чугунных сплавов. Оптимизация производится на определенной и фиксированной области поиска, которая представляет собой гиперпараллелепипед, - границы варьирования процентного содержания химического элемента в сплаве. В программе реализовано десять модификаций алгоритма имитации отжига, позволяющих за конечное число шагов выполнить оценку оптимального значения входных элементов исследуемой функции на многомерном пространстве. В частности, реализованы модификации А, Б и В схем алгоритма с применением функций распределения Больцмана и Коши, а также алгоритм сверхбыстрого отжига и алгоритм Ксин Яо. Приведены результаты вычислительного эксперимента для трех различных функций: от шести, восьми и девяти переменных; проведен сравнительный анализ близости результатов к оптимальным значениям для каждой модификации алгоритма. Полученные данные позволили сделать выводы о преимуществах и недостатках каждой из модификаций алгоритма стохастического поиска. На основе результатов вычислительных экспериментов определены закономерности между временными затратами алгоритмов и их численными параметрами. С помощью линейной регрессии получены аналитические зависимости, позволяющие оценивать время работы алгоритмов в зависимости от значений их численных параметров. Работа содержит ряд выводов о применимости модификаций стохастической оптимизации для решения прикладных задач, выделены недостатки модификаций и их достоинства.
Целью настоящей работы является анализ точности вычислений и величины временных затрат на поиск оптимальных значений для функций нескольких переменных с помощью алгоритмов стохастической оптимизации на основе метода имитации отжига. Для проведения исследования сотрудниками кафедры общей механики Липецкого государственного технического университета создано программное обеспечение, реализующее алгоритмы поиска экстремальных значений для функций нескольких переменных. Функциональное назначение программного обеспечения - интеллектуальная поддержка принятия решений при формировании химических составов чугунных сплавов. Оптимизация производится на определенной и фиксированной области поиска, которая представляет собой гиперпараллелепипед, - границы варьирования процентного содержания химического элемента в сплаве. В программе реализовано десять модификаций алгоритма имитации отжига, позволяющих за конечное число шагов выполнить оценку оптимального значения входных элементов исследуемой функции на многомерном пространстве. В частности, реализованы модификации А, Б и В схем алгоритма с применением функций распределения Больцмана и Коши, а также алгоритм сверхбыстрого отжига и алгоритм Ксин Яо. Приведены результаты вычислительного эксперимента для трех различных функций: от шести, восьми и девяти переменных; проведен сравнительный анализ близости результатов к оптимальным значениям для каждой модификации алгоритма. Полученные данные позволили сделать выводы о преимуществах и недостатках каждой из модификаций алгоритма стохастического поиска. На основе результатов вычислительных экспериментов определены закономерности между временными затратами алгоритмов и их численными параметрами. С помощью линейной регрессии получены аналитические зависимости, позволяющие оценивать время работы алгоритмов в зависимости от значений их численных параметров. Работа содержит ряд выводов о применимости модификаций стохастической оптимизации для решения прикладных задач, выделены недостатки модификаций и их достоинства.
Ключевые слова:
стохастическая оптимизация, метод имитации отжига, схема Больцмана, схема Коши, точность, сходимость, экстремум
стохастическая оптимизация, метод имитации отжига, схема Больцмана, схема Коши, точность, сходимость, экстремум
Введение Для решения задач оптимизации в настоящее время разработаны многочисленные методы стохастического поиска, основанные на марковских случайных процессах [1-6]. В частности, одними из самых эффективных методов для случая оптимизации многофакторной целевой функции являются метаэвристические: генетические алгоритмы, табу-поиск (tabu search), метод имитации отжига (simulated annealing), максимальная муравьиная система (max-min ant system), метод муравьиных колоний (ant colony optimization), оптимизация роем частиц (particle swarm optimization), метод дифференциальной эволюции и др. [6-10]. Преимущество метаэвристических методов на основе стохастических алгоритмов состоит в их способности решать комплекс сложных задач в условиях отсутствия знаний о пространстве поиска; более того, хорошая реализация метаэвристического метода может обеспечить нахождение близкого к оптимальному решения за разумное время или число итераций. Во многом именно поэтому такие методы позволяют находить оптимальные решения для задач, являющихся трудноразрешимыми с точки зрения прямого аналитического исследования. Весьма упрощенно метаэвристики можно рассматривать как алгоритмы, реализующие прямой случайный поиск на дискретном пространстве возможных оптимальных или близких к оптимальным решений задачи, пока не будет выполнено поставленное условие или достигнуто заданное число итераций. Современными исследователями метаэвристики признаны мощным и чрезвычайно популярным классом оптимизационных методов, которые с высокой эффективностью позволяют находить решения для широкого круга задач из различных приложений [7, 11, 12]. Однако часто при решении задач прикладного характера исследователям приходится прибегать к поиску компромиссных решений при построении схем поисковых алгоритмов - необходимо делать выбор между высокой скоростью вычислений и их точностью [13]. Целью данного исследования является анализ точности и скорости сходимости алгоритмов стохастической оптимизации, позволяющих осуществлять поиск оптимальных значений функций нескольких переменных на множествах с размерностью D > 10. Оптимизация таких функций применяется для решения задач в различных отраслях, например для определения химического состава сплавов чугунных отливок [14] или для поиска численных значений параметров характеристических диаграмм, описывающих напряженно-деформированное состояние элементов со сложной композитной структурой [15]. В настоящей работе приводится сравнительный анализ скорости работы и точности искомых значений для следующих модификаций алгоритма имитации отжига (simulated annealing): алгоритм, построенный по схеме Больцмана модификаций А, Б, В; алгоритм, построенный по схеме Коши модификаций А, Б, В; алгоритм сверхбыстрого отжига и алгоритм Ксин Яо. Оптимизация производится на определенном наборе переменных функции f: RD → R (D < 10) и на фиксированной области поиска, которая представляет собой гиперпараллелепипед. Программное обеспечение для проведения вычислительного эксперимента Для проведения исследований написана программа для ЭВМ, позволяющая осуществлять интеллектуальную поддержку принятия решений при формировании химического состава отливок из чугуна. Один из модулей программы позволяет оценить зависимость скорости работы алгоритма стохастического поиска от его численных входных параметров: начальной температуры T0, количества циклов L и параметра снижения температуры c. Главное окно программы показано на рис. 1. Рис. 1. Главное окно программы для определения оптимального химического состава отливок из чугуна В отдельном модуле выбирается модификация алгоритма стохастического поиска. Анализ данных о работе алгоритма представлен в окне модуля, изображенного на рис. 2. Рис. 2. Окно модуля вывода данных о работе алгоритма Программа написана на языке С++ в среде Builder 6.0 и работает в операционных системах Windows 95, 98, ХР и последующих. Программы запускаются в оконном режиме и предусматривают ввод данных вручную. Вывод результата вычислений происходит непосредственно в окнах интерфейса программ. Метод отжига позволяет за конечное число шагов искать глобальный минимум (максимум) некоторой функции f(x), заданной на некотором непрерывном или дискретном пространстве S. Значения функции f в точках, являющихся элементами пространства S, представляются как энергия воображаемой физической системы E = f(x). Температура системы T, заданная в каждый момент, с течением времени уменьшается. Каждое новое состояние системы задается в соответствии с заданной функцией J(x, T), которая является порождающим семейством вероятностных распределений. Функция J(x, T) задает случайный элемент G(x, T) со значениями в пространстве S при фиксированных x и T. С вероятностью, равной h(ΔE, T), система после генерации нового состояния x' = G(x, T) переходит к следующему шагу (уже в состоянии x'), в противном случае повторяется процесс генерации состояния x'. Здесь ΔE = f(x') - f(x) есть приращение функции энергии системы, а величина h(ΔE, T) является вероятностью принятия нового состояния [3]. В качестве функции, задающей вероятность принятия нового состояния, выбирается либо точное значение либо приближенное значение Чаще всего используется вторая формула [3]. Приведем наиболее простой вариант алгоритма метода стохастического поиска simulated annealing. 1. Случайным образом выбирается начальная точка x = x0, x0 Î S. Определяется текущее значение функции энергии системы E = f(x0). 2. Пока не выполнено условие остановки поиска T(k) < Tend, выполнять следующие шаги k-й итерации основного цикла. 2.1. Сравнить значения функции E в состоянии x и в состоянии, являющемся на текущем моменте глобальным минимумом. В случае если значение E = f(x) оказалось меньше, то изменить значение глобального минимума. 2.2. Сгенерировать новое состояние x' = G(x, T). 2.3. Определить значение функции в новом состоянии E' = f(x'). 2.4. Сгенерировать случайное число α Î [0, 1]. 2.5. В случае если α < p(ΔE, T(k)), установить x ← x', E ← E' и перейти к итерации k + 1. Если α ≥ p(ΔE, T(k)), повторять шаг 2.2 до тех пор, пока не будет найдена подходящая точка x'. Возможны следующие модификации приведенного алгоритма: Модификация А. На шаге 2.5, в случае если точка x' не является подходящей, переход к следующей итерации возможен при условии, что следующая итерация начинается с точки x с новым значением уменьшающегося параметра T. Модификация Б. Для случая большой размерности S с целью ускорения работы алгоритма в качестве оценки точки глобального минимума принимается последнее значение x. Однако такой подход может привести к худшему решению, особенно если значение параметра T значительно превышает ноль к моменту завершения работы алгоритма. Модификация В. В начале работы алгоритма на шаге 1 принимается x ← x0, а на шаге 2.2 новая точка x' вычисляется рекуррентно по формуле x' = G(x', T). Такой подход позволяет алгоритму «не застревать». Однако при такой реализации алгоритм simulated annealing практически не отличается от обычного стохастического поиска, что приводит к потере ряда преимуществ алгоритма. Блок-схема полной процедуры поиска минимума целевой функции методом simulated annealing представлен на рис. 3. Рис. 3. Блок-схема алгоритма имитации отжига (поиск минимума) Одной из самых распространенных схем метода simulated annealing является схема Больцмана (больцмановский отжиг). В данной схеме изменение параметра T алгоритма задается формулой , . Плотность вероятностных распределений выбирается как семейство нормальных распределений с математическим ожиданием x и дисперсией T: , где D - размерность метрического пространства состояний. Основной недостаток данной схемы - медленное убывание температуры T. По этой причине исследователями Хартли и Цу [3] была предложена схема алгоритма, в которой для изменения параметра T используется формула . При данной схеме не происходит потеря гарантии нахождения минимума за счет использования соответствующим способом нормированных распределений Коши с плотностью . В данной схеме глобальный минимум определяется гарантированно только при изменении параметра T со скоростью, не превышающей , что намного медленнее больцмановской схемы [3]. С целью исключить недостатки двух описанных методов Л. Ингбером был предложен метод сверхбыстрого стохастического поиска (Very Fast Annealing) [3]. В предложенной схеме пространство S считается состоящим из векторов размерности D: , , где Ai, Bi - граничные значения для элемента xi. Для каждой из координат параметр T может быть различным, т. е. T также является вектором в пространстве с размерностью D. Построение семейства распределений осуществляется следующим образом. Вводится величина y = Δx/(Bi - Ai); новое значение поиска x' вычисляется по формуле где zi - случайная величина на множестве [-1, 1] с плотностью распределения , Случайная величина zi моделируется следующим образом: , где αi - независимые случайные величины, равномерно распределенные на интервале [0, 1]. Преимущество схемы сверхбыстрого поиска заключается в том, что при ее использовании допустимо очень быстрое моделирование плотностей распределения G независимо от размерности множества S. Другим методом сверхбыстрого поиска является алгоритм, предложенный Ксин Яо [3]. Уникальность метода заключается в повторном применении схемы предыдущего алгоритма. Плотность распределения здесь задается следующим способом: . Проведение вычислительного эксперимента, анализ результатов В программе предусмотрено ограничение на количество переменных - функция не может зависеть более чем от тринадцати переменных (максимальное количество химических элементов, содержащихся в отливке из чугуна). В программе предусматриваются ограничения на размер области определения функции и величины значений численных параметров расчетных алгоритмов. Отметим, что время работы программы и точность полученных с помощью нее данных зависят от этих численных параметров. Все числа принимаются в формате целого (int) или плавающего с двойной точностью (double). Исследование проводилось с применением функций f1: R6 → R; f2: R8 → R; f3: R9 → R на фиксированной области поиска, которая представляет собой гиперпараллелепипед: - для функции f1: ; - для функции f2: ; - для функции f3: . При исследовании алгоритмов на точность выдаваемых результатов значение начальной температуры для всех модификаций составляло T0 = 5, значение коэффициента тушения c = 0,999. Вычислительные эксперименты проводились на компьютере с процессором AMD Ryzen 3 1300X Quad-Core 3,50 GHz, ОЗУ 8,00 Гб. Результаты оптимизации (поиска максимума) функций для десяти модификаций алгоритма имитации отжига представлены в табл. 1. Таблица 1 Оптимальные значения функций для различных модификаций алгоритма № п/п * Функция Алгоритм на основе схемы Больцмана Алгоритм на основе схемы Коши Сверхбыстрый отжиг Алгоритм Ксин Яо Без модификции А Б В Без модификции А Б В 1 f 1 48,86 48,88 48,88 48,88 48,88 48,64 48,27 48,52 48,89 48,87 2 48,85 48,84 48,86 48,88 48,82 48,68 48,85 48,32 48,89 48,87 3 48,87 48,84 48,86 48,87 48,87 48,82 48,87 48,82 48,89 48,87 4 48,87 48,87 48,87 48,86 48,86 48,50 48,78 48,80 48,88 48,88 5 48,88 48,87 48,87 48,89 48,88 48,70 48,83 48,52 48,88 48,89 6 48,86 48,87 48,86 48,88 48,85 48,63 48,84 48,76 48,89 48,87 7 f 2 49,35 49,36 49,37 49,37 49,40 49,35 49,37 49,35 49,40 49,35 8 49,36 49,38 49,37 49,39 49,37 49,11 49,35 49,32 49,40 49,35 9 49,38 49,38 49,37 49,38 49,39 49,07 49,40 49,16 49,40 49,36 10 49,38 49,38 49,38 49,38 49,37 48,96 49,38 49,31 49,40 49,38 11 49,39 49,37 49,37 49,36 49,38 49,00 49,37 49,30 49,41 49,38 12 49,36 49,37 49,36 49,36 49,38 49,32 49,37 48,67 49,40 49,35 13 49,38 49,39 49,38 49,33 49,40 49,30 49,38 49,37 49,41 49,35 14 49,38 49,36 49,37 49,40 49,37 49,32 49,37 49,39 49,40 49,36 Окончание табл. 1 № п/п * Функция Алгоритм на основе схемы Больцмана Алгоритм на основе схемы Коши Сверхбыстрый отжиг Алгоритм Ксин Яо Без модификции А Б В Без модификции А Б В 15 f 3 49,16 48,87 49,11 49,11 49,09 49,00 49,13 49,02 49,18 49,13 16 49,14 49,10 49,10 49,12 49,16 49,05 49,13 49,05 49,18 49,16 17 49,08 49,15 49,09 49,15 49,14 49,09 49,15 49,13 49,19 49,11 18 49,16 49,08 49,08 49,10 49,10 48,75 49,15 49,17 49,18 49,16 19 49,11 49,08 49,14 49,15 49,13 49,11 49,17 49,09 49,18 49,15 20 49,11 49,12 49,13 49,16 49,16 49,14 49,10 49,08 49,18 49,13 21 49,11 49,08 49,10 49,15 49,15 49,12 49,12 48,71 49,19 49,12 22 49,10 49,13 49,16 49,14 49,12 48,81 49,11 48,76 49,18 49,11 23 49,11 49,14 49,12 49,15 49,13 49,15 49,04 49,09 49,18 49,12 24 49,12 49,11 49,09 49,11 49,06 49,15 49,17 49,07 49,18 49,15 Среднее значение 49,140 417 49,125 83 49,137 08 49,148 75 49,144 17 48,990 42 49,112 5 48,990 83 49,181 67 49,144 58 Дисперсия 0,037 421 0,041 091 0,037 087 0,035 436 0,039 841 0,057 304 0,069 377 0,087 649 0,038 031 0,033 891 * Номер вычислительного эксперимента. Графическое представление результатов (табл. 1) показано на рис. 4. Рис. 4. Графическое представление результатов вычислительного эксперимента по исследованию точности алгоритмов стохастической оптимизации Наиболее близкие к максимальным (оптимальным) значениям оказались результаты вычислений с применением алгоритма сверхбыстрого отжига и модификация В алгоритма имитации отжига на основе схемы Больцмана. Однако результаты, полученные с применением модификации В алгоритма имитации отжига на основе схемы Больцмана, отличаются меньшей дисперсией, что позволяет сделать утверждение о его предпочтительности для решения задач стохастической оптимизации функций на многомерном пространстве. Результаты вычислительного эксперимента для алгоритма имитации отжига на основе схемы Больцмана представлены в табл. 2. Таблица 2 Временные затраты работы алгоритмов на поиск оптимальных значений № п/п * Функция Количество циклов, I Начальная температура, T0 Коэффициент понижения температуры, c Время работы алгоритма, t, c Алгоритм на основе схемы Больцмана 1 f 1 54 2 0,8 0,044 925 110 160 566 4 2 119 3 0,9 0,012 118 321 813 360 3 3 79 4 0,85 0,014 748 457 546 889 1 4 212 5 0,94 0,008 077 708 742 292 1 5 1 305 5 0,99 0,055 174 227 073 368 0 Окончание табл. 2 № п/п * Функция Количество циклов, I Начальная температура, T0 Коэффициент понижения температуры, c Время работы алгоритма, t, c Алгоритм на основе схемы Больцмана 6 f 1 4 367 5 0,997 0,095 019 918 742 201 3 7 63 6 0,81 0,011 746 943 013 139 5 8 114 6 0,89 0,012 289 795 055 766 9 9 325 6 0,96 0,020 478 301 893 152 5 10 13 298 6 0,999 0,238 728 565 478 303 0 11 82 7 0,85 0,016 788 256 339 893 4 12 185 7 0,93 0,018 551 939 245 125 0 13 2 685 7 0,995 0,049 814 295 944 056 9 14 60 8 0,8 0,012 501 718 396 382 2 15 129 8 0,9 0,012 644 173 090 073 9 16 4 523 8 0,997 0,095 293 103 463 437 1 17 130 9 0,9 0,014 241 658 852 665 2 18 2 735 9 0,995 0,067 309 842 769 295 8 19 f 2 604 2 0,98 0,033 550 132 180 955 0 20 108 3 0,89 0,022 433 683 089 895 1 21 1 283 4 0,99 0,064 975 754 855 990 3 22 139 5 0,91 0,013 086 193 003 833 1 23 13 298 6 0,999 0,239 870 254 844 412 0 24 1 352 8 0,99 0,045 976 519 597 339 8 25 683 10 0,98 0,031 509 454 037 989 7 26 81 15 0,84 0,015 348 760 453 639 1 27 47 396 15 0,999 7 0,791 848 484 484 310 0 28 115 25 0,88 0,015 224 185 875 822 3 29 729 25 0,98 0,035 360 713 750 776 4 30 101 45 0,86 0,014 546 793 289 152 8 31 16 802 200 0,999 0,299 540 012 035 370 0 32 f 3 237 2 0,95 0,025 570 910 634 301 5 33 173 3 0,93 0,016 481 363 203 483 6 34 122 4 0,9 0,014 914 361 572 875 7 35 114 6 0,89 0,017 763 162 330 054 6 36 83 8 0,85 0,016 407 497 806 754 6 37 61 10 0,8 0,013 937 989 999 446 0 38 1 572 15 0,991 0,051 033 661 223 392 7 39 104 20 0,87 0,014 785 097 128 599 9 40 304 028 40 0,999 95 4,883 844 025 593 770 0 41 780 355 60 0,999 98 12,487 829 649 980 600 42 106 100 0,86 0,015 138 302 696 292 2 43 16 110 100 0,999 0,283 464 908 513 896 0 44 161 172 100 0,999 9 2,630 749 519 801 640 0 45 1 611 801 100 0,999 99 25,855 300 032 741 100 46 118 150 0,84 0,017 895 944 174 174 6 * Номер вычислительного эксперимента. Графическое представление результатов показано на рис. 5. Рис. 5. Графическое представление результатов вычислительного эксперимента по исследованию скорости сходимости алгоритмов стохастической оптимизации В табл. 3 представлены средние значения времени работы алгоритмов при оптимизации функций f1, f2 и f3 для аналогичных наборов значений входных параметров T0 и c. Таблица 3 Средние значения временных затрат работы алгоритмов стохастической оптимизации Алгоритм Алгоритм на основе схемы Больцмана Алгоритм на основе схемы Коши Сверхбыстрый отжиг Алгоритм Ксин Яо Без модификации А Б В Без модификации А Б В Время работы, с 1,086 33 1,123 80 1,082 89 1,078 23 0,141 15 0,177 66 0,154 77 0,144 22 1,187 93 1,275 65 Наибольшей скоростью сходимости обладает алгоритм имитации отжига на основе схемы Коши модификаций А, Б и В. Худший результат показал алгоритм Ксин Яо. На основе данных, полученных в ходе вычислительного эксперимента, предложены зависимости, отражающие связь между количеством итераций (I), временными затратами на работу (t) и параметрами (T0, c) для алгоритма: - на основе схемы Больцмана (в том числе модификаций А, Б и В): для с < 0,995 и для с ≥ 0,995; - для алгоритма на основе схемы Коши (в том числе модификаций А, Б и В): для с < 0,995 и для с ≥ 0,995; - для алгоритма сверхбыстрого отжига: для с < 0,995 и для с ≥ 0,995; - для алгоритма Ксин Яо: для с < 0,995 и для с ≥ 0,995; . Заключение Из полученных результатов вычислительных экспериментов следует, что наибольшей точностью при определении экстремальных значений функций нескольких переменных обладают алгоритмы сверхбыстрого отжига и Ксин Яо. Результаты, полученные с помощью алгоритмов на основе схем Больцмана и Коши, имеют отклонения от оптимальных (максимальных) значений. В то же время скорость сходимости алгоритма Ксин Яо существенно превышает скорость сходимости других алгоритмов. Существенным преимуществом алгоритма сверхбыстрого отжига и алгоритма Ксин Яо и модификации В алгоритма на основе схемы Больцмана является малая дисперсия результатов оптимизации функции, т. е. поиск оптимального значения с применением данных алгоритмов не приведет к существенным ошибкам при многократном использовании. Отметим, что для модифицированных алгоритмов на основе схем Больцмана и Коши возможна коррекция расчетных параметров - максимальной (начальной) температуры, количества циклов, параметра снижения температуры. Чтобы повышать точность результатов вычислений с возрастанием временных затрат и, наоборот, в задачах, не требующих высокой точности получаемых результатов, добиваться быстродействия вычислений, целесообразно в модификациях алгоритма simulated annealing увеличивать значение коэффициента понижения температуры (с) для первого случая или уменьшать значение начальной температуры (T0) в последнем случае. Таким образом, алгоритмы на основе метода имитации отжига являются наиболее приемлемым инструментом для прикладных исследований, поскольку допускают варианты соотношений между точностью вычислений и скоростью сходимости стохастического поиска.
1. Жиглявский А. А. Математическая теория глобального случайного поиска. Л.: Изд-во Ленингр. ун-та, 1985. 296 с.
2. Жиглявский А. А., Жилинскас А. Г. Методы поиска глобального экстремума. М.: Наука, 1991. 248 с.
3. Лопатин А. С. Метод отжига // Стохастическая оптимизация в информатике. 2005. Т. 1. № 1-1. С. 133-149.
4. Тихомиров А. С. О быстрых вариантах алгоритма отжига (simulated annealing) // Стохастическая оптимизация в информатике. 2009. Т. 46. № 3. С. 379-394.
5. Тихомиров А. С. О скорости сходимости однородного марковского монотонного поиска экстремума // Журнал вычислительной математики и математической физики. 2007. Т. 47. № 5. С. 817-828.
6. Грибанова Е. Б. Стохастический алгоритм поиска глобального минимума функции // Прикладная информатика. 2017. № 2 (68). С. 130-139.
7. Пантелеев А. В. Метаэвристические алгоритмы поиска глобального экстремума. М.: МАИ, 2009. 160 с.
8. Шмырин А. М., Корнеев А. М., Кавыгин В. В., Кузнецов А. Г. Исследование навыко-вычислительных систем с использованием окрестностного подхода // Вестн. Липец. гос. техн. ун-та. 2017. № 3 (33). С. 18-21.
9. Корнеев А. М., Аль-Сабри Г. М. Ш. Моделирование технологического процесса рекристализационного отжига // Вестн. Липец. гос. техн. ун-та. 2016. № 2 (28). С. 12-16.
10. Корнеев А. М., Абдуллах Л. С., Сметанникова Т. А. Формирование замкнутых множеств параметров сложной формы и деревьев перспективных подмножеств // Современные проблемы науки и образования. 2015. № 1. С. 158.
11. Щербина О. А. Метаэвристические алгоритмы для задач комбинаторной оптимизации (обзор) // Тавриiйський вiсник iнформатики та математики. 2014. № 1 (24). С. 56-72.
12. Wolsey A. L., Nemhauser G. L. Integer and Combinatorial Optimization. New York: Wiley-Interscience, 1988. 784 p.
13. Корнеев А. М., Сметанникова Т. А., Абдуллах Л. С. Моделирование сложных производственных систем с помощью вероятностных автоматов // Вести высших учебных заведений Черноземья. 2014. № 1. С. 39-43.
14. Корнеев А. М., Суханов А. В., Шипулин И. А. Системная методология в приложении к прогнозированию свойств чугунных сплавов // Theoretical & Applied Science. 2018. № 2. С. 181-186.
15. Корнеев А. М., Бузина О. П., Суханов А. В. Математическое моделирование и анализ напряженно-деформированного состояния неоднородных сред с непрерывными и дискретными волокнами // Фундаментальные исследования. 2016. № 8. С. 39-44.
