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

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


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

 

http://dx.doi.org/10.17213/0321-2653-2016-2-3-9

 

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

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

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

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

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

 

Аннотация

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

 

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

 

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

 

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

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

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

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

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.

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

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

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

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

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

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

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