Научный журнал
ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ.
СЕВЕРО-КАВКАЗСКИЙ РЕГИОН.

ТЕХНИЧЕСКИЕ НАУКИ


ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ СЕВЕРО-КАВКАЗСКИЙ РЕГИОН. 2016; 4: 3-10

 

http://dx.doi.org/10.17213/0321-2653-2016-4-3-10

 

ИССЛЕДОВАНИЕ ПОКОЛЕНЧЕСКОЙ СТРАТЕГИИ ПРИ РЕШЕНИИ ОДНОРОДНОЙ И НЕОДНОРОДНОЙ МИНИМАКСНОЙ ЗАДАЧИ РАЗЛИЧНЫМИ МОДИФИКАЦИЯМИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА

Н.И. Щербинина, В.Г. Кобак, А.Г. Жуковский

Щербинина Наталья Игоревна – аспирант, кафедра «Вычислительные системы и информационная безопасность», Донской государственный технический университет,
г. Ростов-на-Дону, Россия. E-mail: TrotsyukNaTa@yandex.ru

Кобак Валерий Григорьевич – профессор, кафедра «Вычислительные системы и информационная безопасность»,  кафедра «Программное обеспечение вычислительной техники и автоматизированных систем», Донской государственный технический университет, г. Ростов-на-Дону, Россия. E-mail: valera33305@mail.ru

Жуковский Александр Георгиевич – канд. техн. наук, профессор, кафедра «Программное обеспечение вычислительной техники и автоматизированных систем», Донской государственный технический университет, г. Ростов-на-Дону, Россия. E-mail: zhykovskij@mail.ru

 

Аннотация

Рассмотрены однородная и неоднородная минимаксные задачи теории расписаний из класса NP-полных задач. Для нахождения субоптимального решения поставленных задач в качестве базового алгоритма рассмотрена генетическая модель Голдберга и ее модификация, использующая принцип участия каждой особи в кроссовере. Для улучшения базовых алгоритмов использована островная модель с миграциями и без, а также поколенческая стратегия. Выполнен анализ эффективности предложенных модификаций алгоритмов, по результатам проведенного вычислительного эксперимента сделаны выводы о работе алгоритмов.

 

Ключевые слова: теория расписаний; NP-полные задачи; генетические алгоритмы; модель Голдберга; островная модель; кольцевая миграция; случайная миграция; поколенческая стратегия.

 

Полный текст: [in elibrary.ru]

 

Ссылки на литературу

1. Кононов А.В. Актуальные задачи теории расписаний: вычислительная сложность и приближенные алгоритмы: автореф. дис. … д-ра физ.-мат. наук. Новосибирск, 2014. 196 с.

2. Кобак В.Г., Троцюк Н.И. Сравнительный анализ алгоритмов: генетического с элитой и Крона с генетическим начальным распределением // Математические методы в технике и технологиях: сб. тр. междунар. науч. конф. Саратов, 2013. С. 62 – 64.

3. Троцюк Н.И., Кобак В.Г. Решение неоднородной минимаксной задачи моделью Голдберга с использованием поколенческой стратегии // Инновации, экология и ресурсосберегающие технологии (ИнЭРТ-2014): тр. XI междунар. науч.-техн. форума. Ростов н/Д., 2014. С. 1497 – 1500.

4. Holland J. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. USA: University of Michigan, 1975, 227 p.

5. Goldberg D. Genetic Algorithms In Search, Optimization, and Machine Learning. USA: Addison-Wesley Publishing Company, Inc., 1989, 403 p.

6. Кобак В.Г., Титов Д.В. Исследование турнирного отбора в генетическом алгоритме для решения однородной минимаксной задачи // Математические методы в технике и технологиях: сб. тр. междунар. науч. конф. Саратов, 2008. Т. 5. С. 12 – 14.

7. Кобак В.Г., Титов Д.В., Троцюк Н.И. Повышение эффективности модифицированной модели Голдберга в однородных системах обработки информации алгоритмическими преобразованиями [Электронный ресурс]: монография / Дон. гос. техн. ун-т. Электрон. текстовые дан. Ростов н/Д.: ДГТУ, 2015. 86 с. URL: http://www.ntb. donstu.ru/content/2015191 (дата обращения 17.06.2016).

8. Щербинина Н.И., Кобак В.Г., Жуковский А.Г. Исследование влияния различных видов миграций при решении минимаксной задачи островной моделью // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2016. № 2 (190). С. 3 – 9.

9. Кобак В.Г. Методология сопоставительно-критериальной аналитической оценки распределительных задач и средства ее программно‑алгоритмической поддержки : автореф. дис. ... д-ра техн. наук. Ростов н/Д, 2008, 46 с.

10. Курейчик В.М., Кныш Д.С. Параллельный генетический алгоритм. Модели и проблемы построения // Интегрированные модели и мягкие вычисления в искуственном интеллекте: сб. науч. тр. V Междунар. науч.-практ. конф. М.: Физматлит, 2009. С. 41 – 51.

11. Whitley D., Rana S., Heckendorn R. The Island Model Genetic Algorithm: On Separability, Population Size and Convergence. USA: Colorado State University, 1998. 17 p.

12. Affenzeller M., Wagner S., Winkler S., Beham A. Genetic Algorithms and Genetic Programming: Modern Concepts and Practical Applications. USA: CRC Press, 2009. 364 c.

13. Калюка В.И., Кобак В.Г., Троцюк Н.И., Зубакин В.В. Алгоритмическое улучшение модифицированной модели Голдберга в однородных системах обработки информации // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2015. № 2 (183). С. 3 – 7.