ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ПАРАЛЛЕЛЬНЫХ ГЕНЕТИЧЕСКИХ
АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ ЗАДАЧИ СОЗДАНИЯ
РАСПИСАНИЯ ЗАНЯТИЙ ВУЗА НА БАЗЕ GRID-СИСТЕМЫ
М.Д. Годлевский,
А.А Абабилов
Исследуется эффективность
применения параллельных генетических алгоритмов, выполняемых на Grid-системе, для решения задачи создания расписания занятий вуза. Рассматриваемая задача относится к классу задач многокритериальной оптимизации и является NP-полной. Применение генетических алгоритмов упрощает поддержку многочисленных требований к расписанию и позволяет легко добавлять новые. Рассматривается влияние генетических операторов (отбор, скрещивание и др.) и их настроек на качество полученной популяции. Исследуется эффективность параллельных генетических алгоритмов двух типов – с использованием островной модели и динамических демов. Рассматривается влияние количества процессов на скорость генетического поиска. Определяются условия целесообразности применения генетического алгоритма с динамическими демами для задачи поиска расписания.
Ключевые слова: NP-полные задачи, многокритериальная оптимизация, генетические алгоритмы, параллельные вычисления, Grid-системы, эффективность алгоритмов, составление расписаний.