Эволюционный алгоритм (Evalutionary algorithm)

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

Решения оптимизационной задачи рассматриваются как особи популяции. Качество каждого решения оценивается с помощью специальной функции годности (fitness function — фитнес-функция), после чего происходит эволюция популяции. Таким образом, эволюционный алгоритм содержит следующие шаги:

1. Формируется начальная популяция методом случайного отбора (первое поколение).
2. Оценивается пригодность каждого члена популяции с помощью фитнес-функции.
3. Повторяются следующие действия (эволюция):
   • отбор — выбор наиболее приспособленных особей для размножения (родители);
   • размножение — формирование новых особей путем скрещивания и мутации, а затем оценка их пригодности;
   • рекомбинация — наименее приспособленные особи предыдущего поколения заменяются наиболее приспособленными особями нового поколения.

Эволюционные алгоритмы имеют следующие преимущества:

• применимы к широкому классу задач оптимизации;
• легко комбинируются с другими методами;
• позволяют получать хорошо интерпретируемые результаты;
• обладают интерактивностью — можно включить в популяцию предложенные пользователем решения;
• рассматривают большое количество альтернативных решений.

К недостатками эволюционных алгоритмов можно отнести:

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

Впервые концепция эволюционных алгоритмов была предложена и реализована Лоуренсом Фогелем в 1965 году.

О том, каким образом объекты реального мира могут быть закодированы для использования в эволюционных алгоритмах и о вариантах их функционирования, узнайте в статье «Генетические алгоритмы — математический аппарат».