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

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

Такие миграции позволяют подпопуляциям совместно использовать генетический материал.

Пусть выполняются 16 независимых генетических алгоритмов, используя подпопуляции из 100 особей в каждой. Если миграции нет, то происходит 16 независимых поисков решения. Все поиски ведутся на различных начальных популяциях и сходятся к определенным особям. Исследования подтверждают, что генетический дрейф склонен приводить подпопуляции к различным доминирующим особям. Это связано с тем, что, во-первых, количество островов, принимающих доминирующих «эмигрантов» с острова ограничено (2−5 островов). Во-вторых, обмен особями односторонен. Поэтому в большой популяции появляться группы островов с различными доминирующими особями. Если популяция имеет небольшой размер, то возможно быстрое мигрирование ложных доминирующих особей.

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

Введение

миграции в островной модели позволяет находить различные особи-доминанты в подпопуляциях, что способствует поддержанию многоо…

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

Для простоты возьмем 4 подпопуляции. Обмен будет происходить каждые 20 поколений, согласно стратегии элитарности будут мигрировать 2 лучшие особи.

Таблица 2.5.3.1. — Сравнение эффективности решения задачи коммивояжера с помощью генетических алгоритмов (с миграциями и без) с эффективными методами решения.

Анализируя табл. 2.5.3.1 легко увидеть, что точность вычислений несколько ухудшается.

Это обусловлено обменом генетической информации между популяциями: появление ложных доминирующих особей в подпопуляциях и вследствие этого попадание в локальные минимумы функции. Сравним так же время выполнения (табл. 2.5.3.2. и рис. 2.5.3.1.). Как видно из полученных данных, время выполнения уменьшилось, но по-прежнему трудоемкость осталась экспоненциальной.

Таблица 2.5.3.2. — Сравнение времени решения задачи коммивояжера с помощью генетических алгоритмов (с миграциями и без) с эффективными методами решения.

Рисунок 2.5.3.1. — Сравнение зависимость времени выполнения генетического алгоритма с и без миграций.

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

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

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

Рисунок 2.5.3.2. — График зависимости времени от числа городов для решения задачи коммивояжера. Набор данных — решение задачи, полученное с помощью эффективных способов.

Сравним так же для 400 городов время выполнения алгоритмов с миграциями и с варьирующимся количеством подпопуляций (рис. 16). Как видно из графика, ощутимый прирост дает уде разделение одной популяции на две, но затем эффективность от увеличения числа подпопуляций падает.

Рисунок 2.5.3.3. — Зависимость времени выполнения генетического алгоритма от числа подпопуляций.