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

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

История

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

Методы

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

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

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

Ингорехнерберг (1971): Эволюционная стратегия - оптимизация технических систем согласно принципам биологической эволюции (кандидатская диссертация). Перепечатано Фромманном-Хольцбогом (1973). ISBN 3-7728-1642-8
Ханс-Пауль Вёлфе (1974): Численная оптимизация компьютерных моделей (докторская диссертация). Перепечатано Биркхойзером (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).

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

[1] Швефель, Ханс-Пауль (1995). Эволюция и поиск оптимума . Серия компьютерных технологий шестого поколения. Нью-Йорк: Уайли. ISBN 978-0-471-57148-3 .

[:0-2] Jump up to: ^а ^б Бек, Томас; Швефель, Ханс-Пауль (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 .

[:1-6] Jump up to: ^а ^б Хансен, Николаус; Остермайер, Андреас (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 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

v т и Эволюционные вычисления
Основные темы	Эволюционный алгоритм Эволюционный анализ данных Эволюционная мультимодальная оптимизация Человеческие эволюционные вычисления Интерактивные эволюционные вычисления
Алгоритмы	Алгоритм клеточной эволюции Стратегия эволюции адаптации ковариационной матрицы (CMA-ES) Культурный алгоритм Дифференциальная эволюция Эволюционное программирование Генетический алгоритм Генетическое программирование Программирование экспрессии генов Стратегия эволюции Стратегия естественной эволюции Нейроэволюция Система классификаторов обучения
Связанные методы	Роевой интеллект Оптимизация колонии муравьев Алгоритм пчел Поиск кукушки Оптимизация роя частиц Оптимизация бактериальных колоний
Метаэвристические методы	Алгоритм Светлячка Поиск гармонии Гауссова адаптация Меметический алгоритм
Связанные темы	Искусственное развитие Искусственный интеллект Искусственная жизнь Цифровой организм Эволюционная робототехника Фитнес-функция Фитнес-ландшафт Приближение фитнеса Генетические операторы Интерактивные эволюционные вычисления Никаких бесплатных обедов в поиске и оптимизации Машинное обучение Брачный пул Синтез программы
Журналы	Эволюционные вычисления (журнал)