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

Боровик В.В.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эффективность параллельных ГА, построенных по такой схеме, определяет именно по взаимодействию компонент. Можно выделить основные характеристики такого обмена:

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

- время изоляции, которое определяет, сколько эпох ГА не будет производиться миграция;

- степень миграции, которая определяет количество особей, участвующих в миграции;

- стратегия отбора особей для миграции;

- стратегия удаления особей из подпопуляции при проведении миграции;

- стратегия репликации мигрирующих особей.

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

Популярность многообщинных параллельных ГА объясняется тем что :

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

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

НОВАЯ ТЕОРЕТИЧЕСКАЯ МОДЕЛЬ КУРЕЙЧИКА В.М.

Суть данной модели заключается в том ,что автор (Курейчик В.М.) предлагает новую систему обмена особями, которая будет иметь довольно гибкую структуру. Автор представляет данную модель как структуру типа «звезда», которая взаимодействует с популяциями через буфер хромосом .Заранее определяется механизм регулирования размера буфера. Буфер заполняется в процессе работы . Весь данный процесс разбивают на два этапа:

1.Формируются все популяции, которые запускаются на выполнение в асинхронном режиме.

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

Каждая популяция эволюционирует отдельно от других. На каждой итерации проверяется условие необходимости миграции. Таковым условием может быть интервал итераций, вырожденность популяции и т.п. Если условие наступило, происходит миграция хромосом особей с буфером хромосом.

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

Достоинство этой модели заключается в большой гибкости, которая позволяет провести исследования различных стратегий и критериев работы параллельных генетических алгоритмов.

Основные проблемы

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

Выделим основные проблемы :

Выбор или разработка стратегии взаимодействия составных частей алгоритма.

Выбор частоты миграций между популяциями.

Определение мигрируемых особей и их количества.

Определение структуры эволюции отдельных популяций.

Рассмотрим каждую проблему более подробно. Топология сети – это важный фактор в производительности параллельного алгоритма, потому что она определяет, как быстро (или как медленно) хорошее решение распространяется в другие популяции. Если сеть является сильно связной, то хорошие решения будут быстро распространяться во все общины и могут быстро «насытить» популяцию. С другой стороны, если сеть слабо связная, решения будут распространяться медленнее и общины будут более изолированными друг от друга . Может происходить дальнейшее параллельно развитие и рекомбинация различных решений для получения потенциально лучших решений.

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

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

Частота миграций также имеет большое влияние на конечное решение. Как известно, слишком частые миграции приводят к вырождению популяций, а редкие, наоборот, к снижению сходимости. Для регулирования частоты миграции применяются различные методы, которые можно разбить на два типа: адаптивные и событийные. В первом случае методы адаптации используются для настройки частоты миграции в процессе работы алгоритма. Во втором случае применяются методы, определяющие необходимость миграции, т.е. миграция осуществляется только при наступлении какого-либо события.

Для отбора особей для миграции применяются механизмы селекции. Известно ,что отдельные хромосомы могут содержать «хорошие» фрагменты генетического кода, но данные части могут находиться в хромосомах, которые отличаются плохой приспособленностью. Но в то же время, исключение подобных может привести к тому ,что произойдет преждевременная сходимость ,либо пропуск глобального оптимума.

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

Вывод

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

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

Список литературы

Курейчик В.М., Кныш Д.С. Параллельный генетический алгоритм. Модели и проблемы построения // -С.1-3.

2. Интернет-ресурс. - Режим доступа : www/ URL: http://www.gotai.net/ - сайт по ИИ.

3. Гладков Л.А., Курейчик В.М., Курейчик В.В. Генетические алгоритмы [Текст]/под ред. В.М. Курейчика . – 2-е издн., испр. и доп. – М.:ФИЗМАТЛИТ ,2006 .-320 с.

4. Иванов Д.Е., Чебанов П.А. Взаимодействие компонент в распределённых генетических алгоритмах генерации тестов / Д.Е. Иванов, П.А. Чебанов // Наукові праці Донецького національного технічного університету. Серія: “Обчислювальна техніка та автоматизація”. Випуск 16(147).- Донецьк: ДонНТУ.- 2009.- С.121-127.

5. Grosso P.B. Computer Simulations of Genetic Adaptation: Parallel Subcomponent Interaction in a Multilocus Model// Unpublished doctoral dissertation, The University of Michigan. (University Microfilms №8520908), 1985.