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

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

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

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

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

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

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

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

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

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

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

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

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

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

Модель диффузии, или островная модель ГА.

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

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

Введение миграций в островной модели позволяет находить различные особи-доминанты в подпопуляциях, что способствует поддержанию многообразия в популяции. Каждую подпопуляции можно принять за остров. Во время миграции подпопуляции обмениваются своим доминирующим генетическим материалом. При частой миграции большого количества особей происходит перемешивание генетического материала. Тем самым устраняются локальные различия между островами. Очень редкие миграции не позволяют предотвратить преждевременную сходимость алгоритма в маленьких подпопуляциях. В рассматриваемой модели с каждого острова миграции могут происходить лишь на определенное расстояние: 2-5 острова в зависимости от количества подпопуляции. Таким образом, каждый остров оказывается почти изолированным. Количество островов, на которые могут мигрировать особи одной подпопуляции, называют расстоянием изоляции. Следует заметить, что взаимные миграции исключены (рис. 5).

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