Исследование модифицированной модели Уитли с различным количеством и различными методами формирования элитных особей

Введение. Представлен сравнительный анализ решений модифицированной модели Уитли при различных способах формирования элитных особей. В данном исследовании для формирования элитных особей используются алгоритмы Крона и Плотникова-Зверева. Целями работы являлись разработка модифицированной модели Уитли с применением алгоритмов Крона и Плотникова-Зверева для формирования элитных особей, а также программного средства для решения задачи теории расписаний. Необходимо было получить лучшее решение этой задачи при различных исходных данных с последующей обработкой результатов и выявлением модификации модели Уитли. Описана задача, которая подразумевает поиск оптимального распределения работ по процессорам с минимизацией максимального времени выполнения работ.

Материалы и методы. Приведено описание всех алгоритмов, которые были реализованы при разработке программного средства решения задачи оптимизации построения расписания. Разработаны следующие алгоритмы: модифицированная модель Уитли, применение стратегии элитизма, алгоритм Крона, алгоритм Плотникова-Зверева.

Результаты исследования. Разработано программное средство, с помощью которого проведён вычислительный эксперимент при различных исходных данных, с использованием одной, двух, трёх и четырёх элитных особей. Вычислительный эксперимент проведён для наиболее распространённых наборов данных при различном количестве элитных особей. Каждая модификация модели Уитли запускалась сто раз с каждым набором исходных данных. В результате сравнительного анализа было выявлено, какое влияние оказывает использование рассмотренных стратегий элитизма в разработанных модификациях генетического алгоритма (модели Уитли) на точность решения однородной минимаксной задачи при различном количестве элитных особей.

Обсуждение и заключения. Определены лучшие результаты работы алгоритмов, выявлена эффективность применения элитизма в модифицированной модели Уитли при решении однородной минимаксной задачи теории расписаний. Проведено сравнение результатов работы алгоритма при одной, двух, трёх и четырёх элитных особях.

1. Алгоритмы: построение и анализ / Т. Кормен [и др.]. — Москва : Вильямс, 2013. — 1328 с.

2. Гладков, Л. А. Генетические алгоритмы / Л. А. Гладков, В. В. Курейчик, В. М. Курейчик. — Москва: Физматлит, 2006. — 320 с.

3. Емельянов, В. В. Теория и практика эволюционного моделирования / В. В. Емельянов, В. В. Курейчик, В. М. Курейчик. — Москва : Физматлит, 2003. — 432 с.

4. Чернышев, Ю. О. Адаптивный генетический алгоритм для решения задач оптимизации на основе стратегии элитизма / Ю. О. Чернышев, А. Ю. Полуян // Известия Южного Федерального университета. Технические науки. — 2008. — № 4 (81). — С. 36–39.

5. Whitley, D. A genetic algorithm tutorial / Computer science department, Colorado State University. — Режим доступа: https://www.cs.colostate.edu/pubserv/pubs/Whitley-genitor-MiscPubs-tutorial.pdf (дата обращения: 20.10.2017).

6. Пантелеев, А. В. Методы глобальной оптимизации. Метаэвристические стратегии и алгоритмы / А. В. Пантелеев, Д. В. Метлицкая, Е. А. Алешина. — Москва : Вузовская книга, 2013. — 244 с.

7. Пантелеев, А. В. Применение эволюционных методов глобальной оптимизации в задачах оптимального управления детерминированными системами / А. В. Пантелеев. — Москва : Издательство МАИ, 2013. — 160 с.

8. Кобак, В. Г. Исследование алгоритма Крона и его модификации при различных исходных данных / В. Г. Кобак, Д. В. Титов, О. А. Золотых // Вестник Дон. гос. техн. ун-та. — 2012. — № 8 (69). — С. 62–67.

9. Кобак, В. Г. Использование алгоритма Крона для формирования элит при решении однородной минимаксной задачи моделью Голдберга / В. Г. Кобак, О. А. Золотых, А. Ю. Гущин // Символ науки. — 2016. №4–3(16). — С. 79–83.

10. Кобак, В. Г. Перспективные алгоритмы решения неоднородной распределительной задачи теории расписаний / В. Г. Кобак, Д. Г. Красный, Р. А. Нейдорф // Известия Южного Федерального университета. Технические науки. — 2008. — № 9 (86). — С. 152–156.