Preview

Вестник Донского государственного технического университета

Расширенный поиск

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

https://doi.org/10.23947/1992-5980-2018-18-2-223-229

Полный текст:

Аннотация

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

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

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

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

Об авторах

Н. С. Кривошей
Донской государственный технический университет
Россия

Кривошей Наталия Сергеевна, аспирантка кафедры «Программное обеспечение вычислительной техники и автоматизированных систем» 

344000, г. Ростов-на-Дону, пл. Гагарина, 1



В. Г Кобак
Донской государственный технический университет
Россия

Кобак Валерий Григорьевич, доктор технических наук, профессор кафедры «Программное обеспечение вычислительной техники и автоматизированных систем» 

344000, г. Ростов-на-Дону, пл. Гагарина, 1



Список литературы

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.


Для цитирования:


Кривошей Н.С., Кобак В.Г. Исследование модифицированной модели Уитли с различным количеством и различными методами формирования элитных особей. Вестник Донского государственного технического университета. 2018;18(2):223-229. https://doi.org/10.23947/1992-5980-2018-18-2-223-229

For citation:


Krivoshey N.S., Kobak V.G. Study on modified Whitley model with different number and various methods of forming elite individuals. Vestnik of Don State Technical University. 2018;18(2):223-229. (In Russ.) https://doi.org/10.23947/1992-5980-2018-18-2-223-229

Просмотров: 89


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1992-5980 (Print)
ISSN 1992-6006 (Online)