Основные модели генетических алгоритмов

В предыдущей статье мы выяснили, какие факторы создают проблемы для работы генетических алгоритмов (ГА). Для улучшения показателей ГА в «трудных» случаях, а так же для оптимизации и ускорения их работы, используют различные модели ГА, о которых и пойдёт речь в этой статье. Если вы ещё не знакомы с понятием «Генетический алгоритм», рекомендуем прочитать вводную статью на эту тему.

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

Такая модель представляет собой смесь ГА и другого метода оптимизации (чаще всего метода локального поиска).

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

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

Параллельный генетический алгоритм

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

При этом расчёт функции пригодности (ФП) особей в популяции реализуется параллельно на нескольких компьютерах.

Макромодель с миграцией особей (островная модель)

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

Переменные параметры модели:

1. Число мигрантов (например, Км = 0,25К)
2. Период миграции – измеряется в целом количестве поколений (например, Nм = 5 поколений)
3. Способ миграции:

• Выбор особей по следующему правилу: особи с наибольшими значениями ФП из одной популяции заменяют на особей с наименьшими значениями ФП из другой.
• Организация связей между особями популяции «один к одному», «один ко многим», «многие ко многим».