Article

Article title GLOBAL ROUTING BY CRYSTALLIZATION OF ALTERNATIVES FIELD (CAF) METHOD
Authors B.K. Lebedev, V.B. Lebedev
Section SECTION I. EVOLUTIONARY MODELLING, GENETIC AND BIONIC ALGORITHMS
Month, Year 07, 2014 @en
Index UDC 681.325
DOI
Abstract We propose a method and algorithm for global routing based on a new, proposed by the authors, the paradigm of collective intelligence - crystallization of alternatives field (CAF). Solution of the problem of global routing is based on a combinatorial approach. Along with metaheuristics, which built swarms algorithms used metaheuristics, which tends to use alternatives (options components) of the best solutions found. The essence of the combinatorial algorithm is that for each connecting network formed set of options for its implementation aim is to find the problem on a given set of options that provide the best solution. In the process of evolutionary collective adaptation by methods of discriminant analysis are generated estimates of fitness alternatives. Suitability of alternatives considered as the probability of its use in the generated solution. Collection of data on alternatives and their assessments of placer alternatives. Discriminant analysis of alternatives in the process of evolutionary adaptation collective named by analogy with the process of isolating objects (crystal formation) crystallization. In other words, in the process of evolutionary adaptation produced collective isolation of many variants of the fittest alternatives. Hence the name of the optimization method – (Crystallization of alternatives field (CAF). Experimental studies have confirmed the effectiveness of the proposed paradigm. Compared with existing algorithms to improve the results achieved by 2–3.

Download PDF

Keywords Global routing; swarm intelligence; ant colony; adaptive behavior; optimization.
References 1. Alpert C.J., Mehta D.P., and Sapatnekar S.S., Handbook of Algorithms for Physical Design Automation. Boston, MA: Auerbach, 2009.
2. Ozdal M.M. and Wong M.D.F. Archer: A history-driven global routing algorithm, in Proc. Int. Conf. Comput.-Aided Des, 2007, pp. 488-495.
3. Kureychik V.M. Osobennosti postroeniya sistem podderzhki prinyatiya resheniy [Features of construction of systems of support of decision making], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 7 (132), pp. 92-290.
4. Pan M. and Chu C. FastRoute 2.0: A high-quality and efficient global router, in Proc. Asia South Pacific Des. Autom. Conf., 2007, pp. 250-255.
5. Roy J.A. and Markov I.L. High performance routing at the nanometer scale, in Proc. Int. Conf. Comput.-Aided Des., 2007, pp. 496-502.
6. Lebedev B.K., Lebedev O.B. Modelirovanie adaptivnogo povedeniya muravinoy kolonii pri poiske resheniy, interpretiruemykh derevyami [Simulation of adaptive behavior ant colony to find solutions, interpreted trees], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 7 (132), pp. 27-34.
7. Lebedev B.K., Lebedev O.B. Mnogosloynaya globalnaya trassirovka metodom kollektivnoy adaptatsii [Multilayer global tracing method of collective adaptation], V Vserossiyskaya nauchno-tekhnicheskaya konferentsiya «Problemy razrabotki perspektivnykh mikro- i nanoelektronnykh sistem - 2012». Sbornik trudov. [V all-Russian scientific-technical conference "Problems of development of micro- and nanoelectronic systems - 2012". Proceedings]. Moscow: IPPM RAN, 2012, pp. 251-257.
8. Kureychik V.M. Issledovaniya shablonnykh resheniy v muravinykh algoritmakh [Research template solutions in ant algorithms] Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 17-22.
9. Lebedev O.B. Trassirovka v kanale metodom muravinoy kolonii [Tracing in the channel method ant colony], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2009, No. 2 (91), pp. 46-52.
10. Lebedev O.B. Modeli adaptivnogo povedeniya muravinoy kolonii v zadachakh proektirovaniya [Models of adaptive behavior of ant colonies in the design tasks]. Taganrog: Izd-vo YuFU, 2013, 199 p.
11. Lebedev B.K., Lebedev V.B. Globalnaya trassirovka na osnove roevogo intellekta [Global tracking based on swarm intelligence], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2010, No. 7 (108), pp. 32-39.
12. Lebedev B.K., Lebedev V.B. Optimizatsiya metodom kristallizatsii rossypi alternativ [Optimization method of crystallization placer alternatives], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 11-17.

Comments are closed.