Введение к работе
Актуальность темы исследования. Существуют практически значимые задачи дискретной оптимизации, в частности, NP-трудные, для которых затруднительно использовать точные алгоритмы решения. Такие задачи чаще всего решаются приближенными алгоритмами, в том числе эвристическими. Для многих распространенных классов задач оптимизации существуют наборы эвристических алгоритмов, решающих задачи соответствующего класса. Например, для решения логистических задач, основанных на задаче коммивояжера, применимы различные эвристики, от приближенного алгоритма, основанного на построении остовного дерева, до одного из наиболее эффективных известных алгоритмов решения задачи коммивояжера Lin-Kernighan-Helsgaun1.
Как правило, выбрать эвристику, которая была бы наиболее эффективна для решения конкретной задачи, довольно затруднительно в силу разнообразия эвристик и трудоемкости анализа особенностей каждой задачи. Кроме того, на разных этапах решения задачи может быть выгодно использовать различные эвристики2. Поэтому задача проектирования метаэвристического алгоритма, позволяющего автоматически выбирать эвристики, наиболее эффективные на данном этапе решения задачи оптимизации, является актуальной.
Степень разработанности темы исследования. В существующих подходах к построению метаэвристических алгоритмов, как правило, используются либо простые приемы, основанные на случайном или жадном выборе эвристик, а также на их параллельном запуске, либо методы, основанные на машинном обучении, в основном, на обучении с подкреплением3. Последние методы представляются наиболее перспективными, так как позволяют учитывать особенности решаемой задачи оптимизации.
Частным случаем метаэвристических алгоритмов являются алгоритмы выбора вспомогательных критериев оптимизации, так как алгоритм оптимизации по тому или иному вспомогательному критерию можно рассматривать как отдельную эвристику. Как правило, вспомогательные критерии связаны с целевым критерием, определяющим исходную задачу оптимизации, поэтому эти эвристики можно считать эвристиками решения исходной задачи оптимизации. Одним из методов выбора вспомогательных критериев является основанный на обучении с подкреплением метод EA+RL (ЕА — эволюционный алгоритм, RL — обучение с подкреплением)4, позволяющий выбирать критерии оптимизации в процессе работы эволюционного алгоритма. Отличительной особенностью этого метода является то, что он не сводится к задаче выбора алгоритмов и учитывает особенности постановки задачи выбора вспомогательных критериев оптимизации, кроме того, для некоторых его вариантов возможен теоретический анализ времени работы.
1 Helsgaun К. An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic, 2000.
2Lissovoi A. et al. On the Runtime Analysis of Generalised Selection Hyper-heuristics for Pseudo-boolean Optimisation, 2017.
3Burke E. K. et al. Hyper-heuristics: A Survey of the State of the Art, 2013.
4Buzdalova A., BuzdalovM. Increasing Efficiency of Evolutionary Algorithms by Choosing between Auxiliary Fitness Functions with Reinforcement Learning, 2012.
Метод EA+RL был разработан для оценки эффективности программ решения задач дискретной математики. Эффективность этого метода была показана как теоретически для ряда модельных задач, так и на практике: EA+RL успешно применялся для генерации тестов производительности решений олим-пиадных задач по программированию. Однако остается открытым вопрос о его применимости для более широкого круга задач, в частности, в динамически меняющихся условиях, при которых на разных этапах оптимизации может быть выгодно использовать разные вспомогательные критерии.
Целью работы является повышение эффективности решения задач дискретной оптимизации.
Основные задачи диссертационной работы состоят в следующем:
а) Произвести анализ существующего метода выбора вспомогательных кри
териев EA+RL в случае использования критериев, повышающих эффек
тивность оптимизации целевого критерия на одних этапах оптимизации
и понижающих на других (переключающиеся критерии).
б) На основе проведенного анализа разработать метод выбора вспомога
тельных критериев, учитывающий, что критерии могут быть переключа
ющимися, и эффективно работающий с такими критериями.
в) Получить асимптотические оценки времени работы алгоритма, реализу
ющего разработанный метод, для определения его эффективности.
г) Осуществить программную реализацию разработанного метода. Прове
сти его экспериментальное исследование и сравнить его с существующи
ми методами выбора вспомогательных критериев.
д) Разработать метод проектирования метаэвристических алгоритмов дис
кретной оптимизации путем обобщения разработанного метода выбора
вспомогательных критериев на случай выбора эвристических алгоритмов
решения задач дискретной оптимизации.
е) Оценить эффективность предложенного метода проектирования метаэв
ристических алгоритмов дискретной оптимизации на примере решения
практически значимой логистической задачи, основанной на задаче ком
мивояжера.
Положения, выносимые на защиту.
а) Получены асимптотические оценки времени работы ранее предложенно
го метода EA+RL в случае использования переключающихся вспомога
тельных критериев. Теоретическими методами определена граница при
менимости ранее предложенного метода выбора вспомогательных крите
риев EA+RL для задач оптимизации, в которых влияние вспомогательных
критериев на процесс оптимизации зависит от того, на каком этапе нахо
дится этот процесс.
б) Разработан метод MOEA+RL, предназначенный для выбора вспомога
тельных критериев оптимизации в многокритериальных эволюционных
алгоритмах (МОЕА), основанный на применении обучения с подкрепле
нием (RL), и реализующие его алгоритмы. Метод позволяет эффектив-
но выбирать переключающиеся критерии, что подтверждено при решении задачи коммивояжера. Продемонстрировано, что предложенный метод позволяет за заданное число вычислений функции приспособленности получить решения такого же или лучшего качества, чем существующие методы выбора вспомогательных критериев оптимизации.
в) Получены асимптотические оценки времени работы метода MOEA+RL
в случае использования многокритериального алгоритма оптимизации
SEMO совместно с алгоритмом Q-обучения. Оценки получены на при
мере задач, содержащих переключающиеся вспомогательные критерии.
г) Разработан метод проектирования метаэвристических алгоритмов дис
кретной оптимизации, использующих вспомогательные оптимизируемые
критерии, основанный на обучении с подкреплением, являющийся обоб
щением метода MOEA+RL.
Научная новизна результатов диссертационной работы заключается в том, что оценка эффективности метода EA+RL в случае использования переключающихся критериев ранее не производилась, а также в том, что впервые предложен метод выбора вспомогательных критериев, эффективность которого в случае использования переключающихся критериев доказана. Насколько известно автору, теоретический анализ метода, совмещающего в себе многокритериальный эволюционный алгоритм и алгоритм обучения с подкреплением, был произведен автором впервые. Предложенный в диссертации метод проектирования метаэвристических алгоритмов дискретной оптимизации, использующих вспомогательные оптимизируемые критерии, является обобщением разработанного метода выбора вспомогательных критериев.
Методология и методы исследований. В работе используются методы дискретной математики, эволюционных вычислений, теории вероятностей и математической статистики, методы организации и проведения вычислительных экспериментов.
Достоверность научных положений, выводов и практических рекомендаций, полученных в диссертации, подтверждается корректным обоснованием постановок задач, точной формулировкой критериев, результатами асимптотического анализа времени работы алгоритма, реализующего предложенный в диссертации метод, а также результатами экспериментов по использованию предложенного метода и их статистическим анализом.
Теоретическое значение работы состоит в том, что с помощью теоретического анализа времени работы определены недостатки ранее разработанного метода выбора вспомогательных критериев EA+RL, полученные знания были учтены при разработке метода MOEA+RL, и отсутствие выявленных недостатков у метода MOEA+RL также доказано. Предложенный в диссертации метод проектирования метаэвристических алгоритмов дискретной оптимизации, использующих вспомогательные оптимизируемые критерии, является обобщением метода MOEA+RL.
Практическое значение работы состоит в том, что предложенный метод выбора критериев позволяет повысить эффективность решения эволюционными алгоритмами NP-трудных задач оптимизации.
Внедрение результатов работы выполнено в компании VeeRoute при решении NP-трудной практической задачи маршрутизации транспортных средств, о чем имеется акт внедрения.
Апробация результатов работы. Основные результаты работы докладывались на следующих конференциях и семинарах:
Всероссийская научная конференция по проблемам информатики СПИСОК (2014, 2016, 2017, Матмех СПбГУ);
Международная конференция ACM SIGEVO Genetic and Evolutionary Computation Conference (2013, Амстердам, 2014, Ванкувер, 2015, Мадрид, 2016, Денвер, 2017, Берлин);
Международная конференция IEEE Symposium Series on Computational Intelligence, SSCI 2016; (2016, Афины);
Международная конференция International Conference on Machine Learning and Applications (2013, Майами, 2014, Детройт);
Международная конференция International Conference on Soft Computing MENDEL (2014, 2016, Брно, Чехия).
Личный вклад автора. Решение задач диссертации, разработанный метод MOEA+RL и его программные реализации, основанные на применении многокритериальных эволюционных алгоритмов, экспериментальные и теоретические результаты, представленные в диссертации и выносимые на защиту, принадлежат лично автору.
В работах, выполненных в соавторстве, Корнеевым Г.А и Шалыто А.А. осуществлена постановка задачи исследования, Буздаловой А.С. выполнена реализация предложенного ею метода EA+RL, Буздаловым М.В. выполнена адаптация разработанных методов для решения задач построения расписаний и генерации тестов, а также сформулированы некоторые модельные задачи для экспериментальных исследований.
Публикации. Основные результаты по теме диссертации изложены в 11 публикациях, две из которых изданы в журналах, рекомендованных ВАК, девять — в изданиях, индексируемых в международных базах цитирования Web of Science или Scopus.
Участие в научно-исследовательских работах. Результаты диссертации были применены при выполнении проектов:
16-31-00380 мола «Повышение эффективности эволюционных алгоритмов с помощью динамически выбираемых вспомогательных критериев оптимизации» (Российский фонд фундаментальных исследований), 2016-2017.
ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы, грант №14337.21.0397 от 06 августа 2012 г. Тема исследования: «Разработка методов построения управляющих конечных ав-
томатов по обучающим примерам на основе решения задачи удовлетворения ограничений». — Программа государственной финансовой поддержки ведущих университетов Российской Федерации (субсидия 074-U01), НИР «Биоинформатика, машинное обучение, технологии программирования, теория кодирования, проактивные системы», 2013-2017.
Объем и структура работы. Диссертация состоит из введения, семи глав, заключения и одного приложения. Объем диссертации составляет 120 страниц с 14 рисунками, 11 таблицами и пятью листингами. Список литературы содержит 91 наименование.