В информатике стратегия эволюции (ES) - это метод оптимизации , основанный на идеях эволюции . Он принадлежит к общему классу эволюционных вычислений или методологий искусственной эволюции .
История
Техника оптимизации «эволюционной стратегии» была создана в начале 1960-х годов и получила дальнейшее развитие в 1970-х, а затем Инго Рехенберг , Ханс-Пауль Швефель и их коллеги.
Методы
В стратегиях эволюции в качестве поисковых операторов используются естественные проблемно-зависимые представления, в первую очередь мутации и отбор . Как и в случае с эволюционными алгоритмами , операторы применяются в цикле. Итерация цикла называется поколением. Последовательность поколений продолжается до тех пор, пока не будет выполнен критерий завершения.
Для пространств поиска с действительным знаком мутация выполняется путем добавления нормально распределенного случайного вектора. Размер шага или сила мутации (т. Е. Стандартное отклонение нормального распределения) часто определяется самоадаптацией (см. Окно эволюции ). Индивидуальные размеры шага для каждой координаты или корреляции между координатами, которые по существу определяются лежащей в основе ковариационной матрицей , на практике контролируются либо самоадаптацией, либо адаптацией ковариационной матрицы ( CMA-ES ). Когда шаг мутации выводится из многомерного нормального распределения с использованием развивающейся ковариационной матрицы , была выдвинута гипотеза, что эта адаптированная матрица аппроксимирует обратный гессиан поискового ландшафта. Эта гипотеза была доказана для статической модели, основанной на квадратичной аппроксимации. [1]
Выбор (окружающей среды) в эволюционных стратегиях детерминирован и основан только на рейтинге пригодности, а не на фактических значениях приспособленности. Таким образом, полученный алгоритм инвариантен относительно монотонных преобразований целевой функции. Простейшая стратегия эволюции действует на популяции размером два: текущая точка (родительская) и результат ее мутации. Только если мутант по крайней мере не хуже, чем родитель, он становится родителем следующего поколения. В противном случае мутант игнорируется. Это (1 + 1) -ES . В более общем смысле, λ-мутанты могут генерироваться и конкурировать с родителем, называемым (1 + λ) -ES . В (1, λ) -ES лучший мутант становится родителем следующего поколения, в то время как текущий родитель всегда игнорируется. Для некоторых из этих вариантов доказательства линейной сходимости (в стохастическом смысле) были получены для унимодальных целевых функций. [2] [3]
Современные производные стратегии эволюции часто используют популяцию μ родителей и рекомбинацию в качестве дополнительного оператора, называемого (μ / ρ +, λ) -ES . Это делает их менее склонными к поселению в локальных оптимумах. [4]
Смотрите также
Рекомендации
- ^ Шир, ОМ; А. Иегудаофф (2020). «О ковариантно-гессианском отношении в эволюционных стратегиях» . Теоретическая информатика . Эльзевир. 801 : 157–174. arXiv : 1806.03674 . DOI : 10.1016 / j.tcs.2019.09.002 .
- ^ Аугер, А. (2005). «Результаты сходимости для (1, λ) -SA-ES с использованием теории φ-неприводимых цепей Маркова» . Теоретическая информатика . Эльзевир. 334 (1–3): 35–69. DOI : 10.1016 / j.tcs.2004.11.017 .
- ^ Jägersküpper, J. (2006). «Как (1 + 1) ES с использованием изотропных мутаций минимизирует положительно определенные квадратичные формы». Теоретическая информатика . Эльзевир. 361 (1): 38–56. DOI : 10.1016 / j.tcs.2006.04.004 .
- ^ Hansen, N .; С. Керн (2004). «Оценка стратегии развития CMA на мультимодальных тестовых функциях». Параллельное решение задач с натуры - PPSN VIII . Springer. С. 282–291. DOI : 10.1007 / 978-3-540-30217-9_29 .
Библиография
- Инго Рехенберг (1971): Стратегия эволюции - Оптимизация технической системы на принципах биологической эволюции (докторская диссертация). Перепечатано Фромманном-Хольцбугом (1973).
- Ханс-Пауль Швефель (1974): Numerische Optimierung von Computer-Modellen (докторская диссертация). Перепечатано Биркхойзером (1977).
- Х.-Г. Бейер и Х.-П. Schwefel. Стратегии эволюции: всестороннее введение . Журнал Natural Computing, 1 (1): 3–52, 2002.
- Ханс-Георг Бейер: Теория эволюционных стратегий: Springer 27 апреля 2001 г.
- Ханс-Пауль Швефель: Эволюция и поиск оптимума: Нью-Йорк: Wiley & Sons, 1995.
- Инго Рехенберг: стратегия развития '94. Штутгарт: Фромманн-Хольцбуг, 1994.
- Дж. Клокгайз и Х. П. Швефель (1970). Эксперименты с двухфазным соплом и струей с полым сердечником . AEG-Forschungsinstitut. Проектная группа MDH Staustrahlrohr. Берлин, Федеративная Республика Германия. Материалы 11-го симпозиума по инженерным аспектам магнитогидродинамики, Калифорнийский технологический институт, Пасадена, Калифорния, 24. – 26.3. 1970 г.
- М. Эммерих, О. М. Шир и Х. Ван: стратегии эволюции . В: Справочник по эвристике, 1-31. Издательство Springer International (2018).
Исследовательские центры
- Техника бионики и эволюции в Техническом университете Берлина
- Кафедра разработки алгоритмов (Ls11) - Дортмундский университет
- Центр совместных исследований 531 - Дортмундский университет