METAHEURISTICS BASED ON THE BEHAVIOR OF A COLONY OF WHITE MOLES
Abstract
Optimization algorithms inspired by the natural world have turned into powerful tools for solv-ing complex problems. However, they still have some disadvantages that require the study of new and more advanced optimization algorithms. In this regard, when solving NP complete problems, there is a need to develop new methods for solving this class of problems. One of these methods can be metaheuristics based on the behavior of a colony of white moles. This paper proposes a new metaheuristic algorithm called the blind white moles algorithm. This algorithm was developed based on the social behavior of blind moles in search of food and protecting the colony from intruders. The proposed solution will be able to overcome many disadvantages of conventional optimization algo-rithms, including falling into the trap of local minima or a low convergence rate. The purpose of this work is to develop an algorithm for optimizing a complex objective function. The scientific novelty lies in the development of a genetic algorithm based on the behavior of a colony of white moles for solving NP complete problems. The problem statement in this paper is as follows: to optimize the search for solutions to complex functions by applying an algorithm based on the behavior of a colony of white moles. The practical value of the work lies in the creation of a new search architecture that allows using the developed algorithm for the effective solution of NP complete problems, as well as conducting a comparative analysis with existing analogues. The fundamental difference from the known approaches is in the application of a new bioinspired search structure based on the behavior of a colony of white moles, which will allow to exclude falling into a local minimum or a low conver-gence rate. The presented results of the computational experiment showed the advantages of the pro-posed multidimensional approach to solving the problems of placing VLSI elements in comparison with existing analogues. Thus, the problem of creating methods, algorithms and software for solving NP complete problems is currently of particular relevance
References
1. Tarasov V.B. Ot mnogoagentnykh sistem k intellektual'nym organizatsiyam: filosofiya, psikhologiya, informatika [From multi-agent systems to intellectual organizations: philosophy, psychology, computer science]. Moscow: Editorial URSS, 2002, 352 p.
2. Yang X-S. A New Metaheuristic Bat-Inspired Algorithm. Nature Inspired Cooperative Strate-gies for Optimization, Stud. Comput. Intell., 2010, Vol. 284, pp. 65-74.
3. Danil'chenko V.I., Kureychik V.M. Geneticheskiy algoritm planirovaniya razmeshcheniya SBIS [Genetic algorithm of VLSI placement planning], Izvestie YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2019, No. 2, pp. 75-79.
4. Danil'chenko V.I., Kureychik V.M. Klassifikatsiya i analiz metodov resheniya zadachi razmeshcheniya SBIS [Classification and analysis of methods for solving the VLSI placement problem], Informatika, vychislitel'naya tekhnika i inzhenernoe obrazovanie [Computer sci-ence, computer engineering and engineering education], 2018, Issue 1.
5. Danilchenko V.I., Danilchenko Y.V., Kureichik V.M. Bio-inspired Approach to Microwave Cir-cuit Design, IEEE EAST-WEST DESIGN & TEST SYMPOSIUM. EWDTS 2020, pp. 362-366. DIO: 10.1109/EWDTS 50664.2020.9224737.
6. Kalent'ev A.A., Garays D.V., Dobush I.M., Babak L.I. Strukturno-parametricheskiy sintez SVCh tranzistornykh usiliteley na osnove geneticheskogo algoritma s ispol'zovaniem modeley monolitnykh elementov [Structural-parametric synthesis of microwave transistor amplifiers based on a genetic algorithm using models of monolithic elements], Doklady TUSURa [Re-ports of TUSUR], December 2012, No. 2 (26), Part 2, pp. 104-112.
7. Tang Maolin and Yao Xin. A memetic algorithm for VLSI floorplanning, IEEE Transactions on Systems, Man, And Cybernetics–Part B: Cybernetics, 2007, No. 37 (1).
8. Goryainov A.E., Dobush I.M., Babak L.I. Postroenie parametricheskikh modeley passivnykh komponentov SVCh monolitnykh integral'nykh skhem s ispol'zovaniem programmy Extrac-tion-P [Construction of parametric models of passive components of microwave monolithic in-tegrated circuits using the Extraction-P program].
9. Kokolov A.A., Salnikov A.S., Sheyerman F.I. and Babak L.I. Broadband Double-Balanced SiGe BiCMOS Mixer With Integrated Asymmetric MBaluns, Int. Conf. “Dynamics of Systems, Mechanisms and Machines” (Dynamics-2017), Omsk, Russia, 2017 (accepted for publication).
10. Akay B., Karaboga D. A modified Artificial Bee Colony algorithm for real-parameter optimi-zation, Inf. Sci., 2010, Vol. 192, pp. 20-142.
11. Taherdangkoo M., Shirzadi M.H., Bagheri M.H. A novel meta-heuristic algorithm for numeri-cal function optimization: blind, naked mole-rats (BNMR) algorithm, Scientific Research and Essays, 2012, No. 7 (41), pp. 3566-3583.
12. Bocklemann D.E. and Eisenstadt W.R. Combined Diff erential and Common-Mode Scattering Parameters: Theory and Simulation, IEEE Trans. on Microwave Theory and Techniques, July 1995, Vol. MTT-43, No. 7, pp. 520–523,.
13. Yang Y., Kamel M.S. An aggregated clustering approach using multi-ant colonies algorithms, Pattern Recognition, 2006, Vol. 39 (7), pp. 1278-1289.
14. Zhabin D.A., Garays D.V., Kalentyev A.A., Dobush I.M. and Babak L.I. Automated Synthesis of Low Noise Amplifi ers Using S-parameter Sets of Passive Elements, Asia-Pacifi c Micro-wave Conference (APMC 2017), Kuala Lumpur, Malaysia, 2017 (accepted for publication).
15. Kalentyev A.A., Garays D.V. and Babak L.I. Genetic-Algorithm-Based Synthesis of Low-Noise Amplifi ers with Automatic Selection of Active Elements and DC Biases, European Mi-crowave Week 2014, Rome, Italy, October 2014, pp. 520-523.
16. Babak L.I., Kokolov A.A. and Kalentyev A.A. A New Genetic-Algorithm-Based Technique for Low Noise Amplifier Synthesis, European Microwave Week 2012, Amsterdam, The Nether-lands, November 2012, pp. 520-523.
17. Mann G.K.I., Gosine R.G. Three-dimensional min–max-gravity based fuzzy PID inference analysis and tuning, Fuzzy Sets and Systems, 2005, Vol. 156, pp. 300-323.
18. Golitsyn G.A. Petrov V.M. Informatsiya i biologicheskie printsipy optimal'nosti: Garmoniya i algebra zhivogo [Information and biological principles of optimality: Harmony and al-gebra of the living]. Moscow: KomKniga 2005.
19. Kolesov Yu.B., Senichenkov Yu.B. Modelirovanie sistem. Dinamicheskie i gibridnye sistemy: ucheb.-metod. Posobie [Modeling of systems. Dynamic and hybrid systems: an educa-tional and methodological guide]. Saint Petersburg: BKhV-Peterburg, 2006.
20. Abraham A., Grosan G., Ramos V. Swarm Intelligence in Data Mining. Berlin. Heidelberg: SpringerVerlag, 2007, 267 p.
