Адаптивный генетический алгоритм с оптимальной рекомбинацией для задачи составления расписаний с учетом расхода энергии
М.Ю. Сахно
Омский филиал Федерального государственного бюджетного учреждения науки Института математики им. С.Л. Соболева Сибирского отделения Российской академии наук, Омск, Россия sosnovskayamy@gmail.com
Ключевые слова: генетический алгоритм, оптимизированный кроссинговер, адаптивная схема, распараллеливаемые работы, энергия, расписание
Страницы: 327-346
Аннотация
В настоящей работе рассматриваются задачи составления расписаний с учетом расхода энергии. Такие задачи возникают в многопроцессорных компьютерных системах и учитывают ресурсные ограничения и возможности распараллеливания. Для этих задач известны алгоритмы жадного и списочного типов с гарантированными оценками точности в худшем случае. В настоящей работе предлагается адаптивный генетический алгоритм с декодировкой решений, основанной на специфике постановок рассматриваемых задач. Его особенностью является то, что в операторе кроссинговера решается задача оптимальной рекомбинации в полной и усеченной версиях. Вызов операторов кроссинговера реализуется адаптивно. Настройка категориальных и числовых параметров выполняется адаптивно современными пакетами. Результаты экспериментального исследования показали статистически значимое преимущество над известными алгоритмами на сериях задач различной структуры.
Наш сайт использует куки. Продолжая им пользоваться, вы соглашаетесь на обработку персональных данных в соответствии с политикой конфиденциальности. Подробнее