ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ СЕВЕРО-КАВКАЗСКИЙ РЕГИОН. 2022; 2: 5-11
http://dx.doi.org/10.17213/1560-3644-2022-2-5-11
ИСПОЛЬЗОВАНИЕ МОДИФИЦИРОВАННОЙ МОДЕЛИ ГОЛДБЕРГА ПРИ РЕШЕНИИ НЕОДНОРОДНОЙ МИНИМАКСНОЙ ЗАДАЧИ С ПОВТОРАМИ И СИЛЬНЫМИ МУТАЦИЯМИ
Кобак Валерий Григорьевич – д-р техн. наук, профессор, кафедра «Программное обеспечение вычислительной техники и автоматизированных систем», valera33305@mail.ru
Цеменко Олег Игоревич – студент, кафедра «Программное обеспечение вычислительной техники и автоматизированных систем».
Аннотация
Рассмотрено влияние сильных мутаций для формирования начальных поколений при повторах, с целью получения улучшенных результатов, по сравнению со случайным формированием начального поколения. Сама минимаксная задача из теории расписания входит в разряд NP-полных, для которой до сих пор не найден точный алгоритм решения за полиноминальное время для больших размерностей. Существуют различные способы решения задачи, например эвристические методы, генетический подход, динамическое программирование, точные решения или гибридные алгоритмы. В данной работе разобран получивший широкое распространение генетический подход, а именно – модифицированная модель Голдберга, в которой применяется принцип скрещивания каждой особи, а также мутации потомства и принцип турнирного отбора. Для решения задачи разработано программное средство, позволяющее указать размерность задачи, задать количество повторов и процент сильной мутации. Полученные результаты представлены в виде таблиц для более наглядного восприятия результатов программы, и сделан вывод, как сильные мутации влияют на полученные результаты.
Ключевые слова: неоднородная задача, теория расписания, NP-полная задача, генетический алгоритм, модифицирован-ная модель Голдберга, минимаксный критерий, классическое скрещивание, основной предок, классическая мутация, сильная мутация, повторы, турнирный отбор
Полный текст: [in elibrary.ru]
Ссылки на литературу
- Конвей Р.В. Теория расписаний / Р.В. Конвей, В.Л. Максвелл, Л.В. Миллер. М.: Наука, 1975. 359 с.
- Алексеев О.Т. Комплексное применение методов дискретной оптимизации. М.: Наука, 1987. 250 с.
- Каширина И.Л. Введение в эволюционное моделирование. Воронеж, 2007. 40 с.
- Goldberg D. Genetic Algorithms In Search, Optimization, and Machine Learning. USA: Addison-Wesley Publishing Company, Inc., 1989. pp. 28–33.
- Кобак, В.Г. Повышение эффективности генетического алгоритма на базе модели Голденберга за счет применения элиты / В. Г. Кобак [и др.] // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2014. № 3. С. 12–15.
- Кобак В.Г., Жуковский А.Г., Кузин А.П. Исследование применения одноточечного кроссовера при решении неоднородной минимаксной задачи // Инженерный вестн. Дона, 2018, №1. URL: ivdon.ru/ru/magazine/archive/n1y 2018/4714
- Кобак В.Г., Поркшеян В.М., Кузин А.П. Использование различных вариантов мутации при решении неоднородной минимаксной задачи модифицированной моделью Голдберга // Научно-практический журнал «Аспирант». 2017. № 10. С. 26–29.
- Кобак В.Г., Жуковский А.Г., Кузин А.П., Исследование модификаций турнирного отбора при решении неоднородной минимаксной задачи модифицированной моделью Голдберга // Инженерный вестн. Дона. 2018. № 2. URL: ivdon.ru/ru/magazine/archive/N2y2018/496
- Панченко Т.В. Генетические алгоритмы. Астрахань: Астраханский университет, 2007.
- Кобак В.Г., Жуковский А.Г., Кузин А.П. Применение гибридного алгоритма при решении неоднородной минимаксной задачи с использованием сильных мутаций // Инженерный вестн. Дона. 2018. № 4. URL: ivdon.ru/ru/ magazine/archive/n4y2018/5396