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