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

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) и победителем выбирается особь с наибольшей приспособленностью. Кроме того, в некоторых реализациях алгоритма применяется так называемая стратегия элитизма, которая заключается в том, что особи с наибольшей приспособленностью гарантировано переходят в новую популяцию. Использование элитизма обычно позволяет ускорить сходимость генетического алгоритма. Недостаток использования стратегии элитизма в том, что повышается вероятность попадания алгоритма в локальный минимум.

Другой важный момент – определение критериев останова.

В качестве критериев останова алгоритма могут использоваться такие:

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