Генетические алгоритмы для глобальной оптимизации

Джон Холланд ввел понятие ГА для задачи оптимизации. ГА представляет собой стохастическую процедуру (с вероятностной компонентой) поиска глобального оптимума, основанную на имитации механизма естественной эволюции.

Естественная эволюция (Natural evolution) представляет собой процесс, который оперирует с хромосомами (chromosomes), являющимися специальными органическими устройствами. Хромосомы кодируют структуру индивидуума, или живого организма (living being). Множество индивидуумов называется популяцией (a population). Популяция развивается во времени благодаря соревнованию: выживает наиболее подходящий (survival of the fittest) – сильнейший, умнейший и т.п. Это биологический закон эволюции.

Естественная эволюция характеризуется тремя основными процессами:

· селекция (selection);

· рекомбинация (recombination);

· мутация (mutation).

Естественная селекция работает по следующей схеме:

(1) каждая хромосома оценивается значением пригодности (fitness), которая соответствует структуре индивидуума с данной хромосомой;

(2) определение хромосом, которые кодируют успешные структуры (имеющие максимальное значение пригодности);

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

Процесс рекомбинации создает различные хромосомы в «детях» комбинируя материал хромосом двух «родителей». Процесс мутации «заставляет» «детские» хромосомы отличаться от «родительских».

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

Основная парадигма ГА: ГА исследует пространство поиска, находит и поддерживает популяцию индивидуумов, структура которых представляет оптимальное решение текущей проблемы. ГА может использоваться в широкой области задач оптимизации и обучения, включая составление оптимальных маршрутов, планирование, машинное зрение, разработка систем управления и т.д. Мы будем рассматривать использование ГА для задач генерации нечетких правил и функций принадлежности для нечетких контроллеров.

Обсудим базовую структуру и механизмы ГА, представленную на рис. 2.21.

Рис 2.21. Структура ГА