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

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

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

В похожем параллельном ГА Пети, Леуза и Грефенстетта (Pettey, Leuze и Grefenstette) [9], копия лучшего индивидуума, найденного в каждой общине, посылается всем его соседям после каждого поколения. Цель этой коммуникации состояла в обеспечении хорошего перемешивания индивидуумов. Как и Гроссо, авторы этой статьи указывают, что параллельные ГА с высоким уровнем коммуникации находят решения того же качества, что и последовательный ГА с большой одиночной популяцией. Эти наблюдения вызывают другие вопросы, которые не разрешены до сих пор.

• · Какой уровень связей необходим, чтобы параллельные ГА не вели себя подобно последовательным ГА?
• · Какова стоимость этих связей?
• · Актуальна ли разработка параллельных ГА при высокой стоимости взаимосвязей?

Для ответа на эти вопросы необходимо большое количество исследований, чтобы понять влияние эффекта миграции на качество поиска в параллельных ГА Все эти важные наблюдения были сделаны достаточно давно, когда другие систематические исследования параллельных ГА только начинались. Например, Танезе (Tanese) [10] предложил параллельный ГА с общинами, соединенными в топологии 4D-гиперкуба. В этом алгоритме миграция совершается в фиксированные интервалы между процессами в направлении одного измерения гиперкуба. Мигранты были выбраны вероятностным путем из лучших индивидуумов в подпопуляции, и они замещали худшие индивидуумы в популяцииприемнике. Сам Танезе провел три серии экспериментов. В первой серии интервал между миграциями был установлен в 5 поколений, и число процессоров изменялось. В тестах с двумя коэффициентами миграции и варьированием числа процессоров параллельный ГА нашел результаты того же качества, что и последовательный ГА. Однако, по экспериментальным результатам, трудно сделать вывод, наше ли параллельный ГА решения быстрее, чем последовательный ГА, потому что диапазон времен слишком большой. Во втором серии экспериментов Танезе изменял коэффициенты мутации и кроссинговера в каждой общине, пытаясь найти значения параметров, чтобы сбалансировать разнообразие и результативность. В третьей серии экспериментов изучалось влияние частоты обмена при поиске; ее результаты показали, что слишком частые или, напротив, слишком редкие миграции ухудшают производительность алгоритма.

В свою очередь, Кохун (Cohoon), Хедж (Hedge), Мартин (Martin) и Ричардс (Richards) отметили определенное сходство между эволюцией решений в параллельном ГА и теорией периодически нарушаемого равновесия (тип эволюции, при котором длительный период равновесия периодически нарушается кратким периодом бурного развития) [11]. Эта теория была предложена Элдриджем и Гоулдом (Eldredge и Gould) для объяснения отсутствующих связей в устаревшей записи. В соответствии с ней, большую часть времени популяции находятся в равновесии (т.е. не происходит никаких значительных изменений в их генетической структуре), однако изменения окружающей среды могут привести к стремительным эволюционным изменениям. При этом важным компонентом среды популяции выступает ее собственная структура, потому что особи (агенты) в популяции соперничают (конкурируют) с другими особями за ресурсы. Поэтому прибытие особей из других популяций может нарушить равновесие и инициировать новые эволюционные процессы. По результатам экспериментов с параллельными ГА Кохун и др. отметили, что даже при достаточно низких значениях коэффициента миграции новые решения были найдены за более короткое время (после обмена особями).

Кохун и соавторы использовали задачу линейного размещения в качестве бенчмарок и проводили эксперименты с вариантами соединения общин, используя различную топологию сети. При этом они указали, что выбор топологии не очень сильно влияет на производительность параллельного ГА до тех пор, пока он имеет «высокую связность и маленький диаметр для обеспечения адекватного «смешивания». Заметим, что сеть, которую они выбрали, является сильно связанной и имеет маленький диаметр (, где r — количество общин).

Позднее эта же группа специалистов расширила область исследований, используя приложение СБИС (задача разбиения графа) на топологии 4D-гиперкуба [12, 13]. Как и в топологии сети, узлы гиперкуба имеют 4 соседа, но диаметр гиперкуба меньше, чем сети (log2r).

Рассмотренные примеры многообщинных параллельных ГА позволяют указать некоторые причины, которые делают эти алгоритмы такими популярными:

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