OPTIMIZATION BASED ON COMBINING MODELS OF ADAPTIVE BEHAVIOR OF A SWARM OF AGENTS
Abstract
A bionic search architecture has been developed to solve the problem of placing VLSI elements
based on the hybridization of the algorithms of a bee colony and a swarm of chromosomes,
which allows you to get out of "local holes" and increases the convergence of the placement algorithm. The initial iterations are implemented by the bee algorithm to provide a broad overview of
the search area, and the final iterations are implemented by the chromosome swarm algorithm,
which ensures the exact localization of the extremum found by the bee algorithm. Agents are represented
as a population of chromosomes, which are genotypes for solving the placement problem.
The paper describes a modified paradigm of a swarm of chromosomes, which, in contrast to the
canonical method, provides the possibility of searching for solutions in the affine space of positions
with integer values of the parameters. In the search population method of optimization by a
swarm of chromosomes, the agents of the population are chromosomes. The chromosome is the
genotype of the optimization object. The essence of the search procedure is the successive change
of the states of the object of optimization (chromosome) by the directed mutation operator and the
search for the optimal state. An affine-relaxation model (ARM) of a swarm of chromosomes is
proposed - this is a graph whose vertices correspond to chromosomes, and arcs correspond to
affine bonds between them. The transition of the chromosome to a new state is carried out using a
relaxation procedure. In the work, the directed mutation operator acts as a means of changing the
solution, the essence of which is to change the integer values of genes in the chromosome. The
purpose of the transition is to reduce the weight of the affine bond between chromosomes. The
mechanisms of the directed mutation operator are described. A modified structure of the bee algorithm
is proposed. For each base chromosome, a probabilistic choice of a set of chromosomes
located in the vicinity of the base chromosome is implemented. It is possible to improve the quality
of the developed algorithm by adjusting the values of the control parameters. The time complexity
of the algorithm for fixed values of the population size and the number of generations is O(n). In
general, the dependence of the running time of the hybrid algorithm is O(n2) – O(n3).
References
integrated circuits and systems]. Moscow: Binom. Laboratoriya znaniy, 20105.
2. Tuchin A.V., Bormontov E.N., Ponomarev K.G. Vvedenie v sistemy avtomatizirovannogo
proektirovaniya integral'nykh mikroskhem [Introduction to computer-aided design of integrated
circuits]. Voronezh: Izdatel'skiy dom VGU, 2017.
3. Norenkov I.P. Osnovy avtomatizirovannogo proektirovaniya [Fundamentals of computer-aided
design]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2006.
4. Alpert C.J., Mehta D.P., and Sapatnekar S.S. Handbook of Algorithms for Physical Design
Automation. Boston, MA: Auerbach, 2009.
5. Lebedev B.K., Lebedev V.B., Lebedev O.B. Metody, modeli i algoritmy razmeshcheniya
[Methods, models and placement algorithms]. Rostov-on-Donu: Izd-vo YuFU, 2015.
6. Jason Cong, Joseph R., Shinnerl и Min Xie (UCLA Computer Science), Tim Kong (Magma
Design Automation) и Xin Yuan (IBM Corporation, Microelectronics Division). Large-Scale
Circuit Placement, ACM Transactions on Design Automation of Electronic Systems. April
2005, Vol. 10, No. 2.
7. Poli R. Analysis of the publications on the applications of particle swarm optimization, Journal
ofArtificial Evolution and Applications, Article ID 685175, 2008.
8. Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye
prirodoy: ucheb. posobie [Modern search engine optimization algorithms. Algorithms inspired
by nature: textbook]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2014.
9. Wang X. Hybrid nature-inspired computation method for optimization: Doctoral Dissertation.
Helsinki University of Technology, TKK Dissertations, Espoo 2009, 161 p.
10. Clerc M. Particle Swarm Optimization. ISTE, London, UK, 2006.
11. Kennedy J., Eberhart R.C. Particle swarm optimization, In Proceedings of IEEE International
Conference on Neural Networks, 1995, pp. 1942-1948.
12. Lebedev B.K., Lebedev O.B.,. Lebedev V.B. Gibridnyy metod stokhasticheskoy optimizatsii na
osnove integratsii modeley evolyutsii i roevogo (staynogo) povedeniya zhivotnykh v affinnykh
prostranstvakh poiska [A hybrid method of stochastic optimization based on the integration of
models of evolution and swarm (packing) behavior of animals in affine search spaces], Sb.
trudov Shestnadtsatoy natsional'noy konferentsii po iskusstvennomu intellektu s
mezhdunarodnym uchastiem KII-2018 [Proceedings of the Sixteenth National Conference on
Artificial Intelligence with International Participation KII-2018]. In 2 vol. Vol. 2. Moscow:
FGP ITAR-TASS filial RKP, 2018, pp. 148-156.
13. Lebedev B.K., Lebedev O.B., Lebedeva E.O., Nagabedyan A.A. Gibridnyy roevoy algoritm
global'noy optimizatsii v affinnom prostranstve poiska [Hybrid swarm algorithm of global optimization
in affine search space], Elektronnyy zhurnal “Programmnye produkty, sistemy i
algoritmy” [Electronic journal "Software products, systems and algorithms"], 2019, No. 1.
14. Lučić P., Teodorović D. Computing with Bees: Attacking Complex Transportation Engineering
Problems, International Journal on Artificial Intelligence Tools, 2003, No. 12, pp. 375-394.
15. Quijano N., Passino K.M. Honey Bee Social Foraging Algorithms for Resource Allocation:
Theory and Application. Columbus: Publishing house of the Ohio State University, 2007, 39 p.
16. Lebedev B.K., Lebedev V.B. Razmeshchenie na osnove metoda pchelinoy kolonii [Placement
based on the bee colony method], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering
Sciences], 2010, No. 12, pp. 12-18.
17. Cong J., Romesis M., and Xie M. Optimality, Scalability and Stability Study of Partitioning
and Placement Algorithms, Proc. of the International Symposium on Physical Design, Monterey,
CA, April 2004, pp. 88-94.
18. MCNC. Electronic and Information Technologies (Online). Available: www.mcnc.org.
19. Wang M., Yang X. and Sarrafzadeh M. Dragon2000: Standard-cell Placement Tool for Large
Industry Circuits, ICCAD 2000, pp. 260-263.
20. Caldwell A.E., Kahng A.B. and Markov I.L. Can Recursive Bisection Alone Produce Routable
Placements?, DAC 2000, pp. 477-482.
21. Chan T., Cong J., Kong T., Shinnerl J. и Sze K. An enhanced multilevel algorithm for circuit
placement, In Proceedings of the IEEE International Conference on Computer Aided Design
(San Jose, Calif.). IEEE Computer Society Press, Los Alamitos, Calif. 2003.
22. Yang X., Choi B.-K. and Sarrafzadeh M. Routability-driven white space allocation for fixeddie
standard-cell placement, IEEE Trans. on Computer-Aided Design of Integrated Circuits
and Systems, 2003, 22 (4), pp. 410-419.
23. CADENCE DESIGN SYSTEMS, INC. QPlace version 5.1.55, compiled on 10/25/1999.
Envisia ultra-placer reference.
