Схема функционирования генетического алгоритма

Теперь, зная как интерпретировать значения генов, перейдем к описанию функционирования генетического алгоритма. Рассмотрим схему функционирования генетического алгоритма в его классическом варианте.

1. Инициировать начальный момент времени t=0. Случайным образом сформировать начальную популяцию, состоящую из k особей. B₀ = {A₁,A₂,…,A_k)
2. Вычислить приспособленность каждой особи F_Ai = fit(A_i) , i=1…k и популяции в целом F_t = fit(B_t) (также иногда называемую термином фиттнес). Значение этой функции определяет насколько хорошо подходит особь, описанная данной хромосомой, для решения задачи.
3. Выбрать особь A_c из популяции. A_c = Get(B_t)
4. С определенной вероятностью (вероятностью кроссовера P_c) выбрать вторую особь из популяции А_c1 = Get(B_t) и произвести оператор кроссовера A_c = Crossing(A_c,A_c1).
5. С определенной вероятностью (вероятностью мутации P_m) выполнить оператор мутации. A_c = mutation(A_c).
6. С определенной вероятностью (вероятностью инверсии P_i) выполнить оператор инверсии A_c = inversion(A_c).
7. Поместить полученную хромосому в новую популяцию insert(B_t+1,A_c).
8. Выполнить операции, начиная с пункта 3, k раз.
9. Увеличить номер текущей эпохи t=t+1.
10. Если выполнилось условие останова, то завершить работу, иначе переход на шаг 2.

Теперь рассмотрим подробнее отдельные этапы алгоритма.

Наибольшую роль в успешном функционировании алгоритма играет этап отбора родительских хромосом на шагах 3 и 4. При этом возможны различные варианты. Наиболее часто используется метод отбора, называемый рулеткой. При использовании такого метода вероятность выбора хромосомы определяется ее приспособленностью, то есть P_Get(Ai) ~ Fit(A_i)/Fit(B_t). Использование этого метода приводит к тому, что вероятность передачи признаков более приспособленными особями потомкам возрастает. Другой часто используемый метод – турнирный отбор. Он заключается в том, что случайно выбирается несколько особей из популяции (обычно 2) и победителем выбирается особь с наибольшей приспособленностью. Кроме того, в некоторых реализациях алгоритма применяется так называемая стратегия элитизма, которая заключается в том, что особи с наибольшей приспособленностью гарантировано переходят в новую популяцию. Использование элитизма обычно позволяет ускорить сходимость генетического алгоритма. Недостаток использования стратегии элитизма в том, что повышается вероятность попадания алгоритма в локальный минимум.

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

Стариков Алексей
BaseGroup Labs

Список литературы:

1. www.math.nsc.ru/AP/benchmarks/UFLP/uflp_ga.html">www.math.nsc.ru/AP/benchmarks/UFLP/uflp_ga.html
2. saisa.chat.ru/ga.html