Page 36 - 4521

1.8 Паралельне виконання ГА
Генетичні алгоритми застосовуються і при паралельних
обчисленнях (Parallel implementations). При цьому формується
декілька популяцій, що живуть окремо. На етапі формування
нового покоління за деяким правилом відбираються особини з
різних популяцій. Популяція, що згенерувала таким чином, в
деяких випадках замінює всі останні. Таким чином, так або
інакше, відбувається міграція особин однієї популяції в інші
популяції. Тому паралельні ГА називають міграціями.

1.8.1 Паралельний ГА
Спершу розглянемо створення простого паралельного
ГА з класичної моделі Холланда. Для цього використовувати-
мемо турнірний відбір. Заведемо N/2 процесів (тут і далі про-
цес розглядається як деяка машина, процесор, який може пра-
цювати незалежно). Кожен з них вибиратиме випадково з по-
пуляції 4 особини, проводити 2 турніри, і переможців схрещу-
вати. Отримані нащадки записуватимуться в нове покоління.
Таким чином, за один цикл роботи одного процесу зміняється
ціле покоління.

1.8.2 Міграція
Модель міграції (Migration) представляє популяцію як
безліч підпопуляцій. Кожна підпопуляція обробляється окре-
мим процесором. Ці підпопуляції розвиваються незалежно
один від одного протягом однакової кількості поколінь T (час
ізоляції). Після закінчення часу ізоляції відбувається обмін
особинами між підпопуляціями (міграція). Кількість особин,
що піддалися обміну (вірогідність міграції), метод відбору осо-
бин для міграції і схема міграції визначає частоту виникнення
генетичного різноманіття в підпопуляціях і обмін інформацією
між популяціями.
Відбір особин для міграції може відбуватися таким чи-
ном:
 випадкова одноманітна вибірка з числа особин;
35