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

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

В однопопуляционном подходе параллельно вычисляются только функции пригодности, а генетические операции выполняются централизованно на host-процессоре. Такой подход, очевидно, ориентирован на master-slave парадигму параллельного программирования [0].

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

Существует большое разнообразие параллельных генетических алгоритмов, ориентированных на различные классы параллельных вычислительных систем и на различные критерии качества алгоритмов. Один из известных вариантов классификации параллельных генетических алгоритмов (PGA) приведен на Рис. 1 [0].

 

 

Рис. 1. Классификация параллельных генетических алгоритмов

 

GPGA (Global Parallel Genetic Algorithm) представляет собой однопопуляционный алгоритм. Host-процессор содержит всё поколение в своей памяти и выполняет над ним операции селекции, кроссовера и мутации. Функции пригодности индивидов вычисляются на slave-процессорах. При высокой вычислительной сложности функций пригодности основной проблемой при реализации данного алгоритма является проблема балансировки загрузки slave-процессоров. Очевидно, что рассматриваемый алгоритм ориентирован на MIMD-вычислительные системы [11].

DGA (Distributed Genetic Algorithm) – это многопопуляционный алгоритм, также ориентированный на MIMD-вычислительные системы. В этом случае каждый процессор запускает свой собственный генетический алгоритм на выделенной ему части всей популяции (подпопуляции). Различают два класса распределенных генетических алгоритмов - с наличием механизма обмена подпопуляций индивидами и без этого механизма. В общем случае, при использовании DGA каждый процессор начинает вычисления с разными параметрами генетического алгоритма и с разными наборами генетических операторов. Как следствие, в процессе вычислений подпопуляции будут развиваться в различных направлениях, что гарантирует большое генетическое разнообразие. Отметим, что миграционные процессы между подпопуляции требуют очень аккуратной настройки: при большом количестве индивидов, подлежащих обмену, и высокой частоте обменов генетическое разнообразие подпопуляций нивелируется; наоборот, при малом объеме обменов и низкой их частоте может иметь место преждевременная сходимость внутри подпопуляций.

MPGA (Massively Parallel Genetic Algorithm) называют также Cellular Algorithm (клеточный алгоритм). Данный алгоритм ориентирован на вычислительные машины класса SIMD [11]. В этом случае каждым процессорным элементом в один момент времени обрабатывается один индивид. Индивиды выбирают пару и рекомбинируют со своими непосредственными соседями (северный, южный, восточный, западный).

Hierarchical PGA представляют собой иерархические алгоритмы, в которых на разных уровнях иерархии реализованы разные генетические алгоритмы (рассмотренные выше и другие). Обычно используются 2-х уровневые иерархии: DGA-модель - на верхнем уровне; GPGA- или MPGA-модель – на нижнем уровне.

Hybrid PGA – класс алгоритмов, использующих сочетание параллельных генетических алгоритмов и классических оптимизационных методов.