Боровик В.В.
Донецький національний технічний університет
Загальна постановка проблеми
Останнім часом з розвитком комп'ютерної техніки і з її зростаючими обчислювальними можливостями, постало питання про ефективне використання обчислювальної потужності даної техніки. При використанні багатоядерних систем необхідно ефективно використовувати механізми розпаралелювання процесів для найбільш продуктивного використання обчислювальних потужностей.
Генетичні алгоритми (ГА) є підкласами більш загальної групи методів, званими еволюційними алгоритмами, які об'єднують різні варіанти використання еволюційних принципів. Дані алгоритми застосовуються для вирішення різних завдань, зокрема, для вирішення проблем пошуку та оптимізації. У відмінності від інших технологій оптимізації ГА містять популяцію пробних рішень, які конкурентно управляються за допомогою певних операторів. ГА притаманне итеративное навчання популяції індивідів.
Потужність генетичних алгоритмів посилюється із застосуванням розподілених обчислень. Такі алгоритми називаються - паралельними генетичними алгоритмами, вони засновані на розбитті популяції на кілька окремих подпопуляцій, кожна з яких буде, незалежно від інших подпопуляцій, оброблятися ГА. Крім того, різноманітні міграції індивідів породжують обмін генетичним матеріалом серед популяцій, які, як правило, покращують точність і ефективність алгоритму.
Класи паралельних генетичних алгоритмів
У теперішній час виділяють три основних типи паралельних генетичних алгоритмів (ПГА):
- Глобальні однопопуляціонние ПГА, модель «господар-раб» (Master-Slave GAs);
- Однопопуляціонние ПГА (Fine-Grained GAs);
- Многопопуляціонние ПГА (Coarse-Grained GAs).
Модель «господар-раб» характеризується тим, що в алгоритмах такого типу селекція
бере до уваги цілу популяцію, на відміну від двох інших моделей. Також варто відзначити те, що можливе випадкове схрещування, тобто будь-які два індивіда можуть схрещуватися, в інших моделях схрещування обмежується строго певним набором індивідуумів.
В алгоритмах другого класу існує головна популяція, але оцінка цільової функції розподілена серед декількох процесорів. Господар зберігає популяцію, виконує операції ГА і розподіляє індивідууми між підлеглими. Вони ж лише оцінюють ЦФ індивідуумів. Однопопуляціонние ГА придатні для масових паралельних комп'ютерів і складаються з однієї популяції. Селекція і схрещування обмежені відносинами близького споріднення. Даний клас ПГА може бути ефективно реалізований на паралельних комп'ютерах.
Третій клас - многопопуляціонние ГА складніша модель, так як вона складається з декількох подпопуляцій, які періодично, за встановленими правилами, обмінюються індивідуумами. Такий обмін індивідуумами називається міграцією і управляється кількома параметрами. Многообщінние ГА дуже популярні, але достатні складні як для розуміння так і для реалізації, тому що наслідки від ефекту міграції, на даний момент, не повністю досліджені. Водночас многообщінние ГА мають схожість з «острівної моделлю» в популяційної генетики, яка розглядає відносно ізольовані громади; тому паралельні ГА в деяких випадках називають «острівними» паралельними ГА.
Острівна модель
Використання невеликого числа відносно велики...
