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

Часть серия на
Эволюционный алгоритм
Генетический алгоритм
Генетическое программирование

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

История

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

Методы

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

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

Выбор (окружающей среды) в эволюционных стратегиях детерминирован и основан только на рейтинге пригодности, а не на фактических значениях приспособленности. Таким образом, полученный алгоритм инвариантен относительно монотонных преобразований целевой функции. Простейшая стратегия эволюции работает с популяцией второго размера: текущая точка (родительская) и результат ее мутации. Только если мутант по крайней мере не хуже, чем родитель, он становится родителем следующего поколения. В противном случае мутант игнорируется. Это (1 + 1) -ES. В более общем смысле, λ-мутанты могут генерироваться и конкурировать с родителем, называемым (1 + λ) -ES. В (1, λ) -ES лучший мутант становится родителем следующего поколения, в то время как текущий родитель всегда игнорируется. Для некоторых из этих вариантов доказательства линейная сходимость (в стохастический смысл) были выведены на унимодальных целевых функциях.[2][3]

Современные производные стратегии эволюции часто используют популяцию μ родителей и рекомбинацию в качестве дополнительного оператора, называемого (μ / ρ +, λ) -ES. Это делает их менее склонными к поселению в локальных оптимумах.[4]

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

Рекомендации

  1. ^ Shir, O.M .; А. Иегудаофф (2020). «О ковариационно-гессианском отношении в эволюционных стратегиях». Теоретическая информатика. Эльзевир. 801: 157–174. Дои:10.1016 / j.tcs.2019.09.002.
  2. ^ Аугер, А. (2005). «Результаты сходимости для (1, λ) -SA-ES с использованием теории φ-неприводимых цепей Маркова». Теоретическая информатика. Эльзевир. 334 (1–3): 35–69. Дои:10.1016 / j.tcs.2004.11.017.
  3. ^ Jägersküpper, J. (2006). «Как (1 + 1) ES с использованием изотропных мутаций минимизирует положительно определенные квадратичные формы». Теоретическая информатика. Эльзевир. 361 (1): 38–56. Дои:10.1016 / j.tcs.2006.04.004.
  4. ^ Hansen, N .; С. Керн (2004). «Оценка стратегии развития CMA на мультимодальных тестовых функциях». Параллельное решение проблем с натуры - PPSN VIII. Springer. С. 282–291. Дои:10.1007/978-3-540-30217-9_29.

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

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