х подпопуляцій та міграція між ними - є однією з головних характеристик многообщінних ПГА.
Можна припустити, що першим систематичним вивченням паралельних ГА з безліччю популяцій була дисертація Р.Б.Гроссо (Grosso). Його метою було імітувати взаємодію паралельних субкомпонентов еволюціонує популяції. При цьому Гроссо імітував диплоїдних особин (використовувалися дві субкомпоненти для кожного «гена»), і популяція була розділена на 5 громад. Кожна громада обмінювалася індивідуумами з усіма іншими громадами при встановленні фіксованих коефіцієнтів міграції. Експериментальним шляхом Гроссо визначив, що поліпшення середньої ЦФ популяції відбувалося швидше при маленьких громадах, ніж при одиночній популяції. Це підтверджує усталений у генетиці популяцій принцип: сприятливі ознаки поширюються швидше, коли громади маленькі, ніж коли вони великі. Проте він також зауважив, що коли громади були ізольовані, стрімке зростання ЦФ зупинився на меншому значенні, ніж при великій популяції. Іншими словами, якість знайденого рішення до збіжності було гірше в ізольованому випадку, чим в одиночній популяції. При низькому коефіцієнті міграції громади все ще вели себе (працювали) незалежно один від одного і досліджували різні регіони простору пошуку. Мігранти не чинили значного ефекту на поведінку громад, і якість рішень було порівнянним з випадком, коли громади були ізольовані. Однак при середніх коефіцієнтах міграції розділена популяція знайшла рішення, схожі з тими, що знайдені для одиночної популяції. Ці спостереження показують, що мається критичне значення коефіцієнта міграції, нижче якого продуктивність алгоритму утруднюється зважаючи ізоляції громад. Для вищерозміщених значень цього коефіцієнта розділена популяція знаходить вирішення того ж якості, що і звичайна одиночна популяція.
Зазвичай дана модель розробляються для кластерних архітектур, які складаються з декількох незалежних робочих станцій зі своєю локальною пам'яттю. На кожній з таких систем виконується своя копія ГА (побудова нових поколінь популяцій). При цьому генетичні параметри роботи цих алгоритмів повинні дещо відрізнятися один від одного. Це дозволить направити пошук на кожному такому «острові» у відмінному від інших напрямку. Через задану кількість ітерацій острова проводять обмін кращими особинами, що дозволяє коригувати напрямок пошуку для менш вдалих островів.
Ефективність паралельних ГА, побудованих за такою схемою, визначає саме по взаємодії компонент. Можна виділити основні характеристики такого обміну:
- Топологія, яка визначає, які подпопуляціі будуть вважатися сусідніми і, відповідно, між якими островами буде можливий обмін особинами;
- Час ізоляції, яке визначає, скільки епох ГА не проводитиметься міграція;
- Ступінь міграції, яка визначає кількість особин, що беруть участь в міграції;
- Стратегія відбору особин для міграції;
- Стратегія видалення особин з подпопуляціі при проведенні міграції;
- Стратегія реплікації мігруючих особин.
Зауважимо також, що хоча популяції розвиваються незалежно і рівноправно, в реалі-зациях такого виду алгоритмів виділяється сервер, який ініціалізує роботу і реалізує топологію обміну даними. Більш того, синхронізація роботи копій ГА на островах вимагає способу їх взаємодії. Точна і коректна реалізація такої взаємодії різних копій ГА в моделі островів є складним завданням.
Популярність многообщінних паралельни...
