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

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

---

А.Е. Кононюк Дискретно-непрерывная математика 
121 
К примеру, пусть вероятность мутации для каждой особи будет 
отдельной. Можно добавить к строке особи подстроку, кодирующую 
эту вероятность. При вычислении приспособленности эта подстрока 
будет игнорироваться, но она будет подвергаться кроссоверу и мутации 
так же, как и остальная часть строки. Вероятность каждого бита данной 
особи быть инвертированным при мутации будет равна значению, 
кодируемому добавленной подстрокой. Инициализируются вероятности 
мутации случайным образом.
Thomas Back (1992) в своей работе заметил, что для унимодальных 
функций вариант с глобальной вероятностью мутации работает лучше, 
однако для многоэкстремальных функций использование адаптивной 
мутации дает лучшие результаты.
3.6. Наблюдения 
Укажем некоторые наблюдения, полученные исследователями 
генетических алгоритмов.
Факторы, создающие сложность для ГА 
Как и для любого алгоритма оптимизации, для генетических 
алгоритмов есть некоторые типы функций, с которыми им работать 
сложнее, чем с другими. Обычно ГА тестируют именно на таких 
функциях. Ниже приведены свойства функций приспособленности, 
создающие сложность для ГА.

Многоэкстремальность
: это проблема для любого метода 
поиска, т. к. создается множество ложных аттракторов. Пример 
— функция Растригина (Растригин Л.А.):

---

А.Е. Кононюк Дискретно-непрерывная математика 
122 
Минимум достигается при всех 
x
i
= 0. Количество аргументов функции 
можно варьировать, тем самым повышая или понижая сложность 
задачи поиска минимума. На картинке изображен график функции 
Растригина с одним аргументом. 

Обманчивость
(
deception
) — это характеристика функции, 
построенной так, что шаблоны малого порядка уводят популяцию к 
локальному экстремуму. Пример: пусть строка состоит из 10-ти 
четырехбитных подстрок. Пусть 
u
i
равно количеству единиц в 
i
-той 
подстроке. Зададим функцию 
g
(
u
) следующей таблицей: