Эволюционный алгоритм (Evalutionary algorithm) Скачать в PDF

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

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

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

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

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

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

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

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

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