4.8.8. Генетические микроалгоритмы

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

1. Сформировать популяцию с числом особей, равным пяти. Можно либо случайным образом выбрать все пять хромосом, либо сохранить одну «хорошую» хромосому, полученную на предыдущих итерациях, и случайным образом «добрать» четыре остальные хромосомы.

2. Рассчитать значения функции приспособленности хромосом в популяции и выбрать лучшую хромосому. Обозначить ее номером 5 и перенести в следующее поколение (элитарная стратегия).

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

4. Выполнить скрещивание с вероятностью 1; вероятность мутации принять равной 0.

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

6. Перейти к шагу 2.

Заметим, что в генетическом микроалгоритме размер популяции предполагается небольшим и фиксированным. Применяется элитарная стратегия, которая предотвращает потерю «хороших» хромосом. Поскольку размер популяции невелик, то выполняется детерминированная селекция. Скрещивание проводится с вероятностью 1. Мутация не требуется, так как достаточное разнообразие обеспечивается формированием новой популяции при каждом «рестарте» алгоритма, т.е. в случае перехода к шагу 1 при обнаружении сходимости. Процедура «старта» и «рестарта» алгоритма предназначена для предотвращения преждевременной сходимости; генетический микроалгоритм всегда ищет наилучшие решения. Главная цель его применения заключается в скорейшем нахождении оптимального (или почти оптимального) решения.