ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ПАРАЛЛЕЛЬНЫХ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ ЗАДАЧИ СОЗДАНИЯ РАСПИСАНИЯ ЗАНЯТИЙ ВУЗА НА БАЗЕ GRID-СИСТЕМЫ

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

Исследуется эффективность применения параллельных генетических алгоритмов, выполняемых на Grid-системе, для решения задачи создания расписания занятий вуза. Рассматриваемая задача относится к классу задач многокритериальной оптимизации и является NP-полной. Применение генетических алгоритмов упрощает поддержку многочисленных требований к расписанию и позволяет легко добавлять новые. Рассматривается влияние генетических операторов (отбор, скрещивание и др.) и их настроек на качество полученной популяции. Исследуется эффективность параллельных генетических алгоритмов двух типов – с использованием островной модели и динамических демов. Рассматривается влияние количества процессов на скорость генетического поиска. Определяются условия целесообразности применения генетического алгоритма с динамическими демами для задачи поиска расписания.

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