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

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

Генетические алгоритмы применяются и при параллельных вычислениях (parallel implementations).

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

При этом популяция разделяется на блоки, над каждым из которых работает отдельный поток.

Однако, такой подход не очень удобен в программировании.

Наиболее часто применимой является модель миграции (Migration). Модель миграции представляет популяцию как множество подпопуляций. Каждая подпопуляция обрабатывается отдельным процессором. Эти подпопуляции развиваются независимо друг от друга в течение одинакового количества поколений T (время изоляции). По истечении времени изоляции происходит обмен особями между популяциями (миграция, «воровство невест»). Количество особей, подвергшихся обмену (вероятность миграции), метод отбора особей для миграции и схема миграции определяет частоту возникновения генетического многообразия в подпопуляциях и обмен информацией между подпопуляциями.

Отбор особей для миграции может проходить следующим образом:

• — случайная однообразная выборка из числа особей;
• — пропорциональный отбор: для миграции берутся наиболее пригодные особи.

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

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

Рисунок 2.5.1.1 — Миграция с топологией полной сети.

Другая основная миграционная схема имеет топологию кольца (рис. 2.5.1.2.). Здесь особи передаются между соседними (по направлению обхода) популяциями. Таким образом, особи из одной подпопуляции могут мигрировать только в одну — соседнюю популяцию.

Рисунок 2.5.1.2. — Миграция с топологией кольца.

Существует стратегия миграции, объединяющая первую и вторую модель, так же она позволяет разрешить коллизии первой модели. Как и при топологии кольца, миграция осуществляется только между ближайшими соседями, однако миграция в этой модели так же возможна между «крайними» подпопуляциями (тороидальные краевые миграции). [7].