Authors N.V. Kholopova, A.N. Samoylov, E.V. Kuliev
Month, Year 07, 2015 @en
Index UDC 004.82
Abstract The article deals with the key problem swarm algorithms and bionic approach, which is to determine the function of the proximity of solutions and research emerging neighborhoods for solving optimization problems. Details considered one of the most important tasks of the design development phase, namely the task of placing the components of VLSI, the quality of decisions which directly affect the quality of the trace circuits and heat, time, energy characteristics. The solution of the problems of the surroundings and the proximity of solutions within them demon- strated by the research methods of hybrid solutions. At the heart of hybridization laid consistent work of genetic algorithms, including genetic research and evolutionary modeling and methods inspired by the behavior of biological systems on the example of the bee colony. The paper proposes a scheme of integrated search, which allows better decisions at every stage of the process of accommodation. Bionic search for solving the problem of VLSI component placement includes consistent performance of two algorithms: genetic and swarm. A distinctive feature of developed bionic approach is its flexibility in finding optimal solutions, by changing the direction of the search. The technology of constructing genetic operators adapted to the location problem of VLSI components. For efficient solutions proposed to use modified genetic operators The use of "blind" approach involves changing the data structure of the chromosome (permutation of pairs of chromosomes). Experimental studies showing that the time complexity of the developed bionic search does not go beyond the polynomial dependence, and can be expressed by the formula: O(nlogn) – O(n2), where n – number of circuit elements.

Download PDF

Keywords Swarm algorithm; genetic algorithm; adaptation; neighborhood; population.
References 1. Kureychik V.V., Zaporozhets D.Yu. Sovremennye problemy pri razmeshchenii elementov SBIS [Modern placement’s problems of VLSI], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2011, No. 7 (120), pp. 68-73.
2. Norenkov I.P. Arutyunyan N.M. Evolyutsionnye metody v zadachakh vybora proektnykh resheniy [Evolutionary techniques in the problems of choice of design solutions], Elektronnyy zhurnal «Nauka i obrazovanie» [Electronic journal "Science and Education"], 2007, No. 9.
3. Kureychik V.V., Kureychik Vl.Vl. Bioinspirirovannyy poisk pri proektirovanii i upravlenii [Search inspired by natural systems, for the design and management], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 11 (136), pp. 178-183.
4. Teodorović D., Dell’Orco M. Bee Colony Optimization – a Cooperative Learning Approach to Complex Transportation Problems, Advanced OR and AI Methods in Transportation: Proceedings of 16th Mini–EURO Conference and 10th Meeting of EWGT (13-16 September 2005). Poznan: Publishing House of the Polish Operational and System Research, 2005, pp. 51-60.
5. Neupokoeva N.V., Kureychik V.M. Kvantovye i geneticheskie algoritmy razmeshcheniya komponentov EVA: Monografiya [Quantum and genetic algorithms for placing components EVA: Monograph]. Taganrog: Izd-vo TTI YuFU, 2010, 144 p.
6. Kureychik V.V., Kureychik V.M., Rodzin S.I. Teoriya evolyutsionnykh vychisleniy [The theory of evolutionary computation]. Moscow: Fizmatlit, 2012, 260 p.
7. Kuliev E.V., Lezhebokov A.A. O gibridnom algoritme razmeshcheniya komponentov SBIS [On the hybrid algorithm of component placement VLSI], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 11 (136), pp. 188-192.
8. Kureychik V.V., Kureychik Vl.Vl. Arkhitektura gibridnogo poiska pri proektirovanii [The architecture of hybrid search for design], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 7 (132), pp. 22-27.
9. Kureychik V.V., Zaporozhets D.Yu. Roevoy algoritm v zadachakh optimizatsii [Swarm algorithm in optimisation promlems], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2010, No. 7 (108), pp. 28-32.
10. 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.
11. 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.
12. Kureychik V.V., Polupanova E.E. Evolyutsionnaya optimizatsiya na osnove algoritma kolonii pchel [Artificial bee colony algorithm of evolutionary optimization], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2009, No. 12 (101), pp. 41-46.
13. Kureychik V.V., Sorokoletov P.V. Kontseptual'naya model' predstavleniya resheniy v geneticheskikh algoritmakh [Conceptual model of decisions representation in genetic algorithms], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2008, No. 9 (86), pp. 7-12.
14. Lebedev B.K., Lebedev O.B. Metody razmeshcheniya: Monografiya [Methods of placement: a Monograph]. Taganrog: Izd-vo TRTU, 2006.
15. Gladkov L.A., Kureychik V.V., Kureychik V.M., Sorokoletov P.V. Bioinspirirovannye metody v optimizatsii [Bioinspired methods in optimization]. Moscow: Fizmatlit, 2009, 384 p.
16. Pham D.T., Ghanbarzadeh A., Koз E., Otri S., Rahim S., Zaidi M. The Bees Algorithm. 2008.
17. Kureychik V.M. Kazharov A.A. Ispol'zovanie roevogo intellekta v reshenii NP-trudnykh zadach [Swarm intelligence using for NP-tasks solving], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2011, No. 7 (120), pp. 30-37.
18. Lebedev B.K. Metody poiskovoy adaptatsii v zadachakh avtomatizirovannogo proektirovaniya SBIS: Monografiya [Methods of search engine adaptation in the tasks of computer-aided VLSI design: a Monograph]. Taganrog: Izd-vo TRTU, 2000, 192 p.
19. Kuliev E.V. Zadacha razmeshcheniya elementov EVA s ispol'zovaniem geneticheskogo algoritma i algoritma pchelinoy kolonii [The problem of placing of elements of EVA using a genetic algorithm and bee colony algorithm], Trudy kongressa po intellektual'nym sistemam i informatsionnym tekhnologiyam «IS–IT’12». Nauchnoe izdanie v 4-kh t. [Proceedings of the Congress on intellectual systems and information technologies "IS–IT'12". Scientific
publication in 4 vol.]. Vol. 3. Moscow: Fizmatlit, 2012, pp. 99-104.
20. Kuliev E.V., Zaruba D.V. Rabota gibridnogo poiska razmeshcheniya komponentov SBIS [The hybrid search component placement of VLSI], Trudy molodykh uchenykh Yuzhnogo federal'nogo universiteta i Yuzhnogo nauchnogo tsentra RAN «Vysokoproizvoditel'nye vychislitel'nye sistemy» [Proceedings of young scientists of Southern Federal University and South scientific center of RAS "High performance computing"]. Issue 2. Izd-vo Rostov-on-Don – Taganrog, 2012, pp. 43-46.
21. Kuliev E.V., Lezhebokov A.A. Issledovanie kharakteristik gibridnogo algoritma razmeshcheniya [Research parameters of hybrid algorithm for placement], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 3 (140), pp. 255-261.

Comments are closed.