Методы теоретического анализа динамики работы эволюционных алгоритмов тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Винокуров Дмитрий Владимирович
Винокуров Дмитрий Владимирович
кандидат наук
2022
- Специальность ВАК РФ00.00.00
- Количество страниц 257
Оглавление диссертации кандидат наук Винокуров Дмитрий Владимирович
Реферат
Synopsis
Introduction
Chapter 1. Analytical Overview and Motivation
1.1 Evolutionary Computation
1.2 Theoretical Analysis
1.2.1 Runtime Analysis
1.2.2 Black-Box Complexity Analysis
1.2.3 Fine-Grained Analyses
1.3 Parameter Setting
1.4 Studied Algorithms
1.4.1 (m+1) Evolutionary Algorithm
1.4.2 Heavy-Tailed (1 + (X,X)) Genetic Algorithm
1.5 Examined Problems
1.6 Chapter 1 conclusion
Chapter 2. Theoretical Tools for Fixed-Target Runtime Analysis
2.1 Artificial Fitness-Level Methods
2.1.1 Generalization to FT-analysis
2.1.2 Application: Hill Climbers on LeadingOnes
2.1.3 Application: Hill Climbers on OneMax
2.1.4 Application: (ц+1) EA on OneMax, Fixed-Target Upper Bound
2.2 Drift Analysis
2.2.1 Additive Drift Theorems
2.2.2 Variable and Multiplicative Drift Theorems
2.2.3 Application: Hill Climbers on MST, Fixed-Target Upper Bound
2.2.4 Application: (1 +1) EA on OneMax, Fixed-Target Lower Bound
2.2.5 Application: Hill Climbers on BinVal, Fixed-Target Upper Bounds
2.3 Chapter 2 conclusion
Chapter 3. Unrestricted Fixed-Target Black-Box Complexity
Analysis
3.1 Notion and Preliminaries
3.2 General Fixed-Target Lower Bound
3.3 Unrestricted Fixed-Target BBC of OneMax
3.3.1 Lower Bound
3.3.2 Upper Bound
3.4 Chapter 3 conclusion
Chapter 4. Optimal Parameter Settings to Reach Fixed-
Target Solutions
4.1 Experimental Setups
4.2 Parameter Tuning of LeadingOnes
4.3 Parameter Tuning of OneMax
4.3.1 (1 + 1) Evolutionary Algorithm
4.3.2 t—Randomized Local Search
4.3.3 Heavy-Tailed (1 + (X,X)) GA
4.4 Parameter Control of t-RLS on OneMax
4.5 Chapter 4 conclusion
Conclusion
References
List of Figures
List of Tables
Appendix A. Copies of Author's Publications
Реферат
Рекомендованный список диссертаций по специальности «Другие cпециальности», 00.00.00 шифр ВАК
Методы обобщения и повышения производительности двухфазного генетического алгоритма со скрещиванием, компенсирующим воздействия мутаций2020 год, кандидат наук Басин Антон
Эффективные алгоритмы инкрементальной и асинхронной недоминирующей сортировки для многокритериальных эволюционных алгоритмов2019 год, кандидат наук Якупов Илья Юрьевич
Методы и алгоритмы идентификации по данным физически обоснованных моделей в форме дифференциальных уравнений2023 год, кандидат наук Масляев Михаил Александрович
Метод совместного использования эволюционных алгоритмов и обучения с подкреплением для оценки эффективности программ решения задач дискретной математики2017 год, кандидат наук Буздалова Арина Сергеевна
Коллективный самонастраивающийся метод оптимизации на основе бионических алгоритмов2016 год, кандидат наук Ахмедова Шахназ Агасувар кызы
Введение диссертации (часть автореферата) на тему «Методы теоретического анализа динамики работы эволюционных алгоритмов»
Общая характеристика работы
Актуальность темы исследования.
Эволюционные алгоритмы (ЭА) нередко используются в качестве методов искусственного интеллекта, позволяющих имитировать когнитивные функции человека, такие как поиск решений без заранее заданного алгоритма1, получая при этом результаты, сопоставимые с результатами деятельности человека и даже превосходящие их2.
Одним из способов поиска путей повышения эффективности ЭА является их теоретический анализ. Современная теория ЭА строится на доказательстве теорем о верхних и нижних оценках для времени нахождения тем или иным ЭА решения определенных задач3. Эти теоремы позволяют понимать преимущества и недостатки существующих ЭА и создавать более эффективные алгоритмы4.
Большинство теоретических исследований изучает поиск наилучшего решения (глобального оптимума функции приспособленности). В то же время в реальной практике использования ЭА целесообразным является скорее получения достаточно хороших, но необязательно оптимальных решений. Теоретический анализ динамики работы эволюционных алгоритмов, который лучше соответствует таким сценариям, в настоящее время развит недостаточно, что определяет актуальность настоящей работы.
10 развитии искусственного интеллекта в Российской Федерации : Указ Президента РФ от 10 октября 2019 г. №490 .
2Annual "Humies" Awards For Human-Competitive Results Produced By Genetic And Evolutionary Computation. 2022. URL: https://www.human-competitive.org/awards.
3Theory of Evolutionary Computation—Recent Developments in Discrete Optimization / ed. by B. Doerr, F. Neumann. Springer, 2020.
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. Выделяют три постановки, связанные с динамикой ЭА: FS-анализ (англ. Fixed-Start) — анализ времени достижения оптимального решения алгоритмом, начинающим работу с решения заданной приспособленности, FB-анализ (англ. Fixed-Budget) — анализ приспособленности решения, достигаемого ЭА за заданное время, и FT-анализ (англ. Fixed-Target) — анализ времени достижения алгоритмом решения заданной приспособленности.
Теоретические исследования в рамках первых двух постановок уже выполнялись ранее6, в то время как целенаправленное получение теоретических результатов в рамках FT-анализа ранее не производилось. В силу этого отсутствуют и специализированные методы получения таких результатов, в отличие от методов FB-анализа7. При этом FT-анализ признается более перспективным для целей повышения эффективности ЭА, например, в части выработки рекомендаций по статической и динамической настройке параметров ЭА8 с целью повышения производительности последних.
С учетом вышесказанного, в данной диссертации исследуются методы получения теоретических результатов, включающих верхние и нижние оценки времени работы ЭА и оценки вычислительной слож-
5Doerr, C. [et al.]. Benchmarking discrete optimization heuristics with IOHprofiler // Appl. Soft Comput. 2020. Vol. 88. P. 106027.
6Antipov, D., Buzdalov, M., Doerr, B. First Steps Towards a Runtime Analysis When Starting With a Good Solution // Parallel Problem Solving from Nature - PPSN XVI. 2020. P. 560-573. (Lecture Notes in Computer Science ; 12270); Jansen, T., Zarges, C. Fixed Budget Computations: A Different Perspective on Run Time Analysis // Proceedings of Genetic and Evolutionary Computation Conference. 2012. P. 1325-1332.
7Lengler, J., Spooner, N. Fixed budget performance of the (1 + 1) EA on linear functions // Foundations of Genetic Algorithms, FOGA 2015. ACM, 2015. P. 52-61.
8Doerr, B., Doerr, C., Ebel, F. From black-box complexity to designing new genetic algorithms // Theoretical Computer Science. 2015. Vol. 567. P. 87-104.
ности задач оптимизации, в рамках FT-анализа как способа исследования динамики работы ЭА.
Цель работы состоит в разработке методологии получения теоретических оценок на время работы ЭА в рамках FT-анализа.
Для достижения данной цели определены следующие задачи:
а) Обзор известных результатов анализов всего процесса работы ЭА в прикладных и теоретических областях эволюционных вычислений.
б) Разработка методов получения времени работы ЭА до достижения ими заданного уровня приспособленности.
в) Разработка методов получения оценок для вычислительной сложности задач оптимизации в постановке достижения алгоритмами заданного уровня приспособленности.
г) Применение разработанных методов на ряде алгоритмов и функций приспособленности.
д) Разработка рекомендаций по выбору оптимальных параметров ЭА в разрезе достижения ими решений заданного уровня приспособленности.
Объект исследования — бионические методы оптимизации (в частности, эволюционные алгоритмы).
Предмет исследования — методы теоретического анализа времени работы бионических методов оптимизации.
Соответствие паспорту специальности. Данная диссертация соответствует пункту 16 «Исследования в области специальных методов оптимизации, проблем сложности и элиминации перебора, снижения размерности» в части объекта исследования.
Основные положения, выносимые на защиту:
а) Методы для доказательств оценок на время работы ЭА при достижении заданного уровня приспособленности.
б) Метод получения нижних оценок для неограниченной вычислительной сложности задач оптимизации при достижении заданного уровня приспособленности.
в) Экспериментально выявленная закономерность изменения оптимальной силы мутации ЭА в зависимости от значения целевой приспособленности решения.
Научная новизна заключается в следующем:
а) Представленные в работе утверждения и теоремы для метода уровней приспособленности и дрейфового анализа, в отличие от известных, впервые приведены сугубо в контексте достижения решений произвольной приспособленности.
б) Теоремы для получения нижних границ неограниченной вычислительной сложности задач в контексте FT-анализа являются первыми в своем роде.
в) Поставленные эксперименты используют точные расчеты оптимальных вероятностей мутации при достижении алгоритмами решений фиксированной приспособленности, а не лучшего качества, которое рассматривалось ранее.
Методология и методы исследования. В работе используются методы дискретной математики, теории вероятностей, объектно-ориентированного программирования, а также методы проведения и анализа вычислительных экспериментов.
Достоверность научных положений, выводов и доказательств, полученных в диссертации, подтверждается корректностью постановок задач, формальным доказательством утверждений относительно корректности разработанных методов, а также результатами проведённых экспериментальных исследований.
Теоретическая значимость работы состоит в том, что с помощью предложенных в работе методов доказано следующее:
- Границы применимости теорем дрейфового анализа для использования в FT-анализе.
- Новые более точные теоремы дрейфового анализа, учитывающие ожидаемое качество решения на момент достижения алгоритмом решения заданной приспособленности.
- Новые оценки FT-анализа на время работы различных ЭА на функциях OneMax и MST.
- Первые верхние и нижние оценки неограниченной вычислительной сложности OneMax до нахождения решений заданной приспособленности.
Практическая значимость работы заключается в том, что результаты исследованного в работе FT-анализа могут быть использованы при разработке новых эффективных ЭА или для увеличения производительности существующих, например, путем оптимального подбора лучших алгоритмов и их параметров на разных стадиях процесса работы ЭА в зависимости от найденных решений.
Внедрение результатов работы. Результаты работы использованы при выполнении гранта Российского фонда фундаментальных исследований (проект 20-51-15009 НЦНИ_а «Теоретические основы динамической настройки параметров в эволюционных алгоритмах», 2020-2022 гг.).
Апробация результатов работы. Основные результаты работы докладывались на следующих конференциях:
а) Parallel Problem Solving from Nature (2022, Дортмунд, Германия);
б) Научная и учебно-методическая конференция ППС (2021, 2022, Университет ИТМО);
в) Всероссийский конгресс молодых учёных (2020, Университет ИТМО);
г) Genetic and Evolutionary Computation Conference (2019, Прага,
Чехия; 2020, онлайн; 2022, онлайн); Личный вклад автора. Автором выполнены доказательства корректности теоретических оценок и анализа времени работы предложенных в диссертации методов, а также реализация программ для расчета оптимальной силы мутаций. В работах, выполненных в соавторстве с научным руководителем Буздаловым М.В., его вклад заключался в общем руководстве работой, предоставлении исходного кода для выполнения ряда экспериментальных исследований, а также в визуализации ряда графиков.
Публикации. Основные результаты по теме диссертации изложены в шести публикациях, все из них опубликованы в изданиях, индексируемых в базе цитирования Scopus.
Содержание работы
Во введении обосновывается актуальность исследований, проводимых в рамках данной диссертационной работы, приводится краткий обзор научной литературы по изучаемой проблеме, формулируется цель, ставятся задачи работы, излагается её научная новизна, теоретическая и практическая значимость.
Первая глава представляет собой аналитический обзор предметной области. В ней представлены ключевые определения, описания рассматриваемых алгоритмов и модельных задач.
Многие задачи, в частности проблемы из класса NP, не имеют детерминированных алгоритмов, умеющих без полного перебора пространства решений находить глобальный оптимум. Поэтому для таких задач часто применяют специальные методы оптимизации -рандомизированные поисковые эвристики (англ. randomized search heuristics), которые обычно умеют находить оптимальное решение довольно быстро, но не гарантируют, что это обязательно произойдет. Эти эвристики обычно имеют некий природный концепт в основе их работы, также отражаемый в названии: например, метод имитации от-жига9 или муравьиные алгоритмы10. Зачастую такие эвристики в целом называют эволюционными алгоритмами (ЭА), хотя не все из них основаны непосредственно на идеях теории эволюции.
Связь ЭА с биологическими принципами отразилась на ключевых определениях, используемых в их сфере: производимое решение-кандидат называется особью, ее вычислимое качество называется приспособленностью, и соответственно функция, которая это качество
9Kirkpatrick, S., Gelatt, C. D., Vecchi, M. P. Optimization by Simulated Annealing // Science. 1983. Vol. 220, no. 4598. P. 671-680.
10Dorigo, M., Gambardella, L. M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem // IEEE Transactions on Evolutionary Computation. 1997. Vol. 1, no. 1. P. 53-66.
определяет, зовется функцией приспособленности. На итерации работы ЭА генерирует решения, образующие дочернюю популяцию особей, применяя локальные операторы мутации или комбинирующие операторы скрещивания к особям родительской популяции.
ЭА являются широко применяемыми на практике инструментами решения сложных задач11, и даже могут являться основой для сложных инструментов машинного обучения: например, архитектура нейронной сети WANN12 (англ. Weight Agnostic Neural Networks) «выращивается» эволюционными алгоритмами таким образом, что веса
«J г—" t» г—"
нейронных связей могут быть заданы случайным образом, и не требуется выполнять затратный этап обучения сети. Однако ввиду вероятностной природы внутрилежащих процессов нетривиально определить, насколько быстро ЭА найдет оптимальное решение поставленной задачи, если вообще может его достичь. Различные свойства работы ЭА являются сферой интересов теоретических исследований, которые приносят вклад в непосредственное углубление знаний в принципы работы ЭА, а также помогают в разработке новых эффективных алгоритмов: таким образом, например, был предложен генетический алгоритм (1 + (Л, А))13. Наиболее часто используемой мерой производительности в теоретических исследованиях является число вычислений функции приспособленности, которое необходимо изучаемому алгоритму для достижения оптимального решения рассматриваемой задачи. Данное число для простоты называют временем работы алгоритма или временем оптимизации.
Классическим видом теоретических исследований является анализ времени работы (англ. runtime analysis), целью которого являет-
11Bianchi, L. [et al.]. A survey on metaheuristics for stochastic combinatorial optimization // Natural Computing. 2009. Vol. 8. P. 239-287.
12Gaier, A., Ha, D. Weight Agnostic Neural Networks // Proceedings of the 33rd International Conference on Neural Information Processing Systems. Curran Associates Inc., 2019.
13Doerr, B., Doerr, C., Ebel, F. From black-box complexity to designing new genetic algorithms // Theoretical Computer Science. 2015. Vol. 567. P. 87-104.
ся исследование времени работы конкретного ЭА на заранее известной задаче. Одними из самых популярных, но не единственными инструментами для получения результатов такого анализа являются метод уровней приспособленности14 (англ. artificial fitness-level method) и дрейфовый анализ15(англ. drift analysis). Большинство других методов либо обладают узкой спецификой применения, такие как генеалогические деревья16(англ. family trees) для исследования (ц + 1) EA, либо требуют выполнения сложных предусловий, например стохастическое доминирование17(англ. stochastic domination). Однако все эти методы анализа заточены в главную очередь на достижение оптимума функции приспособленности.
Еще одним направлением теоретических исследованиях является анализ вычислительной сложности задач оптимиза-ции18(англ. black-box complexity analysis). В таком анализе исследуется время работы лучшего алгоритма из какого-то определенного класса на конкретной задаче, которая и выступает в роли самого «черного ящика», к структуре которого алгоритмы не имеют доступа и могут лишь у него запрашивать приспособленность решения. Это направление исследований полезно при сравнении с традиционным анализом времени работы ЭА, в основном для определения оптимальности известных алгоритмов и мотивации поиска новых эвристик. Как и в случае с анализом времени работы, основной теоретический
14 Wegener, I. Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions // Evolutionary Optimization / ed. by R. Sarker, X. Yao, M. Mohammadian. Kluwer, 2002. P. 349-369.
15He, J., Yao, X. Drift analysis and average time complexity of evolutionary algorithms // Artificial Intelligence. 2001. Vol. 127. P. 51-81.
16 Witt, C. Population size vs. runtime of a simple EA // The 2003 Congress on Evolutionary Computation, 2003. CEC '03. Vol. 3. 2003. P. 1996-2003.
17Doerr, B. Analyzing randomized search heuristics via stochastic domination // Theoretical Computer Science. 2019. Vol. 773. P. 115-137.
18Droste, S., Jansen, T., Wegener, I. Upper and Lower Bounds for Randomized Search Heuristics in Black-Box Optimization // Theory of Computing Systems. 2006. Vol. 39, no. 4. P. 525-544.
инструментарий анализа вычислительной сложности заточен только под поиск оптимума задачи.
Если смотреть только на время оптимизации как на метрику производительности ЭА, то она сводит весь процесс работы в одну точ-
w гт-1
ку во времени, когда найдено лучшее решение задачи. Тем не менее часто требуется более детальная информация обо всем ходе работы, которая может быть мотивирована следующим:
- С точки зрения оптимальности искомого решения на практике часто достаточно получить ответ лишь заданного качества, возможно далекого от лучшего решения. Более того, глобальный оптимум может быть вообще недостижим ЭА, или способ его нахождения может не отличаться от полного перебора всех возможных потенциальных кандидатов-решений.
- ЭА являются особыми видом алгоритмов, которые находят решение на каждой итерации своей работы19 (англ. anytime algorithm). Если прервать процесс оптимизации в любой момент времени, то всегда будет выдано решение некоторого, возможно удовлетворительного, качества. Однако время оптимизации, как мера производительности ЭА, ничего не говорит о таком решении.
- Время достижения оптимального решения не всегда является полезным ориентиром при разработке эффективных алгоритмов. Например, при возможности использования ряда ЭА для решения задачи в каждый момент времени следует использовать самый лучший алгоритм согласно некоторому критерию полезности. Но чтобы определить, когда и на что нужно сменять алгоритмы, необходим более полный теоретический анализ, чем анализ времени оптимизации.
19Dean, T., Boddy, M. An Analysis of Time-Dependent Planning // Proceedings of the Seventh AAAI National Conference on Artificial Intelligence. 1988. P. 49-54.
Более гранулярные исследования процесса работы ЭА, нежели чем только в точке оптимума, довольно редко появляется в теоретических работах, хотя давно и успешно применяются на практике20. В существующих теоретических исследованиях можно выделить следующие постановки, связанные с анализом динамики работы:
- FS-анализ (англ. Fixed-Start analysis) — анализ времени работы до достижения оптимума функции приспособленности, когда алгоритм начинает процесс работы с решений заданного качества.
- FB-анализ (англ. Fixed-Budget analysis) — анализ достижимого качества (приспособленности) решения при ограничении на время работы алгоритма. Данный тип анализа является анализом разновидности оптимизации в ограничениях по време-ни21 (англ. time-constrained optimization), адаптированной в контексте эволюционных вычислений. При обобщении времени работы на произвольное число итераций превращается в неограниченный FB-анализ22 (англ. Unlimited Budget analysis).
- FT-анализ (англ. Fixed-Target analysis) — анализ времени работы ЭА, когда впервые найдено решение заданной приспособленности.
FS-анализ является самым недавним из рассматриваемых вариантов изучения динамики работы ЭА. В обычном сценарии применения ЭА инициализация начальной популяции решений происходит случайным образом; FS-анализ же исследует время работы ЭА, если эта популяция будет содержать решения определенного качества. Данному анализу была посвящена целиком работа Антипова,
20Doerr, C. [et al.]. Benchmarking discrete optimization heuristics with IOHprofiler // Appl. Soft Comput. 2020. Vol. 88. P. 106027.
21 Tang, Z. Time constrained optimization // Proceedings of the 37th IEEE Conference on Decision and Control (Cat. No.98CH36171). Vol. 4. 1998. 3899-3906 vol.4.
22He, J., Jensen, T., Zarges, C. Unlimited budget analysis // Proceedings of Genetic and Evolutionary Computation Conference Companion. 2019. P. 427-428.
Буздалова и Доерра23, в которой в частности показано, что на задаче OneMax алгоритм (1 + (Л, Л)) GA от хорошей инициализации выигрывает сильнее, чем (1 + 1) EA. Однако, данный анализ фокусируется строго на оптимуме функции приспособленности, тем самым изучается динамика только заключительной работы ЭА без учета каким образом были достигнуты решения начальной популяции.
FB-анализ как термин и предмет исследования был представлен в работе Янсена и Заргес24. В работе25 даны оценки на качество решения для ряда простых алгоритмов, таких как RLS (Randomized Local Search) и (1 + 1) EA, на самых часто анализируемых функциях. При получении результатов анализа использовались подходы, применимость которых ограничена исследуемыми функциями и алгоритмами, и доказательства были довольно сложны технически. В другой работе этих же авторов26 были исследованы искусственные иммунные системы (англ. artificial immune systems) в разрезе FB-анализа. Оказалось, что при относительно небольших ограничениях на время работы алгоритма, иммунные системы работают лучше ряда ЭА, хотя с точки зрения времени оптимизации известно, что ЭА в среднем всегда лучше. Первый общий подход к получению результатов FB-анализа был представлен в работе Доерра27 через оценки на концентрацию
результатов FT-анализа; другой способ через оценки дрейфового ана-
23Antipov, D., Buzdalov, M., Doerr, B. First Steps Towards a Runtime Analysis When Starting With a Good Solution // Parallel Problem Solving from Nature - PPSN XVI. 2020. P. 560-573. (Lecture Notes in Computer Science ; 12270).
24Jansen, T., Zarges, C. Fixed Budget Computations: A Different Perspective on Run Time Analysis // Proceedings of Genetic and Evolutionary Computation Conference. 2012. P. 13251332.
25 Jansen, T., Zarges, C. Performance analysis of randomised search heuristics operating with a fixed budget // Theoretical Computer Science. 2014. Vol. 545. P. 39-58.
26 Jansen, T., Zarges, C. Reevaluating Immune-Inspired Hypermutations Using the Fixed Budget Perspective // IEEE Transactions on Evolutionary Computation. 2014. Vol. 18, no. 5. P. 674-688.
27Doerr, B. [et al.]. A method to derive fixed budget results from expected optimisation times // Genetic and Evolutionary Computation Conference, GECCO 2013. ACM, 2013. P. 1581-1588.
лиза был продемонстрирован в работе Ленглера28. Однако применение этих инструментов является не самой простой математической задачей.
FT-анализ является естественным расширением анализа времени оптимизации ЭА, и вероятно по этой причине во многих существующих работах явным образом этот термин не вводился, но одно из первых определений было дано, например, в уже упомянутой работе Доерра. В целом, известных результатов FT-анализа не так много, и в большинстве случаев изучались простые алгоритмы по типу (1 +1) EA на функциях LeadingOnes29 и OneMax30 с использованием специально адаптированных методов для доказательств.
Известно, что для эффективной работы ЭА необходимо соответствующим образом подбирать их параметры в зависимости от оптимизируемой задачи и ее размерности31. Таким параметрами может являться сила мутации, и в самом простом случае это просто вероятность изменить один бит особи. Теоретический анализ же может служить средством для поиска этих величин, например известно, что оптимальная вероятность мутации на задаче LeadingOnes составляет32 « 1.59/n, а для OneMax известно, что она стремится к 1/n. Опять же, эти силы мутаций вычислялись в постановке достижения оптимума задачи, и на данный момент неизвестно, насколько оптимальная сила мутации зависит, если вообще зависит, когда целью ЭА выбрано
решение заданного качества.
28Lengler, J., Spooner, N. Fixed budget performance of the (1 + 1) EA on linear functions // Foundations of Genetic Algorithms, FOGA 2015. ACM, 2015. P. 52-61.
29Doerr, B. Analyzing randomized search heuristics via stochastic domination // Theoretical Computer Science. 2019. Vol. 773. P. 115-137.
30 Carvalho Pinto, E., Doerr, C. Towards a more practice-aware runtime analysis of evolutionary algorithms. 2018. URL: https://arxiv.org/abs/1812.00493.
31Doerr, B., Doerr, C. Theory of Parameter Control for Discrete Black-Box Optimization: Provable Performance Gains Through Dynamic Parameter Choices // Theory of Evolutionary Computation: Recent Developments in Discrete Optimization. Springer, 2020. P. 271-321.
32Böttcher, S., Doerr, B., Neumann, F. Optimal fixed and adaptive mutation rates for the LeadingOnes problem//Parallel Problem Solving from Nature - PPSN XI. 2010. P. 1-10. (Lecture Notes in Computer Science ; 6238).
В теоретических исследованиях обычно фокусируются на довольно простых ЭА, например алгоритмах (1+1) или (р, Л), в основном для понимания внутреннего устройства протекающих стохастических процессов. В данной диссертации исследуемые с теоретической стороны алгоритмы могут быть описаны общей схемой (р + 1) EA:
Листинг 1 (р + 1) EA для оптимизации f: {0,1}n ^ R Require: распределение особей на инициализации D, распределение числа мутаций M for i е {1,... ,р} do
xi ^ случайная особь из D, посчитать f(xi) end for
X ^ {xi,..., хи} > Родительская популяция
while true do
j ^ случайное число из {1,... ,р} I ^ случайное число, выбранное из M y ^ изменить случайные I бит в Xj, посчитать f (y) X ^ р лучших особей из X и {у}, предпочитая y при одинаковой приспособленности
end while
В этой схеме явным образом выделены два распределения D и M. На практике производительность алгоритмов может зависеть от качества изначальной родительской популяции, с которой начинает работу ЭА. Два самых распространенных варианта такой инициализации - это генерация решений случайным образом либо создание фиксировано плохих решений, и этот выбор определяется распределением D. С точки зрения оператора мутации, на практике обычно не имеет смысла создавать особь, не отличающуюся от родительской. Такое поведение можно описать в распределении M, отвечающем в общем за число изменяемых бит. Таким образом, в работе встречаются следующие алгоритмы, представляемые псевдокодом листинга 1: - RLS: р = 1, M = 1. На каждой итерации изменен ровно один бит дочернего решения.
- (1 +1) ЕА: М = В(п,р), где В(п,р) - биномиальное распределение с вероятностью изменения (инверсии) одного бита особи р. Этот алгоритм является самым простым и широко исследованным в теоретическом анализе.
- (1 + 1) ЕА0^: М = тах{1,В(п,р)}: (1 + 1) ЕА, когда число бит для изменения всегда не меньше одного.
- (1 + 1) ЕА>0: М = [х ~ В(п,р) | х > 0]: (1 + 1) ЕА, в котором процесс выбора числа бит для мутации повторяется до тех пор, пока это число не будет больше нуля.
- (д + 1) ЕА: М = В(п,р).
В теоретическом анализе в основном исследуются довольно простые искусственные задачи, нежели чем сложные прикладные проблемы. Такие модельные задачи проще изучать, и при этом они могут указывать на какие-то особенности алгоритма или простым образом раскрывать качества оптимизируемых на практике функций. В данной диссертации рассматривается только область дискретной оптимизации, и все упомянутые в работе функции приспособленности являются псевдобулевыми функциями, определенными на множестве битовых строк длины п, представляющими следующие модельные задачи:
- Функция LEADINGONES возвращает число ведущих единичных бит в особи.
LEADINGONES(x) ^ ^" 1 ! 1 [X = 1]
- Функция ОпеМах возвращает число единичных бит в своем аргументе.
V—<П
ОПЕМАХ(х) ^ X = 1]
- Функция ВшУаь возвращает десятичное значение аргумента, представляющего двоичное число.
ВшУАЬ(Х) ^ ^ 2-1 • [XI = 1]
- В задаче MST (англ. Minimum Spanning Tree) возвращается вес минимального остовного дерева для заданного на входе графа с числом ребер m и их весами wi. Особью является битовая
• г—"
строка длины m, в которой i-ый бит определяет, включено ли i-ое ребро в решение. Функция приспособленности33 в свою очередь определяется через число компонент связности c в текущем решении:
f(x) ^ С • (m • Wmax + 1) + Wi • X = 1]
По всей работе предполагается, что ЭА старается максимизировать функцию приспособленности.
Во второй главе исследуются теоретические инструменты FT-анализа времени работы эволюционных алгоритмов. С помощью новых методов также доказывается ряд новых оценок FT-анализа простых ЭА на ряде модельных функций.
Для образования методики получения времени работы до достижения решений заданного качества, будут рассмотрены инструменты, применимые к большинству алгоритмов и не требующие специфич-
U и /—' и 1 и
ных предусловии - метод уровней приспособленности и дрейфовый анализ.
П w и
В первой части главы рассматривается группа методов уровней приспособленности как теоретического инструмента анализа времени работы ЭА. В этом методе все пространство значений функции приспособленности делится на уровни таким образом, что пространство поиска A разбивается на уровни Ai... Am, где каждому из них принадлежат решения конкретной приспособленности, а глобальный оптимум принадлежит уровню Am. Данный метод хорошо подходит для алгоритмов и задач, когда ЭА посещает все уровни приспособленности один за другим. Данный метод является простым для применения,
Похожие диссертационные работы по специальности «Другие cпециальности», 00.00.00 шифр ВАК
Исследование эволюционных методов решения задач комбинаторной оптимизации2013 год, кандидат наук Еремеев, Антон Валентинович
Обобщенный метод синтеза гиперэвристических эволюционных алгоритмов оптимизации сложных систем2021 год, доктор наук Сопов Евгений Александрович
Система автоматического выбора и оценки алгоритмов кластеризации и их параметров2019 год, кандидат наук Муравьёв Сергей Борисович
Синтез изображений лиц на основе генеративных методов машинного обучения с применением к распознаванию лиц2022 год, кандидат наук Зено Бассель
Модели, алгоритмы и методика проектирования защищенных от киберфизических атак систем физической безопасности на основе микроконтроллеров2021 год, кандидат наук Левшун Дмитрий Сергеевич
Список литературы диссертационного исследования кандидат наук Винокуров Дмитрий Владимирович, 2022 год
Литература
1. Lengler J. Drift analysis // Theory of Evolutionary Computation: Recent Developments in Discrete Optimization. Springer, 2020. P. 89-131. doi: 10.1007/978-3-030-29414-4_2
2. Doerr B. A tight runtime analysis for the cGA on jump functions: EDAs can cross fitness valleys at no extra cost // Proc. Genetic and Evolutionary Computation Conference (GECCO). 2019. P. 14881496. doi: 10.1145/3321707.3321747
3. Hansen N., Auger A., Ros R., Mersmann O., Tusar T., Brockhoff D. COCO: A platform for comparing continuous optimizers in a blackbox setting // Optimization Methods and Software. 2020. in press. doi: 10.1080/10556788.2020.1808977
4. Doerr C., Wang H., Ye F., van Rijn S., Bäck T. IOHprofiler: A benchmarking and profiling tool for iterative optimization heuristics [Электронный ресурс]. URL: https://arxiv.org/abs/1810.05281 (дата обращения: 27.06.2020).
5. Jansen T., Zarges C. Performance analysis of randomised search heuristics operating with a fixed budget // Theoretical Computer Science. 2014. V. 545. P. 39-58. doi: 10.1016/j.tcs.2013.06.007
6. Doerr B., Jansen T., Witt C., Zarges C. A method to derive fixed budget results from expected optimisation times // Proc. 15th Genetic and Evolutionary Computation Conference (GECCO 2013). 2013. P. 1581-1588. doi: 10.1145/2463372.2463565
7. Lengler J., Spooner N. Fixed budget performance of the (1+1) EA on linear functions // Proc. 13th Foundations of Genetic Algorithms (FOGA). 2015. P. 52-61. doi: 10.1145/2725494.2725506
8. Witt C. Runtime analysis of the (ц+1) EA on simple pseudo-Boolean functions // Evolutionary Computation. 2006. V. 14. N 1. P. 65-86. doi: 10.1162/106365606776022751
9. Pinto E.C., Doerr C. Towards a more practice-aware runtime analysis of evolutionary algorithms [Электронный ресурс]. URL: https:// arxiv.org/abs/1812.00493 (дата обращения: 27.06.2020).
10. Vinokurov D., Buzdalov M., Buzdalova A., Doerr B., Doerr C. Fixed-target runtime analysis of the (1+1) EA with resampling // Proc. Genetic and Evolutionary Computation Conference Companion (GECCO'19). 2019. P. 2068-2071. doi: 10.1145/3319619.3326906
11. Doerr B. Analyzing randomized search heuristics via stochastic domination // Theoretical Computer Science. 2019. V. 773. P. 115— 137. doi: 10.1016/j.tcs.2018.09.024
12. Böttcher S., Doerr B., Neumann F. Optimal fixed and adaptive mutation rates for the LeadingOnes problem // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2010. V. 6238. P. 1-10. doi: 10.1007/978-3-642-15844-5_1
13. Badkobeh G., Lehre P.K., Sudholt D. Unbiased black-box complexity of parallel search // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2014. V. 8672. P. 892-901. doi: 10.1007/978-3-319-10762-2_88
14. Doerr B., Doerr C, Ebel F. From black-box complexity to designing new genetic algorithms // Theoretical Computer Science. 2015. V. 567. P. 87-104. doi: 10.1016/j.tcs.2014.11.028
15. Wegener I. Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions // International Series in Operations Research & Management Science. 2003. V. 48. P. 349-369. doi: 10.1007/0-306-48041-7_14
16. Sudholt D. A new method for lower bounds on the running time of evolutionary algorithms // IEEE Transactions on Evolutionary Computation. 2013. V. 17. N 3. P. 418-435. doi: 10.1109/TEVC.2012.2202241
17. Doerr B., Doerr C. The impact of random initialization on the runtime of randomized search heuristics // Algorithmica. 2016. V. 75. N 3. P. 529-553. doi: 10.1007/s00453-015-0019-5
References
1. Lengler J. Drift analysis. Theory of Evolutionary Computation: Recent Developments in Discrete Optimization. Springer, 2020, pp. 89-131. doi: 10.1007/978-3-030-29414-4_2
2. Doerr B. A tight runtime analysis for the cGA on jump functions: EDAs can cross fitness valleys at no extra cost. Proc. Genetic and Evolutionary Computation Conference (GECCO), 2019, pp. 14881496. doi: 10.1145/3321707.3321747
3. Hansen N., Auger A., Ros R., Mersmann O., Tusar T., Brockhoff D. COCO: A platform for comparing continuous optimizers in a blackbox setting. Optimization Methods and Software, 2020, in press. doi: 10.1080/10556788.2020.1808977
4. Doerr C., Wang H., Ye F., van Rijn S., Bäck T. IOHprofiler: A benchmarking and profiling tool for iterative optimization heuristics. Available at: https://arxiv.org/abs/1810.05281 (accessed: 27.06.2020).
5. Jansen T., Zarges C. Performance analysis of randomised search heuristics operating with a fixed budget. Theoretical Computer Science, 2014, vol. 545, pp. 39-58. doi: 10.1016/j.tcs.2013.06.007
6. Doerr B., Jansen T., Witt C., Zarges C. A method to derive fixed budget results from expected optimisation times. Proc. 15th Genetic and Evolutionary Computation Conference (GECCO 2013), 2013, pp. 1581-1588. doi: 10.1145/2463372.2463565
7. Lengler J., Spooner N. Fixed budget performance of the (1+1) EA on linear functions. Proc. 13th Foundations of Genetic Algorithms (FOGA), 2015, pp. 52-61. doi: 10.1145/2725494.2725506
8. Witt C. Runtime analysis of the (^+1) EA on simple pseudo-Boolean functions. Evolutionary Computation, 2006, vol. 14, no. 1, pp. 65-86. doi: 10.1162/106365606776022751
9. Pinto E.C., Doerr C. Towards a more practice-aware runtime analysis of evolutionary algorithms. Available at: https://arxiv.org/ abs/1812.00493 (accessed: 27.06.2020).
10. Vinokurov D., Buzdalov M., Buzdalova A., Doerr B., Doerr C. Fixed-target runtime analysis of the (1+1) EA with resampling. Proc. Genetic and Evolutionary Computation Conference Companion (GECCO'19), 2019, pp. 2068-2071. doi: 10.1145/3319619.3326906
11. Doerr B. Analyzing randomized search heuristics via stochastic domination. Theoretical Computer Science, 2019, vol. 773, pp. 115— 137. doi: 10.1016/j.tcs.2018.09.024
12. Böttcher S., Doerr B., Neumann F. Optimal fixed and adaptive mutation rates for the LeadingOnes problem. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2010, vol. 6238, pp. 1-10. doi: 10.1007/978-3-642-15844-5_1
13. Badkobeh G., Lehre P.K., Sudholt D. Unbiased black-box complexity of parallel search. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2014, vol. 8672, pp. 892-901. doi: 10.1007/978-3-319-10762-2_88
14. Doerr B., Doerr C, Ebel F. From black-box complexity to designing new genetic algorithms. Theoretical Computer Science, 2015, vol. 567, pp. 87-104. doi: 10.1016/j.tcs.2014.11.028
15. Wegener I. Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions. International Series in Operations Research & Management Science, 2003, vol. 48, pp. 349-369. doi: 10.1007/0-306-48041-7_14
16. Sudholt D. A new method for lower bounds on the running time of evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 2013, vol. 17, no. 3, pp. 418-435. doi: 10.1109/TEVC.2012.2202241
17. Doerr B., Doerr C. The impact of random initialization on the runtime of randomized search heuristics. Algorithmica, 2016, vol. 75, no. 3, pp. 529-553. doi: 10.1007/s00453-015-0019-5
18. Spivey M.Z. Combinatorial sums and finite differences // Discrete Mathematics. 2007. V. 307. N 24. P. 3130-3146. doi: 10.1016/j.disc.2007.03.052
Авторы
Буздалов Максим Викторович — кандидат технических наук, научный сотрудник, Университет ИТМО, Санкт-Петербург, 197101, Российская Федерация, Scopus ID: 48160963700, ORCID ID: 0000-0002-7120-8824, mbuzdalov@gmail.com
Винокуров Дмитрий Владимирович — аспирант, Университет ИТМО, Санкт-Петербург, 197101, Российская Федерация, Scopus ID: 57215125737, ORCID ID: 0000-0001-9074-3884, dimaoq@gmail.com
18. Spivey M.Z. Combinatorial sums and finite differences. Discrete Mathematics, 2007, vol. 307, no. 24, pp. 3130-3146. doi: 10.1016/j.disc.2007.03.052
Authors
Maxim V. Buzdalov — PhD, Scientific Researcher, ITMO University, Saint Petersburg, 197101, Russian Federation, Scopus ID: 48160963700, ORCID ID: 0000-0002-7120-8824, mbuzdalov@gmail.com
Dmitry V. Vinokurov — Postgraduate, ITMO University, Saint Petersburg, 197101, Russian Federation, Scopus ID: 57215125737, ORCID ID: 0000-0001-9074-3884, dimaoq@gmail.com
Fixed-Target Runtime Analysis
Maxim Buzdalov
ITMO University Saint Petersburg, Russia
Carola Doerr
Sorbonne Université, CNRS, LIP6 Paris, France
ABSTRACT
Runtime analysis aims at contributing to our understanding of evolutionary algorithms through mathematical analyses of their runtimes. In the context of discrete optimization problems, runtime analysis classically studies the time needed to find an optimal solution. However, both from a practical and a theoretical viewpoint, more fine-grained performance measures are needed. Two complementary approaches have been suggested: fixed-budget analysis and fixed-target analysis.
In this work, we conduct an in-depth study on the advantages and limitations of fixed-target analyses. We show that, different from fixed-budget analyses, many classical methods from the runtime analysis of discrete evolutionary algorithms yield fixed-target results without greater effort. We use this to conduct a number of new fixed-target analyses. However, we also point out examples where an extension of the existing runtime result to a fixed-target
result is highly non-trivial. CCS CONCEPTS
• Theory of computation ^ Theory of randomized search heuristics.
KEYWORDS
Runtime analysis, fixed-target analysis, fixed-budget analysis.
ACM Reference Format:
Maxim Buzdalov, Benjamin Doerr, Carola Doerr, and Dmitry Vinokurov. 2020. Fixed-Target Runtime Analysis. In Genetic and Evolutionary Computation Conference (GECCO '20), July 8-12, 2020, Cancûn, Mexico. ACM, New York, NY, USA, 9 pages. https://doi.org/10.1145/3377930.3390184
1 INTRODUCTION
The classic performance measure in the theory of evolutionary computation [15, 21] is the optimization time, that is, the number of fitness evaluations that an algorithm uses to find an optimal solution for a given optimization problem. Often only expected
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. GECCO '20, July 8-12, 2020, Cancûn, Mexico
© 2020 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-1-4503-7128-5/20/07... $15.00 https://doi.org/10.1145/3377930.3390184
Benjamin Doerr
Laboratoire d'Informatique (LIX), CNRS, École
Polytechnique, Institut Polytechnique de Paris Palaiseau, France
Dmitry Vinokurov
ITMO University Saint Petersburg, Russia
optimization times are analyzed and reported, either for reasons of simplicity or because some analysis methods like drift analysis [28] only yield such bounds.
Some works give more detailed information, e.g., the expectation together with a tail estimate [12, 25, 39]. In some situations, only runtime bounds that hold with some or with high probability are given, either because they are easier to prove or more meaningful (see, e.g., the discussion in [5] on such statements for estimation-of-distribution algorithms), or because the expectation is unknown [16] or infinite. Stochastic domination [4] is another way to give more detailed information on runtimes of algorithms.
Nevertheless, all these approaches reduce the whole optimization process to a single point in time: the moment in which an optimal solution is found. For various reasons, more detailed information on the whole process is also desirable, including the following:
(1) Evolutionary algorithms, different from most classic algorithms, are so-called anytime algorithms: they can be interrupted at essentially any point of time while still providing a valid solution (possibly of a low quality). The optimization time as the only performance measure gives no information on how good an algorithm is as an anytime algorithm. Such information, however, is of great interest in practice. It can be used, for instance, ifone does not know in advance how much time can be allocated to the execution of an algorithm, or when it is important to report whenever a certain milestone (e.g., quality threshold) has been reached.
(2) When several iterative optimization heuristics are available to solve a problem, one can try to start the optimization with one heuristic and then, at a suitable time, switch to another one which then is more powerful. To decide which heuristic to use up to a certain point of time or solution quality, more detailed information than the optimization time is needed.
We note that the importance of reporting runtime profiles instead of only optimization times has for a long time been recognized in algorithm benchmarking [17, 18]. These fine-grained performance analyses have helped to advance our understanding of evolutionary computation methods, and have contributed significantly to the algorithm development. It is therefore surprising that such finegrained notions play only a marginal role in runtime analysis. So far, the following two notions have been used.
• Fixed-budget analyses: For a fixed number ("budget") of fitness evaluations, one studies the (usually expected) quality of the best solution found within this budget.
• Fixed-target analyses: For a fixed quality threshold, one studies the (usually expected) time used to find a solution of at least this quality.
The main goal of this work is a systematic study of fixed-target runtime analysis. We provide, in particular, a comparison of different more fine-grained performance measures (Section 2), a survey of the existing results (Section 4), an analysis how the existing methods for runtime analysis can be used to also give fixed-target results (Sections 5 and 6) together with several applications of these methods, some to reprove existing results, others to prove new fixed-target results. The main insight here is that fixed-target results often come almost for free when there is a result on the optimization time, so it is a waste to not use this opportunity. However, in Section 7 we also point out situations in which the runtime is well understood, but proving fixed-target results is very difficult.
2 FINE-GRAINED RUNTIME ANALYSIS: FIXED-BUDGET AND FIXED-TARGET ANALYSES
The notion to first become the object of explicit scientific attention is fixed-budget analysis [23]. Fixed-budget analysis asks for, given a computational budget b e N, what is the expected fitness of the best solution seen within b fitness evaluations. In the first paper devoted to this topic (extending results presented at GECCO 2012), Jansen and Zarges [23] investigated the fixed-budget behavior of two simple algorithms, randomized local search (RLS) and the (1 + 1) evolutionary algorithm ((1 + 1) EA), on a range of frequently analyzed example problems. For these two elitist algorithms, fixed budget analysis amounts to computing or estimating f (xj), where f is the objective function and xj is the b-th search point generated by the algorithm. Jansen and Zarges considered small budgets, that is, budgets b below the expected optimization time, and argued that instead of larger budgets, one should rather regard the probability to find the optimum within the budget.
Jansen and Zarges [23] obtained rather simple expressions for the fixed-budget fitness obtained by RLS, but those for the (1 + 1) EA were quite complicated. In [24], they evaluated artificial immune systems (AIS). In terms of optimization time, AIS are typically worse than evolutionary algorithms, but in the fixed-budget perspective with relatively small budgets they were proven to outperform evolutionary algorithms. This shows again that fine-grained runtime results can lead to insights not available from optimization times.
These first results were achieved using proof techniques highly tailored to the considered algorithms and problems. Given the innocent-looking definition of fixed-budget fitness, the proofs were quite technical even for simple settings like RLS optimizing Leading-Ones. For the (1 + 1) EA, which can gain more than one fitness level in one iteration, the analyses were even more complicated and many analyses could not cover the whole range of budgets (e.g., for LeadingOnes, only budgets below 0.5n2 were covered, while the well-concentrated optimization time is around 0.86n2, see [2]).
In [13], a first general approach to proving fixed-budget results was presented. Interestingly, it works by estimating fixed-target runtimes and then using strong concentration results to translate them into a fixed-budget result. This might be the first work that explicitly defines the fixed-target runtime, without however using this name. The paper [29] also uses fixed-target runtimes (called approximation times, see [29, Corollary 3]) for a fixed-budget analysis, but most of the results in [29] are achieved using drift arguments.
The first fixed budget analysis for a combinatorial optimization problem was conducted in [30]. Subsequently, several papers more concerned with classical optimization time also formulated their results in the fixed-budget perspective, among them [8-10].
A similar notion of fine-grained runtime analysis, called the unlimited budget analysis [19], was recently proposed. It can be seen as either a complement to the fixed-budget analysis (as it measures how close an algorithm gets to the optimum of the problem in a rather large number of steps) or as an extension of fixed-budget analysis which goes beyond using small budgets only.
For the second main fine-grained runtime notion, fixed-target analysis, due to it being a direct extension of the optimization time, it is harder to attribute a birthplace. As we argue also in Section 5, the fitness level method is intimately related to the fixed-target view. As such, many classic papers can be seen as fixed-target works, and this even more when the fitness level method is not used as a black box, but one explicitly splits a runtime analysis into the time to reach a particular fitness and the another time to find the optimum, as done, e.g., in [37]. The first, to the best of our knowledge, explicit definition of the fixed-target runtime in a runtime analysis paper can be found in the above-mentioned fixed-budget work [13, Section 3]. There, for a given algorithm A, a given objective function f (to be maximized), and a given a e R, the fixed-target runtime T^,f (a) was defined as the number of the first fitness evaluation which gives a fitness of a or larger. Since this notion was merely used as tool in a proof, the name fixed-target runtime was not used yet. Apparently unaware of the fact that the fixed-target notion was used already in [13, 29], [32] re-invented it under the name runtime profiles and it was advocated to use this notion as it gives more information to practitioners. The name fixed-target analysis was, in the context of runtime analysis, first used in the GECCO 2019 student workshop paper [35], the only other work putting fixed-target analysis into its center.
In summary, we see that there are generally not too many runtime results that give additional information on how the process progresses over time. Since fixed-budget analysis, as a topic on its own, was introduced earlier into the runtime analysis community, there are more results on fixed-budget analysis. At the same time, by looking over all fixed-budget and fixed-target results, it appears that the fixed-budget results tend to be harder to obtain.
From the viewpoint of designing dynamic algorithms, that is, algorithms that change parameter values or sub-heuristics during the runtime, it appears to us that fixed-budget results are more useful for time-dependent dynamic choices, whereas fixed-target result aid the design of fitness-dependent schemes. If algorithm A with a budget of b computes better solutions than algorithm B with the same budget, then in a time-dependent scheme one would rather run algorithm A for the first b iterations than B. However, if the runtime to the fitness target x of algorithm A is lower than that of B, then a fitness-dependent scheme would use rather A than B to reach a fitness of at least x.
Since we do not see that the increased difficulty of obtaining fixed-budget results is compensated by being significantly more informative or easier to interpret and since we currently see more fitness-dependent algorithm designs (e.g., [1, 2, 7, 9] than time-dependent ones (where, in fact, we are only aware of a very rough proof-of-concept evolutionary algorithm in the early work [22]),
Algorithm 1 The (ji + A) EA to maximize f : {0, 1}n m R
Require: mutation distribution M, initialization distribution D for i e [i] do
x; ^ sample from D, query f (x;) end for
X ^ {xi,.. .,x^} while true do
for i e [A] do
j ^ sample uniformly from [X], I ^ sample from M y; ^ flip I bits in Xj, query f (y;) end for
Y ^ {yl,..., yi}
X ^ i best solutions from X U Y breaking ties randomly, preferring offspring in the case of ties end while
we advocate in this work to rather focus on fixed-target results. We support this view by elaborating how the existing analyses methods for the optimization time, in particular, the fitness-level methods and drift, can easily be adapted to also give fixed-target results.
3 PRELIMINARIES
We use the notation [a..b] to denote a set of integers {a, a+1,.. ., b -1, b}, and we denote the set [1..n] as [n]. We write Hn for the n-th harmonic number, that is, Hn = 2n=1 1, assuming Ho = 0.
We consider simple algorithms, such as the (1 + 1) EA, the (ji + 1) EA and the (1 + A) EA, which solve optimization problems on bit strings of length n. Due to the increased interest in mutation operators that do not produce offspring identical to the parent [32], we consider them in a generalized form, which samples the number of bits to flip from some distribution M. We also use a distribution over search points D during initialization. A default choice for D is to sample every bit string with equal probability, however, we consider also initialization with the worst individual. These algorithms are presented in the most general form in Algorithm 1 as a (i + A) EA parameterized by M and D.
We consider the following distributions of M for the (1 + 1) EA:
• randomized local search, or RLS: M = 1;
• the (1 + 1) EA with standard bit mutation: M = B(n, p), where B(n, p) is the binomial distribution;
• the (1 + 1) EAom using the shift mutation strategy: M = max{1, B(n, p)};
• the (1 + 1) EA>o using the resampling mutation strategy: M = [x ~ B(n,p) | x > 0].
Sometimes we are only interested in the probability q of flipping exactly one given bit. For a problem size n and mutation strength p, the values of q for the algorithms above are
• RLS: q = 1;
• (1 + 1) EA: q = p(1 - p)n-1;
• (1 + 1) EAom1 q = p(1 - p)n-1 + ;
• (1 + 1) EA>o: q = .
We consider the following classical problems on bit strings:
Zn
[xi = 1]
LeadingOnes(x) M ^ J-1 ^[xj = 1]
BINVAL(x) M -1[x; = 1].
We also consider the minimum spanning tree (MST) problem. The problem is, given a connected undirected graph G with positive weights on each edge, to find a minimum spanning tree of it, that is, a subgraph that contains all vertices of G and has the minimum possible weight. This problem was adapted to bit strings as in [31] as follows: each bit corresponds to one edge of G, and the bit value of 1 means that the edge is included in the subgraph.
4 OVERVIEW OF KNOWN FIXED-TARGET RESULTS
In this section, we list the known fixed-target results. In the whole section, n is the problem size and k is the target fitness.
4.1 LeadingOnes
The paper [37] studied the upper and lower bounds on the running time of the (ji + 1) EA on several benchmark problems. For LeadingOnes, the runtime was proven in [37, Theorem 1] using a technique similar to fitness levels. Then, [37, Corollary 1] bounded the expectation of the time needed to reach a state of at least k leading ones from above by i + 3ek • max {i ln(en), n}.
In [2] exact expected running times for the (1 + 1) EAon Leading-Ones were proven, which was an important cornerstone in the studies of LeadingOnes. The expected time to leave a state with the fitness of i is E(Aj) = 1/((1 - p);p) with mutation probability p. The next fitness value may be greater than i+1, but for LeadingOnes the bits following the i-th bit equal 1 with probability 1/2. This yields the expected optimization time to be ((1 - p)1-n - (1 - p))/(2p2).
Doerr et al. reused this result in [13, Section 4] to prove that the expected time to hit a target k is ((1 -p)1-k - (1 -p))/(2p2) for any p and k. They used p = 1/n, but their proof does not depend on p.
Pinto and Doerr [32, Theorem 11] extended this result to the similar algorithms: (1 + 1) EA>o, (1 + 1) EAom1, and RLS. Note that Theorem 11 claims only the upper bound, however, it is clear from the above that this bound is exact. As the results of our techniques are identical, we direct the reader to our Theorem 5.6.
Finally, in [4, Corollary 4] an even stronger result is proven about the exact distribution of the time the (1 +1) EA needs to hit a certain target. The result is expressed in terms of random variables X; for initial bit values and the probabilities q; to generate a point with a strictly better fitness from a point with fitness i, and reads as ^Ji- X; • Geom(q;), where Geom is the geometric distribution.
4.2 OneMax
As the upper and lower bounds for OneMax are generally less precise than for LeadingOnes, we augment the theoretical results with the actual runtime profiles of the (1 + 1) EA in Figure 1.
In [29, Corollary 3], a lower bound for the (1 +1) EA on OneMax was proven using fitness levels for lower bounds [34]. This result says that for the (1 + 1) EA with mutation probability p = 1/n
optimizing OneMax the expected time until hitting a target k is at
least en ln(n/(n - k)) - 2n lnln n - 16n. This bound is used in [29] to prove fixed-target results. From the fixed-target perspective, this
ns 10
O
at 10
s
al
v
w
10
—•— Upper [32] (1 + 1) EA zero —•— Upper [35] (1 + 1) EArand —♦— Lower [29]
0 0.2 0.4 0.6 0.8 1
Relative fitness, n = 103
0.2 0.4 0.6 Relative fitness, n
10
0.2 0.4 0.6 Relative fitness, n
10
103
101
10 104 102 100
0.998 0.999
0.998 0.999
10
Figure 1: The runtime profile of the (1 + 1) EA on OneMax and the applicable bounds; "zero" stands for starting at the all-zero point and "rand" for starting at a random point
results in a satisfactory lower bound only for a small fraction of possible conditions, see Figure 1 for visual comparison.
In [32, Theorem 10], the fixed-target upper bound was given for various flavors of (1 + 1) EA which start from the worst possible solution consisting of only zeros. Assuming q to be the probability that one given bit, and only it, is flipped, the upper bound is 1 (Hn -Hn-k). This bound is exact for RLS and also captures the behavior of other (1 + 1) EA flavors quite well (see Figure 1).
For random initialization, [35, Theorem 3.1] proves a similar upper bound of 1 (Hn/2 - Hn-k)(1 - o(1)) for k > n/2 + Vn ln n, using the same technique and an additional argument to justify the use of Hn/2. Technically, it was proven only for the (1 + 1) EA>o, but the proof holds also for arbitrary q. This bound also gives a moderately good approximation, see again Figure 1.
In [38, Theorem 6.5], lower bounds for the running times of the (1 + 1) EA on OneMax are proven for mutation probabilities p = O(n-2/3-£). For this, an interval S = [npln2 n; 1/(2p2n ln n)] of distances to the optimum is considered, where p = max{1/n,p}. Multiplicative drift for lower bounds is applied to this interval to yield the lower bound of (1 - o(1))(1 - p)-n(1 /p) min{ln n, ln(1 /(p3n2))}.
This result was used in [35] to obtain the fixed-target lower bounds for the (1 + 1) EA>o on OneMax. These bounds are piece-wise because the interval S in [38, Theorem 6.5] does not cover the entire range of k: for small k it is zero, for large k it does not depend on k, and only for k e S it can be used to bound the algorithm dynamics. As omitting o(1) from 1 - o(1) gives overly optimistic results in this case, we do not provide the plots for these bounds.
4.3 BinVal
The fixed-target bounds for BinVai were proven in [35] for the (1 + 1) EA>o. The methods for proving optimization times for linear functions, such as the ones in [38], were found to be insufficient, so a problem-dependent observation was used. To achieve a target value k such that 2n - 2l < k < 2n - 2t+1, one requires to optimize the t heaviest bits, and it is enough to optimize the t +1 heaviest bits. As a result, reaching the target k is equivalent to solving BinVal of size t + O(1) to optimality using a n/t times smaller mutation rate. The quite complicated bounds from [38] were adapted to the case of BinVal in [35, Theorem 4.1].
5 FITNESS LEVELS
In this section we consider the fitness level theorems in the fixed-target context. Our observation is that the most important theorems of this sort are already suitable to produce fixed-target results.
5.1 Method
In the fitness level method (also known as artificial fitness levels and the method of f -based partitions [36]), the state of the algorithm is typically described by the best fitness of an individual in the population. It is transformed into a fitness level, which may aggregate one or more consecutive fitness values. For the fitness function f (to be maximized) and two search space subsets A and B one writes A <f B if f (a) < f (b) for all a e A and b e B. A partition Ai ... Am of the search space, such that A; <f Ai+1 for all 1 < i < m and Am contains only the optima of the problem, is called an f -based partition. If the best individual in a population of an algorithm A has a fitness f e A;, then it is said to be in A;.
Fitness level theorems work best for the algorithms that typically visit the fitness levels one by one in the increasing order. We now give several most popular fitness level theorems.
ThEorEm 5.1 (FitNESs levels for uppEr bouNDs; LEmmA 1 from [36]). Let {A;}1<;<m be the f-basedpartition, and letp; be the probability that the elitist algorithm A samples a search point belonging to A;+1 U ... U Am provided it is in A;. Then the expected hitting time of Am is at most
Zm-1 v"im-1 1 T-im-1 1
m=1 p [A startsin A; = - =1 - . (1)
THEorEm 5.2 (FitNESs levels for lowEr bounds; THEorEm 3 from [34]). Let {A; }1<; <m be a partition of the search space. Let the probability for the elitist algorithm A to transfer in one step from A; to Aj, i < j, to be at most u; • Yi,j, and Ij-i+l Yi,j = 1. Assume
there is some x, 0 < x < 1, such that Yi,j > X^m- • Yi k for all
' k =j '
1 < i < j < m. Then the expected hitting time of Am is at least
Zm-1 r _ t 1 v^m-l 1
P[A startsin+ m -) . (2)
We also use an upper-bound theorem similar to Theorem 5.2.
ThEorEm 5.3 (REfiNED fiTNESS levels for uppEr bounds; ThEorEm 4 from [34]). Let {Ai }1 <i <m be a partition of the search space. Let the probability for the elitist algorithm A to transfer in one step from Ai to Aj, i < j, to be at least si • Yi,j, and Y^Li+1 Yi,j = 1. Assume there is some x, 0 < x < 1, such that Yi,j < X^™-/ Yi,k
4
2
0
1
for all 1 < i < j < m. Further, assume that (1 - x)si < si+1 for all 1 < i < m - 2. Then the expected hitting time of Am is at most
im-1 1
Zm-1 _ n I 1 1 \
m=i P[A startsin Air ^ + xZ;=-+i -).
(3)
Theorems 5.1-5.3 are applicable only to elitist algorithms. However, a fitness level theorem was proposed in [3] that can be applied to non-elitist algorithms as well. We are sure that our observations can also be extended to that theorem.
ObSErvAtioN 1. If one of Theorems 5.1-5.3 is proven for a certain algorithm on a certain problem, it also holds if a new target fitness level m' is chosen, such that 1 < m' < m, and all fitness levels
Proof. This is essentially the same argument as in [29].
This modification does not alter the estimations of probabilities to leave fitness levels preceding m': pi, u; and si for resp. Theorems 5.1, 5.2 and 5.3. The only affected locations are the constraints on yi,j. Their affected occurrences on the right-hand sides effectively merge by summing up, e.g. y'm, ^ 2J" ' Yi,k. Note that only those right-hand sides, which contain the complete sums from m' to m, survive after the transformation, and not just their parts. For the left-hand sides, only those Yi,j survive where j = m', as all others are either unchanged or cease to exist. However, these oc-curences are trivial, since they are limited only by identity inequalities Yi,m' < XYi, m' in Theorem 5.2 and are not limited by anything in Theorem 5.3 as their limits are conditioned on j < m'. □
It follows from Observation 1 that it is very easy to obtain fixed-target results from the existing optimization time results whose proofs use the above-mentioned fitness level theorems.
Note that, technically, Theorems 5.2, 5.3 and the theorem from [3] do not require the employed partition of the search space to be an f-based partition. As such, they can be freely used in the fixed-target context. However, Observation 1 is more than that, as it says that, if the bounds on the probabilities are known for the optimum-hitting process, they remain the same for a different target.
5.2 Applications
5.2.1 Hill Climbers on LeadingOnes. We re-prove here the statements about the fixed-target performance of the algorithms from the (1 + 1) EA family, which were proven in [13, Section 4] and stated, but not formally proven, in [32, Theorem 11]. For this we use Theorems 5.2 and 5.3, similarly to their use in [34] to prove the results from [2] with fitness levels alone.
LEmmA 5.4. In the context of Theorems 5.2 and 5.3 for Leading-Ones, assuming the target fitness is k, the values Yi, j = 2i-j when j < k, Yi,k = 2i-k+1, and x = 1/2 satisfy their requirements.
PRoof. Follows the proof of [34, Theorem 5]. □
LEmmA 5.5. Assume that qi is the probability for the algorithm A to flip one given bit and not to flip another i given bits. The expected time for A to reach a target of at least k on LeadingOnes of size n is:
k-1 / 1 1 k-1 1 \ 1 k-1 1
ZP [A starts with fitness i] •--> — =-> —. (4)
qi 2 ' q,- 2 ' q,-
2 , q/
J=i+1 /
Proof. The left-hand side of the lemma statement follows from
Lemma 5.4, Theorems 5.2 and 5.3, and Observation 1. The right-
hand side follows by recalling that in LeAdingOnes, it holds for all considered algorithms that P[A starts with fitness i] = 2-i-1, and by reordering the sums as in [2].
We can also derive this result from [4, Corollary 4]. □
ThEorEm 5.6. The expected fixed-target time to reach a target of at least k when optimizing LeadingOnes of size n is exactly
kr for RLS; (1-p)1-k-(1-p ) 2p2
(1-p)1-k-(1-p ) 2p2
1 yfc-1 _
2 • ^i =0 p(1_p)i + i(1-p)
for the (1 + 1) EA; (1 -(1 - p)n) for the (1 + 1) EA>0; —1-for the (1 + 1) EA0^1.
Proof. We use Lemma 5.5 and note that, for a fitness of i:
• for RLS, qi = 1/n;
• for the (1 + 1) EA, qi = (1 - p)1 • p;
• for the (1 + 1) EA>o, qi = (1 - p)1 • p • (1 - (1 - p)n);
• for the (1 + 1) EAom1, qi = (1 - p)1 • p + 1 (1 - p)n.
The simplification of the sum for the (1 +1) EA and the (1 +1) EA>o is done as in [2]. □
5.2.2 Hill Climbers on OneMax, Upper Bounds. We now re-prove the existing results for the (1 + 1) EA variants on OneMax. Our results for the case of random initialization of an algorithm are sharper than in [35], because we use the following argument about the weighed sums of harmonic numbers.
Lemma 5.7. The following equality holds:
n (n ) H- n 1
Z ^ = Hn -Z k2k = Hn -ln2 +O(2-n) = Hn/2 -
k=1
1 - o(1) 2n .
Proof. Proven in [6, Sec. 2.5] with [33, Identity 14]. □
Our results are formalized as follows.
ThEorEm 5.8. The expected fixed-target time for a (1 + 1) EA that flips a single bit with probability q to reach a target of at least k on OneMax of size n, assuming k > n/2 + ^¡n ln n, is at most:
• 1 (Hn - Hn-k) when initializing with the worst solution;
• 1 (Hn/2 - Hn-k - 1 2on(1)) when initializing randomly.
Proof. Let si be the probability for the algorithm to be initialized at fitness i. Assuming pessimistically that the fitness does not improve when two and more bits are flipped, we apply Theorem 5.1 to get the following upper bound:
k-1 k-1 1 1 k-1 Zsi • Z q?n-=7) =1Z^(Hn-i
"Hn-k )<
Hn - Hn-k
q '
The pessimistic bound above proves the theorem for the algorithms initialized with the worst solution. For the random initialization, we note that the initial search point has a fitness i with the probability of (n)/2n.
From the equality above we derive:
2 '—' q:
i=0
Am', Am'+1
Am are merged.
y-1 (IKHn 2-ii=0
and the total time the (ji + 1) EA spends in creating replicas is
«Z n = yn=
q2n
n (i)(Hn-i - Hn-k)
q2n
Zn i=
(n)(Hn_k - H„-i)
k-1
T- « ^ TT_
L=0
ü en
ln -
, , , , , k ln en +
(1 _ p)n n - L (1 - p)n ^ x
x x=n-k+1
T. ini
q2n
<
n)Hn-i Ci )Hn-fc 1
"¿Ji - ~ +
q2
q2"
yin
(")(H"-k - Hn-i)
=k
2n
1 W 1 - o(1) \ 1 Vn (n)(Hn-k - Hn-i)
= q (Hn/2 - Hn-k - I + qL i=k-
q
q
2n
where the last transformation uses Lemma 5.7. The second addend is o(1/qn), because Hn-k - Hn-i = O(lnn) when i > k, which is further multiplied by an exponentially small value, since for k > n/2 + Vn lnn it holds that Zn=k (n) = n-n(ln n) by the Chernoff bound. As a result, the fixed-target upper bound for the random initialization is 1 (Hn/2 - Hn-k - 1 2<n(1)). □
5.2.3 Hill Climbers on OneMax, Lower Bounds. We also apply fitness-levels to the lower bounds to improve the result from [29].
ThEorEm 5.9 (LowEr fixED-tArGEt bounds on (1 + 1) EA for OneMax). For the mutation probability p < 1/(Vn log n), and assuming I = |"n - min {n/log n, 1/(p2nlog n)}l, the expected time to find a solution with fitness at least k > I is at least
1
18/5
Hn-l - Hn-k (1 - p)2 log nj p(1 - p)n-1 .
Proof. We use the proof of [34, Theorem 9] with Observation 1. The particular formula is taken from [34, journal page 428, bottom of left column], so that we do not lose precision when k is close to n, and also to match the shape of Theorem 5.8. □
We conjecture that a similar result can be derived for the generalized (1 + 1 ) EAs as well, however, finding the exact leading multiple would require additional investigation into [34, Theorem 9].
5.2.4 The (ji +1) EAon OneMax, Upper Bounds. We now introduce the fixed-target bounds for the (p + 1) EA using fitness levels. For this we adapt [37, Theorem 2] to the fixed-target manner.
ThEorEm 5.10. Let p = poly(n), and assume b = |_n(1 - 1/l)J. The expected time to reach an individual with fitness at least k > 0 on OneMax is:
Tk « ü +
(1 - p)n Ii
2k - 1 - (n - k) ln
n - k + 1
p(1 - p)
n-1 I -+1
-+T + 77(Hn-b-1 - Hn-k)
k « b + 1, otherwise.
Proof. Similarly to [37, Theorem 2], we pessimistically assume that on every fitness level L the (i +1) EA creates R = min{i, n/(n -L)} replicas of the best individual, and then it waits for the fitness improvement. We also assume that the (p + 1) EA never improves the fitness by more than one.
If there are i < R best individuals, a replica is created with probability (1 - p)ni/i, so the expected time until R replicas are created is at most
yR-11 < ü yn-i-1 1 ¿Jí=1 i « a - p)n ZjÍ=1 i
ü V5-I-1 1
(1 - p)n
(1 - p)
ü -in-en
(1 - p)n
ji
(1 - p)n
(k in en + k - 1 + (n - k) ln(n - k + 1) - n ln n) n
2k - 1 - (n - k) ln
n - k + 1
where we use the condition k > 0 and that, for all 1 < a < b,
-1 > ln - « ln - +
^—lx=a x a
1 + f- l
a Ja
ln — dx x
: ln 1 +
a
x + x ln —
x
-
Concerning the fitness gain, if there are R replicas of the best individual with fitness L, the probability of creating new offspring with fitness L + 1 is at least
R • (n - L) • p(1 - p)n-1/l > min {i(n - L), n} • p(1 - p)n-1/l, so we apply Theorem 5.1 to estimate Tf:
Zk-1 1 i Y",k-1 1
i=0 pi = p(1 - p)n-1 2-1 i=0 min {i(n - i), n} .
Unlike [37], we consider what the min clauses can be. Depending on how the target k relates to b = |_n(1 - 1/i)J, we write
Tf < J np(7—p)n
rj • k, k < b + 1
Tf ^(b +1) + ^(1:;-^, k>b +1 which completes the proof as the fixed-target time is i + Tr +Tf. □
6 DRIFT ANALYSIS
In this section we consider the drift theorems in the fixed-target context. These theorems are generally more powerful, but it appears that one should use them for proving fixed-target results with slightly more care than in the case of fitness levels.
6.1 Method
Drift theorems translate the bounds on the expected progress into the bounds on the expected first-hitting running times. They are usually formulated in terms of a random process that needs to hit a certain minimum value, which corresponds to minimization. Some ofthese theorems prohibit the process from falling below the target, or from visiting an interval between a target and the next greater value. For this reason, some optimization time results cannot be converted into the fixed-target results without additional work, as targets different from the optimum violate the requirements above.
The paper [26] contains a discussion of processes which may fall below the target, and the implications for drift theorems. For instance, [26, Example 6] gives an example of a process with the target 0 and the expected progress of 1 at Xt = 1, which is given by Xt+1 = -n + 1 with probability of 1/n and Xt+1 = 1 otherwise. By mistakenly applying a well-known additive drift theorem from [20] to this process, one can get an overly optimistic upper bound of 1 on the expected running time, which is, in fact, n.
We start the discussion with the additive drift theorems. We provide their versions from [26] which can be adapted to the fixed-target setting. For the first of them we explicitly note that its upper (1 - p)n n - l bound is not (X0 - k)/<5, but a (generally) larger value. Indeed, if
k
a
n
we define Xj to be the value of the process at the hitting time T, it is only known that E[Xj | Xo] < k, and the latter may be far from being an equality. Proving the bounds for E[Xj | Xo] seems to be the essential additional work in order to prove fixed-target results.
Theorem 6.1 (Additive drift, fixED-TArGET upper bounds; Theorem 7 from [26], see also [20]). Let k be the target value, let (Xt)teN be random variables over R, and let T = inf{t | Xt < k}. Suppose that for all t < T it holds that Xt > o, and there exists S > o such that, for all t < T, it holds that Xt - E[Xt+1 | Xo,.. ., Xt] > S. Then E[T | Xo] < (Xo - E[Xj | Xo])/S.
Theorem 6.2 (Additive drift, fixed-target lower bounds; Theorem 8 from [26]). Let k be the target value, let (Xt)teN be random variables overR, and let T = inf{t | Xt < k}. Suppose that there exist S > o and c > o such that, for all t < T, it holds that Xt - £[Xt+1 | Xo,..., Xt ] < S and E[|Xt+1 - Xt | | Xo,..., Xt ] < c. Then E[T | Xo] > (Xo - £[XT | Xo])/S > (Xo - k)/S.
More advanced drift theorems, such as the multiplicative drift
theorems [14] and variable drift theorems [11, 27], make it easier to prove rather sharp bounds on hitting times for processes with drift that depends on the current value. This is more common in evolutionary algorithms even on simple problems.
Most of the popular drift theorems of this sort can be classified using the following properties: they estimate the time for a process either to reach a certain target value k or to surpass a certain threshold value k', and they also may or may not require the process to never fall below the target or to never visit a region between the threshold and the ultimate termination state (usually zero).
The case analysis, motivated by having all variants in one paper [26], revealed that only two of the four variants are suitable to be used for fixed-target research: theorems for upper bounds which require to surpass a threshold k', and theorems for lower bounds which require to reach a target k. The former contain an extra addend in their statement (such as "1+" or "xm;n/h(xmin)"), while the latter do not. This seems to be closely related to the E[Xj | Xo] issue in additive drift theorems, which the "good" theorems pes-simize to the right direction. We continue with theorems which we use in this paper.
Theorem 6.3 (Multiplicative drift, upper bounds [14] adapted to fixed-target settings). Let k' be the threshold value, let (Xt )t eN be random variables over R, and let T = inf{t | Xt < k'}. Suppose that Xo > k',andXt > o for all t < T. Suppose that there exists S > o such that, for all t < T, it holds thatXt-E[Xt+1 | Xo,..., Xt] > SXt.
Then E[T | Xo] < (1 + ln(Xo/k'))/S.
Theorem 6.4 (Variable drift, fixed-target lower bounds; adapted from Theorem 7 from [11]). Let k be the target value, let (Xt)t eN be random variables over R, and let T = inf{t | Xt < k}. Suppose that there are two continuous monotonically increasing functions c, h : R+ m R+, and that for all t < T it holds that Xt+1 > c(Xt) and E[Xt - Xt+1 | Xt] < h(c(Xt)).
Then E[T | Xo] > /fo ^d(z).
6.2 Applications
6.2.1 Minimum SpanningTrees. We begin with fixed-target bounds for minimum spanning trees solved by variations of the (1 + 1) EA. In
the context of evolutionary computation, the function to optimize can be defined in different ways. We follow [31] and use a function which consists of two parts: the number of connectivity components with a large weight to faciliate connecting all vertices, and the weight of the chosen edges. This function is to be minimized. It is known [14, 31] that the (1 + 1) EA optimizes this function in time O(m2(log nwmax)), where m is the number of edges, n is the number of vertices, and wmax is the maximum edge weight.
Theorem 6.5. Starting from a randomly initialized graph, the expected time for a (1 + 1) EA that flips a single bit with probability q to find a graph with at most k connected components is at most 1 (1 + ln m-1).
Proof. Consider the potential g(x) = s-1, where s is the number of connectivity components in the subgraph, which consists of the edges included in the genotype x. If there are s such components, there are at least s - 1 edges, which can be added to decrease the number of components. To do that, it is enough to flip at least one bit corresponding to these edges. To apply Theorem 6.3, we estimate the drift as E[g(Xt) - g(Xt+1) | g(Xt) = c] > cq.
The target of k connected components maps to the target potential of k - 1 and hence to the threshold value k, By applying Theorem 6.3 we get the desired bound. □
Theorem 6.6. Starting from some spanning tree, the expected time for a (1 + 1) EA that flips exactly two bits with probability q to find spanning tree with the weight at most k larger than the minimum possible weight is at most1 (1 + ln (m k+i''™").
Proof. We again re-use the corresponding result from [14]. The process is defined as Xt = w(x) - wopt, and [14] gives the drift bound of E[Xt - Xt+1 | Xt = x] > Xt • q. The application of Theorem 6.3 yields the desired upper bound on the fixed-target runtime, as Xo < (m - 1)wmax. □
We give the two-bit probabilities for the common algorithms.
• RLS which flips pairs of bits: q = m(m-1);
• (1 + 1) EA and (1 + 1) EAoM1: q = p2(1 - p)m-2;
• (1 + 1) EA>o: q = ^--P ;
• (1 + 1) EAom2: q = p2(1 - p)m-2 + (1 - p)m mm-).
Note that RLS which flips pairs of bits is a rather a mind experiment than an algorithm to use, however, one may use RLS that tosses a coin and flips either single bits or pairs of bits, which just halves the probability above.
6.2.2 The (1 + 1) EA on OneMax, Lower Bounds. We prove the lower fixed-target bounds using variable drift.
Theorem 6.7 (The lower fixed-target bound on (1 + 1) EA with p = 1/n for OneMax). The expected time to find an individual with fitness at least 2n/3 < k < n, when n is large enough, is at least
, , , , V"T3 + 2 n + 16(n - k) + 32Vn - k \ (1 - o(1/n))en 2ln v-+ ln- ( ) 1
Vn - k + 2
n + 16 f + 32A/n/'3
Proof. The basis of this proof is [11, Theorem 5]. Our aim is to apply the Theorem 6.4, which allows jumps below the target. This allows to use the original the potential function Xt = n - f(x) and
2 10'
a
o
at
s
al
v
w
10
10
0.2 0.4 0.6 0.8 Relative fitness, n = 103
0.2 0.4 0.6 Relative fitness, n
10
0.2 0.4 0.6 Relative fitness, n
0.8 : 105
10
103
101
10 104 102 100
—-— /
—
0.998 0.999 1
/
-1
0.998 0.999
Figure 2: The comparison of the fixed-target lower bounds for the (1 + 1) EA on OneMax
the existing bound on the expected drift [11, Lemma 6]:
e[X( - X(+1 | Xt = s]< esn(1 + ^).
Following [11], we bound the step size with c(x) = x - sfx. We also denote the bad step being the event of increasing the fitness of more than -\[x. To condition on that, we estimate the probability of making a bad step for 2 < x < n, which was shown in [11] to be O(n-3) for x > 9. For a good fixed-target result, we need to cover the rest. For 5 < x < 8, the probability of a bad step is at most (3)p3 = = O(n-3). For 2 < x < 4, the similar calculation yields the probability of O(n-2). Since the latter bound corresponds to only 0(1) fitness values, which takes at most O(n) iterations in expectation, the union bound over all bad steps during en ln n iterations is at most O((n ln n)/n3) = o(1/n). This is reflected as the 1 - o(1/n) quotient in the bound.
We also reuse the function h(x) from [11, Theorem 5], which is h(x) <
X (1 + 16+n2"ft ), and apply Theorem 6.4 to get
E[T | Xq] >
r XQ
Jk '
dx
en
ln
(x + 2Vx)(1 + 16 + 32Vx/n) (Vi + 2)2 8 arctan ((4Vx + 4)/Vn - 16)
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.