ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ СЕВЕРО-КАВКАЗСКИЙ РЕГИОН. 2021; 2: 5-9
http://dx.doi.org/10.17213/1560-3644-2021-2-5-9
ИССЛЕДОВАНИЕ ПРИМЕНЕНИЯ МНОГОТОЧЕЧНОГО КРОССОВЕРА ПРИ РЕШЕНИИ НЕОДНОРОДНОЙ МИНИМАКСНОЙ ЗАДАЧИ БОЛЬШОЙ РАЗМЕРНОСТИ
Кобак Валерий Григорьевич – д-р техн. наук, профессор, кафедра «Программное обеспечение вычислительной техники и автоматизированных систем», Донской государственный технический университет, г. Ростов-на-Дону, Россия. E-mail: valera33305@mail.ru
Поркшеян Виталий Маркосович – канд. физ.-мат. наук, доцент, кафедра «Математика», Донской государственный технический университет, г. Ростов-на-Дону. E-mail: spu-46@donstu.ru
Жуковский Александр Георгиевич – д-р полит. наук, профессор, канд. техн. наук, доцент, кафедра «Программное обеспечение вычислительной техники и автоматизированных систем», Донской государственный технический университет, г. Ростов-на-Дону, Россия. E-mail: zhykovskij@mail.ru
Кузин Александр Павлович – ст. преподаватель, кафедра «Программное обеспечение вычислительной техники и автоматизированных систем», Донской государственный технический университет, Ростов-на-Дону. E-mail: alexpavkuzin@gmail.com
Аннотация
Рассматривается проблема решения неоднородной минимаксной задачи, характерной для теории расписаний. Данная задача является NP-полной и для нее не существует точного алгоритма решения, имеющего полиномиальное время для задач большой размерности. Поэтому используются быстрые алгоритмы, которые в самом общем случае получают приближенные значения. В качестве возможного метода решения данной задачи рассматривается генетическая модель, представляющая собой модифицированную модель Голдберга. Модифицированная модель Голдберга рассматривается со смешанным кроссовером и наиболее перспективной мутацией. Так как аналитически произвести расчеты крайне затруднительно и на практике зачастую невозможно, то в данной работе был проведен вычислительный эксперимент для матриц большой размерности (больше 1000 элементов распределения).
Результаты проведенного эксперимента описываются в таблицах, в которых наглядно показано сравнение эффективности работы модифицированной модели Голдберга при использовании смешанного кроссовера. Сравнение проводится на основе оценки точности полученных результатов, для матриц большой размерности, при базовых параметрах генетического алгоритма. Показывается, что применение смешанного кроссовера приводит к результатам, более приближенным к оптимальному значению, несмотря на ухудшение временных характеристик поиска решения.
Ключевые слова: многоточечный кроссовер; смешанный кроссовер; генетический алгоритм; модифицированная модель Голдберга; мутация; минимаксная задача; теория расписаний; лучшая особь; особь; поколение.
Полный текст: [in elibrary.ru]
Ссылки на литературу
1. Алексеев О.Т. Комплексное применение методов дискретной оптимизации. М.: Наука, 1987. 250 с.
2. Кобак В.Г., Жуковский А.Г., Кузин А.П. Исследование применения одноточечного кроссовера при решении неоднородной минимаксной задачи // Электронный научный журн. «Инженерный вестник Дона». 2018. № 1.
3. Кобак В.Г., Жуковский А.Г., Кузин А.П. Исследование модификаций турнирного отбора при решении неоднородной минимаксной задачи, модифицированной моделью Голдберга // Электронный научный журн. «Инженерный вестник Дона». 2018. № 2.
4. Кобак В.Г., Жуковский А.Г., Кузин А.П. Применение гибридного алгоритма при решении неоднородной минимаксной задачи с использованием сильных мутаций // Электронный научный журн. «Инженерный вестник Дона». 2018. № 4.
5. Кобак В.Г., Жуковский А.Г., Золотых О.А., Ростов А.Н. Решение однородной минимаксной задачи различными модификациями алгоритма Крона // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2016. № 3. С. 3 – 8. DOI:10.17213/0321-2653-2016-3-3-8
6. Щербинина Н.И., Кобак В.Г., Жуковский А.Г. Исследование поколенческой стратегии при решении однородной и неоднородной минимаксной задачи различными модификациями генетического алгоритма // Изв. вузов.
Сев.-Кавк. регион. Техн. науки. 2016. № 4. С. 3 – 10. DOI: 10.17213/0321-2653-2016-4-3-10
7. Кобак В.Г., Жуковский А.Г., Золотых О.А., Ростов А.Н. Различные подходы к решению однородной минимаксной задачи теории расписаний эвристическими алгоритмами // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2016. № 1. С. 41 – 46. DOI: 10.17213/0321-2653-2016-1-41-46
8. Коновалов И.С., Кобак В.Г., Фатхи В.А. Применение генетического алгоритма для решения задачи покрытия множеств // Вестн. Донского гос. техн. ун-та. 2016. № 3. С. 125 – 132. DOI: 10.12737/20225
9. Кобак В.Г., Титов Д.В., Калюка В.И., Слесарев В.В. Алгоритмическое улучшение генетического алгоритма для нечетного количества однородных устройств // Изв. ЮФУ. Техн. науки. 2011. № 5. С. 159 – 163.
10. Кобак В.Г., Титов Д.В., Калюка В.И., Золотых О.А. Исследование эффективности генетических алгоритмов распределения для однородных систем // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2011. № 3. С. 19 – 22.