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

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

Простейший параллельный ГА.

Рассмотрим создание простейшего параллельного ГА из классической модели Холланда. Для этого будем использовать турнирный отбор. Заведем N/2 процессов (под процессом подразумевается некоторая машина, процессор, который может работать независимо). Каждый из них будет выбирать случайно из популяции 4 особи, проводить 2 турнира, и победителей скрещивать. Полученные потомки будут записываться в новое поколение. Таким образом, за один цикл работы одного процесса будет сменяться целое поколение.

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

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

• случайная однообразная выборка из числа особей;

• пропорциональный отбор: для миграции берутся наиболее пригодные особи.

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

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

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

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

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

Алгоритм «Рабочий и Хозяин» (Global model - worker/farmer) реализуется с применением нескольких одновременно работающих компьютеров (см. схему 5). Среди всех компьютеров выделяют «Хозяина» и «Рабочих». Компьютеры - «Рабочие» отвечают за процессы воспроизводства, мутации и вычисления функции пригодности особей для их отбора в новое поколение. Все созданные и оцененные «Рабочими» особи поступают к компьютеру - «Хозяину», который затем проводит отбор особей согласно оценке их пригодности в новую популяцию. Отобранные особи передаются «Хозяином» к компьютерам - «Рабочим».