UNIV. NEWS. NORTH-CAUCAS. REG. TECHNICAL SCIENCES SERIES. 2016; 3: 9-17
http://dx.doi.org/10.17213/0321-2653-2016-3-9-17
THE SOLUTION OF THE PROBLEM PARTITIONING DIRECTED ACYCLIC GRAPH USING MODIFIED ARTIFICIAL IMMUNE SYSTEM ALGORITHM WITH CLONAL SELECTION
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),
Abstract
Formulated the task of finding the best partition weighted directed acyclic graph by criterion of the minimum total weight of all cuts subject to the requirements of the acyclic component of the resulting graph. Introduces the concept of partitioning schemes and analyzed the necessary combinatorial relations and algorithms to organize the search for exact solutions of direct search options. For finding an approximate solution is proposed to use a modified algorithm of artificial immune system with clonal selection, coupled with the island model. Presented the results of numerical experiment for a randomly generated graph.
Keywords: directed acyclic graph (DAG); decompositions of graphs; directed cut; strongly connected components; component graph; artificial immune system (AIS); clonal selection; island model
Full text: [in elibrary.ru]
References
1. Evstigneev V.A. Primenenie teorii grafov v programmirovanii [Application of graph theory in programming].
2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, Third Edition. MIT Press and McGraw-Hill, 2009. 1313 p.
3. Eremin G.S. Razbienie proizvol'nogo mnozhestva vershin orientirovannogo beskonturnogo grafa na vypuklye podmnozhestva [Splitting an arbitrary set of vertices of a directed acyclic graph on convex subsets]. Avtomatika i telemehanika, 1987, no. 8, pp. 137–143. [In Russ.]
4. Eremin G.S. Algoritm razbienija nevypuklogo mnozhestva vershin orientirovannogo grafa [Algorithm for partitioning a non-convex set of vertices of a directed graph]. Avtomatika i telemehanika, 1989, no. 9, pp. 187–190. [In Russ.]
5. Ivanchenko A.N., Nguen Van Ngon. Imitacionnoe modelirovanie processa osvoenija modul'noj obrazovatel'noj programmy [Simulation modeling of the process study of the modular curriculum]. Izv. vuzov. Sev.-Kavk. Region. Tehn. nauki, 2015, no. 3, pp. 28-33. [In Russ.]
6. Ivanchenko A.N., Nguen Van Ngon, Shajda A.Ju. Modelirovanie processov jelektronnogo obuchenija s ispol'zovaniem temporal'nyh i sluchajnyh grafov [Modelling of e-learning using temporal and random graphs]. Izv. vuzov. Sev. - Kavk. region. Tehn. nauki, 2016, no. 1, pp. 15-19. [In Russ.]
7. Thanassis Hadzilacos, Dimitris Kalles, Dionysis Karaiskakis, Maria Pouliopoulou. 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. Baranov V.I., Stechkin B.S. Jekstremal'nye kombinatornye zadachi i ih prilozhenija [Extreme combinatorial problems and their applications].
9. Kreher D.L., Stinson D.R. Combinatorial Algorithms: Generation, Enumeration and Search. CRC press LTC,
10. Borzunov G.I. Sovershenstvovanie matematicheskoj modeli poiska jekstremal'nyh razbienij mnozhestv [Improvement of mathematical model for finding extreme set partitions]. Bezopasnost' informacionnyh tehnologij, 2008, no. 3, pp. 58-61. [In Russ.]
11. Kombinatornyj analiz. Zadachi i uprazhnenija [Combinatorial analysis. Exercises]. Edit by K.A. Rybnikova.
12. Vairamuthu M., Porselvi S., Balaji DR. A.N., Rajesh Babu J. Artificial Immune System algorithm for multi objective flow shop scheduling problem // International Journal of Innovative Research in Science, Engineering and Technology. -
13. de Castro L.N., Fernando J. Von Zuben. The Clonal Selection Algorithm with Engineering Applications // In Workshop Proceedings of GECCO. Workshop on Artificial Immune Systems and Their Applications,
14. Karpenko A.P. Sovremennye algoritmy poiskovoj optimizacii. Algoritmy, vdohnovlennye prirodoj [Modern search optimization algorithms. Algorithms inspired by nature: a tutorial].
15. Shherbinina N.I., Kobak V.G., Zhukovskij A.G. Issledovanie vlijanija razlichnyh vidov migracij pri reshenii minimaksnoj zadachi ostrovnoj model'ju [Investigation of the effect of different types of migration in the solution of the minimax problem of the island model]. Izv. vuzov. Sev. - Kavk. region. Tehn. nauki, 2016, no. 2, pp. 3-9. [In Russ.]
16. Kurejchik V.M., Knysh D.S. Parallel'nyj geneticheskij algoritm. Modeli i problemy postroenija [Parallel genetic algorithm. Models and problems of building]. Integrirovannye modeli i mjagkie vychislenija v iskustvennom intellekte: sb. nauch. tr. V Mezhdunar. nauch.- praktich. konf. [The integrated models and soft calculations in artificial intelligence: collection of scientific works of the V International scientific practical conference].