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

• Басин Антон
• кандидат наук
• 2020

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

Реферат

Synopsis

Introduction

Chapter 1. Background and Motivation

1.1 Notation

1.2 Introduction to Evolutionary Computation

1.3 Parameters in Evolutionary Algorithms

1.4 The Usefulness of Crossover

1.5 Considered Search Spaces and Their Properties

1.6 Considered Evolutionary Algorithms

1.6.1 The (1 + 1) Evolutionary Algorithm

1.6.2 The (1 + (X, X)) Genetic Algorithm

1.7 Considered Benchmark Problems

1.8 Existing Works on the (1 + (X, X)) Genetic Algorithm

1.9 Summary of Chapter

Chapter 2. Modifying the Probability Distributions in the Evolutionary Operators and the Crossover Scheme

in the (1 + (X,X)) GA

2.1 Modifications of the (1 + (X,X)) GA

2.2 Experiments with Easy Problems

2.2.1 General Methodology

2.2.2 Results: OneMax

2.2.3 Results: Linear Functions

2.2.4 Results: Easy Maximum Satisfiability Problems

2.2.5 Analysis of Robustness

2.3 Experiments with Harder Problems

2.4 Summary of Chapter

Chapter 3. The Modified Population Size Adaptation

in the (1 + (X,X)) GA

3.1 Self-adjusting Population Size in the (1 + (X,X)) GA

3.2 On Evaluations Until Improvement

3.3 Parameter Adaptation Trajectories

3.4 Proposed Modification

3.5 Experimental Evaluation

3.6 Runtime Analysis on ONEMAX

3.7 Approximation of Performance Assuming Optimal Parame-

ter Choices

3.8 Summary of Chapter

Chapter 4. The (1 + (A, A)) Genetic Algorithm for Permutations

4.1 Mutations for Permutations

4.2 The (1 + (A, A)) GA for Permutations

4.3 Running Time Analysis

4.4 Experiments

4.4.1 Running Times

4.4.2 Parameter Landscape Analysis

4.5 Comparison to a Commercial Solver

4.5.1 The HAM Function

4.5.2 The Ham Function with Ruggedness

4.6 Summary of Chapter

Conclusion

References

List of Figures

List of Tables

Appendix A. Copies of Author's Publications

Реферат

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

Общая характеристика работы

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

Несмотря на то, что большая часть идей, заложенных в эволюционных алгоритмах, появлялась как компьютерная модель того или иного процесса, протекающего в природе (эволюция живых существ, сложное роевое поведение социальных животных, физические процессы на микро-и макроуровнях), ряд современных эволюционных алгоритмов, показывающих наибольшую производительность на практике, спроектирован на основе результатов теоретического и экспериментального анализа алгоритмов-предшественников. К таким алгоритмам можно, например, отнести эволюционную стратегию с адаптацией ковариационной матри-цы1, являющуюся одним из общепризнанных лидеров среди методов решения вещественнозначных задач оптимизации, алгоритмы решения так называемых задач «серого ящика» (англ. gray-box optimization) для решения комбинаторных задач большой размерности2, а также перспективные эволюционные алгоритмы оценки распределений (англ. estimation-of-distribution algorithms)3.

Рассматриваемый в данной диссертации двухфазный генетический алгоритм со скрещиванием, компенсирующим воздействия мутаций, известный как генетический алгоритм (1 + (Л,Л)) (далее (1 + (X, Л))-ГА), также является одним из таких алгоритмов. Данный алгоритм был предложен в работе4 исходя из чисто теоретических соображений, состоящих

1 Hansen, N., Ostermeier, A. Completely derandomized self-adaptation in evolution strategies // Evolutionary Computation. 2001. Vol. 9. P. 159-195.

2Sanches, D. S., Whitley, D., Tinos, R. Improving an exact solver for the traveling salesman problem using partition crossover // Proceedings of Genetic and Evolutionary Computation Conference. 2017. P. 337-344.

3Doerr, B., Krejca, M. S. Significance-based estimation-of-distribution algorithms // Proceedings of Genetic and Evolutionary Computation Conference. 2018. P. 1483-1490.

4Doerr, B., Doerr, C., Ebel, F. From black-box complexity to designing new genetic algorithms // Theoretical Computer Science. 2015. Vol. 567. P. 87-104.

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

Несмотря на указанные положительные черты, применение (1 + (Л, Л))-ГА на практике в настоящее время все еще следует считать ограниченным. Этому способствует как недостаточное внимание авторов и пользователей данного алгоритма к отдельным его аспектам, влияющим на его поведение количественно (но не качественно), что приводит к снижению наблюдаемой производительности относительно теоретически возможной7, так и ряд более существенных недостатков в самом алгоритме, приводящим к необходимости модификации его компонентов для повышения его производительности при решении более сложных задач8. Кроме данных недостатков, применимость (1 + (Л, Л))-ГА на практике ограничивается и тем, что вследствие обладания им более сложной структурой, чем у более распространенных эволюционных алгоритмов, внесение изменений — таких как адаптация данного алгоритма к задачам, заданным на пространстве поиска, отличном от битовых строк — затруднено. Поэтому обобщение и повышение производительности данного алгоритма является актуальной задачей.

Степень разработанности темы. Эффективность эволюционных алгоритмов часто измеряют как математическое ожидание числа вычислений функции приспособленности, необходимых для нахождения оптимума решаемой задачи оптимизации. Для (1 + (Л, Л))-ГА известен ряд оценок производительности на модельной задаче О^Мах (задача, заданная на битовых строках длиной п, упрощенная формулировка которой состоит в максимизации числа единичных бит), наиболее значимая из которых — О(п) вычислений функции приспособленности в среднем при использовании так называемого правила «одной пятой» в качестве

5Goldman, B., Punch, W. Parameter-less population pyramid // Proceedings of Genetic and Evolutionary Computation Conference. 2014. P. 785-792.

6Gandomi, A., Goldman, B. Parameter-less population pyramid for large-scale tower optimization // Expert Systems with Applications. 2018. Vol. 96. P. 175-184.

7Foster, M. [et al.]. Do sophisticated evolutionary algorithms perform better than simple ones? // Proceedings of Genetic and Evolutionary Computation Conference. 2020. P. 184-192.

8Buzdalov, M., Doerr, B. Runtime analysis of the (1 + (X, X)) genetic algorithm on random satisfiable 3-CNF formulas // Proceedings of Genetic and Evolutionary Computation Conference. 2017. P. 1343-1350.

метода настройки параметра Л9. Отметим, что константный множитель в данной оценке игнорируется, и его значение до сих пор не оценено с достаточной точностью, а в зависимости от модификаций алгоритма, не влияющих на характер его поведения, данный множитель может варьироваться в достаточно широких пределах, достигая значения 10-13.

Для достижения производительности, сопоставимой с другими практически применяемыми алгоритмами, в ряде работ5'6 были предприняты меры по модификации (1 + (Л, Л))-ГА, направленные на избежание выполнения заведомо бесполезных вычислений функции приспособленности, такие как повторное применение оператора мутации, в случае если его предыдущее применение привело к фактическому отсутствию изменений в решении. В работе10 (1 + (Л, Л))-ГА также был модифицирован подобным, но не идентичным образом, при этом сравнение двух вариантов модификации не производилось. Подобный подход также описан в работе11 в приложении к другому генетическому алгоритму, где он не только привел к повышению его производительности, но и продемонстрировал его фундаментальное преимущество по отношению к алгоритмам, не использующим скрещивание.

Также одним из методов повышения производительности, исследованных в отношении (1 + (Л, Л))-ГА, является метод настройки гиперпараметров. В работе10 было исследовано пятимерное пространство гиперпараметров, два из которых относились к методу настройки параметра Л, а три других связывали данный параметр и размеры популяции, при этом было достигнуто улучшение производительности до 15 % по сравнению со значениями параметров по умолчанию. Однако при этом исследовалась лишь одна модельная задача оптимизации, в частности, не была исследована переносимость утверждений об производительности данного выбора параметров на другие задачи оптимизации.

При исследовании (1 + (Л, Л))-ГА на более сложных задачах было обнаружено8 что метод настройки параметра Л, основанный на правиле «одной пятой», не дает удовлетворительной производительности и даже скорее снижает ее. Для восстановления производительности потребовалось внести изменение в данный метод настройки параметра, введя дополнительное ограничение сверху Л для возможных значений параметра Л. Несмотря на то, что после внесения данной модификации производительность (1 + (Л, Л))-ГА стала асимптотически превышать производительности более простых эволюционных алгоритмов, данное обстоя-

9Doerr, B., Doerr, C. Optimal static and self-adjusting parameter choices for the (1 + (X, X)) genetic algorithm // Algorithmica. 2018. Vol. 80, no. 5. P. 1658-1709.

10Dang, N., Doerr, C. Hyper-Parameter Tuning for the (1 + (X, X)) GA// Proceedings of Genetic and Evolutionary Computation Conference. 2019. P. 889-897.

11Pinto, E. C., Doerr, C. A simple proof for the usefulness of crossover in black-box optimization // Parallel Problem Solving from Nature - PPSN XV, Vol. 2. 2018. P. 29-41. (Lecture Notes in Computer Science ; 11102).

тельство позволяет утверждать, что правило «одной пятой» не является универсальным правилом, подходящим для решения любых задач. Отметим, что в работах5'6 также были предприняты менее эффективные меры подобного рода, связанные с недостаточной эффективностью метода настройки параметра. Все указанные задачи можно охарактеризовать единым свойством — слабой корреляцией между приспособленностью решения задачи и расстоянием Хэмминга между этим решением и оптимумом. Влияние данного свойства на ход работы (1 + (Л, Л))-ГА было установлено в работе8.

Отдельно стоит отметить, что все теоретические и практические работы, исследовавшие (1 + (Л, Л))-ГА, рассматривали данный алгоритм исключительно на псевдобулевых задачах оптимизации. Ни одной работы, применяющей (1 + (Л, Л))-ГА к решению задач, заданных на других распространенных пространствах поиска, таких как векторы целых или вещественных чисел, перестановки или другие комбинаторные объекты, при анализе литературы обнаружено не было.

На основе вышеизложенного можно сделать следующие выводы:

- оптимизации производительности (1 + (Л, Л))-ГА путем модификации его составляющих, не влияющей на качественные характеристики его поведения — в частности, избежанию заведомо нецелесообразных запросов к функции приспособленности — уделялось недостаточное внимание, в то время как данный аспект важен при применении данного алгоритма на практике;

- метод настройки параметра Л, при разработке которого учитывалось лишь поведение (1 + (Л, Л))-ГА на простых модельных задачах, оказывается недостаточно эффективным при решении задач со слабой корреляцией между приспособленностью и расстоянием до оптимума, для преодоления чего нередко требуется дополнительный анализ, что также создает препятствия при применении данного алгоритма на практике;

- алгоритм (1 + (Л, Л))-ГА в настоящее время существует лишь в варианте, способном решать псевдобулевы задачи оптимизации, в то время как для других пространств поиска отсутствуют как модификации данного алгоритма, так и способы их осуществления.

Целью работы является обобщение и повышение производительности генетического алгоритма (1 + (Л, Л)).

Для достижения указанной цели определены следующие задачи:

- разработка метода повышения производительности генетического алгоритма (1 + (Л, Л)) путем модификации его структуры и используемых вероятностных распределений;

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

ритма (1 + (Л, Л)) на задачах со слабой корреляцией между приспособленностью и расстоянием до оптимума;

- разработка метода обобщения генетического алгоритма (1 + (Л, Л)) для решения задач, отличных от псевдобулевых, на примере задач, заданных на перестановках.

Объект исследования — генетический алгоритм (1 + (Л, Л)).

Предмет исследования — производительность генетического алгоритма (1 + (Л, Л)) на различных задачах оптимизации, особенности поведения данного алгоритма на данных задачах, а также структура данного алгоритма и ее связь с особенностями пространства поиска решаемых задач.

Соответствие паспорту специальности. Данная работа относится к специальности 05.13.17 «Теоретические основы информатики» и соответствует пункту 13 «Применение бионических принципов, методов и моделей в информационных технологиях» в части объекта и предмета исследований.

Основные положения, выносимые на защиту:

- метод повышения производительности генетического алгоритма (1 + (Л, Л)) путем модификации его структуры и используемых вероятностных распределений;

- модифицированный метод настройки размера популяции, повышающий производительность генетического алгоритма (1 + (Л, Л)) на задачах со слабой корреляцией между приспособленностью и расстоянием до оптимума;

- метод обобщения генетического алгоритма (1 + (Л, Л)) для решения задач, отличных от псевдобулевых, на примере задач, заданных на перестановках.

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

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

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

- Разработана первая модификация (1 + (Л, А))-ГА для решения задач, представленных перестановками. Эффективность полученного нового алгоритма была доказана на модельной задаче, состоящей в сортировке перестановки по возрастанию. Идеи, на которых основана предложенная модификация, могут быть также применены и при адаптации для других видов пространств поиска.

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

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

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

Практическая значимость. Одним из практически значимых результатов диссертации является модификация нескольких параметров генетического алгоритма (1 + (Л, Л)), ускоряющая его работу практически в два раза на обширном классе задач оптимизации и рекомендуемая, как следствие, в качестве значений «по умолчанию» при использовании данного алгоритма на практике. Сходное практическое значение имеет предложенная в диссертации модификация механизма адаптации параметров. Способ обобщения генетического алгоритма (1 + (Л, Л)) для задач, заданных на перестановках, также применимый к другим пространствам поиска, существенно увеличивает круг практических приложений данного алгоритма.

Внедрение результатов работы. Результаты работы использованы при выполнении гранта Российского научного фонда (проект 17-7120178 «Методы построения эффективных эволюционных алгоритмов», 2017-2020 гг.), а также в рамках государственной финансовой поддержки ведущих университетов Российской Федерации, субсидия 08-08 (НИР «Методы, модели и технологии искусственного интеллекта в биоинформатике, социальных медиа, киберфизических, биометрических и речевых системах», 2018-2020 гг.).

Результаты работы также внедрены в учебный процесс факультета информационных технологий и программирования Университета ИТМО в курсе «Генетические и эволюционные вычисления» магистерской программы «Технологии разработки программного обеспечения», что подтверждается актом об использовании.

Апробация результатов работы. Основные результаты работы докладывались на следующих конференциях и семинарах:

а) Genetic and Evolutionary Computation Conference (2019, Прага, Чехия; 2020, Online);

б) Mathematical Optimization Theory and Operations Research Conference (2020, Новосибирск);

в) Всероссийская научная конференция по проблемам информатики СПИСОК (2019, СПбГУ);

г) XLVII Научная и учебно-методическая конференция (2018, Университет ИТМО).

Личный вклад автора. Автором выполнена разработка, реализация, доказательство корректности, теоретический и практический анализ времени работы предложенных в диссертации методов обобщения и повышения производительности двухфазного генетического алгоритма (1 + (А, А)). В работах, выполненных в соавторстве с научным руководителем Буздаловым М.В., его вклад заключался в общем руководстве работой, а также в повышении эффективности программной реализации некоторых алгоритмов.

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

Содержание работы

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

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

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

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

п

О^МАХ(х) = х1-i=1

По указанным соображениям далее будут также приведены упрощенные формулировки основных используемых модельных задач.

- Задача поиска наибольшего значения линейной функции с положительными целыми весами LININTW, характеризуемая максимальным значением веса W:

п

LININT(x) = ^^ Wi ' X, 1 < ^ < Ж

i=1

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

- Задача о выполнимости булевой формулы в максимизационной постановке, МАХ^АТ. Целью данной задачи является поиск такого вектора булевых значений х = {х^, i = 1... п, что число выполненных выражений в булевой формуле, находящейся в конъюнктивной нормальной форме с тремя переменными в каждом дизъюнкте, является максимальным.

В работе также рассматривается модельная задача на основе перестановок длиной n, называемая Ham (сокращенно от Hamming, так как функция соответствует расстоянию Хэмминга). Ее свойства схожи со свойствами задачи OneMax, а целью является максимизация числа совпадений элементов перестановки с индексами:

Работа посвящена методам повышения производительности и обобщения (1 + (Л, Л))-ГА. Данный алгоритм12 хранит одну особь — текущее лучшее решение. На каждой итерации в фазе мутации создается Л потомков-мутантов путем применения оператора мутации к текущей особи. Данный оператор инвертирует во всех особях одинаковое число бит I, выбираемое так, что E[£] « Л, при этом Л часто бывает значительно больше единицы, что нетипично для эволюционных алгоритмов. Далее выбирается потомок-мутант с лучшим значением приспособленности. Затем к нему и текущей лучшей особи Л раз применяется оператор скрещивания, который способен компенсировать вредные воздействия мутаций путем выбора битов мутанта с вероятностью всего лишь 1 /Л. Текущая особь заменяется лучшим из результатов скрещивания, если его лучшая приспособленность не хуже, чем у текущей особи. Размер популяции Л может настраиваться в ходе работы алгоритма.

Показано13, что (1 + (Л, Л))-ГА асимптотически превосходит все эволюционные алгоритмы, использующие только операторы мутации. на задаче О^Мах. (1 + (Л, Л))-ГА также имеет более высокую14 или сравнимую с известными эволюционными алгоритмами15 производительность на более сложных модельных задачах и некоторых задачах, имеющих применимость на практике16. Однако его эффективность падает при ослаблении корреляции между приспособленностью и расстоянием до глобального оптимума. К тому же до настоящего момента все рассматриваемые в контексте (1 + (Л, Л))-ГА задачи оптимизации являлись псевдобулевыми.

12Doerr, B., Doerr, C., Ebel, F. From black-box complexity to designing new genetic algorithms // Theoretical Computer Science. 2015. Vol. 567. P. 87-104.

13Doerr, B., Doerr, C. Optimal static and self-adjusting parameter choices for the (1 + (X, X)) genetic algorithm // Algorithmica. 2018. Vol. 80, no. 5. P. 1658-1709.

14Buzdalov, M., Doerr, B. Runtime analysis of the (1 + (X, X)) genetic algorithm on random satisfiable 3-CNF formulas // Proceedings of Genetic and Evolutionary Computation Conference. 2017. P. 1343-1350.

15Antipov, D., Doerr, B., Karavaev, V. A tight runtime analysis for the (1 + (X, X)) GA on Leadin-gOnes // Foundations of Genetic Algorithms. 2019. P. 169-182.

16Goldman, B., Punch, W. Parameter-less population pyramid // Proceedings of Genetic and Evolutionary Computation Conference. 2014. P. 785-792.

n

i=1

Во второй главе представлен метод модификации вероятностных распределений операторов мутации и скрещивания, а также схемы стадии скрещивания, повышающих производительность (1 + (Л, А))-ГА. Экспериментальное исследование влияния выбора различных операторов для (1 + (Л, А))-ГА при решении задач псевдобулевой оптимизации подтверждает эффективность предложенных модификаций. Произведен анализ результатов экспериментов, который выявил стабильно эффективную конфигурацию (1 + (Л, А))-ГА, содержащую предлагаемые конфигурации и настроенные значения гиперпараметров.

В изначальной версии генетического алгоритма (1 + (Л, Л)) имеется вероятность потери вычислений функции приспособленности на продуктах эволюционных операторов, идентичных родительским особям. В фазе мутации генерируется число случайных бит £, инвертируемых в каждом потомке мутации. Выборка данной величины производится из диапазона значений [0..п], где п — размерность решаемой задачи, согласно биномиальному распределению. Проблема заключается в том, что I = 0 ведет к 2Л излишним вычислениям функции приспособленности, так как все потомки фаз эволюционного алгоритма будут являться дубликатами родительской особи, а при I = 1 все возможные результаты скрещивания ранее встречались, так как родительские особи различаются на один бит. Для иных значений I потеря производительности также может возникать в фазе скрещивания, так как существует вероятность получить продукт скрещивания, идентичный родительской особи.

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

Также в качестве одной из возможностей модификации (1 + (Л, Л))-ГА впервые предлагается выбирать вероятность скрещивания (являющуюся параметром биномиального распределения) на фазе скрещивания равной рс = 1/£, против изначального значения рс = 1/Л. Кроме того, использование динамической адаптации параметра Л, доказавшее свою эффективность в предыдущих работах, предполагает вещественное значение Л и вводит необходимость округления данного параметра для определения числа мутаций и скрещиваний. В данной работе, помимо используемого в исходном варианте алгоритма округления вверх, систематически исследуется вариант с округлением Л вниз, а также вариант со стохастическим округлением: вероятность округления к одному из вариантов (вверх или вниз) линейно возрастает по мере приближения значения Л к нему.

Впервые предложенные модификации (1 + (Л, Л))-ГА описывают поведение алгоритма в случае нахождения продукта мутации лучшего, чем родительская особь. Предлагается дополнительно рассматривать лучшего мутанта в процессе селекции после скрещивания. При этом, в фазе скрещивания нужно либо пропускать вычисление функции приспособленности на особи, идентичной одному из родителей, либо производить перегенерацию продукта скрещивания до тех пор, пока не получится отличающаяся от родителей особь. Если же при таком подходе получить отличающегося потомка доказуемо невозможно (при £ = 1), то следует пропускать фазу скрещивания.

Сравнительное экспериментальное исследование было проведено на четырех типах псевдобулевых задач оптимизации: О^Мах, линейные функции LININT со случайными весами [1..^] (использовались W = 2 и W = 5) и задача максимальной выполнимости формул МАХ^АТ. При проведении исследований рассмотрены три различных оператора мутации, шесть операторов скрещивания, три варианта округления вещественного значения Л, а также четыре варианта действий в случае, когда лучший продукт фазы мутации побеждает родительскую особь по значению приспособленности. Такое разнообразие операторов дает 216 различных конфигураций алгоритма, каждая из которых используется с тремя различными стратегиями адаптации размера популяции Л. Более того, те гиперпараметры, которые остаются неизменными на протяжении всей работы алгоритма, были рассмотрены не только с их известными эффективными значениями, но и со значениями, которые были настроены инструментальным пакетом ^асе17 (программный пакет, предоставляющий средства автоматической настройки параметров эволюционных алгоритмов), подобно тому, как это было сделано в одной из предшествующих работ18. Исследование столь обширного разнообразия конфигураций (1 + (Л, Л))-ГА является первым подобным исследованием для данного алгоритма.

Список литературы диссертационного исследования кандидат наук Басин Антон, 2020 год

Литература

[1] Benjamin Doerr, Carola Doerr, and Franziska Ebel. From black-box complexity to designing new genetic algorithms. // Theoretical Computer Science, Vol. 567, 87-104, 2015.

[2] Maxim Buzdalov and Benjamin Doerr. Runtime Analysis of the (1 + (Л, Л)) Genetic Algorithm on Random Satisfiable 3-CNF Formulas. // Proceedings of Genetic and Evolutionary Computation Conference, 1343-1350, 2017.

[3] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. // W. H. Freeman & Co., New York, NY, USA, 1979.

[4] B. W. Goldman and W. F. Punch. Parameter-less Population Pyramid. // Proceedings of Genetic and Evolutionary Computation Conference, 785-792, 2014.

Selection of Auxiliary Objectives Using Landscape Features and Offline Learned Classifier

Anton Bassin(B) and Anna Buzdalova

ITMO University, 49 Kronverksky Pr., Saint-Petersburg, Russia 197101 [e-mail], [e-mail]

Abstract. In order to increase the performance of an evolutionary algorithm, additional auxiliary optimization objectives may be added. It is hard to predict which auxiliary objectives will be the most efficient at different stages of optimization. Thus, the problem of dynamic selection between auxiliary objectives appears. This paper proposes a new method for efficient selection of auxiliary objectives, which uses fitness landscape information and problem meta-features. An offline learned meta-classifier is used to dynamically predict the most efficient auxiliary objective during the main optimization run performed by an evolutionary algorithm. An empirical evaluation on two benchmark combinatorial optimization problems (Traveling Salesman and Job Shop Scheduling problems) shows that the proposed approach outperforms similar known methods of auxiliary objective selection.

Keywords: Evolutionary algorithms • Multi-objective optimization • Auxiliary objectives • Fitness landscape features

1 Introduction

Evolutionary algorithms (EAs) are generic meta-heuristic optimization algorithms. An EA searches solution candidates based on the current state whilst previously reached historical states are not taken into account during the runtime. The information derived from the fitness landscape and from the optimization problem instance may be used to determine the state of an evolutionary algorithm. In these terms, the optimization problem transforms into searching the EA states which correspond to global optima on the fitness landscape. Auxiliary objectives may be used instead of the target objective or along with the target objective. Auxiliary objectives serve to multi-objectivise a single objective problem. In some cases this transformation may increase efficiency of an EA.

An auxiliary objective is efficient if its usage leads to decrease of the time needed to find the optimum of the target objective. Different auxiliary objectives have different efficiency on various stages of optimization. For example, at the stagnation point of the EA the most aggressive auxiliary objective may move the optimization process away from getting stuck in a local optimum. Inversely,

© Springer International Publishing AG 2017

B. Hu and M. Lopez-Ibanez (Eds.): EvoCOP 2017, LNCS 10197, pp. 173-188, 2017. DOI: 10.1007/978-3-319-55453-2-12

if the current algorithm state corresponds to the situation where solution candidates are located near the global optimum, we would want to use less aggressive auxiliary objectives.

At present time, researchers are looking for new ways of parameterizing fitness landscape features and applying received techniques in the evolutionary computation field [1,2]. Authors of paper [3] suggested a method to multi-objectivise single objective problems by using an elementary landscape decomposition of their objective function. However, to the best of our knowledge, landscape features have never been used to guide dynamical selection of auxiliary objectives. The existing objective selection algorithms use random selection based on the number of iterations [4] or reinforcement learning based on differences in target objective values [5].

One of the first approaches to transform a single-objective problem into a multi-objective one was proposed by Knowles et al. in [6]. The authors suggest decomposing the target objective into several components, which should be independent. The decomposed objectives are optimized simultaneously. Another method belongs to Jensen [4]. The idea is to use auxiliary objectives in combination with the target objective. Furthermore, the auxiliary objectives used in paper [4] are changed dynamically. The author concluded from the obtained experimental results that using one auxiliary objective at a time is the best approach, but he also underlined questions on when to change the auxiliary objective and to which objective it should be changed. There also exists an adaptive auxiliary objective selection method based on reinforcement learning called EA+RL [5]. The main idea is to use the reinforcement learning to train online (during the EA runtime) an agent, which tries to predict the most efficient auxiliary objective on each evolutionary iteration. The aforementioned method was improved by Petrova et al. in [7].

We tested the efficiency of the method that we propose in the present paper on multiple instances of two benchmark problems: The Traveling Salesman Problem (TSP) and The Job Shop Scheduling Problem (JSSP). However, the proposed method is not designed for solving any specific optimization problem, it is a general approach for selection of the most efficient auxiliary objective during EA runtime. Therefore, we compared the proposed method with other approaches of objective selection. Additionally, to confirm the reliability of the obtained results we checked the corresponding values for statistical distinguishability.

The rest of the paper is organized as follows. In Sect. 2 discusses the main aspects of the proposed method of auxiliary objective selection. Section 3 presents experiment results of solving TSP. Section 4 presents the results for the JSSP, and we conclude in Sect. 5.

2 The OLHP Method

We propose a new auxiliary objective selection strategy named The Offline Learned Helper Picker (OLHP). The term Offline is used because the meta-classifier for auxiliary objective selection is trained offline with machine learning methods. The learning dataset is gathered from the training EA runs on training instances of an optimization problem. The learning dataset vector contains

properties of the problem instance and feature values of the fitness landscape of the current EA population. The term Helper is used as a synonym to "auxiliary objective". The OLHP consists of two main phases: the meta-classifier learning and objective selection during the EA runtime. The implementation of OLHP, along with experimental evaluation results, is available at Bitbucket repository1.

2.1 Learning the Meta-Classifier Phase

The meta-classifier is learned only once for each optimization problem T. Input parameters of this phase are: 1. A set of training problem instances L C T, L consists of any i E T, where T is the set of all possible instances of a particular optimization problem. 2. A set of rules for auxiliary objectives generation G = [g(i)},9(i) = hi : IN ^ H, where H is the set of all possible auxiliary objectives for the considered optimization problem.

At the considered phase we construct the dataset of learning samples and then build the meta-classifier. To do this we need to perform n runs of the EA for each training problem instance. The value of the constant n may be manually tuned to find better meta-classifier metrics.

The current EA state is described by two components: static meta-features of the problem instance and features of the target objective landscape at the current population, which are extracted dynamically during the runtime. From each particular EA state stj we make k runs (k = \Hk \ is the total number of used auxiliary objectives, G(H) = Hk = {hi} is a set of generated auxiliary objectives) in parallel for niter = ^^ iterations, where Imax corresponds to the maximum number of iterations in a training run of the EA. Thus, the maximum number of considered EA states is j = k. Accordingly, there is a chance for each auxiliary objective to be picked at each EA state. All parallel EA threads optimize different auxiliary objective function hi simultaneously with the target objective. After performing latter evaluations we can make an assumption on which auxiliary objective hi would be the most efficient if using it from the EA state stj for niter EA iterations.

We identify an efficiency of an auxiliary objective by comparing the values of target objective for the best solution candidate in the beginning of each EA thread and in the end of its work. If several threads showed an equal increase in the target fitness value of the best solution, then the best auxiliary objective for the EA state stj is selected from the first thread. Thereby, we have one learning dataset vector which is comprised of the meta-features of the problem instance and the fitness landscape features corresponding to the EA state stj. The target value (or class value) of this vector is number i, which corresponds to the most efficient auxiliary objective hi.

After performing the training evaluations from the EA state stj, we move forward to a new state stj+1. As the state stj+1 we pick an EA state after using the most efficient auxiliary objective hj. The steps described above are processed until the maximum number of EA iterations Imax is reached. The final thing to

1 https://bitbucket.org/BASSIN/2017-olhp-tsp-jssp/src.

do is to train and save the meta-classifier for selection of auxiliary objectives. Algorithm 1 presents the pseudocode of the meta-classifier learning phase.

Algorithm 1. Learning of the meta-classifier

1: procedure learnselector(Inststr, G) > Inststr is a set of training instances,

G - set of auxiliary objective generating rules

2: r — the number of runs for each training instance 3: for all tr in Inststr do

4: metaFeatures — e^tractMetaFeatures(tr)

5: Hk — G(tr) > Generate auxiliary objectives for

train problem instance tr

6: i — 0 7: while i < r do

8: Imax — calculateMaxIterationNumber(tr)

9: niter — | Tjax > Setting iterations number between

algorithm states

10: EA.initialize(tr) > Initialize evolutionary algorithm

with train instance tr

11: j — 0

12: while j < Imax

do

13: stj — saveState(EA, metaF eatures)

14: for all h in Hk do > For each auxiliary objective

15: EA. run (niter, h) > Run EA with auxiliary objective h for

niter iterations

16: fitnessRaiseh — calculateFitnessDif f (EA)

17: sth — saveState(EA)

18: end for

19: hbest — findBestHelper(VfitnessRaiseh) > Identify the most

efficient auxiliary objective

20: dataset.put(hbest, stj.getMetaFeatures(), stj.getLandscapeFeatures())

21: EA.setState(sthbegt) > Set EA state to the state after

using the best auxiliary objective

22: j — j + niter

23: end while

24: i — i +1

25: end while

26: end for

27: classifier.train(dataset) > Learn the meta-classifier for objective selection

28: classifier.serialize() > Serialize trained model for future usages

29

end procedure

2.2 Objective Selection During the EA Runtime

This subsection describes the algorithm that dynamically selects and applies auxiliary objectives during EA runtime. The input parameters for this OLHP phase are: 1. An instance of the optimization problem we want to solve i E T, where T is a space of all possible instances of a particular optimization problem; 2. A set of rules for generation of auxiliary objectives G = {g(i)},g(i) = hi :

IN ^ H, where H is the set of all possible auxiliary objective functions we are working with. 3. A meta-classifier learned beforehand on problem instances from T: predict(v) = k, g(k) = hbest, where v is the vector of fitness landscape features of the current population and static meta-features of the problem instance.

The first step of this phase is initialization of all required structures and deserialization of the meta-classifier for considered optimization problem. At the next step, we start an evolutionary algorithm. Each n;ter = ^^ (k = \Hk \ = |G(H)|) iteration period we predict the most efficient auxiliary objective basing on the problem instance static features and fitness landscape features of the current EA population. The predicted objective hbest is used by the EA simultaneously with the target objective for the next n;ter iterations. Restriction on optimization by only one additional objective is made for making it possible to learn and solve many problem instances of various sizes for a reasonable computational time. Algorithm 2 presents the detailed pseudocode for this OLHP phase.

Algorithm 2 Solving the problem instance

1: procedure S0LVEPR0BLEM(inst,G, cl) > inst is a problem instance to optimize, cl - learned classifier

2: cl.deserialize()

3: metaFeatures ^ extractMetaFeatures(inst)

4: Hk ^ G(inst) > Generate auxiliary objectives for the

problem instance 5: Imax ^ calculateMaxIterationNumber(inst)

6: niter ^ "fSkr > Setting iterations number between algo-

rithm states

7: EA.initialize(inst) > Initialize EA with optimization problem

instance

j ^ 0

while j < Imax do

if j mod niter = 0 then > Time for switching an auxiliary objective

stj ^ getState(EA, metaFeatures, getLandscapeFeatures(EA)) hpredicted ^ cl.pr edict (stj ) EA.setHelper(hpredicted) end if

EA.runIteration() > Make one iteration of EA

j ^ j + 1 end while

EA.saveBestSolution() > Save the optimization result

end procedure

2.3 Fitness Landscape Features

We use generic fitness landscape features of an EA population which are eligible for almost any optimization problem. A population of size p may be represented as a set of random variables P = {si},i = 1..p. On each EA iteration we can obtain values of random variables si. Hence, we can calculate statistical metrics of set P.

Since we are solving meta-classification task for any instance of optimization problem T, we need to normalize the values of received landscape features. For such a normalization, we propose to use the ratio of the target objective value on current solution candidate to the best known solution candidate value: ,G(s'\ = xi, where G(s) is the target objective function. The set of random variables [xi] = ^normalized is normalized for all instances of problem T. Thus, we suggest to use the following statistical metrics calculated on the set Pnormalized as fitness landscape features:

1. Med - the median value.

2. X = Li xi - the arithmetical mean.

3. Hmean "p

p i ,Xi > 0 - the harmonic mean.

¿^'=1 X'

4. Dev - the standard deviation.

5. Qmean = ^Jp P=i(xi _ X)2 - the sample variance.

3 Applying OLHP to Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is a classic NP-hard problem in combinatorial optimization. Each TSP instance may be described by a set of cities [ci],Wi = 1 ...N and a distance matrix M of size N x N. Elements of M represent the distance between a pair of cities. For example, M(ci,cj) is the distance between the cities ci and Cj. The TSP asks the following question: "What is the shortest possible route that visits each city once and returns to the origin city?". In other words, we need to find a Hamiltonian path with the lowest total distance. For the path vector p = (pi,p2,...,pN) we can calculate the total distance cost using (1):

N

D(p) = YJ M (cp['],Cp['ffil]),

(1)

i + 1, if i<N

where i © 1 = <

1, if i = N

In experimental evaluations, we use symmetric TSP problem instances. In the symmetric TSP problem, the value of a path from one city to another is equal to the value of the reverse path: M(ci,cj) = M(cj ,ci). More detailed explanation of the TSP may be found in [8].

3.1 TSP Meta-Features

We need to specify TSP meta-features which we would use as a part of machine learning vector. Meta-features should contain information, which represents the properties of a particular TSP instance. The following features meet this requirement:

Selection of Auxiliary Objectives Using Landscape Features 179 Vnum - the number of cities.

Emin - the minimum distance between a pair of cities.

Emax - the maximum distance.

Eavg - the average distance.

Emed - the median distance.

Dev_g - the standard deviation of distances.

QE-avg - the number of distances shorter than Eavg.

SumminE - the sum of Vnum minimal distances.

The latter TSP meta-features were successfully used by Kanda et al. in [9] to classify Traveling Salesman Problems and in [10] to recommend meta-heuristics for solving TSP.

3.2 TSP Auxiliary Objectives Generation

In the OLHP method, an auxiliary objective is required to have some property, which depends only on the problem instance, but not on the individual or the iteration number. Unfortunately, the existing approaches of auxiliary objective generation [4,6] do not provide us objectives with such kind of a property, because in these approaches objectives are generated using randomly picked cities.

To generate auxiliary objectives which depend only on the problem instance, we propose a new method of auxiliary objective generation inspired by the k-nearest neighbor classification algorithm [11].

In [4], the following auxiliary objective function was proposed:

|s|

h(p,s) =5Z(M (cp[p-1[s[i]0i],cs[i])+M (cs[i] , c[p-1 [s[i]]ffii] ) , (2)

i=i

where s is the subset of the set of cities C = [1, 2,... ,N], p-i(x) is the position of x in p, ©1 is the reverse operator to © 1.

In our approach, we use Eq. (2) to generate auxiliary objectives. We generate subsets of cities (the s parameter in (2)) by partitioning the set of cities C = [ci],i = 1. ..N using the following algorithm:

1. Sort the set of all cities C by the following criteria:

Knn(C) ^ Sc = [ci,c2,...,cn ], (3)

where Knn(C) is the sorting operator, SC - is the ordered set. For each pair of elements from SC:

ci — knn cj ,

(4)

where i,j = 1 ...N and the relation —knn is true when the total distance from city ci to k nearest neighbor cities is less or equal to the corresponding total distance for the city cj.

2. Divide the ordered set SC into subsets sj C SC ,j = 1. ..r of equal cardinality.

The number of elements in the last subset sr may be less than the number of

elements in the other subsets.

Note that si n sj = 0, Wi,j = 1. ..r,i = j. This fact means that the generated auxiliary objectives h(p,sj) have disjoint properties on a problem instance. This should make possible for each auxiliary objective to be the most efficient objective at different stages of optimization process.

3.3 Experimental Evaluation on TSP

We compare the OLHP method with the following approaches of optimizing the target objective with auxiliary objectives. First, we consider the method proposed by Jensen [4], where the auxiliary objective is dynamically rese-lected after a fixed number of EA iterations. In the second considered approach [7], named Multi-Objective Evolutionary Algorithm + Reinforcement Learning (MOEA+RL), RL agent learns to select auxiliary objectives during the EA runtime and non-stationarity of the environment is taken into account. The last considered approach is a modified combination of two known algorithms. Two auxiliary objectives are composed in the manner described by Jahne et al. in [12] and the first selected auxiliary objective is switched to another one at the half of the EA runtime as suggested in [4].

The TSP instances for the experimental evaluation were taken from TSPLIB2 library. The crossover and mutation operators were identical to the corresponding operators from the papers mentioned above. Also, the 2-opt local search heuristic [13] was used.

The crossover probability was equal to 40%. The population size was Psize = 100. The limit of target objective evaluations for each EA run was calculated in the manner proposed in [12]: evmax(N, m) = VN3 * m, where N is the total number of cities, m is a manually chosen parameter (in our experiments we used m = 10). The number of EA runs for each training problem instance was n = 4.

The auxiliary objectives for the methods proposed by Jensen and Jahne were generated using the rules, which are provided in the related papers. The results for both the OLHP and MOEA+RL algorithms were obtained using the same auxiliary objectives, namely the K-nn auxiliary objectives proposed in Sect. 3.2. We used the following parameters to generate auxiliary objectives: k = 5, r = 5.

The comparison with MOEA+RL was intended to evaluate the efficiency of the proposed objective selection scheme without the influence of the objective generation approach, as the both OLHP and MOEA+RL algorithms are in equal conditions in terms of the used auxiliary objectives. At the same time, in the Jensen and Jahne/Jensen methods, the original auxiliary objectives from the corresponding works were applied, so the comparison with these methods was performed to evaluate the efficiency of the entire proposed approach for the TSP optimization.

2 http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95.

The Non-dominated Sorting Genetic Algorithm II (NSGA-II) [14] was used as the base evolutionary algorithm in all experiments. The program code was written in Java and Groovy languages. The following frameworks were used: Watchmaker3 - for evolutionary computations, Weka4 - for the OLHP machine learning operations.

Learning of Meta-Classifier. The Random Forest classifier was used for building the OLHP auxiliary objective selector. The Random Forest parameters had default5 values from the Weka framework.

To obtain train and test sets, TSP instances from the TSPLIB were divided into subsets. We were guided by the idea that train and test instances should have items with similar meta-properties. The train TSP instances are listed in Appendix A.

To estimate how accurately our predictive model would perform in practice, we cross-validated our classifier. For the same limitation on similarity of train and test problem instances we were forced to use a special set of problems for cross-validation. We made 10-fold cross-validation on instances listed in Appendix A. The performance metric values of our classification model on TSP after the cross-validation were: Estimated Error Rate = 0.16, Precision = 0.90, Recall = 0.96, F-measure = 0.93. The latter values confirm that there exists a correlation between the EA state features and selection of the most efficient auxiliary objective.

Results of Solving TSP. We used 44 TSP instances to perform experiments. Further, the final solution results for each method of auxiliary objective selection were obtained n = 40 times and averaged.

Table 1 shows mean and standard deviation of the best obtained value of the target objective for the OLHP, MOEA+RL, Jensen and Jensen/Jahne methods. Cells with the best values are marked with bold text. The last row of Table 1 shows the total number of instances, on which the particular method has outperformed other approaches. Note that the sum of the values in the last row is not equal to the number of total considered test instances. It is explained by the situation when several methods showed the best mean target value. In this case, we increment the corresponding counters for each such method. To summarize, it can be concluded from Table 1 that the newly proposed OLHP method outperformed the considered approaches of auxiliary objective selection on the set of test TSP instances.

Statistical Testing. According to [15], we used the Wilcoxon signed-rank test to detect significant differences in behavior of two algorithms. The pairwise statistical test was applied on the average results obtained on test instances for each pair of the considered approaches. In order to perform multiple comparisons and

3 http://watchmaker.uncommons.org.

4 http://www.cs.waikato.ac.nz/ml/weka.

5 http://weka.sourceforge.net/doc.dev/weka/classifiers/trees/RandomForest.html.

Problem Best OLHP MOEA+RL Jensen Jen/Jah

a280 2579 2597.9 ± 13.1 2599.4 ± 13.4 2597.2 ± 16.3 2597.2 ± 11.8

ali535 202339 204624.4 ± 1587.0 204382.0 ± 1482.5 205909.5 ± 1505.1 204853.0 ± 1463.7

att48 10628 10628.5 ± 2.2 10629.1 ± 4.9 10631.4 ± 6.5 10645.1 ± 17.7

bier127 118282 118337.3 ± 116.0 118436.2 ± 259.4 118320.6 ± 83.0 118358.1 ± 187.9

brg180 1950 1952.8 ± 4.5 1952.5 ± 4.3 1950.0 ± 0.0 1950.0 ± 0.0

ch150 6528 6548.0 ± 12.4 6550.8 ± 12.7 6544.4 ± 12.6 6547.6 ± 12.9

d1291 50801 51585.9 ± 210.2 51594.4 ± 240.7 51592.7 ± 191.1 51560.5 ± 270.5

d657 48912 49292.3 ± 151.9 49353.6 ± 141.5 49285.6 ± 127.6 49358.0 ± 131.0

dsj1000 18659688 18860887.9 ±45886.0 18870762.9 ±50593.3 18861694.6 ±60582.9 18887428.3 ±61706.0

eil76 538 544.4 ± 0.0 544.5 ± 0.5 544.7 ± 0.9 544.4 ± 0.1

fl417 11861 11927.0 ± 5.2 11926.8 ± 6.0 11942.1 ± 13.9 11939.7 ± 22.4

gr137 69853 69862.6 ± 28.5 69878.8 ± 57.9 69878.8 ± 44.4 69864.0 ± 29.3

gr229 134602 135130.0 ± 400.5 135087.3 ± 346.0 135048.9 ± 346.7 135051.8 ± 267.1

gr666 294358 297940.3 ± 1536.3 298189.9 ± 1454.3 297663.3 ± 1336.9 297826.6 ± 1426.5

gr96 55209 55305.2 ± 58.1 55312.6 ± 77.0 55352.1 ± 60.6 55326.9 ± 70.2

kroA100 21282 21287.0 ± 9.5 21287.0 ± 10.0 21287.0 ± 10.0 21285.4 ± 0.0

kroA200 29368 29393.5 ± 59.2 29398.2 ± 67.6 29426.1 ± 111.9 29395.7 ± 62.3

kroB100 22141 22140.9 ± 11.1 22148.2 ± 28.7 22141.3 ± 13.3 22145.9 ± 21.6

kroB150 26130 26148.2 ± 49.5 26190.0 ± 64.9 26162.5 ± 60.7 26149.8 ± 51.1

kroC100 20749 20750.8 ± 0.0 20750.8 ± 0.0 20750.8 ± 0.0 20750.8 ± 0.5

kroD100 21294 21311.2 ± 30.1 21333.5 ± 45.0 21374.0 ± 31.8 21314.5 ± 33.2

lin105 14379 14383.0 ± 0.0 14383.0 ± 0.0 14383.0 ± 0.0 14383.0 ± 0.0

lin318 42029 42321.6 ± 175.3 42323.7 ± 180.6 42314.6 ± 154.1 42297.7 ± 167.8

pcb1173 56892 57909.2 ± 166.2 57982.5 ± 250.3 57885.9 ± 199.6 57909.2 ± 201.1

pcb442 50778 51263.1 ± 132.1 51305.7 ± 199.0 51312.8 ± 202.1 51307.3 ± 167.3

pr1002 259045 262779.5 ± 868.7 263100.1 ± 1115.0 263427.5 ± 786.9 263178.0 ± 942.0

pr107 44303 44328.9 ± 39.9 44337.7 ± 50.8 44372.1 ± 74.5 44336.6 ± 50.0

pr124 59030 59030.7 ± 0.0 59030.7 ± 0.0 59032.9 ± 9.6 59030.7 ± 0.0

pr144 58537 58535.2 ± 0.0 58536.1 ± 5.2 58562.5 ± 14.8 58565.3 ± 19.9

pr152 73682 73697.4 ± 41.3 73711.2 ± 55.0 73783.6 ± 61.2 73691.6 ± 49.9

pr226 80369 80374.6 ± 12.4 80374.4 ± 12.4 80382.9 ± 38.8 80385.8 ± 29.7

pr299 48191 48320.1 ± 111.8 48370.7 ± 165.5 48434.7 ± 210.8 48398.6 ± 134.6

pr439 107217 107600.7 ± 424.3 107597.9 ± 354.4 107666.0 ± 498.6 107875.6 ± 510.4

rat195 2323 2340.6 ± 5.5 2344.9 ± 6.3 2343.1 ± 5.2 2342.9 ± 6.1

rat783 8806 8932.3 ± 23.8 8949.3 ± 25.4 8946.2 ± 25.5 8941.6 ± 22.8

rd100 7910 7912.3 ± 8.3 7911.9 ± 5.4 7914.7 ± 12.5 7914.7 ± 11.4

rd400 15281 15394.0 ± 54.6 15428.7 ± 58.8 15386.8 ± 54.3 15377.9 ± 55.8

si1032 92650 92650.0 ± 0.2 92656.6 ± 19.8 92720.3 ± 43.9 92673.4 ± 22.2

si535 48450 48496.4 ± 17.4 48496.2 ± 22.6 48543.2 ± 33.1 48487.8 ± 16.2

tsp225 3916 3876.3 ± 21.1 3877.8 ± 21.1 3873.1 ± 21.5 3869.2 ± 16.8

u1060 224094 226731.1 ± 671.0 226627.1 ± 721.0 226825.6 ± 690.4 226962.5 ± 687.4

u159 42080 42075.7 ± 0.0 42075.7 ± 0.0 42075.7 ± 0.0 42075.7 ± 0.0

u724 41910 42298.9 ± 137.3 42337.1 ± 119.3 42247.3 ± 96.4 42280.5 ± 121.7

vm1084 239297 241691.7 ± 962.0 241953.6 ± 898.0 241432.7 ± 704.0 241822.2 ± 770.0

Total best 21 10 12 12

control the family-wise error rate we adjusted the obtained p-values by using the Holm-Bonferroni correction method.

The adjusted p-values for pairs of methods of auxiliary objective selection were the following: OLHP - MOEA+RL = 1.0e-03, OLHP - Jensen = 4.2e-02, OLHP - Jensen/Jähne = 4.2e-02. Therefore, the OLHP method shows a significant improvement over MOEA+RL, Jensen and Jensen/Jahne approaches, with the level of significance a = 0.05.

4 Applying OLHP to Job Shop Scheduling Problem

The OLHP method was applied to the Job Shop Scheduling Problem (JSSP) for further verification of its efficiency. Similarly to TSP, JSSP is a well-known NP-hard combinatorial optimization problem.

A JSSP instance of size n x m consists of n jobs {J1,J2,...,Jn} = J and m machines {M1, M2,..., Mm} = M. Each job Ji contains a sequence of m operations (on, oil,... ,oim). Jobs and machines have mutual constraints, because an operation oij may be processed only on the corresponding machine Mj. Each operation oj takes the corresponding processing time Tij E IN. All jobs from the set J need to be scheduled properly on the given machines, while trying to minimize the amount of spent time resources. We consider the following JSSP variation: each machine may process only one operation at the same time, operations related to one job can not be processed concurrently and processing of an operation can not be interrupted.

There are several types of target objective which can be used in evolutionary computations for the JSSP. We minimize the total flow-time of the schedule S:

n

F (S) = ^(S(omaXs)+TDmaXi), (5)

i=1

where omaXi is the operation of the job Ji with the maximum start time in the schedule S, S(omaxj) defines the start time value of operation omaxj and T0max is the processing time of operation omaXi.

4.1 JSSP Meta-Features

The JSSP meta-features were developed similarly to the TSP meta-features from Sect. 3.1. The following features present the JSSP instance properties:

Jnum - the number of jobs.

MJrat;o = MM""" - the ratio between the number of machines and the number of jobs.

Tmin - the minimum operation processing time. Tmax - the maximum operation processing time. Tmean - the mean operation processing time.

DevT - the standard deviation of the operation processing time.

o ■ -

TavgM = —j=1 m n--the average processing time, which is also averaged

per machine.

Mn - the number of machines.

8

4.2 JSSP Auxiliary Objectives Generation

The restriction mentioned in the Sect. 3.2 (an auxiliary objective should have some property defined by the problem instance) is reached by the The Shortest

Job First (SJF) auxiliary objective generating method proposed by Lochtefeld et al. in [16].

Each particular job has a minimum processing time, which can be calculated by the following equation: Fmin(Ji) = Xj=i °ij■ The next step is to define the subset of jobs Hk, which would be used in the fc-th auxiliary objective. Then, the Eq. (5) evaluates the value of each auxiliary objective. The following algorithm is used to determine a subset of jobs Hk of the particular auxiliary objective:

1. The minimum processing times of all jobs Fminj,i = 1. ..n are calculated.

2. The set of all jobs J is sorted with respect to the minimum processing time:

Sort(J) ^ Sj = Ji,J2,..., Jn, whereFmin(Ji) < Fmin(Jj )■ (6)

3. The sorted set of all jobs SJ is divided into r subsets with equal number of elements. Such a subset defines the auxiliary objective.

More details about the SJF auxiliary objectives can be found at [17].

The subsets Hk for the objectives can also be formed in a random way. Such a technique is used by Jensen in [4]. We test performance of the random composed subsets of jobs and the subsets generated by the SJF algorithm.

4.3 Experimental Evaluation on JSSP

In [4], Jensen also suggests using random auxiliary objectives for the JSSP problem. In [18] Petrova et al. apply the MOEA + RL method to this problem. We also consider the problem specific approach proposed by Lochtefeld et al. [16], based on job prioritization for auxiliary objective selection order. The OLHP method was compared with the aforementioned algorithms.

The JSSP instances were taken from the Beasley's OR Library6. The Generalized Order Crossover (GOX) [19] and the Position Based Mutation (PBM) were used in all the considered algorithms. EA solution candidates were represented as an ordered permutation list of different operations with repetitions. For example, an individual for a 2 x 3 problem may be encoded as (1,2,2,1,1,2), where the first "1" is the first operation of the job J1, the second "1" is the second operation of J1 and so forth. Furthermore, the Giffler-Thompson schedule builder [20] is used to transform genome to the proper solution candidate.

The crossover probability was set to 80%. The population size was Psize = 100. The stopping condition was whether an EA reached the limit of iterations. This limit was calculated as follows: itermax(N, M) = N * M * 2, where N was the total number of machines, M was the total number of jobs in the problem instance. Likewise in the TSP experiments, we used NSGAII algorithm. The number of EA runs for each training instance was n = 4. For the OLHP, Lochtefeld's, MOEA+RL methods we used 4 different SJF auxiliary objectives (remember that only one auxiliary objective was optimized simultaneously with

6 http://people.brunel.ac.uk/~mastjjb/jeb/.

Table 2. Mean and standard deviation of resulting fitness (JSSP)

Problem Best OLHP MOEA+RL Lochtefeld Jensen

abz6 7808 8180.2 ± 143.8 8261.3 ± 137.6 8213.2 ± 134.3 8244.6 ± 125.9

abz7 12561 13116.1 ± 167.3 13272.3 ± 180.7 13193.5 ± 188.9 13150.7 ± 179.7

abz9 12813 13441.6 ± 187.7 13574.6 ± 172.9 13475.9 ± 191.0 13463.0 ± 216.9

ft06 265 272.7 ± 7.0 272.0 ± 7.1 272.2 ± 7.0 270.4 ± 6.8

ft20 14279 16047.1 ± 516.4 16892.9 ± 542.8 16370.6 ± 499.5 16426.7 ± 590.5

la01 4832 4989.6 ± 81.7 5043.2 ± 96.6 5015.2 ± 87.6 5003.3 ± 71.3

la03 4175 4236.4 ± 68.2 4328.6 ± 70.5 4271.8 ± 64.6 4280.6 ± 73.9

la05 4094 4189.0 ± 59.5 4270.0 ± 61.6 4215.3 ± 63.5 4263.4 ± 66.1

la06 8694 9298.3 ± 162.3 9693.7 ± 201.4 9442.8 ± 215.1 9435.1 ± 189.1

la08 8176 8708.9 ± 202.6 9175.4 ± 194.6 8929.1 ± 221.8 8947.6 ± 229.2

la09 9452 9777.7 ± 140.6 10166.5 ± 170.2 9932.6 ± 170.4 9952.9 ± 211.5

la10 9230 9557.7 ± 161.7 10015.0 ± 214.6 9698.0 ± 176.8 9762.9 ± 189.8

la11 14801 15840.5 ± 321.2 16786.1 ± 367.3 16197.8 ± 339.1 16253.5 ± 434.1

la12 12484 13449.3 ± 263.5 14319.7 ± 301.4 13783.4 ± 339.3 13928.9 ± 377.5

la14 15595 16199.8 ± 268.9 17119.5 ± 300.9 16568.6 ± 338.3 16624.7 ± 341.3

la16 7393 7836.2 ± 136.7 7984.5 ± 151.4 7893.9 ± 158.1 7872.4 ± 145.4

la17 6555 6847.5 ± 99.5 6907.5 ± 96.3 6850.9 ± 88.1 6866.2 ± 99.5

la20 7427 7751.9 ± 117.6 7832.4 ± 144.0 7794.4 ± 124.8 7773.9 ± 119.5

la21 12953 13940.4 ± 203.1 14272.6 ± 200.6 14083.7 ± 253.4 14068.1 ± 219.9

la22 12106 13120.0 ± 221.2 13251.0 ± 213.5 13094.6 ± 208.3 13132.4 ± 223.9

la25 12465 13154.3 ± 222.3 13445.0 ± 243.1 13344.7 ± 260.6 13246.0 ± 214.8

la26 20234 22351.7 ± 309.0 22823.0 ± 312.0 22467.0 ± 272.3 22449.4 ± 311.8

la29 20404 21498.7 ± 394.6 22047.7 ± 386.5 21707.8 ± 383.1 21733.0 ± 392.2

la30 22333 23725.8 ± 472.4 24323.1 ± 382.8 24026.2 ± 471.2 23948.2 ± 419.7

la31 39007 44400.9 ± 619.9 45201.8 ± 541.6 44548.8 ± 580.2 44524.4 ± 614.9

la35 44059 46014.8 ± 638.6 46843.0 ± 633.2 46382.7 ± 679.1 46161.3 ± 784.9

la36 17073 18461.3 ± 289.8 18565.4 ± 244.1 18485.6 ± 272.2 18484.2 ± 270.3

la38 16621 17346.9 ± 290.6 17595.4 ± 280.3 17474.5 ± 280.0 17439.8 ± 282.9

la40 16618 17667.4 ± 264.3 17894.0 ± 270.7 17771.0 ± 267.2 17726.0 ± 274.6

orb02 7353 7684.6 ± 123.8 7753.5 ± 118.9 7739.5 ± 125.5 7708.2 ± 125.8

orb03 8280 8772.8 ± 170.3 8895.3 ± 194.0 8774.7 ± 189.7 8784.9 ± 235.5

orb06 8418 8950.3 ± 205.2 9113.8 ± 221.3 8979.7 ± 202.7 8950.6 ± 203.8

orb07 3296 3505.6 ± 61.5 3551.1 ± 74.9 3523.7 ± 63.2 3510.5 ± 74.1

orb09 7582 8025.0 ± 180.5 8231.8 ± 233.7 8062.8 ± 162.9 8149.8 ± 198.5

orb10 8043 8335.7 ± 125.8 8419.0 ± 146.9 8358.3 ± 147.4 8367.5 ± 134.5

swv01 20688 24859.5 ± 711.2 25710.4 ± 649.8 25441.2 ± 630.2 25461.3 ± 709.7

swv03 23266 24617.6 ± 623.1 25547.2 ± 633.0 25023.4 ± 668.7 25150.6 ± 652.5

swv04 24271 25665.5 ± 574.4 26457.5 ± 543.8 25978.6 ± 642.5 25957.5 ± 660.7

swv07 27385 32738.5 ± 710.4 33407.3 ± 652.0 32744.2 ± 711.8 32843.7 ± 755.0

swv08 32976 36043.0 ± 775.3 36655.9 ± 765.7 36136.3 ± 852.7 36265.8 ± 724.1

swv09 31841 33783.7 ± 696.4 34350.2 ± 744.4 34037.0 ± 855.6 33920.3 ± 788.5

swv11 108842 140735.9 ± 2939.1 145240.3 ± 3350.8 142351.2 ± 3360.4 141638.6 ± 3386.9

swv12 109128 140695.3 ± 3173.4 145495.7 ± 3093.0 142674.0 ± 2961.3 141281.9 ± 3247.0

swv14 126333 137137.8 ± 3101.6 141119.4 ± 3524.9 137850.9 ± 2779.5 137362.5 ± 3225.5

swv15 131037 139467.0 ± 3991.3 143849.0 ± 3676.6 140435.0 ± 3224.6 140211.6 ± 3476.1

swv16 113398 117369.9 ± 1303.0 119494.0 ± 1008.8 117937.3 ± 1045.1 117466.7 ± 1194.2

swv17 110145 113689.1 ± 1020.0 115666.0 ± 1042.6 114240.4 ± 981.0 113760.8 ± 1444.7

swv20 109742 112866.7 ± 1060.6 115285.1 ± 977.5 113277.0 ± 1038.2 113184.2 ± 1043.8

yn1 17317 18199.5 ± 234.9 18397.8 ± 212.6 18236.6 ± 210.0 18229.1 ± 227.3

yn4 19107 19916.3 ± 253.7 20115.0 ± 220.2 19997.4 ± 244.7 19959.7 ± 222.8

Total best 48 0 1 1

the target objective). Jensen's method was compared with the approach based on random generating of auxiliary objectives. We used the same OLHP implementation and the same frameworks as for the TSP.

Meta-Classifier Learning. The meta-classifier for selection of auxiliary objectives was trained on 32 JSSP instances (see Appendix A). The considered training instances were not so diverse as the training instances for the TSP. So we could cross-validate the learned classifier model on the training set of JSSP instances with high probability not to have a situation, when we would try to validate on some data, which was not considered in the learning process. The performance measure values of our classification model on JSSP after the 10-fold cross-validation were: Estimated Error Rate = 0.21, Precision = 0.72, Recall = 0.74, F-measure = 0.73. The correlation between the EA state features and selection of the most efficient auxiliary objective also exists for this benchmark problem.

Results of Solving the JSSP. There were 50 various JSSP test instances. Each instance was solved n = 100 times with NSGAII and each auxiliary objective selection method. We present comparison results in the same way as for the TSP problem. The averaged results for each method of objective selection with the standard deviations are listed in Table 2. The calculated comparison results show that the OLHP method has significantly outperformed all the other methods of auxiliary objective selection. It is also worth mentioning that we were not able to find sources with the best known solutions for the Beasley's OR Library problems. So we run a single objective EA 1000 times on each instance and gathered the best found results.

Statistical Testing. As in the TSP problem experiments, we used the Wilcoxon signed-rank test and the Holm-Bonferroni correction method for statistical verification of the results. We obtained the following adjusted p-values for pairs of objective selection methods: OLHP - MOEA+RL = 2.3e-09, OLHP - Lochtefeld = 2.3e-09, OLHP - Jensen = 2.3e-09. The aforementioned adjustedp-values show that average performance of the OLHP method and the other considered algorithms was significantly different. Moreover, the confidence level of this fact is more than 99%.

5 Conclusion and Future Work

The new method for selection of the most efficient auxiliary objective named The Offline Learned Helper Picker is proposed in this paper. The OLHP approach consists of two stages. At first, training instances of an optimization problem are used to build a meta-classifier for selection of auxiliary objectives. Properties of a problem instance and features derived from the fitness landscape of the current EA population compose the state of the evolutionary algorithm, i.e. the data vector for machine learning. Further, the trained meta-classifier is used to predict the most efficient auxiliary objective at different EA runtime points. Specifically, the selected auxiliary objective is predicted and optimized simultaneously with the target objective during a number of EA iterations.

The OLHP method was compared with similar approaches of objective selection on two NP-hard combinatorial problems: The Traveling Salesman Problem and The Job Shop Scheduling Problem. The newly proposed method outperformed the considered algorithms. Statistical significance of the obtained results was confirmed by the Wilcoxon signed-rank test followed by the Holm-Bonferroni correction.

In the future work we plan to use additional well-known statistical, probabilistic and informational measures for fitness landscapes. This should increase performance of the meta-classifier used for selection of auxiliary objectives. It is also desirable to use more computational power for obtaining experimental evaluation on real world problems. Better computational performance will also provide an opportunity to automatically find and use the most efficient parameters for EA with OLHP and other auxiliary objective selection methods. For example, the most efficient algorithm settings may be found with tools such as the irace package [21].

A Appendix: TSP and JSSP Instances Lists

TSP Train: att532, bays29, brazil58, ch130, d198, d493, eil101, gil262, gr120, gr202, gr24, gr431, hk48, kroA150, kroB200, kroE100, p654, pa561, pr136, pr264, rat575, rat99, si175, st70, ts225, u574, ulysses22. TSP Cross-validate: a280, att48, bayg29, bays29, berlin52, bier127, brazil58, brg180, burma14, ch130, ch150, d198, d493, dantzig42, eil101, eil51, eil76, fl417, fri26, gil262, gr17, gr21, gr24, gr48, gr96, gr120, gr137, gr202, gr229, gr431, hk48, kroA100, kroA150, kroA200, kroB100, kroB150, kroB200, kroC100, kroD100, kroE100, lin105, lin318, pcb442, pr76, pr107, pr124, pr136, pr144, pr152, pr226, pr264, pr299, pr439, rat195, rat99, rd100, rd400, si175, st70, swiss42, ts225, tsp225, u159, ulysses16, ulysses22.

JSSP Train and Cross-validate: abz5, abz8, ft10, la02, la04, la07, la13, la15, la18, la19, la23, la24, la27, la28, la32, la33, la34, la37, la39, orb01, orb04, orb05, orb08, swv02, swv05, swv06, swv10, swv13, swv18, swv19, yn2, yn3.

References

1. Pitzer, E., Affenzeller, M.: A comprehensive survey on fitness landscape analysis. In: Fodor, J., Klempous, R., Araujo, C.P.S. (eds.) Recent Adv. Intell. Eng. Syst., pp. 161-191. Springer, Heidelberg (2012)

2. Picek, S., Jakobovic, D.: From fitness landscape to crossover operator choice. In: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, pp. 815-822. ACM (2014)

3. Ceberio, J., Calvo, B., Mendiburu, A., Lozano, J.A.: Multi-objectivising the quadratic assignment problem by means of an elementary landscape decomposition. In: Puerta, J.M., Gamez, J.A., Dorronsoro, B., Barrenechea, E., Troncoso, A., Baruque, B., Galar, M. (eds.) CAEPIA 2015. LNCS (LNAI), vol. 9422, pp. 289300. Springer, Heidelberg (2015). doi:10.1007/978-3-319-24598-0_26

4. Jensen, T.: Helper-objectives: using multi-objective evolutionary algorithms for single-objective optimisation. J. Math. Model. Algorithms 3(4), 323-347 (2005)

5. Buzdalova, A., Buzdalov, M.: Increasing efficiency of evolutionary algorithms by choosing between auxiliary fitness functions with reinforcement learning. In: 2012 11th International Conference on Machine Learning and Applications (ICMLA), vol. 1, pp. 150-155. IEEE (2012)

6. Knowles, J.D., Watson, R.A., Corne, D.W.: Reducing local optima in single-objective problems by multi-objectivization. In: Zitzler, E., Thiele, L., Deb, K., Coello Coello, C.A., Corne, D. (eds.) EMO 2001. LNCS, vol. 1993, pp. 269-283. Springer, Heidelberg (2001). doi:10.1007/3-540-44719-9_19

7. Petrova, I., Buzdalova, A., Buzdalov, M.: Improved selection of auxiliary objectives using reinforcement learning in non-stationary environment. In: 2014 13th International Conference on Machine Learning and Applications (ICMLA), pp. 580-583. IEEE (2014)

8. Applegate, D.L., Bixby, R.E., Chvatal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton (2011)

9. Kanda, J., Carvalho, A., Hruschka, E., Soares, C.: Using meta-learning to classify traveling salesman problems. In: 2010 Eleventh Brazilian Symposium on Neural Networks, pp. 73-78. IEEE (2010)

10. Kanda, J.Y., de Carvalho, A.C., Hruschka, E.R., Soares, C.: Using meta-learning to recommend meta-heuristics for the traveling salesman problem. In: 2011 10th International Conference on Machine Learning and Applications and Workshops (ICMLA), pp. 346-351. IEEE (2011)

11. Cover, T., Hart, P.: Nearest neighbor pattern classification. IEEE Trans. Inf. Theory 13(1), 21-27 (1967)

12. Jahne, M., Li, X., Branke, J.: Evolutionary algorithms and multi-objectivization for the travelling salesman problem. In: Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pp. 595-602. ACM (2009)

13. Johnson, D.S., McGeoch, L.A.: The traveling salesman problem: a case in study local optimization. Local Search Comb. Optim. 1, 215-310 (1997)

14. Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182-197 (2002)

15. Derrac, J., Garcia, S., Molina, D., Herrera, F.: A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm Evol. Comput. 1(1), 3-18 (2011)

16. Lochtefeld, D.F., Ciarallo, F.W.: Deterministic helper-objective sequences applied to job-shop scheduling. In: Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, pp. 431-438. ACM (2010)

17. Lochtefeld, D.F., Ciarallo, W.: Helper-objective optimization strategies for the jobshop scheduling problem. Appl. Soft Comput. 11(6), 4161-4174 (2011)

18. Petrova, I., Buzdalova, A., Buzdalov, M.: Improved helper-objective optimization strategy for job-shop scheduling problem. In: 2013 12th International Conference on Machine Learning and Applications (ICMLA), pp. 374-377, vol 2. IEEE (2013)

19. Bierwirth, C.: A generalized permutation approach to job shop scheduling with genetic algorithms. Oper. -Res. -Spektrum 17(2-3), 87-92 (1995)

20. Giffler, B., Thompson, G.L.: Algorithms for solving production-scheduling problems. Oper. Res. 8(4), 487-503 (1960)

21. Lopez-Ibaiiez, M., Dubois-Lacoste, J., Stiitzle, T., Birattari, M.: The irace package, iterated race for automatic algorithm configuration. Technical report TR/IRIDIA/2011-004, IRIDIA, Universite Libre de Bruxelles, Belgium (2011)