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

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

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

Глава 4. Генетические алгорип

4.9. Примеры оптш

ации функции с помощью программы FlexTool

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

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

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

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

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

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

Дата добавления: 2015-06-04