Дискретно-непрерывная математика. Кн. 0 : Алгоритмы. Ч. Генетические алгоритмы

3.2. Настройка ГА 
Генетический алгоритм производит поиск решений двумя методами 
одновременно: отбором гиперплоскостей (
hyperplane sampling
) и 
методом 
hill-climbing
. Кроссовер осуществляет первый из них, 
поскольку комбинирует и совмещает шаблоны родителей в их детях. 
Мутация обеспечивает второй метод: особь случайным образом 

---

А.Е. Кононюк Дискретно-непрерывная математика 
111 
изменяется, неудачные варианты вымирают, а если полученное 
изменение оказалось полезным, то, скорее всего, эта особь останется в 
популяции.
Возникает вопрос: какой же из этих методов лучше осуществляет поиск 
хороших решений? Исследования показали, что на простых задачах, 
таких, как максимизация унимодальной функции, ГА с мутацией (и без 
кроссовера) находят решение быстрее. Также для такого метода 
требуется меньший размер популяции. На сложных 
многоэкстремальных функциях лучше использовать ГА с кроссовером, 
поскольку этот метод более надежен, хотя и требует большего размера 
популяции.
С точки зрения теоремы шаблонов, мутация только вредит росту 
количества представителей хороших шаблонов, поскольку лишний раз 
их разрушает. Однако мутация просто необходима для ГА с малым 
размером популяции. Дело в том, что для малочисленных популяций 
свойственна 
преждевременная сходимость
(
premature convergence
). 
Это ситуация, когда в некоторых позициях все особи имеют один и тот 
же бит, но такой набор битов не соответствует глобальному 
экстремуму. При этом кроссовер практически не изменяет популяции, 
т. к. все особи почти одинаковы. В этом случае мутация способна 
инвертировать «застрявший» бит у одной из особей и вновь расширить 
пространство поиска.
Введем понятие 
давления отбора
(
selection pressure
) — это мера того, 
насколько различаются шансы лучшей и худшей особей популяции 
попасть в промежуточную популяцию. Для пропорционального отбора 
эта величина имеет свойство уменьшаться с увеличением средней 
приспособленности популяции. Действительно, при этом для каждой 
особи отношение 
f
⁄ <
f
> стремится 1, а значит шансы плохой и хорошей 
особей создать потомство уравниваются.
При увеличении 
p
c
или 
p
m
и при уменьшении давления отбора 
(например, за счет использования других стратегий отбора) 
размножение представителей приспособленных шаблонов замедляется, 
но зато происходит интенсивный поиск других шаблонов. Обратно, 
уменьшение 
p
c
или 
p
m
и увеличение давления отбора ведет к 
интенсивному использованию найденных хороших шаблонов, но 

---

А.Е. Кононюк Дискретно-непрерывная математика 
112 
меньше внимания уделяется поиску новых. Таким образом, для 
эффективной работы генетического алгоритма необходимо 
поддерживать тонкое равновесие между 
исследованием и 
использованием
. Это можно сформулировать также как необходимость 
сбалансированной сходимости
ГА: быстрая сходимость может привести 
к схождению к неоптимальному решению, а медленная сходимость 
часто приводит к потере найденной наилучшей особи.
Методология управления сходимостью классического ГА до сих пор не 
выработана.