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

 
3.9.8. 
Генетические микроалгоритмы
Генетический микроалгоритм - это модификация классического 
генетического алгоритма, предназначенная для решения задач, не 
требующих больших популяций и длинных хромосом. Такие алгорит-
мы применяются при ограниченном времени вычислений в случае, 
когда решение (не обязательно глобальное) необходимо найти быстро. 
Речь идет о том, чтобы не производить трудоемких вычислений, 
связанных с большим количеством итераций. Генетические микроал-
горитмы обычно находят несколько худшие решения, однако экономят 
вычислительные ресурсы компьютера. В качестве примера можно 
привести генетический микроалгоритм программы 
FlexTool. 
Он 
подразделяется на шесть шагов.

---

А.Е. Кононюк Дискретно-непрерывная математика 
161 
1. Сформировать популяцию с числом особей, равным пяти. Можно 
либо случайным образом выбрать все пять хромосом, либо сохранить 
одну «хорошую» хромосому, полученную на предыдущих итерациях, и 
случайным образом «добрать» четыре остальные хромосомы. 
2. Рассчитать значения функции приспособленности хромосом в 
популяции и выбрать лучшую хромосому. Обозначить ее номером 5 и 
перенести в следующее поколение (элитарная стратегия).
3. Выбрать для репродукции остальные четыре хромосомы на основе 
детерминированного метода турнирной селекции (наилучшая 
хромосома также участвует в соревновании за право включения ее 
копии в родительский пул). В ходе турнирной селекции хромосомы 
группируются случайным образом, при этом соседствующие пары со-
перничают за оставшиеся четыре места. Следует обращать внимание 
на то, чтобы родительская пара не составлялась из двух копий одной и 
той же хромосомы.
4. Выполнить скрещивание с вероятностью 1; вероятность мутации 
принять равной 0.
5. 
Проверить 
сходимость 
алгоритма 
(с 
использованием 
соответствующей меры сходимости генотипов или фенотипов). В 
случае обнаружения сходимости вернуться к шагу 1.
6. Перейти к шагу 2.
Заметим, что в генетическом микроалгоритме размер популяции 
предполагается небольшим и фиксированным. Применяется элитарная 
стратегия, которая предотвращает потерю «хороших» хромосом. 
Поскольку размер популяции невелик, то выполняется детерми-
нированная селекция. Скрещивание проводится с вероятностью 1. 
Мутация не требуется, так как достаточное разнообразие обеспечива-
ется формированием новой популяции при каждом «рестарте» алго-
ритма, т.е. в случае перехода к шагу 1 при обнаружении сходимости. 
Процедура «старта» и «рестарта» алгоритма предназначена для пре-
дотвращения преждевременной сходимости; генетический микроал-
горитм всегда ищет наилучшие решения. Главная цель его применения 
заключается в скорейшем нахождении оптимального (или почти 
оптимального) решения.