Создание начальной популяции

Перед первым шагом нужно случайным образом создать начальную популяцию; даже если она окажется совершенно неконкурентоспособной, вероятно, что генетический алгоритм всё равно достаточно быстро переведёт её в жизнеспособную популяцию. Таким образом, на первом шаге можно особенно не стараться сделать слишком уж приспособленных особей, достаточно, чтобы они соответствовали формату особей популяции, и на них можно было подсчитать функцию приспособленности (Fitness). Итогом первого шага является популяция H, состоящая из N особей.

Отбор (селекция)

На этапе отбора нужно из всей популяции выбрать определённую её долю, которая останется «в живых» на этом этапе эволюции. Есть разные способы проводить отбор. Вероятность выживания особи h должна зависеть от значения функции приспособленности Fitness(h). Сама доля выживших s обычно является параметром генетического алгоритма, и её просто задают заранее. По итогам отбора из N особей популяции H должны остаться sN особей, которые войдут в итоговую популяцию H'. Остальные особи погибают.

• Турнирная селекция - сначала случайно выбирается установленное количество особей (обычно две), а затем из них выбирается особь с лучшим значением функции приспособленности

• Метод рулетки - вероятность выбора особи тем вероятнее, чем лучше её значение функции приспособленности p i = f i ∑ i = 1 N f i {\displaystyle p_{i}={\frac {f_{i}}{\sum _{i=1}^{N}{f_{i}}}}}

где p_i p i {\displaystyle p_{i}} - вероятность выбора i особи,

f_i f i {\displaystyle f_{i}} - значение функции приспособленности для i особи,

N N {\displaystyle N} - количество особей в популяции.

• Метод ранжирования - вероятность выбора зависит от места в списке особей отсортированном по значению функции приспособленности p i = 1 N ( a − ( a − b ) i − 1 N − 1 ) {\displaystyle p_{i}={\frac {1}{N}}(a-(a-b){\frac {i-1}{N-1}})}

,

где , a ∈ [ 1 , 2 ] {\displaystyle a\in [1,2]}

b = 2 − a {\displaystyle b=2-a} i {\displaystyle i} i - порядковый номер особи в списке особей отсортированном по значению функции приспособленности.

• Равномерное ранжирование - вероятность выбора особи определяется выражением:

где параметр метода.

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

где

f_avg - среднее значение целевой функции для всей популяции, σ - среднеквадратичное отклонение значения целевой функции.

Выбор родителей

Размножение в генетических алгоритмах обычно половое — чтобы произвести потомка, нужны несколько родителей, обычно два.

Можно выделить несколько операторов выбора родителей:

1. Панмиксия - оба родителя выбираются случайно, каждая особь популяции имеет равные шансы быть выбранной

2. Инбридинг - первый родитель выбирается случайно, а вторым выбирается такой, который наиболее похож на первого родителя

3. Аутбридинг - первый родитель выбирается случайно, а вторым выбирается такой, который наиболее не похож на первого родителя

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