Article

Article title MODIFIED ANT COLONY ALGORITHM FOR BUILDING THE STEINER MINIMAL TREES
Authors B. K. Lebedev, O. B. Lebedev, E. О. Lebedeva
Section SECTION I. DESIGN AUTOMATION
Month, Year 07, 2017 @en
Index UDC 004.896
DOI
Abstract We propose new technologies, principles and mechanisms for solving the problem of con-structing a Minimal Steiner Tree using mathematical methods, which lay down the principles of natural decision-making mechanisms. The problem of constructing a Steiner tree is represented in the form of an adaptive system, based on the integration of the principles of self-organization and the ant approach to finding a solution. The well-known Steiner problem consists in the following. Given is a set of P points in the plane. An orthogonal grid is formed by conducting a horizontal and vertical line through a set of points P located on a plane. An orthogonal grid G=(V, E) is formed, where V is the set of points (nodes) of intersections of grid lines. The initial problem is equivalent to the problem of finding a tree G*=(V*, E*) in the graph G=(V, E) having the minimal total weight F of edges and including a given set of vertices P of G; PV*V, E * E. The construction of the Minimal Steiner Tree is reduced to the problem of constructing and selecting (n-1) s-routes connecting the n major vertices. The problem is solved in two stages. At the first stage, a set of alternative variants of s-routes is formed, of course, of greater dimension than (n-1) covering the Minimal Steiner Tree. In the second step, the (n-1) s-routes covering the Minimal Steiner Tree are selected from the generated set. The paper discusses combinatorial and parallel sequential approaches to the construction of the Minimal Steiner Tree: each of the s-routes is constructed sequentially, but all (n-1) s-routes covering the Minimal Steiner Tree are built in parallel. Both approaches are based on the method of the ant colony. In the general case, the search for a solution to the problem of constructing a Minimal Steiner Tree is performed by a population of clusters of agents A={Aσ|σ = 1, 2, ..., nσ}. At each iteration, the agents of each cluster Aσ = {aσk | k = 1, 2, ..., n-1} construct their concrete Steiner tree. In other words, the number of decisions generated by agents at each iteration is equal to the number of agent clusters. The method of double indirect communication is used for the first time. The method is based on the composite structure of pheromone and its differentiated deposition method. Each agent in cluster Aσ marks the path (route edges) with two kinds of pheromone: pheromone-1 and pheromone-2. The testing was performed on benchmarks. Compared with the existing algorithms, the improvement of results is achieved by 6–7 %. The probability of obtaining the global optimum was 0.94. The time complexity of the algorithm for fixed values M and T of the iterations number and population size lies in the range O(n).

Download PDF

Keywords Steiner tree; new technologies; principles; natural mechanisms; decision making; adaptive system; clusters of agents; ant colony; algorithm; optimization.
References 1. Norenkov I.P. Osnovy avtomatizirovannogo proektirovaniya [Fundamentals of computer-aided design]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2006.
2. Den'dobrenko B.P., Malika A.S. Avtomatizatsiya proektirovaniya radioelektronnoy apparatury [Automation of designing of radio-electronic equipment]. Moscow: Vyssh. shk., 2002, 384 p.
3. Promel H.J. and Steger A. The Steiner Tree Problem: A Tour Through Graphs, Algorithms, and Complexity. Friedrich Vieweg and Son, Braunschweig, 2002.
4. Zachariasen M. and Rohe A. Rectilinear group Steiner trees and applications in VLSI design, Mathematical Programming, 2003, pp. 407-433.
5. Lebedev B.K., Lebedev O.B., Chernyshev Yu.O. Osnovnye zadachi sinteza topologii SBIS [The main tasks of synthesis of VLSI topology]. Rostov-on-Don: Izd-vo RGASKhM, 2006, 184 p.
6. Lebedev B.K. Intellektual'nye protsedury sinteza topologii SBIS [Intellectual procedures for the synthesis of VLSI topology]. Taganrog: Izd-vo TRTU, 2003, 107 p.
7. Kureychik V.M., Lebedev B.K. Postroenie minimal'nogo svyazyvayushchego dereva Shteynera na osnove metoda vetvey i granits [Construction of a minimal Steiner binding tree on the basis of the branch and boundary method], Metody i programmy resheniya optimizatsionnykh zadach na grafakh i setyakh. Ch. 2. Materialy 2 vsesoyuznogo soveshchaniya [Methods and programs for solving optimization problems on graphs and networks. Part 2. Materials of the 2nd All-Union Conference]. Novosibirsk, 1982, pp. 82-85.
8. Shchemelinin V.M. Avtomatizatsiya topologicheskogo proektirovaniya BIS [Automation of topological design of BIS]. Moscow: MIET, 2001, 132 p.
9. Lisin A.V., Fayzullin R.T. Evristicheskiy algoritm poiska priblizhennogo resheniya zadachi Shteynera, osnovannyy na fizicheskikh analogiyakh [Heuristic algorithm for the search for an approximate solution of the Steiner problem, based on physical analogies], Komp'yuternaya optika [Computer optics], 2013, Vol. 37, No. 4, pp. 503-510.
10. Ryzhenko N.V. Zadacha postroeniya dereva Shteynera dlya etapa global'noy trassirovki. «Vysokoproizvoditel'nye vychislitel'nye sistemy i mikroprotsessory» [The task of constructing a Steiner tree for the global trace phase. "High-performance computing systems and micropro-cessors"], Trudy IMVS RAN [Proceedings of IMVS RAS]. Moscow, 2003, Issue 4, pp. 96-105.
11. Zaglyadin G.G., Syrtsov I.A., Shkola A.V. Algoritm sinteza mnozhestva ostovnykh derev'ev dlya vypolneniya global'noy trassirovki zakaznykh SBIS [Algorithm for the synthesis of a set of spanning trees for performing a global trace of custom VLSI], Izvestiya vysshikh uchebnykh zavedeniy. Elektronika [Izvestiya Vysshikh Uchebnykh Zavedenii. Electronics], 2010, No. 5 (85), pp. 36-40.
12. Yang, Z.-X. Geometry Experiment Algorithm Steiner Minimal Tree Problem, Journal of Applied Mathematics, 2013, pp. 1-10.
13. Rabkin M. Efficient use of Genetic Algorithms for the Minimal Steiner Tree and Arborescence Problems with applications to VLSI Physical Design, Genetic Algorithms and Genetic Pro-gramming at Stanford, 2002, No. 1, pp. 195-202.
14. Kalashnikov R.S. Eksperimental'nye issledovaniya kombinirovannogo evristicheskogo algoritm postroeniya dereva Shteynera osnovannogo na metode evolyutsionnogo poiska dlya etapa global'noy trassirovki [Experimental studies of the combined heuristic algorithm for constructing a Steiner tree based on the method of evolutionary search for the stage of global tracing], Izvestiya TRTU [Izvestiya TSURE], 2005, No. 3.
15. Lebedev V.B. Postroenie svyazyvayushchikh setey na osnove roevogo intellekta i geneticheskoy evolyutsii [Construction of connecting networks based on swarm intelligence and genetic evolution], Sbornik nauchnykh trudov XIV Vserossiyskoy nauchno-tekhnicheskoy konferentsii "Neyroinformatika-2012” [Collection of scientific papers of the XIV All-Russian Scientific and Technical Conference "Neuroinformatics-2012."]. Part 2. Moscow: Izd-vo Fizmatlit, 2012, pp. 93-103.
16. Tao Huang, Evangeline F.Y. Obstacle-avoiding rectilinear Steiner minimum tree construction: an optimal approach, Proceeding ICCAD '10 Proceedings of the International Conference on Computer-Aided Design San Jose, California, 2010, pp. 610-613.
17. Polezhaev P.N., Mironov A.P., Polyak R.I. Primenenie algoritmov murav'inoy kolonii v reshenii zadachi Shteynera [Application of the algorithms of the ant colony in solving the Steiner prob-lem], Filosofskie problemy informatsionnykh tekhnologiy i kiberprostranstva [Philosophical Problems of Information Technologies and Cyberspace], 2015, Issue No. 1, pp. 96-105.
18. Patel M.K., Kabat M.R., Tripathy C.R. A hybrid ACO/PSO based algorithm for QoS multicast routing problem, Ain Shams Engineering Journal, 2014, Vol. 5, Issue 1, pp. 113-120.
19. OR-Library is collection of test data for a variety of OR problem. Available at: http://mscmga.ms.ic.ac.uk.
20. Warme D.M. A new exact algorithm for rectilinear Steiner trees. INFORMS Conf., San-Diego, California, 1997.
21. Andrew B.K., Mandoiu I. RMST-Pack: Rectilinear minimum spanning tree algorithms. Available at: http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/RSMT/RMST/.
22. Chen H., Qiao C., Zhou F., and Cheng C.-K. Refined single trunk tree: A rectilinear Steiner tree generator for interconnect prediction, In Proc. ACM Intl. Workshop on System Level Inter-connect Prediction, 2002, pp. 85-89.
23. Hai Zhou. Efficient Steiner tree construction based on spanning graphs, In Proc. Intl. Symp. on Physical Design, 2003, pp. 152-157.
24. Griffith J., Robins G., Salowe J.S., and Zhang T. Closing the gap: Near-optimal Steiner trees in polynomial time, IEEE Trans. Computer-Aided Design, 1994, No. 13 (11), pp. 1351-1365.
25. Chris Chu. FLUTE: Fast lookup table based wirelength estimation technique, In Proc. IEEE/ACM Intl. Conf. on Computer-Aided Design, 2004, pp. 696-701.
26. GeoSteiner – software for computing Steiner trees http://www.diku.dk/geosteiner/.
27. Chu C. and Wong Y.-C. Fast and accurate rectilinear steiner minimal tree algorithm for VLSI design, In Proc. International Symposium on Physical Design. ACM Press, 2005, pp. 28-35.

Comments are closed.