ЭВОЛЮЦИОННЫЙ АЛГОРИТМ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ДИСПЕТЧЕРИЗАЦИИ

Аннотация

Рассмотрена одна из важных задач оптимизации – задача диспетчеризации. Она от- носится к классу NP- сложных оптимизационных задач. В работе приведена и описана постановка задачи диспетчеризации. Здесь массив заявок пользователей на компьютерноеобслуживание в Grid- системах моделируется протяжённой линейной полиэдралью коор- динатных ресурсных прямоугольников. При этом диспетчирование представляется лока- лизацией линейной полиэдрали в оболочку области вычислительно-временных ресурсов сис- темы согласно многоцелевому критерию качества применяемого назначения заявок на об- служивание. В связи со сложностью данной задачи для ее эффективного решения предла- гаются методы эволюционного моделирования. В статье предложена и описана модифи- цированная архитектура эволюционного поиска. В качестве модификации введены допол- нительно три блока. Это блок «внешней среды», блок эволюционной адаптации и блок «не- перспективных решений». Для ее реализации авторами разработан модифицированный эволюционный алгоритм, использующий в качестве отбора решений модели эволюций Ч. Дарвина и Ж. Б. Ламарка. Это позволяет значительно сократить время получения резуль- тата, частично решить проблему преждевременной сходимости алгоритма и получать наборы квазиоптимальных решений за полиномиальное время. Разработан программный модуль на языке C#. Проведен вычислительный эксперимент на тестовых примерах. Про- веденные экспериментальные исследования, показали, что качество решений, полученных на основе разработанного эволюционного алгоритма, в среднем на 5 процентов превосхо- дит результаты решений, полученные с использованием известных алгоритмов последова- тельного, начально-кольцевого и уровневого при сопоставимом времени, что говорит об эффективности предложенного подхода.