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

u
 
0 1 2 3 4 
g
(
u
) 
3 2 1 0 4 

и пусть функция приспособленности равна сумме 
g
(
u
i
) по всем 
i
= 1..10:


Локальный максимум достигается при всех битах, равных 0, 
глобальный — при всех 1. В большинстве случаев при 
добавлении единицы в подстроку приспособленность особи 
будет падать (за исключением случая, когда все остальные 
биты подстроки уже равны 1). При замене 1 на 0 она будет 

---

А.Е. Кононюк Дискретно-непрерывная математика 
123 
расти. Поэтому с большой вероятностью популяция сойдется к 
решению, при котором большинство подстрок будут состоять 
из всех нулей, и лишь некоторые из всех единиц. Однако это не 
будет глобальным максимумом. Из этого решения попасть в 
глобальный максимум, т. е. заменить все нули единицами, для 
ГА будет сложно.

Изолированность
(«поиск иголки в стоге сена») — также 
проблема для любого метода оптимизации, поскольку функция 
не предоставляет никакой информации, подсказывающей, в 
какой области искать максимум. Лишь случайное попадание 
особи в глобальный экстремум может решить задачу.

Дополнительный шум
(
noise
) разбрасывает значения 
приспособленности шаблонов, поэтому часто даже хорошие 
гиперплоскости малого порядка не проходят отбор, что 
замедляет поиск решения.
Размер популяции 
Для того, чтобы получить хорошие результаты, необходимо правильно 
выбрать размер популяции. На графике изображена зависимость 
количества вычислений функции приспособленности для нахождения 
максимума унимодальной функции от размера популяции. Видно, что 
существует оптимальный размер популяции. Действительно, если 
популяция мала, то при заданном ограничении количества вычислений 

---

А.Е. Кононюк Дискретно-непрерывная математика 
124 
функции приспособленности (а значит, фиксированном времени 
вычислений) она успеет создать большее количество поколений, но 
вероятнее всего преждевременно сойдется. Слишком большая 
популяция должна найти решение, но она может не успеть достичь 
этого момента, т. к. ей отведено малое количество поколений.
Для алгоритмов с кроссовером (т. е. без мутации) существуют оценки 
оптимального размера, а для ГА с мутацией (и без кроссовера) их пока 
нет. Однако эксперименты показывают, что для них оптимальный 
размер популяции тоже существует. В любом случае, он зависит от 
задачи.