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

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

История

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

Методы

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

Особенностью ЭС является самоадаптация размеров шагов мутаций и связанная с ней коэволюция . 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). Эволюция и поиск оптимума. Серия компьютерных технологий шестого поколения. Нью-Йорк: Уайли. ISBN 978-0-471-57148-3.
2. Бек, Томас; Швефель, Ханс-Пауль (1993). «Обзор эволюционных алгоритмов оптимизации параметров». Эволюционные вычисления . 1 (1): 1–23. дои : 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) , Сан-Матео, Калифорния: Морган Кауфманн, 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 на мультимодальных тестовых функциях», Параллельное решение проблем из природы - PPSN VIII , vol. 3242, Берлин, Гейдельберг: Springer, стр. 282–291, doi : 10.1007/978-3-540-30217-9_29, ISBN. 978-3-540-23092-2
8. Шир, ОМ; А. Иегудаев (2020). «О ковариационно-гессианском отношении в эволюционных стратегиях». Теоретическая информатика . 801 . Эльзевир: 157–174. arXiv : 1806.03674 . дои : 10.1016/j.tcs.2019.09.002 .
9. Оже, А. (2005). «Результаты сходимости для (1,λ)-SA-ES с использованием теории φ-неприводимых цепей Маркова». Теоретическая информатика . 334 (1–3). Эльзевир: 35–69. дои : 10.1016/j.tcs.2004.11.017.
10. Егерскюппер, Дж. (2006). «Как (1+1) ES с использованием изотропных мутаций минимизирует положительно определенные квадратичные формы». Теоретическая информатика . 361 (1). Эльзевир: 38–56. дои : 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.
• Ханс-Георг Бейер: Теория стратегий эволюции . Спрингер, 27 апреля 2001 г. ISBN 3-540-67297-4. 
• Инго Рехенберг: Стратегия эволюции '94 . Штутгарт: Фромманн-Хольцбуг 1994. ISBN 3-7728-1642-8. 
• Дж. Клокгетер и Х. П. Швефель (1970). Эксперименты с двухфазным соплом и полой струей. AEG-Институт Форшунгов. Проектная группа MDH Staustrahlrohr. Берлин, Федеративная Республика Германия. Труды 11-го симпозиума по инженерным аспектам магнитогидродинамики, Калифорнийский технологический институт, Пасадена, Калифорния, 24.–26.3. 1970.
• М. Эммерих, О. М. Шир и Х. Ван: Стратегии эволюции. В: Справочник по эвристике, 1–31. Международное издательство Springer (2018).

Исследовательские центры

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