|Article title||СO-EVOLUTION ROUTING ALGORITHM BASED ON THE ANT COLONY METHOD FOR SOLVING THE CHANNEL ROUTING PROBLEM|
|Authors||B. K. Lebedev, O. B. Lebedev, E. O. Lebedeva|
|Section||SECTION I. DESIGN AUTOMATION|
|Month, Year||04, 2018 @en|
|Abstract||In this paper, a co-evolution algorithm based on the ant colony method has been proposed for solving the channel routing problem (CRP). The co-algorithm involves the parallel operation of a given number of subalgorithms of the ant colony, which use different, but isomorphic search strategies. The proposed approach allows you to organize a system of collective adaptation with a high degree of expedient behavior and convergence. The key problem that was solved in this paper is related to the development of principles for the interaction of subpopulations, which differ in strategies for finding interpretations of solutions in isomorphic functioning environments. Periodically, agents migrate from one subpopulation to another, transferring their experience. A list is used to interpret the CRP solution. In fact, each list is an indirect (numeric) coding scheme for a QCT solution. A decoder is an operator performing the laying of horizontal fragments according to the rules laid down in it, which allows one to go from an indirect (numerical) coding scheme for solving a problem to a phenotype. The list is decoded into a graphical representation of the solution (sketch) only using the appropriate strategy. The main goal is to find a list for which, using a sequential decoding procedure, fragments of chains are placed in the minimum number of trunks. To construct a constructive (built-in) procedure for finding a solution, the ant uses a modified left-end algorithm. Successive construction of a route is actually a process of sequentially placing horizontal fragments in highways. To enhance the convergence of the algorithm and the ability to exit from local optima, a combined estimate has been developed that characterizes the advantage of choosing a given vertex to include it in the generated route. The basis of the formulas for calculating the probability of the inclusion of a vertex in the formed route is based on heuristic considerations about the preferences that the vertex is part of the optimal route. The co-evolutionary approach provides a wider overview of the solution space and a higher probability of localizing the global extremum of the problem. Compared to existing algorithms, an improvement in the quality of solutions has been achieved up to 5 %.|
|Keywords||Swarm intelligence; optimization; co-evolutionary algorithm; ant algorithm; hybridization; subpopulation; channel routing; decoder.|
|References||1. Lebedev B.K. Intellektual'nye protsedury sinteza topologii SBIS [Intelligent synthesis procedures for VLSI topology]. Taganrog: Izd-vo TRTU, 2003, 96 p.
2. Sarrafzadeh M. and Wong C.K. An Introduction to VLSI Physical Design. New York: McGraw Hill, 1996, 198 р.
3. Den'dobrenko B.P., Malika A.S. Avtomatizatsiya proektirovaniya radioelektronnoy apparatury [Automation design of electronic equipment]. Moscow: Vyssh. shk., 2002, 156 p.
4. Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye prirodoy: ucheb. posobie [Modern search engine optimization algorithms. Algorithms inspired by nature: tutorial]. Modcow: Izd-vo MGTU im. N.E. Baumana, 2014, 448 p.
5. Dorigo M. and Stützle T. Ant Colony Optimization. MIT Press, Cambridge, MA, 2004, 187 р.
6. Lebedev O.B. Modeli adaptivnogo povedeniya murav'inoy kolonii v zadachakh proektirovaniya [Models of adaptive behavior of the ant colony in design problems]. Taganrog: Izd-vo YuFU, 2013, 199 p.
7. Wang X. Hybrid nature-inspired computation method for optimization: Doctoral Dissertation. Helsinki University of Technology, TKK Dissertations, Espoo, 2009, 161 p.
8. Lebedev B.K., Lebedev O.B., Lebedev V.B. Gibridizatsiya roevogo intellekta i geneticheskoy evolyutsii na primere razmeshcheniya [Hybridization of Swarm Intelligence and Genetic Evolution on the Example of Placement], Programmnye produkty, sistemy i algoritmy [Software, systems and algorithms], 2017, No. 4.
9. Vorob'eva E.Yu., Karpenko A.P., Seliverstov E.Yu. Ko-gibridizatsiya algoritmov roya chastits [Co-hybridization of particle swarm algorithms], Nauka i obrazovanie [Science and Education], 2012, No. 4. Available at: http://www.technomag.edu.ru/doc/355729.html.
10. Lebedev O.B. Trassirovka v kanale metodom murav'inoy kolonii [Channel tracing using the ant colony method], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2009, No. 2 (91), pp. 46-52.
11. Lebedev V.B. Postroenie kratchayshikh svyazyvayushchikh setey na osnove roevogo intellekta [Construction of the shortest connecting networks based on swarm intelligence], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2011, No. 7 (120), pp. 37-44.
12. 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, 2003, pp. 88-94.
13. MCNC Electronic and Information Technologies (Online). Available: www.mcnc.org.
14. Yoshimura T. аnd Kuh E.S. Efficient algorithms for channel routing, IEEE Trans. Computer Aided Design Integrated Circuits & Syst., 1982, Vol. 1, No. 1, pp. 25-35.
15. Yan T. and Wong M.D.F. BSG-Route: A Length-Constrained Routing Scheme for General Planar Topology, In Proc. Int. Conf. Comp.- Aided Des., 2008, pp. 499-505.
16. Knysh D.S., Kureychik V.M. Geneticheskiy algoritm trassirovki kommutatsionnykh blokov [Genetic switching unit tracing algorithm], Izvestiya vuzov. Elektronika. Skhemotekhnika i proektirovanie [News of universities], 2009, No. 5 (79), pp. 28-34.
17. Lebedev B.K., Lebedev O.B., Lebedeva E.O. Modifitsirovannyy murav'inyy algoritm postroeniya minimal'nogo dereva Shteynera [A modified ant algorithm for constructing a minimal Steiner tree], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2017, No. 7 (192), pp. 38-53.
18. Lebedev O.B., Purchina O.A. Roevoy algoritm trassirovki v prikanal'noy nad"yacheechnoy oblasti [Swarm tracing algorithm in the over-the-cell region], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015, No. 6 (167), pp. 41-51.
19. Kureichik V.M., Lebedev В.К., Lebedev O.B. Channel Routing Based on Ant Colony Adaptive Behavior Model, Journal of Computer and Systems Sciences International, 2015, Vol. 54,
No. 2, pp. 278-293. ISSN 10642307.
20. Lebedev O.B., Lebedeva E.M., Orlov A.N. Reshenie zadachi trassirovki s pomoshch'yu ortogonal'nykh derev'ev Shteynera [Solving the trace problem using Steiner orthogonal trees], Informatika, vychislitel'naya tekhnika i inzhenernoe obrazovanie [Computer science, computer engineering and engineering education], 2014, No. 2 (17).