DEVELOPMENT OF A MODIFIED MODEL OF ADAPTIVE BEHAVIOR OF A ROY OF PARTICLES FOR ISSUING A MAXIMUM CLICK IN A GRAPH
Abstract
A method is proposed for solving the problem of highlighting the maximum clique in a graph based on a modified model of adaptive behavior of a swarm of particles. The particle swarm method is a stochastic optimization method somewhat similar to evolutionary algorithms. This method does not model evolution, but swarm and pack behavior of animals. Unlike population methods, the particle swarm method works with one static population, whose members gradually improve with the advent of information about the search space. As a data structure that carries information about the solution, a sequence is used, which is the order in which the solution is formed, which is called a priority list. A priority list is a coded solution, in terms of a genetic algo-rithm, a “chromosome”. The priority list is an indirect decision coding scheme. The transition from the priority list to the decision is made using a decoder. A decoder is an operator that allows you to switch from an indirect (numerical) coding scheme for solving a problem to a phenotype. In fact, a priority list is an interpretation of a solution in a particular subject area. The search proce-dures in the space of solutions, the mechanisms of behavior of the modernized swarm of particles are described. The key problem that was solved in this paper is related to the development of the structure of an affine position space that allows us to display and search for interpretations of solutions with integer parameter values. In contrast to the canonical particle swarm method, in order to reduce the weight of affine bonds, by moving the particle to a new position in the affine solution space, a directed mutation operator has been developed, the essence of which is to change the integer values of the genes in the chromosome. The temporal complexity of the algorithm ob-tained experimentally coincides with theoretical studies and for the considered test problems is О(n2) – О(n3). The probability of obtaining a global optimum was 0.94. On average, launching a program provides solutions that differ from the optimal solution by less than 1.5 %. The results show that the proposed approach is an acceptable alternative for solving combinatorial problems.
References
2. Kuznetsov O.P. Diskretnaya matematika dlya inzhenera [Discrete math for an engineer]. Saint Petersburg: Lan', 2004, 400 p. 3. Lebedev B.K. Intellektual'nye protsedury sinteza topologii SBIS [Intelligent synthesis proce-dures for VLSI topology]. Taganrog: Izd-vo TRTU, 2003, 156 p.
4. Norenkov I.P. Osnovy avtomatizirovannogo proektirovaniya [Basics of computer-aided de-sign]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2006, 278 p.
5. Kureychik V.M., Lebedev B.K., Lebedev O.B. Poiskovaya adaptatsiya: teoriya i praktika [Search adaptation: theory and practice]. Moscow: Fizmatlit, 2006, 277 p. Available at: https://elibrary.ru/item.asp?id=21261209.
6. Мazumder P., Rudnick E. Genetic Algorithm For VLSI Design, Layout & Test Automation. India, Pearson Education, 2003.
7. Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye prirodoy: ucheb. posobie [Modern search engine optimization algorithms. Algorithms inspired by nature: a training manual]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2014, 446 p. Avail-able at: https://elibrary.ru/item.asp?id=25070137.
8. Engelbrecht A.P. Fundamentals of Computational Swarm Intelligence. John Wiley & Sons, Chichester, UK, 2005.
9. Clerc M. Particle Swarm Optimization. ISTE, London, UK, 2006, 187 р.
10. Dorigo M. and Stützle T. Ant Colony Optimization. MIT Press, Cambridge, MA, 2004.
11. Lebedev B.K., Lebedev O.B. Modifitsirovannye mekhanizmy peremeshcheniya roya chastits (agentov) v affinnom prostranstve s tselochislennymi parametrami [Modified mechanisms for mov-ing a swarm of particles (agents) in an affine space with integer parameters], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2018, No. 4 (198), pp. 121-136.
12. Lebedev O.B. Modeli adaptivnogo povedeniya murav'inoy kolonii v zadachakh proektirovaniya [Models of adaptive behavior of the ant colony in design problems]. Taganrog: Izd-vo YuFU, 2013, 199 p.
13. OR-Library is collection of test data for a variety of OR problem. Available at: http://mscmga.ms.ic.ac.uk.
14. Lebedev B.K., Lebedev O.B. Gibridnyy bioinspirirovannyy algoritm na osnove integratsii metoda vetvey i granits i metoda murav'inoy kolonii [Hybrid bioinspired algorithm based on the integration of the branch and bound method and the ant colony method], Vestnik Rostovskogo gosudarstvennogo universiteta putey soobshcheniya [Bulletin of the Rostov State Transport Univer-sity], 2018, No. 2 (70), pp. 77-88. Available at: https://elibrary.ru/item.asp?id=35154092.
15. Vorob'eva E.Yu., Karpenko A.P., Seliverstov E.Yu. Ko-gibridizatsiya algoritmov roya chastits [Co-hybridization of particle swarm algorithms], Nauka i obrazovanie. MGTU im. N.E. Baumana [Sci-ence and Education. MGTU them. N.E. Bauman], 2012, No. 4. Available at: https://elibrary.ru/ item.asp?id=18126595.
16. Agasiev T.A., Karpenko A.P. Sovremennye tekhniki global'noy optimizatsii [Modern technol-ogy of global optimization], Informatsionnye tekhnologii [Information technologies], 2018, No. 6, pp. 370-386. Available at: https://elibrary.ru/item.asp?id=35154610.
17. Wang X. Hybrid nature-inspired computation method for optimization: Doctoral Dissertation. Helsinki University of Technology, TKK Dissertations, Espoo 2009, 161 p.
18. Blum C., Roli A. Metaheuristics in combinatorial optimization: overview and conceptual com-parison, ACM computing surveys, 2003, No. 35, pp. 268-308.
19. Lebedev V.B. Postroenie kratchayshikh svyazyvayushchikh setey na osnove roevogo intellekta [Construction of the shortest connecting networks on the basis of swarm intelligence], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2011, No. 7 (120), pp. 37-44.
20. Sha D.Y. and Cheng-Yu. A hybrid particle swarm optimization for job shop scheduling prob-lem, Computers & Industrial Engineering, 2006, pp. 791-808.
21. Kureychik, V.V., Polupanov A.A. Obzor evolyutsionnykh metodov optimizatsii na osnove roevogo intellekta [A review of evolutionary optimization methods based on swarm intelli-gence], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2011, No. 7 (120), pp. 7-12.
