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

Боровик В.В.

Донецкий национальный технический университет

Общая постановка проблемы

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

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

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

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

В настоящие время выделяют три основных типа параллельных генетических алгоритмов (ПГА) :

- глобальные однопопуляционные ПГА, модель «хозяин-раб» (Master-Slave GAs);

- однопопуляционные ПГА (Fine-Grained GAs);

- многопопуляционные ПГА (Coarse-Grained GAs).

Модель «хозяин-раб» характеризуется тем, что в алгоритмах такого типа селекция

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

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

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

Островная модель

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

Можно предположить , что первым систематическим изучением параллельных ГА с множеством популяций была диссертация Р.Б.Гроссо (Grosso). Его целью было имитировать взаимодействие параллельных субкомпонентов эволюционирующей популяции. При этом Гроссо имитировал диплоидных особей (использовались две субкомпоненты для каждого «гена»), и популяция была разделена на 5 общин. Каждая община обменивалась индивидуумами со всеми другими общинами при установлении фиксированных коэффициентов миграции. Экспериментальным путем Гроссо определил, что улучшение средней ЦФ популяции происходило быстрее при маленьких общинах, чем при одиночной популяции. Это подтверждает устоявшийся в генетике популяций принцип: благоприятные признаки распространяются быстрее, когда общины маленькие, чем когда они большие. Однако он также заметил, что когда общины были изолированы, стремительный рост ЦФ остановился на меньшем значении, чем при большой популяции. Другими словами, качество найденного решения до сходимости было хуже в изолированном случае, чем в одиночной популяции. При низком коэффициенте миграции общины все еще вели себя (работали) независимо друг от друга и исследовали различные регионы пространства поиска. Мигранты не оказывали значительного эффекта на поведение общин, и качество решений было сопоставимым со случаем, когда общины были изолированы. Однако при средних коэффициентах миграции разделенная популяция нашла решения, схожие с теми, что найдены для одиночной популяции. Эти наблюдения показывают, что имеется критическое значение коэффициента миграции, ниже которого производительность алгоритма затрудняется ввиду изоляции общин. Для вышележащих значений этого коэффициента разделенная популяция находит решения того же качества, что и обычная одиночная популяция.

Обычно данная модель разрабатываются для кластерных архитектур, которые состоят из нескольких независимых рабочих стан

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать