Параллельные ГА

В природе все процессы происходят параллельно и независимо друг от друга. Генетические алгоритмы тоже можно организовать как несколько параллельно выполняющихся процессов, и это увеличит их производительность. Как сделать из классического ГА параллельный? – например, использовать турнирный отбор. Заведем N ⁄ M процессов, каждый из которых может работать независимо в некотором процессоре. Каждый процесс будет выбирать случайно из популяции особи, выявлять победителей, скрещивать, записывать детей в новое поколение. И, в конце концов, проводятся турниры между процессами, ускоряя поиск оптимальных решений.

Островная модель — это тоже модель параллельного генетического алгоритма. Она заключается в следующем: пусть у нас есть 16 процессов и 1600 особей. Разобьем их на 16 подпопуляций по 100 особей. Каждая их них будет развиваться отдельно с помощью некого генетического алгоритма. Таким образом, можно сказать, что мы расселили особи по 16-ти изолированным островам. Изредка (например, каждые 5 поколений) процессы (или острова) будут обмениваться несколькими хорошими особями. Это называется миграция. Она позволяет островам обмениваться генетическим материалом.

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

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