Дослідження ефективності паралельних генетичних алгоритмів для вирішення задачі створення розкладу занять вузу на базі Grid-системи

М.Д. Годлевський, О.О. Абабілов

Досліджується ефективність застосування паралельних генетичних алгоритмів, що виконуються на Grid-системі, для вирішення задачі створення розкладу занять вузу. Задача, що розглядається, відноситься до класу задач багатокритеріальної оптимізації та є NP-повною. Застосування генетичних алгоритмів спрощує підтримку численних вимог до розкладу та дозволяє легко додавати нові. Розглядається вплив генетичних операторів (відбір, схрещування та ін.) та їхніх налаштувань на якість отриманої популяції. Досліджується ефективність паралельних генетичних алгоритмів двох типів – із використанням острівної моделі та динамічних демів. Розглядається вплив кількості процесів на швидкість генетичного пошуку. Визначаються умови доцільності застосування генетичного алгоритму із динамічними демами для задачі пошуку розкладу.

Ключові слова: NP-повні задачі, багатокритеріальна оптимізація, генетичні алгоритми, паралельні обчислення, Grid-системи, ефективність алгоритмів, складання розкладів.