Метод проектирования метаэвристических алгоритмов дискретной оптимизации, использующих вспомогательные оптимизируемые критерии, основанный на обучении с подкреплением тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Петрова Ирина Анатольевна

• Петрова Ирина Анатольевна
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Петрова Ирина Анатольевна

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. ОБЗОР ПРЕДМЕТНОЙ ОБЛАСТИ

1.1 Эволюционные алгоритмы

1.2 Использование вспомогательных критериев

1.3 Выбор вспомогательных критериев при помощи обучения с подкреплением

1.4 Алгоритмы выбора оптимизационных эвристик

1.5 Выводы по главе

ГЛАВА 2. ТЕОРЕТИЧЕСКИЙ АНАЛИЗ ВРЕМЕНИ РАБОТЫ МЕТОДА EA+RL ДЛЯ ВЫБОРА ПЕРЕКЛЮЧАЮЩИХСЯ ВСПОМОГАТЕЛЬНЫХ

КРИТЕРИЕВ

2.1 Анализируемая реализация метода EA+RL

2.2 Модельные задачи

2.2.1 Задача OneMax с переключающимися критериями

2.2.2 Задача Generalized OneMax (OM^) с переключающимися критериями

2.2.3 Задача XdivK с переключающимися критериями

2.3 Теоретическая оценка времени работы метода EA+RL на задаче OneMax с переключающимися вспомогательными критериями

2.3.1 Марковская цепь

2.3.2 Оценка времени работы алгоритма RLS+Q-learning

2.4 Оценка времени работы метода EA+RL на задаче OM^ с переключающимися вспомогательными критериями

2.5 Оценка времени работы метода EA+RL на задаче XdivK с переключающимися вспомогательными критериями

2.5.1 Марковская цепь

2.5.2 Экспериментальное исследование

2.6 Выводы по главе

ГЛАВА 3. МЕТОД MOEA+RL ДЛЯ ВЫБОРА ВСПОМОГАТЕЛЬНЫХ КРИТЕРИЕВ С ПОМОЩЬЮ МНОГОКРИТЕРИАЛЬНОГО ЭВОЛЮЦИОННОГО АЛГОРИТМА И ТЕОРЕТИЧЕСКИЙ АНАЛИЗ

ВРЕМЕНИ ЕГО РАБОТЫ

3.1 Метод MOEA+RL

3.2 Анализируемая реализация метода MOEA+RL

3.3 Теорема, используемая для доказательства времени работы SEMO+Q-learmng

3.4 Оценка времени работы SEMO+Q-leammg на задаче OMd

3.5 Выводы по главе

ГЛАВА 4. АЛГОРИТМ ОБУЧЕНИЯ С ПОДКРЕПЛЕНИЕМ ДЛЯ

РЕШЕНИЯ ЗАДАЧИ ВЫБОРА ПЕРЕКЛЮЧАЮЩИХСЯ КРИТЕРИЕВ

4.1 Применение существующих методов обучения с подкреплением в нестационарной среде к решению поставленной задачи

4.2 Первая версия предлагаемого алгоритма

4.3 Экспериментальные исследования первой версии предложенного алгоритма

4.3.1 Модельная задача

4.3.2 Описание экспериментов

4.3.3 Результаты экспериментов

4.4 Вторая версия предложенного алгоритма

4.5 Экспериментальные исследования второй версии предложенного алгоритма

4.5.1 Модельная задача

4.5.2 Описание экспериментов

4.5.3 Результаты экспериментов

4.6 Выводы по главе

ГЛАВА 5. ПРИМЕНЕНИЕ ПРЕДЛОЖЕННОГО АЛГОРИТМА ВЫБОРА ВСПОМОГАТЕЛЬНЫХ КРИТЕРИЕВ ДЛЯ РЕШЕНИЯ ЗАДАЧИ

КОММИВОЯЖЕРА

5.1 Задача коммивояжера

5.2 Методы решения задачи коммивояжера при помощи вспомогательных критериев

5.2.1 Получение вспомогательных критериев из разбиения целевого

5.2.2 Введение новых вспомогательных критериев

5.2.3 Получение вспомогательных критериев путем сегментации

5.3 Предлагаемый метод решения задачи коммивояжера с помощью вспомогательных критериев

5.4 Описание экспериментов

5.5 Эксперименты с методом EA+RL

5.5.1 Описание экспериментов

5.5.2 Результаты экспериментов

5.6 Эксперименты с методом MOEA+RL

5.6.1 Описание экспериментов

5.6.2 Результаты экспериментов

5.7 Выводы по главе

ГЛАВА 6. МЕТОД ПРОЕКТИРОВАНИЯ МЕТАЭВРИСТИЧЕСКИХ АЛГОРИТМОВ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ, ИСПОЛЬЗУЮЩИХ

ВСПОМОГАТЕЛЬНЫЕ ОПТИМИЗИРУЕМЫЕ КРИТЕРИИ

6.1 Обобщение по числу и способу использования критериев

6.2 Переход от выбора критериев к выбору эвристик

6.3 Регулярность в действиях в контексте обучения с подкреплением

6.4 К методу проектирования метаэвристических алгоритмов

6.5 Выводы по главе

ГЛАВА 7. ВНЕДРЕНИЕ

7.1 Формулировка задачи

7.2 Интерпретация задачи в терминах обучения с подкреплением

7.3 Описание адаптации разработанного метода к решению поставленной задачи

7.3.1 Выбранная структура ^-значений. Подход к экстраполяции ^-значений ранее не выполнявшихся действий

7.3.2 Построение метаэвристического многокритериального алгоритма оптимизации, использующего существующие алгоритмы оптимизации в качестве операторов мутации

7.4 Предварительное экспериментальное исследование

7.5 Перенос результатов обучения и его экспериментальное исследование

7.5.1 Схема переноса результатов обучения

7.5.2 Результаты экспериментального исследования

7.6 Выводы по главе

ЗАКЛЮЧЕНИЕ

Список литературы

ПРИЛОЖЕНИЕ А. РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТАЛЬНЫХ ИССЛЕДОВАНИЙ ПРИ ВНЕДРЕНИИ БЕЗ ПЕРЕНОСА РЕЗУЛЬТАТОВ ОБУЧЕНИЯ

А.1 Набор данных с1_10_1

А.2 Набор данных с1_10_2

А.3 Набор данных с1_10_3

А.4 Набор данных с1_10_4

А.5 Набор данных с1_10_5

А.6 Набор данных с1_10_6

А.7 Набор данных с1_10_7

А.8 Набор данных с1_10_8

А.9 Набор данных с1_10_9

А.10 Набор данных с1_10_10

А.11 Набор данных с1_2_1

А.12 Набор данных с1_2_2

А.13 Набор данных с1_2_3

А.14 Набор данных с1_2_4

А.15 Набор данных с1_2_5

А.16 Набор данных с1_2_6

А.17 Набор данных с1_2_7

А.18 Набор данных с1_2_8

А.19 Набор данных с1_2_9

А.20 Набор данных с1_2_10

Введение диссертации (часть автореферата) на тему «Метод проектирования метаэвристических алгоритмов дискретной оптимизации, использующих вспомогательные оптимизируемые критерии, основанный на обучении с подкреплением»

Актуальность темы исследования. Существуют практически значимые задачи дискретной оптимизации, в частности, ИР-трудные, для которых затруднительно использовать точные алгоритмы решения. Такие задачи чаще всего решаются приближенными алгоритмами, в том числе эвристическими. Для многих распространенных классов задач оптимизации существуют наборы эвристических алгоритмов, решающих задачи соответствующего класса. Например, для решения логистических задач, основанных на задаче коммивояжера, применимы различные эвристики, от приближенного алгоритма, основанного на построении остовного дерева [3], до одного из наиболее эффективных известных алгоритмов решения задачи коммивояжера Lm-Kerшghan-Не^аип [52].

Как правило, выбрать эвристику, которая была бы наиболее эффективна для решения конкретной задачи, довольно затруднительно в силу разнообразия эвристик и трудоемкости анализа особенностей каждой задачи. Кроме того, на разных этапах решения задачи может быть выгодно использовать различные эвристики [62]. Поэтому задача проектирования метаэвристического алгоритма, позволяющего автоматически выбирать эвристики, наиболее эффективные на данном этапе решения задачи оптимизации, является актуальной.

Степень разработанности темы исследования. В существующих подходах к построению метаэвристических алгоритмов, как правило, используются либо простые приемы, основанные на случайном или жадном выборе эвристик, а также на их параллельном запуске [16], либо методы, основанные на машинном обучении, в основном, на обучении с подкреплением [53]. Последние методы представляются наиболее перспективными, так как позволяют учитывать особенности решаемой задачи оптимизации.

Частным случаем метаэвристических алгоритмов являются алгоритмы выбора вспомогательных критериев оптимизации, так как алгоритм оптимизации по тому или иному вспомогательному критерию можно рассматривать как

отдельную эвристику. Как правило, вспомогательные критерии связаны с целевым критерием, определяющим исходную задачу оптимизации, поэтому эти эвристики можно считать эвристиками решения исходной задачи оптимизации. Одним из методов выбора вспомогательных критериев является основанный на обучении с подкреплением метод EA+RL (EA — эволюционный алгоритм, RL — обучение с подкреплением) [34], позволяющий выбирать функции приспособленности в процессе работы эволюционного алгоритма. Отличительной особенностью этого метода является то, что он не сводится к задаче выбора алгоритмов [82] и учитывает особенности постановки задачи выбора вспомогательных критериев оптимизации, кроме того, для некоторых его вариантов возможен теоретический анализ времени работы [26—28].

Метод EA+RL был разработан для оценки эффективности программ решения задач дискретной математики. Эффективность этого метода была показана как теоретически для ряда модельных задач, так и на практике: EA+RL успешно применялся для генерации тестов производительности решений олим-пиадных задач по программированию. Однако остается открытым вопрос о его применимости для более широкого круга задач, в частности, в динамически меняющихся условиях, при которых на разных этапах оптимизации может быть выгодно использовать разные вспомогательные критерии.

Целью работы является повышение эффективности решения задач дискретной оптимизации.

Основные задачи диссертационной работы состоят в следующем:

а) Произвести анализ существующего метода выбора вспомогательных критериев EA+RL в случае использования критериев, повышающих эффективность оптимизации целевого критерия на одних этапах оптимизации и понижающих на других (переключающиеся критерии).

б) На основе проведенного анализа разработать метод выбора вспомогательных критериев, учитывающий, что критерии могут быть переключающимися, и эффективно работающий с такими критериями.

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

г) Осуществить программную реализацию разработанного метода. Провести его экспериментальное исследование и сравнить его с существующими методами выбора вспомогательных критериев.

д) Разработать метод проектирования метаэвристических алгоритмов дискретной оптимизации путем обобщения разработанного метода выбора вспомогательных критериев на случай выбора эвристических алгоритмов решения задач дискретной оптимизации.

е) Оценить эффективность предложенного метода проектирования метаэв-ристических алгоритмов дискретной оптимизации на примере решения практически значимой логистической задачи, основанной на задаче коммивояжера.

Положения, выносимые на защиту.

а) Получены асимптотические оценки времени работы ранее предложенного метода EA+RL в случае использования переключающихся вспомогательных критериев. Теоретическими методами определена граница применимости ранее предложенного метода выбора вспомогательных критериев EA+RL для задач оптимизации, в которых влияние вспомогательных критериев на процесс оптимизации зависит от того, на каком этапе находится этот процесс.

б) Разработан метод MOEA+RL, предназначенный для выбора вспомогательных критериев оптимизации в многокритериальных эволюционных алгоритмах (МОЕА), основанный на применении обучения с подкреплением (RL), и реализующие его алгоритмы. Метод позволяет эффективно выбирать переключающиеся критерии, что подтверждено при решении задачи коммивояжера. Продемонстрировано, что предложенный метод позволяет за заданное число вычислений функции приспособленности

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

в) Получены асимптотические оценки времени работы метода MOEA+RL в случае использования многокритериального алгоритма оптимизации SEMO совместно с алгоритмом Q-обучения. Оценки получены на примере задач, содержащих переключающиеся вспомогательные критерии.

г) Разработан метод проектирования метаэвристических алгоритмов дискретной оптимизации, использующих вспомогательные оптимизируемые критерии, основанный на обучении с подкреплением, являющийся обобщением метода MOEA+RL. Метод 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 публикациях [6, 7, 30, 31, 35, 74—79], две из которых изданы в журналах, рекомендованных ВАК [6, 7], девять — в изданиях, индексируемых в международных базах цитирования Web of Science или Scopus [30, 31, 35, 74—79].

Участие в научно-исследовательских работах. Результаты диссертации были применены при выполнении проектов:

— 16-31-00380 мол_а «Повышение эффективности эволюционных алгоритмов с помощью динамически выбираемых вспомогательных критериев оптимизации» (Российский фонд фундаментальных исследований), 2016-2017.

— ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы, грант №14.В37.21.0397 от 06 августа 2012 г. Тема

исследования: «Разработка методов построения управляющих конечных автоматов по обучающим примерам на основе решения задачи удовлетворения ограничений». — Программа государственной финансовой поддержки ведущих университетов Российской Федерации (субсидия 074-Ш1), НИР «Биоинформатика, машинное обучение, технологии программирования, теория кодирования, проактивные системы», 2013-2017.

Объем и структура работы. Диссертация состоит из введения, семи глав, заключения и одного приложения. Объем диссертации составляет 120 страниц с 14 рисунками, 11 таблицами и пятью листингами. Список литературы содержит 91 наименование.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Петрова Ирина Анатольевна

ЗАКЛЮЧЕНИЕ

В результате диссертационного исследования получены следующие результаты:

а) Разработан метод МОЕА+ЯЬ для выбора вспомогательных критериев оптимизации, эффективно работающий в том числе в случае использования переключающихся критериев. Его особенностями являются:

— использование многокритериальных эволюционных алгоритмов;

— использование предложенного алгоритма перезапуска обучения с подкреплением.

б) Получены асимптотические оценки времени работы метода МОЕА+КЬ в случае использования многокритериального алгоритма SEMO совместно с Q-обучением.

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

г) Путем обобщения метода МОЕА+ЯЬ разработан метод проектирования метаэвристических алгоритмов дискретной оптимизации, использующих вспомогательные оптимизируемые критерии, основанный на обучении с подкреплением.

д) Разработанный обобщенный метод внедрен в компанию VeeRoute при решении задачи маршрутизации транспортных средств.

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

Список литературы диссертационного исследования кандидат наук Петрова Ирина Анатольевна, 2018 год

СПИСОК ЛИТЕРАТУРЫ

1 Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы.

— Физматлит, 2010. — 368 с.

2 Еремеев А. В. Исследование эволюционных методов решения задач комбинаторной оптимизации: дис. ... док. / Еремеев Антон Валентинович. — Институт математики им. Соболева Сибирского отделения РАН, дек. 2013.

3 Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. Второе издание. — М. : Издательский дом «Вильямс», 2005. — 1296 с.

4 Курейчик В. М., Каланчук С. А. Обзор и состояние проблемы роевых методов оптимизации // Информатика, вычислительная техника и инженерное образование. — 2016. — Т. 25, № 1. — С. 1—13.

5 Николенко С. И., Тулупьев А. Л. Самообучающиеся системы. —М., 2009.

6 Петрова И. А., Буздалова А. С., Шалыто А. А. Метод динамического выбора вспомогательных критериев в многокритериальных эволюционных алгоритмах // Научно-технический вестник информационных технологий, механики и оптики. — 2016. — 3(16). — С. 460—466.

7 Петрова И. А., Буздалова А. С., Шалыто А. А. Теоретический анализ метода выбора переключающихся вспомогательных критериев на задаче XdivK // Научно-технический вестник информационных технологий, механики и оптики. — 2017. — 3(17). — С. 409—416.

8 СкобцовЮ. А., ФедоровЕ. Е. Метаэвристики. — Донецк : Ноулидж, 2013.

— 426 с.

9 Эволюционные методы моделирования и оптимизации сложных систем. Конспект лекций / Е. Семенкин [и др.]. — Федеральное агентство по образованию. Сибирский федеральный университет, 2007. — 310 с.

10 A Fast and Elitist Multi-Objective Genetic Algorithm: NSGA-II / K. Deb [et al.] // IEEE Transactions on Evolutionary Computation. — 2002. — Vol. 6, no. 2.

— P. 182-197.

11 A Method to Control Parameters of Evolutionary Algorithms by Using Reinforcement Learning / Y. Sakurai [et al.] // Signal-Image Technology and Internet-Based Systems (SITIS), 2010 Sixth International Conference on. — 2010. — P. 74-79. — DOI: 10.1109/SITIS.2010.22.

12 A Practical Tutorial on the Use of Nonparametric Statistical Tests as a Methodology for Comparing Evolutionary and Swarm Intelligence Algorithms / J. Der-rac [et al.] // Swarm and Evolutionary Computation. — 2011. — Vol. 1, no. 1.

— P. 3-18.

13 A Reinforcement Learning - Great-Deluge Hyper-Heuristic for Examination

□

Timetabling / E. Ozcan [et al.] // Applied Metaheuristic Computing. — 2010.

— Vol. 1,no. 1. — P. 39-59.

14 A unified hyper-heuristic framework for solving bin packing problems / E. Lopez-Camacho [et al.] // Expert Systems with Applications. — 2014. — Vol. 41, no. 15. — P. 6876-6889.

15 Afanasyeva A., Buzdalov M. Optimization with Auxiliary Criteria using Evolutionary Algorithms and Reinforcement Learning // Proceedings of 18th International Conference on Soft Computing MENDEL 2012. — Brno, Czech Republic, 2012. — P. 58-63.

16 Alanazi F., Lehre P. K. Runtime analysis of selection hyper-heuristics with classical learning mechanisms //2014 IEEE Congress on Evolutionary Computation (CEC). —2014. — P. 2515-2523.

17 Alanazi F., Lehre P. K. Limits to Learning in Reinforcement Learning Hyper-heuristics // Evolutionary Computation in Combinatorial Optimization:

16th European Conference, EvoCOP Proceedings. — Springer, 2016. — P. 170-185.

18 Aleti A., Moser I., Mostaghim S. Adaptive Range Parameter Control // Proceedings of Congress on Evolutionary Computation. — 2012. — P. 1-8.

19 Aleti A., Moser I. Entropy-based Adaptive Range Parameter Control for Evolutionary Algorithms // Proceedings of Genetic and Evolutionary Computation Conference. —2013. — P. 1501-1508.

20 Arkhipov V., Buzdalov M., Shalyto A. Worst-Case Execution Time Test Generation for Augmenting Path Maximum Flow Algorithms using Genetic Algorithms // Proceedings of the International Conference on Machine Learning and

Applications. Vol. 2. — IEEE Computer Society, 2013. — P. 108-111.

□

21 Asta S., Ozcan E. An apprenticeship learning hyper-heuristic for vehicle routing in HyFlex // IEEE Symposium on Evolving and Autonomous Learning Systems. — 2014. — P. 65-72.

22 Auer P., Cesa-Bianchi N., Fischer P. Finite-time Analysis of the Multiarmed Bandit Problem // Machine Learning. — 2002. — Vol. 47, no. 2-3. — P. 235-256.

23 Auger A., Doerr B. Theory of Randomized Search Heuristics: Foundations and Recent Developments. — River Edge, NJ, USA : World Scientific Publishing Co., Inc., 2011.

24 Basso E. W., Engel P. M. Reiforcement learning in non-stationary continuous time and space scenarios // Proceedings of the VII Brasilian Meeting on Artificial Intelligence ENIA. — Bento Concalves, Brazil : SBC Press, 2009. — P. 687-696.

25 Brockhoff D., Wagner T. GECCO 2016 Tutorial on Evolutionary Multiobjective Optimization // Proceedings of Genetic and Evolutionary Computation Conference Companion. — 2016. — P. 201-227.

26 Buzdalov M., Buzdalova A., Shalyto A. A First Step towards the Runtime Analysis of Evolutionary Algorithm Adjusted with Reinforcement Learning // Proceedings of the International Conference on Machine Learning and Applications. Vol. 1. — IEEE Computer Society, 2013. — P. 203-208.

27 Buzdalov M., Buzdalova A. Analysis of Q-Learning with Random Exploration for Selection of Auxiliary Objectives in Random Local Search // Proceedings of IEEE Congress on Evolutionary Computation. — 2015. — P. 1776-1783.

28 Buzdalov M., Buzdalova A. Can OneMax Help Optimizing LeadingOnes using the EA+RL Method? // Proceedings of IEEE Congress on Evolutionary Computation. — 2015. —P. 1762-1768.

29 Buzdalov M., Buzdalova A. OneMax Helps Optimizing XdivK: Theoretical Runtime Analysis for RLS and EA+RL // Proceedings of Genetic and Evolutionary Computation Conference Companion. —ACM, 2014. —P. 201-202.

30 Buzdalov M., Buzdalova A., Petrova I. Generation of Tests for Programming Challenge Tasks Using Multi-Objective Optimization // Proceedings of Genetic and Evolutionary Computation Conference Companion. — ACM, 2013. — P. 1655-1658.

31 Buzdalov M., Petrova I., Buzdalova A. NSGA-II Implementation Details May Influence Quality of Solutions for the Job-Shop Scheduling Problem // Proceedings of Genetic and Evolutionary Computation Conference Companion. — 2014. — P. 1445-1446.

32 Buzdalov M., Shalyto A. A Provably Asymptotically Fast Version of the Generalized Jensen Algorithm for Non-Dominated Sorting // Parallel Problem Solving from Nature-PPSN XIII. — Springer, 2014. —P. 528-537. — (Lecture Notes in Computer Science ; 8672).

33 Buzdalova A., Buzdalov M. Adaptive Selection of Helper-Objectives with Reinforcement Learning // Proceedings of the International Conference on Machine Learning and Applications. Vol. 2. — IEEE Computer Society, 2012.

— P. 66-67.

34 Buzdalova A., Buzdalov M. Increasing Efficiency of Evolutionary Algorithms by Choosing between Auxiliary Fitness Functions with Reinforcement Learning // Proceedings of the International Conference on Machine Learning and Applications. Vol. 1. —2012. — P. 150-155.

35 Buzdalova A., Petrova I., Buzdalov M. Runtime Analysis of Different Approaches to Select Conflicting Auxiliary Objectives in the Generalized OneMax Problem // Proceedings of IEEE Symposium Series on Computational Intelligence. —2016. — P. 280-286.

36 Coello C. A. C., Lamont G. B., Veldhuizen D. A. V. Evolutionary Algorithms for Solving Multi-Objective Problems. — Second. — Springer-Verlag, 2006.

— 800 p.

37 Corne D. W., Knowles J. D., Oates M. J.The Pareto Envelope-based Selection Algorithm for Multiobjective Optimization // Parallel Problem Solving from Nature - PPSN VI. — Springer, 2000. — P. 839-848. — (Lecture Notes in Computer Science; 1917).

38 Cowling P., Kendall G., Soubeiga E. A Hyperheuristic Approach to Scheduling a Sales Summit // Practice and Theory of Automated Timetabling III. — 2001.

— P. 176-190.

39 Cowling P., Kendall G., Soubeiga E. Hyperheuristics: A Tool for Rapid Prototyping in Scheduling and Optimisation // Applications of Evolutionary Computing: EvoWorkshops 2002: EvoCOP, EvoIASP, EvoSTIM/EvoPLAN. —2002.

— P. 1-10. — (Lecture Notes in Computer Science ; 2279).

40 Dealing with Non-stationary Environments Using Context Detection / B. C. D. Silva [et al.] // Proceedings of the 23rd International Conference on Machine Learning. — ACM Press, 2006. — P. 217-224.

41 Dispatching rules for production scheduling: a hyper-heuristic landscape analysis / G. Ochoa [et al.] // Congress on Evolutionary Computation. — IEEE, 2009.

— P. 1873-1880.

42 Doerr C. Non-Static Parameter Choices in Evolutionary Computation // Proceedings of Genetic and Evolutionary Computation Companion. — 2017. — P. 736-761.

43 Dumas Y., Desrosiers J., Soumis F. The pickup and delivery problem with time windows // European Journal of Operational Research. — 1991. — Vol. 54, no. 1. — P. 7-22.

44 Eiben A. E., Smith J. E. Introduction to Evolutionary Computing. — Berlin, Heidelberg, New York : Springer-Verlag, 2015. — 287 p.

45 Fortin F.-A., Grenier S., Parizeau M. Generalizing the Improved Run-time Complexity Algorithm for Non-dominated Sorting // Proceedings of Genetic and Evolutionary Computation Conference. — ACM, 2013. — P. 615-622.

46 Fu H., Lewis P. R., Yao X. A Q-learning Based Evolutionary Algorithm for Sequential Decision Making Problems // Proceedings of the Workshop "In Search of Synergies between Reinforcement Learning and Evolutionary Computation" at the 13th International Conference on Parallel Problem Solving from Nature.

— VUB Artificial Intelligence Lab, 2014.

□

47 Gibbs J., Kendall G., Ozcan E. Scheduling English football fixtures over the holiday period using hyper-heuristics // Parallel Problem Solving from Nature -PPSN XI. — 2010. — P. 496-505. — (Lecture Notes in Computer Science ; 6238).

48 Gosavi A. Reinforcement Learning: A Tutorial. Survey and Recent Advances //INFORMS Journal on Computing. —2009. — Vol. 21, no. 2. —P. 178-192.

49 Granmo O.-C., Berg S. Solving Non-Stationary Bandit Problems by Random Sampling from Sibling Kalman Filters //IEA/AIE (3). —2010. — P. 199-208. — DOI: 10.1007/978-3-642-13033-5\_21.

50 Hajek B. Hitting-Time and Occupation-Time Bounds Implied by Drift Analysis with Applications // Advances in Applied Probability. — 1982. — Vol. 14, no. 3. — P. 502-525.

51 He J., He F., Dong H. Pure Strategy or Mixed Strategy? // Evolutionary Computation in Combinatorial Optimization: 12th European Conference (EvoCOP 2012). —2012. —P. 218-229. —(Lecture Notes in Computer Science; 7245).

52 Helsgaun K. An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic // European Journal of Operational Research. — 2000. — Vol. 126, no. 1. — P. 106-130.

53 Hyper-heuristics: a survey of the state of the art / E. K. Burke [et al.] // Journal ofOperationalResearch Society. —2013. — Vol. 64, no. 12. —P. 1695-1724.

54 Jahne M., Li X., Branke J. Evolutionary Algorithms and Multi-objectivization for the Travelling Salesman Problem // Proceedings of Genetic and Evolutionary Computation Conference. — New York, NY, USA : ACM, 2009. — P. 595-602.

55 Jensen M. T. Helper-Objectives: Using Multi-Objective Evolutionary Algorithms for Single-Objective Optimisation: Evolutionary Computation Combinatorial Optimization // Journal of Mathematical Modelling and Algorithms. — 2004. — Vol. 3, no. 4. — P. 323-347.

56 Jensen M. T. Reducing the Run-time Complexity of Multiobjective EAs: The NSGA-II and Other Algorithms // IEEE Transactions on Evolutionary Computation. —2003. — Vol. 7, no. 5. — P. 503-515.

57 Kaelbling L. P., Littman M. L., Moore A. W.Reinforcement Learning: A Survey // Journal of Artificial Intelligence Research. —1996. — Vol.4. —P. 237-285.

58 Knowles J. D., Watson R. A., Corne D. Reducing Local Optima in Single-Objective Problems by Multi-objectivization // Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization. — SpringerVerlag, 2001. — P. 269-283.

59 Knowles J. D., Corne D. W.Approximating the Nondominated Front Using the Pareto Archived Evolution Strategy // Evolutionary Computation. — 2000. — Vol. 8, no. 2. — P. 149-172.

60 Kung H.-T., Luccio F., Preparata F. P. On Finding the Maxima of a Set of

Vectors // Journal of ACM. — 1975. — Vol. 22, no. 4. — P. 469-476.

□

61 Lehre P. K., Ozcan E. A Runtime Analysis of Simple Hyper-heuristics: To Mix or Not to Mix Operators // Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII. —2013. — P. 97-104.

62 Lissovoi A., Oliveto P. S., Warwicker J. A. On the runtime analysis of generalised selection hyper-heuristics for pseudo-boolean optimisation // Proceedings of Genetic and Evolutionary Computation Conference. — ACM, 2017.

— P. 849-856.

63 Lochtefeld D. F., Ciarallo F. W.An Analysis of Decomposition Approaches in Multi-objectivization via Segmentation//Appl. SoftComput. —2014. —Vol. 18. — P. 209-222.

64 LochtefeldD. F., Ciarallo F. W.Deterministic Helper-Objective Sequences Applied to Job-Shop Scheduling // Proceedings of Genetic and Evolutionary Computation Conference. — ACM, 2010. — P. 431-438.

65 Maden i., Uyar §., Ozcan E. Landscape analysis of simple perturbative hyper-heuristics // 15th International Conference on Soft Computing Mendel. — 2009.

— P. 16-22.

66 Mitchell M. An Introduction to Genetic Algorithms. — Cambridge, MA : MIT Press, 1996. —221 p.

67 Multi-objectivization of reinforcement learning problems by reward shaping / T. Brys [et al.] //2014 International Joint Conference on Neural Networks. — 2014. — P. 2315-2322.

68 Multiple model-based reinforcement learning / K. Doya [et al.] // Neural Computation. — 2002. — Vol. 14. — P. 1347-1369.

69 Neumann F., Wegener I. Can Single-Objective Optimization Profit from Mul-tiobjective Optimization? // Multiobjective Problem Solving from Nature. — Springer Berlin Heidelberg, 2008. — P. 115-130. — (Natural Computing Series).

70 Neumann F., Wegener I. Minimum Spanning Trees Made Easier via Multi-objective Optimization // Natural Computing. — 2006. — Vol. 5, no. 3. — P. 305-319.

71 Ochoa G., QuR, Burke E. K. Analyzing the Landscape of a Graph Based Hyper-heuristic for Timetabling Problems // Proceedings of Genetic and Evolutionary Computation Conference. —2009. — P. 341-348.

72 PAC Model-free Reinforcement Learning / A. L. Strehl [et al.] // Proceedings of the 23rd International Conference on Machine Learning. — 2006. — P. 881-888.

73 PESA-II: Region-based Selection in Evolutionary Multiobjective Optimization / D. W. Corne [et al.] // Proceedings of Genetic and Evolutionary Computation Conference. — Morgan Kaufmann Publishers, 2001. — P. 283-290.

74 Petrova I., Buzdalova A. Reinforcement learning based dynamic selection of auxiliary objectives with preservation of the best found solution // Proceedings of the Genetic and Evolutionary Computation Conference Companion. — 2017. — P. 1435-1438.

75 Petrova I., Buzdalova A., Buzdalov M. Improved Helper-Objective Optimization Strategy for Job-Shop Scheduling Problem // Proceedings of the International Conference on Machine Learning and Applications. Vol. 2. — IEEE Computer Society, 2013. — P. 374-377.

76 Petrova I., Buzdalova A., Buzdalov M. Selection of Extra Objectives using Reinforcement Learning in Non-Stationary Environment: Initial Explorations // Proceedings of 20th International Conference on Soft Computing MENDEL 2014.

— Czech Republic, 2014. — P. 58-63.

77 Petrova I., Buzdalova A. Selection of Auxiliary Objectives in the Travelling Salesman Problem using Reinforcement Learning // Proceedings of Genetic and Evolutionary Computation Conference Companion. —2015. —P. 1455-1456.

78 Petrova I., Buzdalova A., Buzdalov M. Improved Selection of Auxiliary Objectives using Reinforcement Learning in Non-Stationary Environment // Proceedings of the International Conference on Machine Learning and Applications.

— 2014. — P. 580-583.

79 Petrova I., Buzdalova A., Korneev G. Runtime analysis of random local search with reinforcement based selection of non-stationary auxiliary objectives: initial study // Proceedings of 22nd International Conference on Soft Computing MENDEL 2016. — Czech Republic, 2016. — P. 95-102.

80 Pratt L. Y. Discriminability-based transfer between neural networks // Advances in Neural Information Processing Systems. — 1993. —P. 204-211.

81 R Core Team. R: A Language and Environment for Statistical Computing / R Foundation for Statistical Computing. — 2013. — URL: http : / / www . R-

project.org/.

82 Rice J. R. The algorithm selection problem // Advances in Computers. — 1976.

— Vol. 15. — P. 65-118.

83 Running Time Analysis of Multi-objective Evolutionary Algorithms on a Simple Discrete Optimization Problem / M. Laumanns [et al.] // Proceedings of the 7th International Conference on Parallel Problem Solving from Nature. — London, UK : Springer-Verlag, 2002. — P. 44-53. — (Lecture Notes in Computer Science ; 2439). — ISBN3-540-44139-5. — URL: http://dl.acm.org/ citation.cfm?id=64 582 6.6695 97.

84 Srinivas N., Deb K. Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms // Evolutionary Computation. — 1994. — Vol. 2, no. 3. — P. 221-248.

85 Sutton R. S., Barto A. G. Reinforcement Learning: An Introduction. — Cambridge, MA, USA : MIT Press, 1998.

86 The Traveling Salesman Problem: A Computational Study (Princeton Series in Applied Mathematics) / D. L. Applegate [et al.]. — Princeton, NJ, USA : Princeton University Press, 2007.

87 Watchmaker Framework for Evolutionary Computation. — URL: http : / / watchmaker.uncommons.org.

88 Whittle P. Arm-Acquiring Bandits // The Annals of Probability. — 1981. — Vol. 9, no. 2. — P. 284-292.

89 Zitzler E., Laumanns M., Thiele L. SPEA2: Improving the Strength Pareto Evolutionary Algorithm for Multiobjective Optimization // Proceedings of the EU-R0GEN'2001 Conference. —2001. — P. 95-100.

90 Zitzler E., Thiele L. Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach // IEEE Transactions on Evolutionary Computation. — 1999. — Vol. 3, no. 4. — P. 257-271.

91 Скобцов Ю. А. Основы эволюционных вычислений. — Донецк : ДонНТУ, 2008.