Стратегия эволюции

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

История

Метод оптимизации «стратегии эволюции» был создан в начале 1960-х годов и получил дальнейшее развитие в 1970-х годах и позднее Инго Рехенбергом , Гансом-Полем Швефелем и их коллегами.

Методы

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

Особенностью ES является самоадаптация размеров шагов мутации и связанная с ней коэволюция . ES кратко представлена ​​с использованием стандартной формы, ^{[1] [2] [3]} указывая на то, что существует множество вариантов. ^{[4] [5] [ 6] [7]} Действительная хромосома содержит, в дополнение к переменным решения, размеры шагов мутации , где: . Часто один размер шага мутации используется для всех переменных решения или каждая имеет свой собственный размер шага. Выбор партнера для получения потомства является случайным, т.е. не зависит от приспособленности. Во-первых, новые размеры шагов мутации генерируются за одно спаривание путем промежуточной рекомбинации родительской с последующей мутацией следующим образом: ${\displaystyle n}$ ${\displaystyle n'}$ ${\displaystyle {\sigma }_{j}}$ ${\displaystyle 1\leq j\leq n'\leq n}$ ${\displaystyle \lambda }$ ${\displaystyle {\sigma }_{j}}$

${\displaystyle {\sigma }'_{j}=\sigma _{j}\cdot e^{({\mathcal {N}}(0,1)-{\mathcal {N}}_{j}(0,1))}}$

где — нормально распределенная случайная величина со средним значением и стандартным отклонением . применяется ко всем , в то время как заново определяется для каждого . Далее, за дискретной рекомбинацией переменных решения следует мутация с использованием новых размеров шагов мутации в качестве стандартных отклонений нормального распределения. Новые переменные решения вычисляются следующим образом: ${\displaystyle {\mathcal {N}}(0,1)}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle {\mathcal {N}}(0,1)}$ ${\displaystyle {\sigma }'_{j}}$ ${\displaystyle {\mathcal {N}}_{j}(0,1)}$ ${\displaystyle {\sigma }'_{j}}$ ${\displaystyle x_{j}'}$

${\displaystyle x_{j}'=x_{j}+{\mathcal {N}}_{j}(0,{\sigma }_{j}')}$

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

ES знает два варианта наилучшего отбора для генерации следующей родительской популяции: в -ES используются только лучшие потомки, тогда как в элитарном -ES лучшие отбираются из родителей и детей. ${\displaystyle (\mu ,\lambda )}$ ${\displaystyle \mu }$ ${\displaystyle (\mu +\lambda )}$ ${\displaystyle \mu }$

Бэк и Швефель рекомендуют, чтобы значение было в семь раз больше размера популяции , ^[2] при этом не должно быть выбрано слишком маленьким из-за сильного давления отбора. Подходящие значения для зависят от области применения и должны быть определены экспериментально. ${\displaystyle \lambda }$ ${\displaystyle \mu }$ ${\displaystyle \mu }$ ${\displaystyle \mu }$

Индивидуальные размеры шагов для каждой координаты или корреляции между координатами, которые по существу определяются базовой ковариационной матрицей , на практике контролируются либо самоадаптацией, либо адаптацией ковариационной матрицы ( CMA-ES ). ^[6] Когда шаг мутации извлекается из многомерного нормального распределения с использованием развивающейся ковариационной матрицы , была выдвинута гипотеза, что эта адаптированная матрица аппроксимирует обратный гессиан поискового ландшафта. Эта гипотеза была доказана для статической модели, основанной на квадратичном приближении. ^[8]

Выбор следующего поколения в стратегиях эволюции детерминирован и основан только на рейтингах приспособленности, а не на фактических значениях приспособленности. Поэтому полученный алгоритм инвариантен относительно монотонных преобразований целевой функции. Простейшая стратегия эволюции работает с популяцией размера два: текущая точка (родитель) и результат ее мутации. Только если приспособленность мутанта по крайней мере так же хороша, как у родителя, он становится родителем следующего поколения. В противном случае мутант игнорируется. Это -ES . В более общем смысле, мутанты могут быть созданы и конкурировать с родителем, называемым -ES . В -ES лучший мутант становится родителем следующего поколения, в то время как текущий родитель всегда игнорируется. Для некоторых из этих вариантов доказательства линейной сходимости (в стохастическом смысле) были получены на унимодальных целевых функциях. ^{[9] [10]} ${\displaystyle {\mathit {(1+1)}}}$ ${\displaystyle \lambda }$ ${\displaystyle {\mathit {(1+\lambda )}}}$ ${\displaystyle (1,\lambda )}$

Смотрите также

• Стратегия эволюции адаптации ковариационной матрицы (CMA-ES)
• Оптимизация без производных
• Эволюционные вычисления
• Генетический алгоритм
• Стратегия естественной эволюции
• Эволюционная теория игр

Ссылки

1. Швефель, Ганс-Пауль (1995). Эволюция и поиск оптимума. Серия «Технологии компьютеров шестого поколения». Нью-Йорк: Wiley. ISBN 978-0-471-57148-3.
2. Бэк, Томас; Швефель, Ганс-Пауль (1993). «Обзор эволюционных алгоритмов для оптимизации параметров». Эволюционные вычисления . 1 (1): 1–23. doi :10.1162/evco.1993.1.1.1. ISSN  1063-6560.
3. Швефель, Ганс-Пауль; Рудольф, Гюнтер; Бек, Томас (1995), Моран, Фредерико; Морено, Альваро; Мерело, Дж. Дж.; Чакон, Пабло (ред.), «Современные стратегии эволюции», Труды Третьей европейской конференции по достижениям в области искусственной жизни , Берлин, Гейдельберг: Springer, стр. 893–907, doi :10.1007/3-540-59496-5_351, ISBN 978-3-540-59496-3
4. Бэк, Томас; Хоффмайстер, Франк; Швефель, Ханс-Пауль (1991), Белью, Ричард К.; Букер, Лэшон Б. (ред.), «Обзор стратегий эволюции», Труды Четвертой международной конференции по генетическим алгоритмам (ICGA) , Сан-Матео, Калифорния: Morgan Kaufmann, ISBN 978-1-55860-208-3
5. Коэльо, В.Н.; Коэльо, ИМ; Соуза, MJF; Оливейра, штат Техас; Кота, LP; Хаддад, Миннесота; Младенович, Н.; Сильва, RCP; Гимарайнш, ФГ (2016). «Гибридные самоадаптивные стратегии эволюции, управляемые структурами окрестности, для задач комбинаторной оптимизации». Эволюционные вычисления . 24 (4): 637–666. дои : 10.1162/EVCO_a_00187. ISSN  1063-6560.
6. Хансен, Николаус; Остермайер, Андреас (2001). «Полностью дерандомизированная самоадаптация в стратегиях эволюции». Эволюционные вычисления . 9 (2): 159–195. дои : 10.1162/106365601750190398. ISSN  1063-6560.
7. Хансен, Николаус; Керн, Стефан (2004), Яо, Синь; Берк, Эдмунд К.; Лозано, Хосе А.; Смит, Джим (ред.), «Оценка стратегии эволюции CMA на многомодальных тестовых функциях», Parallel Problem Solving from Nature - PPSN VIII , т. 3242, Берлин, Гейдельберг: Springer, стр. 282–291, doi :10.1007/978-3-540-30217-9_29, ISBN 978-3-540-23092-2
8. Шир, ОМ; А. Йехудайофф (2020). «О ковариационно-гессеновской связи в эволюционных стратегиях». Теоретическая информатика . 801. Elsevier: 157–174. arXiv : 1806.03674 . doi : 10.1016/j.tcs.2019.09.002 .
9. Auger, A. (2005). "Результаты сходимости для (1,λ)-SA-ES с использованием теории φ-неприводимых цепей Маркова". Теоретическая информатика . 334 (1–3). Elsevier: 35–69. doi :10.1016/j.tcs.2004.11.017.
10. Jägersküpper, J. (2006). «Как (1+1) ES, использующая изотропные мутации, минимизирует положительно определенные квадратичные формы». Теоретическая информатика . 361 (1). Elsevier: 38–56. doi : 10.1016/j.tcs.2006.04.004 .

Библиография

• Инго Рехенберг (1971): Evolutionsstrategie – Optimierung technischer Systeme nach Prinzipien der Biologischen Evolution (докторская диссертация). Перепечатано Фромманном-Хольцбогом (1973). ISBN 3-7728-1642-8 
• Ханс-Пауль Швефель (1974): Numerische Optimierung von Computer-Modellen (докторская диссертация). Перепечатано Биркхойзером (1977).
• Ганс-Пауль Швефель : Эволюция и поиск оптимума . Нью-Йорк: Wiley & Sons 1995. ISBN 0-471-57148-2 
• Х.-Г. Бейер и Х.-П. Швефель. Стратегии эволюции: всеобъемлющее введение . Журнал Natural Computing, 1(1):3–52, 2002.
• Ханс-Георг Бейер: Теория эволюционных стратегий . Springer, 27 апреля 2001 г. ISBN 3-540-67297-4 
• Инго Рехенберг: Стратегия эволюции '94 . Штутгарт: Фромманн-Хольцбуг 1994. ISBN 3-7728-1642-8. 
• J. Klockgether и HP Schwefel (1970). Двухфазное сопло и эксперименты с полым сердечником струи. AEG-Forschungsinstitut. Проектная группа MDH Staustrahlrohr. Берлин, Федеративная Республика Германия. Труды 11-го симпозиума по техническим аспектам магнитогидродинамики, Caltech, Pasadena, Cal., 24.–26.3. 1970.
• М. Эммерих, О. М. Шир и Х. Ванг: Стратегии эволюции. В: Справочник по эвристике, 1-31. Springer International Publishing (2018).

Научно-исследовательские центры

• Бионика и техника эволюции в Техническом университете Берлина
• Кафедра алгоритмической инженерии (Ls11) – Технический университет Дортмунда
• Центр совместных исследований 531 – Технический университет Дортмунда