Подход к уменьшению времени работы модифицированной модели Голдберга при решении неоднородной минимаксной задачи

Аннотация

Кобак В.Г., Жуковский А.Г., Кузин А.П, Тхазаплижева А.Н.

Дата поступления статьи: 19.03.2019

В статье рассматривается проблема решения неоднородной минимаксной задачи, характерной для теории расписаний. Данная задача является NP-полной и для нее не существует точного алгоритма решения, имеющего полиномиальное время для задач большой размерности. В качестве метода решения данной задачи рассматривается модифицированная модель Голдберга. Модель Годберга рассматривается с несколькими кроссоверами и наиболее эффективной мутацией. При определенных параметрах (большое количество особей и повторов) модифицированная модель Голдберга получает решение за достаточно долгое время, поэтому в статье подробно анализируется один из подходов по уменьшению времени работы без потери точности. Так как аналитически произвести расчеты крайне затруднительно и практически невозможно в работе был поставлен вычислительный эксперимент. В результате вычислительного эксперимента, в таблицах приводится сравнение эффективности работы модифицированной модели Голдберга после применения HT технологии. Применение HT технологии приводит к существенному уменьшению временных затрат. Статья опубликована в рамках реализации программы Международного Форума «Победный май 1945 года».

Ключевые слова: одноточечный кроссовер, двухточечный кроссовер генетический алгоритм, модифицированная модель Голдберга, мутация, минимаксная задача, теория расписаний, особь, поколение, hyper-threading

05.13.01 - Системный анализ, управление и обработка информации (по отраслям)

05.13.18 - Математическое моделирование, численные методы и комплексы программ

`