Генетический метод

Генетический метод сочетает направленный поиск, основанный на эвристиках, с элементами случайности, цель которых – исключение «застревания» поиска в точках локального оптимума.

• хромосома – любое решение задачи синтеза, т.е. определенным образом организованная совокупность выходных параметров, характеризующих решение задачи;

• гены – поля хромосом, содержащие значения проектных параметров (аллели);

• начальная популяция – исходное множество решений;

• кроссинговер (кроссовер) – оператор, осуществляющий скрещивание хромосом, т. е. взаимный обмен генами между хромосомами предварительно выбранной пары родителей, порождающий пару новых решений;

• мутация – случайное перестроение генов отдельных решений – порождает новые решения и служит для исключения «застревания» поиска в точках локального оптимума.

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

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

Для завершения процесса могут использоваться те же условия, что и у итерационного метода.

Алгоритмы, реализующие генетический метод, гарантируют получение лишь приближенного решения.

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

Максимальное усиление любого из достоинств генетического метода способно свести остальные его преимущества на нет, превращая его в чисто вероятностный или полностью детерминированный метод.

Простейшим примером вырожденного случая является итераци-онный алгоритм парных обменов, в котором репродуцируется одно начальное решение и выполняется парный обмен генов, т. е. скрещивание хромосом.