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

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

 

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

Эта модель разбивает популяции решения на множество подпопуляций. Эти популяции функционируют независимо друг от друга. Некоторое число поколений по достижению времени обмена производит обмен между подпопуляциями, при этом задаются:

1. Число обмениваемых особей и называется это миграционная степень.

2. Метод отбора особей для миграции.

3. Схема миграции, которая определяет способ обмена между подпопуляциями. Выбор особей для миграции может осуществляться несколькими методами, как и отбор родителей.

а.) однородный отбор – случайный выбор особи;

б.) пропорционально значению целевой функции;

в.) линейное ранжирование.

Существуют несколько стандартных схем обмена отобранными особями между подпопуляциями:

 

1. Каждая популяция обменивается с каждой из остальных подпопуляций

 

Это общая схема обмена, при этом особи могут непосредственно мигрировать от одной подпопуляции к другой. Для каждой подпопуляции формируется Pop-множество потенциальных эмигрантов из других подпуляций. Из него по определенному закону выбираются эмигранты для данной подпопуляции.

 

2. Обмен по кольцу – особи могут мигрировать только в одну соседнюю популяцию.

 

 

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

Глобальная модель «Рабочий – хозяин»

Модель выполняется по следующему закону:

 

 

Диффузная модель

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

В процессе поиска возникает и эволюционные виртуальные острова, т.е. сменные области особей с приблизительно одинаковыми значениями целевой функции.

Рис. Виртуальные острова вследствие диффузии информации.

 

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

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