ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ СЕВЕРО-КАВКАЗСКИЙ РЕГИОН. 2016; 3: 9-17
http://dx.doi.org/10.17213/0321-2653-2016-3-9-17
РЕШЕНИЕ ЗАДАЧИ РАЗБИЕНИЯ ОРИЕНТИРОВАННОГО АЦИКЛИЧЕСКОГО ГРАФА МОДИФИЦИРОВАННЫМ АЛГОРИТМОМ ИСКУССТВЕННОЙ ИММУННОЙ СИСТЕМЫ С КЛОНАЛЬНОЙ СЕЛЕКЦИЕЙ
Ivanchenko Alexander Nikolaevich – Candidate of Technical Sciences, professor, department «Software Computer Engineering», Platov South-Russia State Polytechnic University (NPI).
Nguyen Van Ngon – post-graduate student, department «Software Computer Engineering», Platov South-Russia State Polytechnic University (NPI),
Аннотация
Формулируется задача поиска наилучшего разбиения взвешенного ориентированного ациклического графа по критерию минимума суммарного веса всех разрезов с учетом требования ацикличности результирующего компонентного графа. Вводится понятие схемы разбиения и анализируются необходимые комбинаторные соотношения и алгоритмы, позволяющие организовать поиск точного решения прямым перебором вариантов. Для отыскания приближенного решения предлагается использовать модифицированный алгоритм искусственной иммунной системы с клональной селекцией, сопряженный с островной моделью. Приводятся результаты численного эксперимента для случайно сгенерированного графа.
Ключевые слова: ориентированный ациклический граф; декомпозиция графа; ориентированный разрез; сильно связные компоненты; компонентный граф; искусственная иммунная система; клональная селекция; островная модель
Полный текст: [in elibrary.ru]
Ссылки на литературу
1. Евстигнеев В.А. Применение теории графов в программировании. М.: Наука, 1985. 352 с.
2. Cormen T.H., Leiserson Ch.E., Rivest R.L., Stein C. Introduction to Algorithms, Third Edition. MIT Press and McGraw-Hill, 2009. 1313 p.
3. Еремин Г.С. Разбиение произвольного множества вершин ориентированного бесконтурного графа на выпуклые подмножества // Автоматика и телемеханика. 1987. № 8. С. 137 – 143.
4. Еремин Г.С. Алгоритм разбиения невыпуклого множества вершин ориентированного графа // Автоматика и телемеханика. 1989. № 9. С. 187 – 190.
5. Иванченко А.Н., Нгуен Ван Нгон. Имитационное моделирование процесса освоения модульной образовательной программы // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2015. № 3. С. 28 – 33.
6. Иванченко А.Н. Нгуен Ван Нгон, Шайда А.Ю. Моделирование процессов электронного обучения с использованием темпоральных и случайных графов // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2016. № 1. С. 15 – 19.
7. Hadzilacos T., Kalles D., Karaiskakis D., Pouliopoulou M. Using Graphs in Developing Educational Material // Proceedings of the 2nd International Workshop on Building Technology Enhanced Learning Solutions for Communities of Practice. TEL-CoPs'07. Sissi, Lassithi Crete.
8. Баранов В.И., Стечкин Б.С. Экстремальные комбинаторные задачи и их приложения. М.: Наука. Гл. ред. физ.-мат. лит., 1989. 160 с.
9. Kreher D.L., Stinson D.R. Combinatorial Algorithms: Generation, Enumeration and Search. CRC press LTC,
10. Борзунов Г.И. Совершенствование математической модели поиска экстремальных разбиений множеств // Безопасность информационных технологий. 2008. № 3. С. 58 – 61.
11. Комбинаторный анализ. Задачи и упражнения: учеб. пособие / под ред. К.А. Рыбникова. М.: Наука. Гл. ред. физ.-мат. лит., 1982. 368 с.
12. Vairamuthu M., Porselvi S., DR. Balaji A.N., Rajesh Babu J. Artificial Immune System algorithm for multi objective flow shop scheduling problem / M. Vairamuthu, // International Journal of Innovative Research in Science, Engineering and Technology.
13. Castro L.N. de. Zuben von F.J. // The Clonal Selection Algorithm with Engineering Applications / , In Workshop Proceedings of GECCO. Workshop on Artificial Immune Systems and Their Applications,
14. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой: учеб. пособие. М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. 446 с.
15. Щербинина Н.И., Кобак В.Г., Жуковский А.Г. Исследование влияния различных видов миграций при решении минимаксной задачи островной моделью // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2016. № 2. С. 3 – 9.
16. Курейчик В.М., Кныш Д.С. Параллельный генетический алгоритм. Модели и проблемы построения // Интегрированные модели и мягкие вычисления в искуственном интеллекте: сб. науч. тр. V Междунар. науч.-практ. конф. М.: Физматлит, 2009. С. 41 – 51.