METAHEURISTIC OPTIMIZATION METHOD BASED ON THE STEM CELL BEHAVIOR MODEL
Abstract
The paper discusses optimization methods that are based on processes occurring in nature. Such
methods have become increasingly used to solve complex problems. However, such methods have some
drawbacks, which stimulates the development of new and more advanced optimization methods. Solving
NP complete problems requires optimal methods that will meet all design requirements, so there is a
need to develop new and more advanced methods for solving this class of problems. As such a method,
the authors propose an optimization method based on a model of the behavior of stem cells in the natural
environment. The conducted studies of the proposed method provide solutions that can overcome
many of the shortcomings of standard optimization approaches, such as getting into the local optimum
or low convergence rate of the algorithm based on the method under consideration. The purpose of this
work is to develop an optimization method and an algorithm based on it for solving a complex objective
function. The scientific novelty lies in the development of an optimization method based on the stem cell
behavior model for solving NP complete problems. The aim of the work is to create conditions for theoptimal search for a solution to complex functions by applying the search method and, based on it, an
algorithm for the behavior of stem cells. The practical value of the work lies in the development of a new
metaheuristic optimization method for the efficient solution of NP complete problems. Also in the work,
a comparative analysis with well-known competitors was carried out. The main difference of the proposed
method from other known methods is the use of a new approach of bioinspired search based on
the behavior of stem cells, which, as shown by practical comparison, has an advantage over known
analogues. The results of a practical comparison of methods and algorithms based on them showed the
advantages of the approach proposed in the work on known test functions. After analyzing the problem
of creating methods, algorithms and software for solving NP complete problems, we can conclude that
the development of such approaches is currently an urgent task.
References
SBIS [Genetic algorithm of VLSI placement planning], Izvestie YuFU. Tekhnicheskie nauki
[Izvestiya SFedU. Engineering Sciences], 2019, No. 2 (204), pp. 26-34.
2. Danil'chenko V.I., Danil'chenko E.V. 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 [Informatics,
computer engineering and engineering education], 2018, Issue 1.
3. Danilchenko V.I., Danilchenko Y.V., Kureichik V.M. Bio-inspired Approach to Microwave Circuit
Design, IEEE EAST-WEST DESIGN & TEST SYMPOSIUM. EWDTS 2020, pp. 362-366.
DIO: 10.1109/EWDTS 50664.2020.9224737.
4. 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 [Proceedings
of TUSUR University], 2012, No. 2 (26), Part 2, pp. 104-112.
5. 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).
6. Goryainov A.E., Dobush I.M., Babak L.I. Postroenie parametricheskikh modeley passivnykh
komponentov SVCh monolitnykh integral'nykh skhem s ispol'zovaniem programmy Extraction-
P [Construction of parametric models of passive components of microwave monolithic integrated
circuits using the Extraction-P program], Doklady TUSURa [Proceedings of TUSUR
University], 2012, No. 2 (26), pp. 98-103.
7. 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).
8. 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.
9. Golitsyn G.A. Petrov V.M. Informatsiya i biologicheskie printsipy optimal'nosti: Garmoniya i
algebra zhivogo [Information and biological principles of optimality: Harmony and algebra of
the living]. Moscow: KomKniga 2005.
10. Kolesov Yu.B., Senichenkov Yu.B. Modelirovanie sistem. Dinamicheskie i gibridnye sistemy:
ucheb.- metod, posobie [Modeling of systems. Dynamic and hybrid systems: an educational
and methodological guide]. Saint Petersburg: BKhV-Peterburg, 2006.
11. Abraham A., Grosan G., Ramos V. Swarm Intelligence in Data Mining. Berlin. Heidelberg:
SpringerVerlag, 2007, 267 p.
12. Kureychik V.V., Kureychik V.M., Sorokoletov P.V. Analiz i obzor modeley evolyutsii [Analysis
and review of evolution models], Izvestiya Rossiyskoy akademii nauk. Teoriya i sistemy
upravleniya [Proceedings of the Russian Academy of Sciences. Theory and control systems],
2007, No. 5, pp. 114-126.
13. Rodzin S.I., Kureychik V.V. Teoreticheskie voprosy i sovremennye problemy razvitiya
kognitivnykh bioinspirirovannykh algoritmov optimizatsii (obzor) [Theoretical issues and modern
problems of the development of cognitive bioinspired optimization algorithms (review)],
Kibernetika i programmirovanie [Cybernetics and programming], 2017, No. 3, pp. 51-79.
14. Ob upravlenii na osnove geneticheskogo poiska [About management based on genetic search],
Avtomatika i telemekhanika [Automation and telemechanics], 2001, No. 10, pp. 174-187.
15. Bova V.V., Kureychik V.V. Integrirovannaya podsistema gibridnogo i kombinirovannogo
poiska v zadachakh proektirovaniya i upravleniya [Integrated subsystem of hybrid and combined
search in design and management tasks], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya
SFedU. Engineering Sciences], 2010, No. 12 (113), pp. 37-42.
16. Gatchin Yu.A., Korobeynikov A.G. Metody predstavleniya matematicheskikh modeley v SAPR
pri kontseptual'nom i infologicheskom modelirovanii [Methods of representation of mathematical
models in CAD in conceptual and infological modeling], IEEE AIS-03, CAD-2003.
Intellektual'nye sistemy, intellektual'nye SAPR [IEEE AIS-03, CAD-2003. Intelligent systems,
intelligent CAD]. Moscow: Fizmatlit, 2003, Vol. 2, pp. 35-41.
17. Bershadskiy A.M. Primenenie grafov i gipergrafov dlya avtomatizatsii konstruktorskogo
proektirovaniya REA i EVA [Application of graphs and hypergraphs for automation of design
design of REA and EVA]. Saratov: Izd-vo SGU, 1993.
18. Novikov F.A. Diskretnaya matematika dlya programmistov [Discrete mathematics for programmers].
Saint Petersburg: Piter, 2000.
19. Akimov O.E. Diskretnaya matematika: logika, gruppy, grafy, fraktaly [Discrete mathematics:
logic, groups, graphs, fractals]. Moscow: Izdatel' AKIMOA, 2005.
20. Bershteyn L.S., Bozhenyuk A.V. Nechetkie grafy i gipergrafy [Fuzzy graphs and hypergraphs].
Moscow: Nauchnyy mir, 2005.
