В информатике стратегия эволюции (ES) — это метод оптимизации , основанный на идеях эволюции . Он принадлежит к общему классу методологий эволюционных вычислений или искусственной эволюции .
История
Техника оптимизации «стратегии эволюции» была создана в начале 1960-х годов и получила дальнейшее развитие в 1970-х, а затем позже Инго Рехенбергом , Хансом-Паулем Швефелем и их коллегами.
Методы
Стратегии эволюции используют естественные представления, зависящие от проблемы, поэтому проблемное пространство и пространство поиска идентичны. Как и в эволюционных алгоритмах , операторы применяются в цикле. Итерация цикла называется генерацией. Последовательность поколений продолжается до тех пор, пока не будет выполнен критерий завершения.
Особенностью ЭС является самоадаптация размеров шагов мутаций и связанная с ней коэволюция . ES кратко представлен в стандартной форме, [1] [2] [3] с указанием, что существует множество вариантов. [4] [5] [6] [7] Действительная хромосома содержит, помимо переменных решения, размеры шагов мутации , где: . Часто для всех переменных решения используется один размер шага мутации или каждый имеет свой собственный размер шага. Выбор партнера для производства потомства является случайным, т.е. не зависит от приспособленности. Во-первых, новые размеры шагов мутации генерируются для каждого спаривания путем промежуточной рекомбинации родительского элемента с последующей мутацией следующим образом:
где – нормально распределенная случайная величина со средним и стандартным отклонением . применяется ко всем , хотя для каждого определяется заново . Затем за дискретной рекомбинацией переменных решения следует мутация с использованием новых размеров шагов мутации в качестве стандартных отклонений нормального распределения. Новые переменные решения рассчитываются следующим образом:
Это приводит к эволюционному поиску на двух уровнях: во-первых, на уровне самой проблемы и, во-вторых, на уровне размера шага мутации. Таким образом, можно гарантировать, что ES будет искать свою цель все более точными шагами. Однако существует также опасность того, что большие недопустимые области в пространстве поиска будут пропущены с трудом.
ES знает два варианта лучшего отбора для генерации следующей родительской популяции: в -ES используется только лучшее потомство, тогда как в элитарном -ES отбираются лучшие из родителей и детей.
Бек и Швефель рекомендуют, чтобы значение в семь раз превышало размер популяции [2] , при этом не следует выбирать слишком маленькое значение из-за сильного давления отбора. Подходящие значения зависят от применения и должны определяться экспериментально.
Индивидуальные размеры шага для каждой координаты или корреляции между координатами, которые по существу определяются базовой ковариационной матрицей , на практике контролируются либо путем самоадаптации, либо путем адаптации ковариационной матрицы ( CMA-ES ). [6] Когда шаг мутации рисуется из многомерного нормального распределения с использованием развивающейся ковариационной матрицы , была выдвинута гипотеза, что эта адаптированная матрица аппроксимирует обратную гессианскую среду поиска. Эта гипотеза была доказана для статической модели, основанной на квадратичном приближении. [8]
Выбор следующего поколения в стратегиях эволюции является детерминированным и основан только на рейтингах приспособленности, а не на фактических значениях приспособленности. Таким образом, полученный алгоритм инвариантен относительно монотонных преобразований целевой функции. Простейшая стратегия эволюции действует на популяции размером два: текущая точка (родительская) и результат ее мутации. Только если приспособленность мутанта хотя бы так же хороша, как у родительского, он становится родителем следующего поколения. В противном случае мутант игнорируется. Это -ES . В более общем смысле, мутанты могут создаваться и конкурировать с родителем, называемым -ES . В -ES лучший мутант становится родителем следующего поколения, тогда как текущий родитель всегда игнорируется. Для некоторых из этих вариантов доказательства линейной сходимости (в стохастическом смысле) были получены на унимодальных целевых функциях. [9] [10]
Смотрите также
Рекомендации
- ^ Швефель, Ханс-Пол (1995). Эволюция и поиск оптимума. Серия компьютерных технологий шестого поколения. Нью-Йорк: Уайли. ISBN 978-0-471-57148-3.
- ^ Аб Бек, Томас; Швефель, Ханс-Пауль (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.
- ^ аб Хансен, Николаус; Остермайер, Андреас (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): 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 – Дортмундский университет