Генетический алгоритм (Genetic algorithm)

Разделы: Алгоритмы

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

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

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

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

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

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

  • Инициализация — формирование начальной популяции случайным образом, число особей колеблется от нескольких сотен до нескольких тысяч.
  • Выбор (селекция) — на каждой итерации отбирается часть текущей популяции для формирования следующего поколения. Отбираются особи, для которых значение фитнес-функции достаточно высокое.
  • Применение генетических операторов — к выбранным на предыдущем шаге особям применяются операторы скрещивания и мутации. Для формирования каждой новой особи выбираются два родителя, которые создают новую особь, наследующую признаки своих родителей. Хотя методы репродукции, основанные на использовании двух родителей, более соответствуют биологической основе метода, исследования показали, что использование трех и более родительских особой порождает потомков более высокого качества. В результате средний уровень пригодности популяции повышается.
  • Завершение — алгоритм продолжает работу до тех пор, пока не будет выполнено одной из условий остановки:
    • найдено решение, удовлетворяющее некоторому минимуму фитнес-функции;
    • достигнуто заданное число итераций;
    • значение фитнес-функции для новых особей перестало расти.

В качестве недостатков генетических алгоритмов можно выделить:

Генетические алгоритмы предложены Джоном Холландом в 1960 году.

Подробнее о генетических алгоритмах и принципах их использования в статье «Генетические алгоритмы — математический аппарат».