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

Острівна модель (англ. island model) — модель паралельного генетичного алгоритму.

Суть моделі

Розіб'ємо популяцію на кілька підпопуляцій. Кожна з них буде розвиватися окремо за допомогою якогось генетичного алгоритму.
Таким чином, можна сказати, що ми розселили особини на кількох ізольованих островах (рис. 1).Зрідка (наприклад, кожні 5 поколінь) відбувається міграція — острова обмінюються кількома хорошими особинами.

Параметри моделі

Острівна модель надає два параметра:

• Розмір міграції — число особин в популяції, що будуть мігрувати;
• Частота міграці — число поколінь між міграціями;

Проблеми налаштування параметрів моделі

Так як населеність островів невелика, то підпопуляціі будуть схильні до передчасної збіжності. Тому важливо правильно встановити частоту та розиір міграції:

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

Переваги «острівної моделі»

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

Джерела

1. Theodore C. Belding. The distributed genetic algorithm revisited. In L. Eshelman, editor, Proc. of the 6th Int'l. Conf. on GAs, pages 114—121. Morgan Kaufmann, 1995.
   
2. Mitchell M. An Introduction to Genetic Algorithms. Cambridge, MA: The MIT Press, 1996.