Ant Colony Optimization and Rectilinear Steiner Minimal Trees by Anthony Curtis Blackman B . S c , University of the West Indies, 2003 THESIS S U B M I T T E D IN P A R T I A L F U L F I L L M E N T OF THE REQUIREMENTS FOR T H E D E G R E E OF Master of Science in T H E F A C U L T Y OF G R A D U A T E STUDIES (Mathematics) The University of British Columbia A p r i l 2006 © Anthony Curtis Blackman, 2006 Abstract This paper consists of two distinct parts. In the first part, we introduce the Rectilinear Steiner Minimal Tree (RSMT) problem and describe the Ant Colony algorithm which we use to construct the RSMT. The development of an Ant Colony algorithm called AntCol Steiner is described and we create a working program of the algorithm using the Sun Microsystems Java programming language (see appendix A to H for details). We investigate the effectiveness of our algorithm by using AntCol Steiner to construct; and draw RSMT a given a random set of terminals. In the second part, we look at an application of the Kirchoff's Matrix Tree theorem. We find the length of a Rectilinear Minimal Spanning Tree (RMST) spanning a set of random terminals. We verify the accuracy of our results from the Kirchoff's Matrix Tree algorithm using Prim's RMST Algorithm. Our original plan was to develop an algorithm based on this theorem to determine the length of a RSTM. However, we were unable to modify the algorithm we used to find the length of the RMST, for the case of a RSMT. ii Contents Abstract ii Contents iii List of Tables vi List of Figures vii Acknowledgements ix Dedication 1 2 x Introduction 1 1.1 Rectilinear Steiner Problem 1 1.2 Hanan's Grid 4 T h e A n t C o l o n y Idea 6 2.1 Ant Colony Optimization (ACO) 8 2.2 Development of A C O Algorithms for the Steiner Problem . . . . . . 8 2.3 AntGol Steiner Algorithm Intuition 10 2.4 The Most Critical Methods of AntCol Steiner 11 2.4.1 The AntColSteiner(N, M) Method 11 2.4.2 The constructSteinerTreeByACO(terminals, grid, intensity, gridLimits) Method 13 iii 2.4.3 2.4.4 2.5 3 5 minals, colony, antID, gridLimits) Method 15 The pRime(sTree, grid, gridLimits) Method 16 Formulas used in the AntCol Steiner Algorithm Kirchoff's Matrix Steiner Tree Formula 18 21 3.1 A n Application of Kirchoff's Matrix-Tree Theorem 22 3.2 Kirchoff's Algorithm for Calculating the Minimal Length of a Tree . 25 3.2.1 Time Complexity of Calculating the Determinant 25 3.2.2 Algorithm Description 27 3.3 4 The AntMove(colony[m],info[l], info[2], id, grid, intensity, ter- A n Interesting Observation 29 Results 31 4.1 Results from the AntCol Steiner Algorithm 31 4.2 Results from the Kirchoff's Matrix Tree Algorithm 32 4.2.1 32 Results from MST_via_MatrixTree_Nu(N) with N = 5 . . . . Conclusions 35 5.1 AntCol Steiner Conclusion 35 5.2 Kirchoff's Matrix Tree Conclusion 36 Bibliography 38 Appendix A Graphical Results Obtain from AntCol Steiner 40 Appendix B Source Code for InputUI.java 45 Appendix C Source Code for AntCol.java 62 Appendix D Source Code for HananGrid.java 73 Appendix E Source Code for TreeConstruct.java 83 iv Appendix F Source Code for Ant.java 98 Appendix G Source Code for Utilities.java 127 Appendix H Source Code for Display.Java 133 Appendix I Source Code for the MST_via_MatrixTree_Nu.m 136 Appendix J Prim's Algorithm using Matlab 142 v List of Tables 3.1 The T R E E . V E R T data structure 28 3.2 The V S E T data structure corresponding to table 6 28 4.1 AntCol Steiner results 32 vi List of Figures 1.1 A n example of a R S M T constucted using GeoSteiner 3.1 [14]. ... 1.2 A n example of a Hanan grid for a set T with N = 20 points 2.1 Arrow thickness represents probability of ants choosing one path over 2 5 another. (t=0) Foraging ant chooses the path based on a 50% probability; (t=l) Follower ants also choose their path on a 50% probability; (t=2) Ants that choose the shorter path get the food faster; (t=8) First forager is coming back to the nest, because more ants completed the shorter path, a greater pheromone concentration will attract the first ant to that path; (t=4) Following ants choose the shorter path with a higher probability as more and more ants choose the same path; (t=5) Alter some time of this autocatalytic process A.l the probability of ants choosing the longer path is very small 7 The Graphical User Interface of the AntCol Steiner Program 41 A.2 This Screen show the Steiner Tree before and after Priming. The prepruned tree is located in the bottom left hand corner of the figure. The primed tree is on the right hand side of the figure 42 A.3 Hanan Grid with M = 50 terminals which was generated using AntCol Steiner. On this grid the "x" represents the terminal vertices and the "o" represent the possible Steiner points vii 43 .4 The Steiner Tree with M = 50 terminals; Tree Length = 182 units and Total Time = 14016 milliseconds obtained after using the AntCol Steiner program on the Hanan Grid above A.3. On this tree the "x" represents the terminal vertices and the "o" represent the Steiner points. The parameter values are Alpha = 5, Beta = 1, Q = 1000, Rho = 0.1, Gamma = 1 and M A X L O O P = 30 viii Acknowledgements I would like to thank my supervisor, Prof. David Brydges for his guidance, his patience and for his many wonderful suggestions, corrections and remarks over the last few months. His advice and kind ways were always motivational and instrumental to my progress. Many thanks to Prof. Gordon Slade for proofreading this thesis and for his help and assistance reorganizing the thesis. I am specially grateful to the University of British Columbia, Probability Group for their generous financial support over the years. This paper is rightfully dedicated to my parents, Anthony, and Beverley Blackman and to my sister Kristle Blackman whom have all given me tremendous emotional support when I needed it most. A N T H O N Y CURTIS The University of British Columbia April 2006 ix BLACKMAN To my family Anthony, Beverley and Kristle Blackman. x Chapter 1 Introduction 1.1 Rectilinear Steiner Problem Connecting a set of points in the plane with a minimum length collection of vertical and horizontal wires is called the rectilinear Steiner problem. These spanning trees have been used often in the placement and global routing phases of circuit design since timing considerations require routing paths of minimal length. Optimum solutions to the problem have been investigated, but since the problem was proved to be NP-complete by Garey, M . R., and D. S. Johnson [7], only heuristic solutions are practical. The fastest exact rectilinear Steiner minimal tree (RSMT) algorithm is Geo-Steiner 3.1 created by David Warme, Pawel Winter, and Martin Zachariasen [14]. However, the main drawback to this algorithm is the length of time it takes to produce a solution. In figure 1.1 we illustrate a RSMT GeoSteiner 3.1 [14]. which is a solution of . .. A n .algorithm based on Ant Colony Optimization (ACO) was developed by Gurdip Singh, Sanjoy Das, Shekhar V . Gosavi, and Sandeep Pujar in [4]. Then in an attempt to find an algorithm which has faster convergence times than Geo-Steiner 3.1, an A C O algorithm based on the ideas of [4] called ACO-Steiner [9] was created. The algorithm shows significant improvements in convergence times for large values of M. However, these improvements were achieved by sacrificing the accuracy in 1 Steiner Minimal Tree: 200 points, length = 104178, 3.47 seconds Figure 1.1: A n example of a R S M T constructed using GeoSteiner 3.1 [14]. 2 determining the length of the RSMT. These conclusions can be seen from Table 1 of [9]. Ants live in colonies and have evolved to exhibit very complex patterns of social interaction. Such interactions are clearly seen in the foraging strategy of ants. Despite the extremely simplistic behavior of individual ants they can communicate with one another through secretions called pheromone. This cooperative activity of the ants in a nest gives rise to an emergent phenomenon known as [2], swarm intelligence Ant Colony Optimization (ACO) algorithms are a class of algorithms that mimic the cooperative behavior of real ants to achieve complex computations. Ant colony optimization was originally introduced as a metaheuristic for the well-known traveling salesman problem (TSP), which is a path based optimization problem. This problem is proven to be NP-complete, which is a subset of a class of difficult optimization problems that are not solvable in polynomial time (unless P = N P ) . Since an exponential time algorithm is infeasible for larger scale problems in class NP, much research has focused on applying stochastic optimization algorithms such as genetic algorithms and simulated annealing to obtain good (but not necessarily globally optimal) solutions. The ant colony approach is a stochastic algorithm with some ability to learn from previous attempts to solve the problem. Definition 1.1.1 A tree is said to be rectilinear if all of its edges are horizontal or vertical. Definition 1.1.2 The RSMT problem is described as follows [9]. Given a set T' of M points called terminals in the plane, find a set S of additional points called Steiner points such that the length of a rectilinear minimal spanning tree with vertex setTuS is minimized. Definition 1.1.3 The cost between vertex i and vertex j is c(i,j), Manhattan distance between vertex i andj. 3 which is the Definition 1.1.4 The Manhattan distance function computes the distance thai would be traveled to get from one data point to the other if a grid-like path is followed. The Manhattan distance between a point i = (i\,i'2) and a point j = (ji,.72) 'is: c{i, j) =| h - ji 1.2 I + I ii - J2 I . Hanan's Grid Definition 1.2.1 Given a set T of-M points in the plant, the Hanan grid [8] is obtained by constructing a horizontal and a vertical line through each point in T. This grid is very helpful since the following theorem by Hanan [8] states that all of the possible Steiner points S can be found at intersections of this grid. This can be stated more precisely as follows: Theorem 1.2.1 A shortest rectilinear Steiner spanning tree over a set of points exists on the Hanan grid induced, by the points. From looking at the figure 1.2 this theorem is intuitive since the edges of any rectilinear spanning tree can only coincide with the edges of the grid. That, is every possible rectilinear spanning tree is a subset of the Hanan grid. 4 (1-1) * 1 i i ! J i^- "' -< > • — — — — — j ,• ! > i t 1 Figure 1.2: A n example of a Hanan grid for a set T w i t h N = 20 points. 5 i | | | Chapter 2 The Ant Colony Idea T h e A n t System algorithm is biologically inspired by the foraging pattern of ants. N a t u r a l ants when following a pheromone trail decide where to go next based on the concentration of pheromone in a given direction. Deneubourg [5] performed an experiment with real world ants that consists of a trail leading from the ant's nest to a food source. A l o n g the way. at certain points the trail branched into two paths of equal length, then unified into one trail again shortly after. In a controlled environment, ants in search of food would follow that trail and then would have to decide which branch to take. T h e first ant has no additional information on which to base its decision, so it just chooses any one of the two at random. Other ants following will also choose with roughly equal probability. W h e n the first ant is coming back from the food location towards the nest, it again will randomly choose one of the trails because the amount of pheromone in the two trails will be very similar. T h e next experiment, known as double bridge made things very clear. A g a i n , the ants are i n an artificial controlled environment where there is a path from their nest to a food source. T h i s time, there are two bifurcations i n sequence as i n figure 2.1, but unlike the first experiment, one branching path is shorter than the others. Initially the situation will be the same as the first experiment, but when the first ant is returning from food to nest, the concentration of pheromone 6 in the shorter path will be stronger, simply because the How of ants using that path was greater due to the length difference. Ants who chose the shorter path will get to the unification point sooner that the ones who chose the longer paths. This autocatalytic process starts to repeat over and over, and soon almost all ants will be choosing the shorter path over the longer ones. Figure 2.1: Arrow thickness represents probability of ants choosing one path over another. (t=0) Foraging ant chooses the path based on a 50% probability; (t=l) Follower ants also choose their path on a 50% probability; (t=2) Ants that choose the shorter path get the food faster; (t=3) First forager is coming back to the nest, because more ants completed the shorter path, a greater pheromone concentration will attract the first ant to that path; (t=4) Following ants choose the shorter path with a higher probability as more and more ants choose the same path; (t=5) After some time of this autocatalytic process the probability of ants choosing the longer path is very small. 7 2.1 Ant Colony Optimization (ACO) F r o m the conclusion of the experiments of Deneubourg an algorithm based on these observation seems to be a natural approach to obtaining an approximate time efficient solution to the Steiner problem. Algorithms which mimic this natural behavior of ants are called A n t Colony Optimization meta-heuristic algorithms. 2.2 Development of ACO Algorithms for the Steiner Problem T h e A n t Colony Optimization algorithms employs a cooperating colony of ants in an attempt to find good solutions to difficult discrete optimization problems. Cooperation is a key design component of A C O algorithms. In these algorithms the artificial ants share the computational resources and communicate among each other indirectly. G o o d solutions are an emergent property of the artificial ants cooperative interaction. Artificial ants have a double nature. First, they are an abstraction of real ants found i n nature and of their behavior. O n the other hand, artificial ants have also been enriched with some capabilities which are not found among their natural counterparts. Since the artificial ants axe employed i n software to solve difficult discrete optimization problems, it, is reasonable to give the ants some capabilities, which while not found i n real ant behavior, make them more efficient and effective. We will comment on this more later. First, i n a paper called " A n t Colony Algorithms for Steiner Trees: A n A p plication to R o u t i n g in Sensor Networks" an algorithm based on A n t Colony O p timization was developed by G u r d i p Singh, Sanjoy Das, Shekhar V . Gosavi, and Sandeep Pujar. T h i s algorithm can be found in [4]. In this paper, the authors verified their results using various problem instances taken from Beasley [1]. T h e test, cases described i n problem set B , Beasley 8 [1], which consisted of randomly generated graphs whose edges were assigned weights between 1 and 10, were used. The test cases chosen consisted of instances with 50 to 100 nodes, and up to 200 edges. These problem instances all had well known optimal solutions and the authors used Beasley's results to determine the accuracy of their algorithm. In [4] the authors used Matlab to implement three strategies for selecting the ants to be moved between vertices. These strategies were: 1. Fixed sequence strategy: Here the ants are picked in a fixed sequence, for reassignment into a different vertex. After the last ant is moved, the algorithm is reset to pick the first, ant in the fixed sequence. 2. Shuffled sequence strategy: Here the algorithm also iterates through the ant set. However, after each ant, was moved to a different location exactly once, the algorithm shuffles the order of the ants randomly before beginning all over again. 3. Random strategy: In comparison to the other methods, this approach is the most random way to move ants. No ordering is maintained, and an ant is picked up for movement, from the set of all existing ants in a random manner with uniform probability. From among these strategies the Random approach gave the best results when compared to [1] problem set, B . Secondly, an Ant Colony Optimization Steiner Algorithm called ACO-Steiner was developed by Hu, Jing, Hong, Feng, Hu and Yan [9]. In this case they looked at the R S M T problem on the Hanan's Grid. They used C++ to implement their algorithm and used the Random strategy described in [4] to select the ants to be moved between vertices. The experimental results of ACO-Steiner were compared with Geo-Steiner 3.1 and showed that ACO-Steiner could produce shorter running times while keeping comparable high performance. 9 2.3 AntCol Steiner Algorithm Intuition After seeing the results of applying the A C O to the Steiner problem in [4] we decided to develop an A C O algorithm called AntCol Steiner using Java as the language of implementation. AntCol Steiner is a hybrid between the ideas of ACO-Steiner and the algorithm found in [4]. Before we get into the details of the AntCol Steiner algorithm. I will present an intuitive overview of how the algorithm really works. Note that the ants in our program use information that would not be available to more realistic ants such as the distance to the closest trail of another ant. The following steps, which build a tree, are repeated JVIAXLOOP times: Every ant is initially at a terminal. A n ant is selected at random and moved until it dies as described below. Then a remaining ant is selected at random and so on until only one ant is left. Each ant has a "tabu list", called "tour", of points in the Hanan grid that it is forbidden to move to. Initially this list contains only the terminal where the ant starts. Each Hanan grid point visited by the ant is copied into the ant's tabu list. When an ant first encounters a point in the tabu list of another ant, it appends its tabu list into the other ant's tabu list and it dies. The moving ant deterministically moves to a neighboring grid point according to the formula (2.4) unless it is trapped. Formula (2.4) requires extensive explanation which will be given later, but the idea is that one selects the neighbor in the Hanan grid move according pheroinone level and according to how close the neighbor is to the tabu list of some other ant. because the tree is short if the ants die quickly. If the moving ant is trapped then it is repeatedly relocated to a randomly chosen point in its tabu list until it is no longer trapped. In the program this procedure is called "de-confused". After all but one ant has died the tree is pruned in order to remove dead-ends created when ants get trapped. Next, the pheromone on the edges of the Hanan 10 grid is updated. If the length of the pruned tree is smaller that that of the best previously found tree then the previously found tree is replaced by the new one. 2.4 The Most Critical Methods of AntCol Steiner In this section we describe the core methods of the A n t C o l Steiner program. These methods are AntColSteiner, constructSteinerTreeByACO, A n t M o v e and pRune. AntColSteiner is used to select the best of a l l possible trees. constructSteinerTreeB y A C O implements the ant selection strategy and constructs the tree by merging the trails of each of the selected ants when they meet. A n t M o v e is used to determine which direction the ant should move v i a the Hanan grid. Finally, the pRune method removes all non terminal leaves from the tree obtained from constructSteinerTreeByACO. 2.4.1 The AntColSteiner(N, M) Method INPUT ARGUMENTS: N : T h i s is the dimensions of a square grid. M : This is the number of terminal points that are randomly generated and placed inside the square array. OUTPUT A Rectilinear Steiner Tree 1. B E G I N . 2. A n N by N array of string type is initialized with blank spaces. 3. M random vertices are generated. T h e y have the form (r, c) where r represents row r and c represents column c of the grid, r and c were chosen to be even numbers so that each point i n the grid was at least one space away from the other points. The only reason vertices were placed i n rows r and columns c w i t h even indexes was to make our output easier to understand. 11 4. A t each v e r t e x ( r , c) t h e l e t t e r x is p l a c e d o n t h e g r i d t o i n d i c a t e t h a t a t e r m i n a l v e r t e x is c r e a t e d . 5. U s i n g t h e t e r m i n a l vertices a H a n a n G r i d is g e n e r a t e d . D u r i n g t h e c o n s t r u c t i o n o f t h e g r i d each t i m e a v e r t i c a l edge a n d a h o r i z o n t a l edge crossed, t h e l e t t e r o is p l a c e d o n t h e g r i d t o represent a possible S t e i n e r p o i n t . 6. A n e q u a l a m o u n t o f p h e r o m o n e is p l a c e d o n each edge o f t h e Ha,nan G r i d . T h i s represents t h e i n i t i a l t r a i l i n t e n s i t y . 7. A n a n t d a t a s t r u c t u r e is c r e a t e d a n d M instances o f t h e data, s t r u c t u r e axe d e c l a r e d a n d i n i t i a l i z e d . T h e s e are o u r a r t i f i c i a l a n t s . 8. I n i t i a l i z e t h e bestSteinerTree = c o n s t r u c t S t e i n e r T r e e B y A C O ( t e r m i n a l s , grid, intensity, g r i d L i m i t s ) see t h e d e s c r i p t i o n o f t h i s m e t h o d b e l o w . 9. bestSlength = g e t T L e n g t h Q T h i s m e t h o d gets t h e l e n g t h o f t h e S t e i n e r tree j u s t g e n e r a t e d . 10. B E G I N 11. WHILE while(couut < MAXLOOP) • F O R each edge i n t h e H a n a n g r i d - IF * T h e a n t w a l k e d o n edge o f t h e g r i d d u r i n g t h e p r e v i o u s i t e r a t i o n s , u p d a t e t h e p h e r o m o n e i n t e n s i t y a l o n g t h a t edge u s i n g updateIntensity(sLength, • row, col, intensity) - E L S E r e d u c e t h e level o f p h e r o m o n e i n t e n s i t y . - ENDIF ENDFOR 12. steinerTree = c o n s t r u c t S t e i n e r T r e e B y A C O ( t e r m i n a l s , grid, intensity, g r i d L i m i t s ) 12 13. s L e n g t h = getTLength() This method returns the length of the Steiner tree just generated. 14. indicate = chooseBestSol(bestSlength, sLength) returns true if old tree is still the best. • IF (indicate) - keep the bestSteinerTree. • ELSE — copy the content of steiner Tree into bestSteinerTree. • ENDIF 15. count = count + 1. 16. E N D W H I L E . 17. After M A X L O O P iterations bestSteinerTree was displayed. 18. E N D . 2.4.2 T h e c o n s t r u c t S t e i n e r T r e e B y A C O ( t e r m i n a l s , grid, intensity, gridLimits) Method. INPUT ARGUMENTS: terminals: This is a two dimensional integer array used to store all of the vertices in such away that (terminals[i)[Q], terminals = (r,c)i where i represents the ith vertex that was randomly generated. g r i d L i m i t s : This is an integer array used to store the border values of the grid in the following manner: g r i d L i m i t s [ 0 ] = x m a x This is the value of the last row of the Hanan's grid. g r i d L i m i t s [ l ] = y m a x This is the value of the last column of the Hanan's grid. g r i d L i m i t s [ 2 ] =. x m i n This is the value of the first row of the Hanan's grid. gridLimits[3] = y m i n This is the 13 value of the first column of the Hanan's grid, intensity: This is the an array that stores the intensity values for all of edges in the Hanan's grid. O U T P U T A Rectilinear Steiner Tree 1. B E G I N 2. Place an ant on each of the M terminal vertices (r, c) of the Hanan's grid using the place A n t (tool, colony [i], terminals [i] [0], terminals[i][l], i) method for i = 1 to M. 3. W H I L E • while(ant number greater than one) • choose one of the ants sitting on the vertices of the grid randomly. • Move the chosen ant to one of its neighboring vertices using the info = A n t M o v e ( t o o l , colony[m],info[l], info[2], i d , grid, intensity, terminals, colony, a n t I D , g r i d L i m i t s ) method. • W H I L E The ant k is not at a vertex in the tabu list of another ant - Continue moving him using the info = A n t M o v e ( t o o l , colony[m],info[l], info[2], i d , grid, intensity, terminals, colony, a n t I D , g r i d L i m its) method. • END WHILE • IF The ant k met a vertex in the tabu list of ant r. - The tabu list of ant r is expanded so as to include the tabu list of ant k. . - Ant k will be killed. - ant number = ant number - 1 ; - Ant r will be relocated to another vertex in its own tabu-list. • E N D IF 14 4. E N D W H I L E 5. sTree = pRune(sTree, grid, g r i d L i m i t s ) This method was used to remove all leaves that were not terminals. 6. R e t u r n sTree 7. E N D 2.4.3 T h e A n t M o v e ( c o l o n y [ m ] , i n f o [ l ] , info[2], i d , g r i d , i n t e n s i t y , t e r m i n a l s , colony, a n t I D , g r i d L i m i t s ) M e t h o d . INPUT ARGUMENTS: info[l] stores the current row the ant occupies. info[2] stores the current column the ant occupies, colony This stores the entire nest of ants and their personal information such as nodes visited, colony [m] This is the current ant that has been selected to move, i d This is the indicator that was used to determine if an ant met the tabu list of another ant or not. If the ant met another ant i d would store the identification number of the ant it met. Else, i d would have the value of — 1. a n t I D This is an array which indicates the mortal status of the ants in the colony. If antID[i] = — 1 this means ant i is dead. If antID[i] = 1 this means ant i is alive. 1. B E G I N 2. The: ant who was chosen, will "stand up" and look around at all of its immediate nearest neighbors vertices (possible Steiner points as well as terminal vertices). A n ant can have at most four such neighbors on the Hanan Grid. 15 • IF any of its neighbors are in the tabu list (tour) then it is not allowed to visit that neighbor again. That means that the weight of visiting that vertex is 0. • E L S E The ant will calculate the weight to move to that vertex via the edge on the Hanan Grid by using.a formula (2.4) which takes into consideration the pheromone intensity (2.2) levels and the ant's desire (2.1) to go to its neighbor. • ENDIF 3. IF • all the weight to visit its neighboring vertices is zero then the ant is trapped. In this case we have to "de-confuse" the ant. De-conmse means to repeatedly place it at a random location in its tabu list until it is not trapped anymore. This de-confusion was executed using the deconfuse(m,terminals, grid, antlndex) method. 4. E L S E • There will be positive weight to visit one of its neighbors. So after all the weights of visiting its possible neighbors have been calculated the ant moves to the neighbor with the highest weight. 5. E N D I F 6. Return info 7. E N D 2.4.4 The pRune(sTree, grid, gridLimits) INPUT ARGUMENTS: 16 Method A unpruned Rectilinear Steiner Tree called slYee. During the execution of the program there are occasions when the ant has nowhere to go because the weight to visit all of its neighbors is zero. In this case the ant is said to be confused and has to be de-confused. The de-confuse method repeatedly places it on a random vertex in its tabu list until the ant is no longer confused. What happens during this procedure is that the trail which caused the ant to be trapped is left on the grid and is a dead end trail. The end of the trail is a vertex which is not in the tabu list of another ant. This is because if it was then the ant would have met another ant, died and would not have been confused. Therefore the only other possibility is that the vertex has to be a possible Steiner point. This fact plus the fact that the vertex is at the end of a dead end trail means that it is a non terminal leaf in the tree. These non terminal leaves ha,ve to be trimmed off the tree. This process of trimming off all of the non terminal leaves and their trails is called pruning. The pRune method is used to perform the pruning in the AntCol Steiner program. O U T P U T A Pruned Rectilinear Steiner Tree called sTree. 1. B E G I N 2. F O R loops = 0 to loops = NSquared • FOR, row = gridLimits[2] to gridLimits[0] - F O R col = gridLimits[3] to gridLimits[l] * IF grid [row] [col] is N O T "x" A N D sTree[row][col] is N O T " " • calculate the degree of the sTree element at position (raw, col) • IF the degree of the element at position (row, col) of sTree is equal to one then delete s1ree[row][col] • ENDIF * ENDIF col = col + 1 17 - ENDFOR row = row + 1 • ENDFOR loops = loops + 1 3. E N D F O R 4. R e t u r n s T r e e 5. E N D R e m a r k 2.4.1 Since all of the ants were leaving pheromone on the edges of the Hanan grid, they crossed, there will be edges which have strong pheromone levels and edges which do not have a high concentration of pheromone. Therefore the edges with the highest pheromone levels will have a higher probability of being crossed, again thus further increasing the probability of being crossed in the future iteration of the algorithm. This means that the more often a path, is crossed the more likely it will be to be crossed in the future. The convergence theory of Ant Colony algorithms can be found in section 4-3 of [6], but the results there do not claim that the algorithm, converges to a minimal tree. 2.5 Formulas used in the AntCol Steiner Algorithm. In AntCol Steiner, we generate the Hanan Grid of the terminal set T. Then we place ants on each element of T. A n ant, i then determines a new vertex j to visit, via an edge of the Hanan grid. The choice is based on a higher value p^j, which is a trade-off between the desirability and the trail intensity. Each ant maintains its own tabu-list, which records the vertices it visits to avoid revisiting them again. Then in the case where ant T meets ant $2, ant, T dies, and adds the vertices in its tabu-list into the tabu-list of ant il. After every movement of an ant the trail of the ant is 18 also recorded in a data structure called globalView. This data structure allow us to see the interaction of the ants while they are building the RSMT. Each ant in the globalView data structure is identified via its identification number. Therefore, the trail of ant 2 would be displayed as sequence of 2's on the path of the trail in the globalView data structure, while the trail of ant 3 would be displayed as a sequence of 3's on the path of the trail in the globalView data structure and so on. At the point the ant T meets ant fi, ant V dies and the trail labeled T in the globalView data structure would be merged with iVs trail in the globalView data structure. Thus, all Ts will be changed to fls in the globalView data structure to reflect iVs new trail. The trail intensity is updated at the end of each iteration of M A X L O O P . The globalView data structure eventually contains the ant identification number on the trail of the only surviving ant. This identification trail is used to display the R M S T before pruning. Let j be a neighbor of i in the Hanan grid. Given an ant m, on vertex i, the desirability of vertex j is: W! . = (o I) - 71 \c(i,3)+l-m ' where 7 is a constant, ip™ is the distance from vertex i to the nearest vertex in the tabu-list of another ant. This makes the current ant join into others as quickly as possible. The superscript m is there because 'ip™ depends on the previous ant trails. The updating of the trail intensity in the Hanan edge is defined as follows: T,j(t + l) = (l-p). (t) TlJ + p • ATij(t) (2.2) where p is a constant, representing the pheromone evaporation parameter, t, which is called count, is the variable that ranges between 1 and M A X L O O P in our earlier summary on page 10. The increments of updating is given by the following formula: 19 I c(S(i)) Sm if V(*,u I 0 otherwise Ar, (t) = I " d where c(S(t)) o f S(t) j) € E(t) ' (2.3) K is t h e t o t a l c o s t o f t h e c u r r e n t S t e i n e r t r e e S(t). E(i) is t h e e d g e s e t a n d Q is a p a r a m e t e r c o n s t a n t t h a t s p e c i f i e s t h e a m o u n t o f p h e r o m o n e the s u r v i v i n g ant has to d i s t r i b u t e t h r o u g h its trail. T h e w e i g h t o f a n ant at i t o m o v e o n edge (t) = l Pid [ Efch.fcWl-Kil" 0 if j 6 A and k 7 is d e n n e d a s * tabu-list follows: (rn) ( 2.4) otherwise w h e r e A is t h e s e t m a k i n g u p o f a l l v e r t i c e s w h i c h a r e c o n n e c t e d w i t h i a n d i s n o t i n t h e t a b u - l i s t o f a n t in. T h e p a r a m e t e r s a a n d [3 c o n t r o l t h e r e l a t i v e o f e a c h v a r i a b l e 77. - a n d ij™ 7 section i n (2.4). importance T h e r e s u l t s o f t h i s a l g o r i t h m c a n b e seen 4.1. 1 20 in Chapter 3 Kirchoff's Matrix Steiner Tree Formula This section describes an algorithm to calculate the length of a minimal spanning tree on N vertices using the matrix tree theorem. The algorithm is 0(N ) 3 but not as fast as the standard Prim's algorithm [13] which can be shown to run in time which is O(ElnN) where E is the number of edges. The reason we looked at this method was that we hoped that we could adapt it to find the length of the minimal Steiner tree without calculating the Steiner tree or the Steiner points and perhaps thereby avoid the N P completeness problem, but we have not so far found a formula in terms determinants that properly accounts for Steiner points. For this reason the content in this chapter is not closely related to the previous chapters of this thesis and only represents a possible future direction. The matrix tree theorem is as follows. Let A p be a symmetric N x N matrix a whose row sums are zero except for the first row which sums to one. T h e o r e m 3.0.1 Kirchoff's matrix-tree theorem [12]. detA = ^2 21 Y[ A a0 ,N] and where T is summed over all tree graphs with vertex set {1,2,- a,peT means {a, (3} is in the edge set of T. 3.1 A n Application of Kirchoff's Matrix-Tree Theorem Let Vertex.set = {A" } be a finite set of points in the plane. These are the terminals. a We are about to describe a way to calculate the length of a minimal spanning tree. Note there are no Steiner points. Let K a and Kp e Vertex.set. If K = (i ,ja) a and Kp = {ip,jp) for any a a, (3 = 1, 2. • • • , JV, the Manhattan distance c(K ,Kp) a between K a and Kp is given by definition 1.1.4. Define the matrix A ( m ) by _ -m-c(K ,Kp) if a ^ (3 a e A p{m) = a -m. (K ,A- ) EA C A 7 + 5 L r ) a S l fp) I F Q, = (3-1) ^ From this definition A ( m ) is a symmetric matrix of the form i4 (m) ... A \(m) 2 A (m) ... \ A (m) A (m) ... ' An(m) , A(m) = A / Ny 12 22 N2 Ai/v(?n) \ A (m) 2N A (m) NN J with -Ay(m) = Aji(m), that is ( A ( m ) ) = A ( m ) . Further all of the row sums of T A(m) are zero except for the first row which sums to one. That is and E/tLi ^i/.-( ) EALI Ajk(m) = 0 for each row j = 2, • • • ,N. Using this definition and the Matrix-Tree Theorem 3.0.1 we obtain. 22 m = 1 det A(m) = Y II / T e~ m<Kc a,f)eT T -m(Totat.J.engUi(T)) Further, we can fix A?" and take m —* oo and consider — In det A ( m ) 1_ m 1 In det A ( m l We obtain ,-m-(TolalJength,(T)) m 1 j n g—m(M inimumJength(T)) m = — Minimum Jength(T) F r o m this we have a formula for calculating the length of the m i n i m u m spanning tree T v i a det A ( m ) . E x a m p l e 3.1.1 Consider the graph G which has three vertices labelled V\, Vi and, V-i. Let the rectilinear distance between each vertex be defined as follows. c(V\, V2) = 2, c(V*i, V3) = 3 and c(V2, V 3 ) = 6 then the length, of the minimum spanning tree of G is clearly c(V\,Vi) + c(Vi, V3) = 2 + 3 = 5. I will demonstrate the Matrix-Tree theorem by calculating the length of the minimal spanning tree using (3.1). T h e distance matrix D for the example above is given below. In this matrix D an element i n row % and column j represents the rectilinear distance between vertex Vi and vertex Vj. ( 0 D 2 \ 3 23 2 3^ 0 6 6 0 j From this we obtain: + e-'im\ (1 + e- 2m A(m) = -2m _ -2m —e . -2m -e - 6 m - e~ —e- 6 m . - 3 m - 3 m e / - 3 m e + e - 6 m A Therefore. + e- ) (e- detA(m) = {1 + e- Am —2m —e -5»n = e Now - 5 m 2m im -e- " - e 9 -8m. -3?n 2e- 1 7m 1 + 2e~ + e2m _ 2 m + e - 6 m (e- 3 m + e~ +e 3 m + e" ) - 6m ) 6?r« + e-9 m . + 2 e --1 0 m + 4e ym 3m + e" ium + 2e" 4m 1 2 m e _ 6 m , „—Zmi„—2m 8m )(e- 5m -11m + 4e- 6m if we take natural logs on both sides we obtain, In det A(m) = —5m + In 1 + 2e~ + e~ 3m 2m + e•4m + 2 e - 5 m + ^-Sn. which implies that, 1 In det m In - 3 m 1 + 2e- 2 m . A(m) = - 5 + +< " + 2e~ + 4e — l! 5m 6?7? m Therefore we conclude that, — lndetA(m)| rn [ 1 as m —> oo. So the absolute value of our limit agrees with the length of the minimal spanning tree as expected. Now that we have an idea that this technique actually work we will now develop an algorithm to compute the length of the minimal spanning tree of a graph G which has n randomly generated vertices. 24 3.2 Kirchoff's Algorithm for Calculating the Minimal Length of a Tree In the previous section we saw aformulathat related the minimal length of T to det A ( m ) . Now we verify that det A ( m ) can be computed in polynomial time. In fact it can be shown that there exists an algorithm that will calculate the det A ( m ) with time complexity 0(n ). The main idea behind this algorithm is Gaussian ,:i Elimination. 3.2.1 T i m e Complexity of Calculating the Determinant For simplicity in notation of the proof we will write det(A) instead of det A ( m ) . The idea is to evaluate det (A) by reducing the matrix A to an upper-triangular form, in which case the determinant is just the product of elements on the diagonal. The general algorithm is, for an n x n matrix: FOR i = 2 • • • n row FOR, j = 1 • • • i — 1 row above FOR k — j • • - n column to be reduced Aji- := An,- — • A-jk (consider this to take constant time K). In practice, we need to take precautions against the situation in which Ajj = 0, but this does not change the order of the algorithm, so will not be considered here. Once a matrix is in upper-triangularform,its determinant is just the product of elements on the diagonal det (A) = IX;^"! s o it c a n he evaluated with (n — 1) multiplications which takes order 0(n) time. T h e o r e m 3.2.1 The cost of calculating det(A) for a general n x n matrix using Gaussian Elimination is 0(n ). A Proof. Let C(n) be the cost to calculate the det(A) for a general n x n matrix A then, 25 7—1 77 71 ,'=2 j=\ k=j 71 7—1 7=2 J= ] i-1 = / r £ | ( „ + i ) ( i - i ) - £ ; j 7=2 77 »(» - 1) 2 (n+l)(i-l) 7=2 77 i ( i - 1) (n + l ) ( i - l ) 7=1 K 77 r -i - (2n + 3)i - 2{n + 1) 2 i=l •n(n + l)(2ra + 1) + n(n + l ) ( 2 n + 3) 2??.(?7, + 6 = A' n(??,+ 1) 1 + 2n n(n + 1) K 2n + 3 + 4(n- _ 1) O 1) 6 K = K 2n(n + l ) ( n - 1) 6 n(n 2 - 1) 3 G 0(r? 3 Since the cost of now evaluating the determinant of the upper-triangular m a t r i x is just O ( n ) , it is correct to say that the cost C(n) of the whole procedure is 0(n ). 3 R e m a r k 3.2.1 In [11] there, are algorithms which can calculate the determinant of a matrix A faster than 0 ( n , ) . 3 26 3.2.2 A l g o r i t h m Description In this section, a detailed algorithm for determining the length of a minimum spanning tree T with N vertices is outlined. The algorithm is based on Kirchoff's MatrixTree theory and has a time complexity of 0(N ). ii 1. BEGIN 2. Create a N x 3 array and call it VSET (Vertex.Set). 3. Set all of the elements of array VSET to zero. 4. Create two arrays of size N x N. Call the first one MTREE and the other one TREE.VERT 5. Set all of the elements of MTREE (Matrix JTree) (Tree-Vertex). and TREE.VERT to zero. 6. FOR k = 1 to N • Generate a random number between 1 and N. • Store the number in i. • Generate a random number between 1 and 7V. • Store the number in j. • At position k insert, value of k in column 1; value of % in column 2 and the value of j in column 3 of VSET. • Put a 1 at position (i,j) in TREE-VERT ENDFOR E x a m p l e 3.2.1 Consider the arrays below which illustrates the contents of arrays TREE.VERT and, VSET for a tree with N = 6 randomly generated points. 27 i/j 1 2 3 4 5 6 TREE.VERT 1 2 3 4 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 5 0 0 0 0 0 0 6 0 0 1 0 0 0 Table 3.1: The TREEJVERT data structure. VSET k i 1 1 2 2 3 3 4 3 5 5 6 6 j 1 4 2 6 3 2 Table 3.2: The VSET data structure corresponding to table 6. 7. FOR m = 1 TO MAXLOOP • FOR a. = 1 TO N. - FOR (3—1 TO N * IF a = fi THEN • SET MTREE[a]\f}\{m) TO E ^K K e~ < ^ ^ m a K * ELSE • SET MTREE{a}[[3](m) TO - - < °> p) m K e * ENDIF - ENDFOR • ENDFOR • Calculate determinant of MTREE(m.) • Take the log of the determinant of MTREE(rn) • Divide log of determinant of MTREE(m) by m. K K + 6i(a)8) {(3) ENDFOR 9. Choose the max{MTREE(m)} to estimate the value of c(MST) 10. Print the results. 11. END. 3.3 A n Interesting Observation Remark 3.3.1 Vm > 1 c(MST) > MTREE(m) Proof. Since, detA(m) = £ J] - - * m c( a KB) e a,/3eT T n< -mc(K ,K ) > a fi a,/3er we have lndetA(m)> ^ In -'" ( '- » c A A e a,/3eT ]P -771 c ( K aJ<l3), which implies, 1 In det A ( m ) m T z c(K ,Kp) a a,/3GT > - - In det A ( m ) —' 777, Hence, c(MST) = nun ^ L a,/3eT c(K ,Kp) a > m In det A ( m ) 29 MTREE(m) Vm > 1 This statement clearly states that the minimum length of the tree will always be greater than or equal to the computed value MTREE(m). Knowing this fact we implement a Kirchoff's Matrix Tree Algorithm called MST.via_MatrixTree_Nu.m. The results of these algorithm are discussed in the next chapter. 30 Chapter 4 Results 4.1 Results from the AntCol Steiner Algorithm In order to get sufficiently good results from the limited number of iterations of MAXLOOP, all the parameters were set to the default settings which were taken from the algorithm in the paper by Gurdip Singh, Sanjoy Das, Shekhar V. Gosavi, and Sandeep Pujar [4] since they achieved optimum results with their values. The total length of the tree is calculated to be the total number of dashes in the tree as shown in figure A.4. In the case of figure A.2, the before and after pruning images axe displayed. Pruning is the process of removing all non terminal leaves from the resulting Steiner tree. Alter each execution of the program, the execution time and tree length was recorded and their averages were calculated over 10 executions of the program with fixed values of N and M where N is the side length of the square grid and M is the number of terminals. These experiments are all preformed on an Intel Pentium 4, 2.6 GHz custom built computer with 1 GB of DDR 400 RAM running Microsoft Windows XP Professional Edition with Service Pack 2. The results "obtained are shown in the table 4.1 below. Screen shots and graphical results of AntCol Steiner can be seen in Appendix A. The source code for the entire program can be found in Appendix B to Appendix H. 31 M 9 - 12 15 20 25 30 40 50 70 100 Avg. Steiner Tree Length 38 71 73 103 129 170 182 220 340 370 N 25 30 30 30 30 40 40 40 50 50 RESULTS Avg. Time (s) 0.750 1.062 1.203 1.812 1.907 4.390 4.557 6.915 20.127 25.266 Best Steiner Length 32 69 71 97 113 167 175 215 305 343 Best Time 0.554 0.996 0.998 1.132 1.787 3.980 4.012 5.788 15.876 17.437 Table 4.1: AntCol Steiner results. 4.2 Results from the Kirchoff's Matrix Tree Algorithm For the Kirchoff's Matrix Tree theorem we implemented the algorithm via the Matlab programming language. We called our program MSTJuia-MatrixTreeJVu(N) where A is the dimension of the matrix. In'the next section one will find step by r step execution of the program. The source code for MSTjvia.MatrixTree-Nu(N) can be found in. Appendix I. 4.2.1 Results from MST_viaJVIatrixTreeJNu(N) w i t h N = 5 T h i s r e p r e s e n t s t h e s e t o f random v e r t i c e s g e n e r a t e d program. VSet = 1 5 2 2 3 1 2 3 3 32 by t h e 4 5 3 5 2 4 The next table displays the values of MTREE(m) f o r d i f f e r e n t values of m. As you can see i n t h i s case the value of MTREE(m) when m = 10 i s the same as the value of the length of the MST generated by Prim's Algorithm. Also note that we actually approach the length of the MST from below as m got larger. MinTreeValues = m MTREE(m) 1 0000 4 4456 2 0000 5 6934 3 0000 5 9204 4 0000 5 9775 5 0000 5 9933 6 0000 5 9979 7 0000 5 9993 8 0000 5 9998 9 0000 5 9999 10 0000 6 0000 maximum = 6.0000 This show the o r i g i n a l distance matrix. 33 Distance_Matrix 0 5 4 1 5 5 0 1 4 2 4 1 0 3 1 1 4 3 0 4 5 2 1 4 0 The l i s t below show t h e edges of t h e MST. T h i s l i s t is genera using Prim's Algorithm. MST = 3 2 4 1 5 3 3 4 T h i s l e n g t h i s t h e e x a c t l e n g t h o f t h e MST g e n e r a t e d by P r i m ' Algorithm. MSTree_length = 6 34 Chapter 5 Conclusions 5.1 AntCol Steiner Conclusion The ACO Algorithm is a natural algorithm for achieving good estimates of the Rectilinear Steiner Tree Problem. The main achievement here has been to get the algorithm working properly, but it is certainly not written in an optimal way yet and it does not yet compete well with the results claimed in [9]. Upon analyzing the results, my first suggestion for trying to improve the convergence times of the algorithm for large instances of M concerns the pRune method. In the AntCol Steiner program the pRune method carried out a very expensive operation. Thus, in future versions of AntCol Steiner this method will be eliminated. With the current version of the AntCol Steiner program, the Steiner tree has to be pruned because every time an ant is confused it leaves a dead end trail on the graph which is ultimately a non-terminal leaf. An alternative solution to the pR.une method would be to use a stack data structure where, the coordinates of each step of the ant are pushed onto the stack until it meets the trail of another ant. If it moves to a vertex and is not confused then we can easily pop the steps back off the stack into its tabu list thereby, marking the ant's trail. On the other hand if the ant is confused it will be placed at a non confusing position within its tabu-list and the ant would restart its walk. Then we would delete all of the coordinates inside the 35 stack and push the ant's new steps into the stack as soon as the ant starts walking. When the ant finally meets the trail of another ant we will continue as described above. Other improvements to speed up ACO algorithms were suggested in [10]. The improvements included techniques to reduce the search space. ACO-Steiner and AntCol Steiner were implemented on the Hanan's grid, therefore., if one can create a. technique to reduce the size of the grid without losing valid information we would in fact reduce the search space. This would cause the algorithm to be much more efficient. The three techniques mentioned in [10] were called Convex Hull Reduction: fulsome Steiner tree (FST) Reduction and Terminal Reduction. It is our belief, that ACO algorithms are one of best heuristic algorithms used for finding Steiner Trees. This is because they naturally have very short convergent times which makes them very practical. 5.2 Kirchoff's Matrix Tree Conclusion The results of this experiment verified the theory that the length of a MST can be determined using this theorem. However, there were two main drawbacks to the algorithm. Firstly, the algorithm only had the ability to tell us how long the MST is going to be but, it never produces a, graphical representation of the tree. Secondly, the algorithm requires us to calculate the determinant of a matrix called A ( m ) , which is a more expensive procedure than Prim's algorithm. So in fact we spent more time to get less information. However, originally as mentioned the aim of this approach was to determine the length of a RSMT without actually constructing the tree. The main problem we faced during our experimentation is due to the fact that the Kirchoff's Matrix Tree algorithm cannot be applied directly to the Hanan Grid, because instead of obtaining a RSMT we would obtain a MST with vertices consisting of terminals and possible Steiner points. However, not every vertex in the Hanan Grid will be an actual Steiner point in the RSMT. This situation causes our idea to fail since all efforts to maneuver around this problem caused us to loose 36 the property that ^2k=i ik{m) A = 1 and jk{in) A = 0 from (3.1). Losing this property would cause the Kirchoff's Matrix Tree theorem to become the Kirchoff's Matrix Forest theorem and in this case we would not longer be measuring a single tree. 37 Bibliography [1] Beasley, J. E. (1984). An Algorithm for the Steiner Problem in Graphs, Networks, 14: 147-159. [2] Bonabeau, E. Dorigo, M. Theraulaz, T. (1999). From Natural to Artificial Swarm Intelligence, Oxford University Press, New York. [3] Chung, F.R.K. and Langlands, R. P. (1996). A Combinatorial Laplacian with, vertex weights, Journal of Combinatorial Theory, Series A 75 , no. 2, 316-327. [4] Das, S., Singh, G., Gosavi, S., and Pujar, S. (2004). Ant Colony Algorithms for Steiner Trees: An Application to Routing in Sensor Networks, Recent Developments in Biologically Inspired Computing, Eds. L. N. de.Cast.ro, F. J. von Zuben, Idea Group Publishing, pp. 181-206. [5] Deneubourg, J. L., Aron, S., Goss, S., and Pasteels, J. M. (1990). The SelfOrganizing Exploratory Pattern of the Argentine ant, Journal of Insect Behavior, 3: pp. 159168. [6] Dorigo, M. and Stiitzle, T. (2004). Ant Colony Optimization, A Bradford Book, The MIT Press. [7] Garey, M. R., and Johnson D. S. (1977). The Rectilinear Steiner Tree Problem is NP-Complete. SIAM Journal of Applied Mathematics, 32, pp. 855 - 859. [8] Hanan, M. (1966). On Steiner's problem with rectilinear distance, SIAM Journal of Applied Math, 14(2), pp. 255-265. 38 ' • [9] Hu, Y., Jing, T., Hong, X., Feng, Z., Hu, X. and Yan, G. (2005). ACO-Steiner: Ant Colony Optimization Based Efficient Rectilinear Steiner Minimal Tree Construction, http://www.paper.edu.cn. [10] Hu, Y., Jing, T., Hong, X., Feng, Z., Hu, X. and Yan, G. (2006). ACO-Steiner: Ant Colony Optimization Based Rectilinear Steiner Minimal Tree Algorithm, J. Comput. Sci. and Technol. Vol 21, No. 1, pp. 147-152. [11] Kaltofen, E. and Villard, G. (2001) On the Complexity of Computing Determinants, Proc. Fifth Asian Symposium on Computer Mathematics ASCM 2001 at Ehime University, Japan Sep 26-28, World Scientific Publishing Company, Singapore. [12] Kirchhoff, G. (1847). Ann. Phys. Chem. 72, 497; Brooks, R.L., Smith, C.A.B., Stone, A.H. and Tutte, W.T. (1940). Duke Math. J. 7, 312; Nerode, A. and Shank, H. (1961). Amer. Math. Monthly 68, 244. [13] Prim, R. C. (1957). Shortest connection networks and some generalisations. Bell System Technical Journal, 36, pp. 1389 - 1401. [14] Warme, D., Winter, P., and Zachariasen, M. (2001). GeoSteiner 3.1 http://www.diku.dk/geosteiner . 39 Appendix A Graphical Results Obtain from AntCol Steiner In this section we display the user screens and program results in a graphical form. The tree in figure A.4 contains M = 50 terminals and is created using the Hanan grid A.3 as its initial graph. The input graphical user interface consists of three display panels namely Parameters. Inputs and Outputs. In the Parameters panel a list of all of the program's parameters are displayed with various values to allow the user the experiment with the parameter values. The recommended values for the program are the default values which can be selected by clicking the Edit — > Default Settings or by pressing F2. The Help Manual can be accessed by clicking Help — > Manual or by pressing F l . Selecting rho = 1.0 produces N O tree as it evaporates the entire pheromone trail. The Inputs panel consisted of two input fields. The first input held N is designed for the user to enter the size of the underline grid they wished to work with. While the second input held M is used to allow the user to specify how many random terminals to generate. Finally, the Outputs panel is used to display the time taken in milliseconds to execute the program and the length of the tree generated. In both the Hanan Grid A.3, and the Steiner Tree A.4 each vertical or horizontal dash has a length of one unit while each vertex had a length of zero. 40 File Edit Help AntCol Steiner -Parameters^— Alphas'' 15.0 R!io = 0.1 Bata= j 1.0 Gamma = 1 L MAXLOOP= Q•='•• / . lioo r-lnputs — Grid Length (HK . D e f a u l t (N.=-25) # o f T e r m i n a l s (M); Default ( M = r O i i t p u t s — — Total'.time = millseconds Tree Length = units Start Figure A . l : The Graphical User Interface of the AntCol Steiner Program. 41 9) »••' O • %• 0* S - i * ;The S t e i n e r Tree length I s : AntCol Steiner |The 40 e x e c u t i o n time M i l 484 m i l l i s e c o n d s . -Parameters Alpha • Ww- Bata = Gail»IM MAXLOOP - Of Ml Length (NS Default m • 25) p o f ! es mtnats (M) Mam Total Time • 9) nmaendi i units Tree Lenutti - j This IM - is che S t e i n e r Tree Before P r u n i n g Figure A.2: This Screen show the Steiner Tree before and after Pruning. The prepruned tree is located in the bottom left hand corner of the figure. The pruned tree is on the right hand side of the figure. 12 [ ', Hanan GridFinished Fxecutton Save ) 1 x - o - - o o - D ••• 0 i l l - o - o - o - o - o ! j - 1 • Print 0 • o Close " 0 - 1 1 - O ~ O '" o - o - x - o - o o •• o - • * • - o - a - • o ~ o - o - o - o - o - • - o - a - o - • - o x o - o o o - - o o - o - - o 1 1 .. j a • x x • • - o -- o -- o - x o o o o o - a - o •-• - - O o X - - • o • O - B • o O 0 o O • o 0 • X o * 0 0 0 o o - o o _ - - 1 - " o - 0 1 : • - o - o - - - o - o o - - • - - 0 o - o - 1 0 1 1 O " - 1 1 - o - o - o f - X 1 i - X - o j - o - o - o 1 - 1 \ i 1 1 ! 1 o 0 - • i O - X 0 - o - o - - o • o o • o • o • - o • o o - o " o - • - - o - o - - ... o •• - - Q - - - o - - „ 0 1 1 o - - o • • o - o - o 0 j o o 0 ]j - - - x o - o - • o ••• o - o - O - 0 X - o ; j - o - o - o o i - o o - o o •- x -• • - " o - o o - o o - 0 o o- - 0 X - O Q ' o ~ o ~ 0 " o • O ' o - 0 o - o - o - o - 0 - o - o - o Q - x - o - ~ O " U o - - 0 - • o o • ' X ' Q •• o b - o " 0 - x -n 0 - ~ 0 • o 0 ... - 0 - o 0 0 - 0 0 0 X ' " 0 0 0 •• o •• • X x - - O 0 O o O o o Q o - x 0 ' o • 0 x 0 • [ o • - o o 0 o x • ... u •• O o - - • - - O " x - - 0 0 " o • Q .. • o • X ... Q X ... Q ... • - - 0 ) \ O - O o x - o ••• x - o •••• o - o ~ o ~ o - O ... o - o o - o - o " o - X o - o • o ~ x - 0 o - - o Figure A.3: Hanan Grid with M = 50 terminals which was generated using AntCol Steiner. On this grid the "x" represents the terminal vertices and the "o" represent the possible Steiner points. 43 I Hut Tour • Finished Fxecglion j Ant Java \f_ T Irh peutUS jlavteiner Tree length is: 162 while(coun The execution time was: 14016 miliseconds, x-o II 0 o-o-x-x-o-o-o-x-o file Edti Hep l B | ata = 10 . |»| 1000 !»| GndLengK i H) =; 2 of lermiMls M () I I 1 MCo/ Sfemer Parameters- I C aimma = 1 MMOOP=M Delat* (N-251 MaH iM i 9| o-o- 14016 is: I o-o-o-o x-x- I x- 0 X I x-o- vjuiiiuia Total lime • IteelenjIM o-o-o X I mtlsecoiuls m«s I 0 I 0 0 - 0 Figure A.4: The Steiner Tree with M = 50 terminals; Tree Length = 182 units and Total Time = 1401 (i milliseconds obtained after using the AntCol Steiner program on the Hanan Grid above A..'1. On this tree the "x" represents the terminal vertices and the "o" represent the Steiner points. The parameter values are Alpha = 5, Beta = 1, Q = 1000, Rho = 0.1, Gamma = 1 and MAXLOOP = 30. R e m a r k A . 0 . 1 The solution presented in figure A.4 is not an optimal solution. 11 Appendix B Source Code for InputUI.java R e m a r k B.0.2 This class contains the Java main method. The other methods in this class are designed to generate, display and respond to all of the graphical user interface components presented infigureA.l. This class does not contain any ACO algorithm properties. package A n t S t e i n e r . u i ; import j avax.swing.*; import AntSteiner.*; import j ava.awt.*; import j a v a . a w t . e v e n t . * ; /** * D e s c r i p t i o n : T h i s c l a s s h a n d l e s a l l of t h e imput GUI stuff. * C l a s s : InputUI.j ava * ©author Anthony * ©version A p r i l Blackman 10, 2006 */ p u b l i c c l a s s InputUI extends JFrame 45 implements ActionListener{ /**This v a r i a b l e was private static /**This v a r i a b l e was used as a r e f e r e n c e AntCol t o the AntCol ac; used t o s t o r e the number of terminals generated*/ private static JTextField / * * T h i s v a r i a b l e was M; used t o s t o r e the d i m e n s i o n of generated*/ private static JTextField / * * T h i s v a r i a b l e was class*/ N; used t o s t o r e M and private static /**This i s a reference private static /**This i s a reference private static /**This i s a reference private JLabel /**This i s a reference N*/ i n t [] gridLTermN; t o the JTextField timeTaken; t o the JTextField JTextField*/ JTextField*/ steinerLength; t o the JLabel*/ defaultN; t o the JLabel*/ . 46 the p r i v a t e JLabel defaultM; /**This i s a reference t o the Start button*/ p r i v a t e JButton run; / * * T h i s i s a r e f e r e n c e t o t h e JComboBox*/ p r i v a t e s t a t i c JComboBox alphaBox; / * * T h i s i s a r e f e r e n c e t o t h e JComboBox*/ p r i v a t e s t a t i c JComboBox bataBox; / * * T h i s i s a r e f e r e n c e t o t h e JComboBox*/ p r i v a t e s t a t i c JComboBox rhoBox; / * * T h i s i s a r e f e r e n c e t o t h e JComboBox*/ p r i v a t e s t a t i c JComboBox maxloopBox; / * * T h i s i s a r e f e r e n c e t o t h e JComboBox*/ p r i v a t e s t a t i c JComboBox gammaBox; / * * T n i s i s a r e f e r e n c e t o t h e JComboBox*/ 47 private static JComboBox qBox; /**This is a reference to the parameter values of the program * the values include alpha, bata, gamma, rho, Q, maxloop*/ public static String [] parameters; /**This is a reference to the JFrame*/ private JFrame f; /**This is a reference to the InputUI class*/ private static InputUI u i ; /**This is the default constructor.*/ public InputUI(){ gridLTermN = new int [2]; inputScreenQ ; } /** * Description: This method creates the input user interface *(AntCol Steiner) screen. • */ public int [] inputScreenO{ f = new JFrame("AntCol Steiner"); f .getContentPaneO ; JMenuBar mainMenuBar = new JMenuBarQ; 48 //This creates a f i l e Menu with a mnemonic under the F. . JMenu fileMenu = new JMenuC'File"); mainMenuBar.add(fileMenu); f ileMenu.setMnemonic(KeyEvent.VK_F); //This creates a e d i t Menu with a mnemonic under the E. JMenu editMenu = new JMenu("Edit"); mainMenuBar.add(editMenu); editMenu.setMnemonic(KeyEvent.VK_E); //This creates a help Menu with a mnemonic under the H. JMenu helpMenu = new JMenu("Help"); mainMenuBar.add(helpMenu); helpMenu.setMnemonic(KeyEvent.VK_H); //This creates a c l e a r menu item under the E d i t menu. JMenuItem c l e a r = new JMenuItemC'Clear", KeyEvent.VK_C); editMenu.add(clear); //This creates a default menu item under the E d i t menu. JMenuItem d e f a u l t S e t t i n g s = new JMenuItem("Default S e t t i n g s " , KeyEvent.VK_D); editMenu.add(defaultSettings); //This creates an e x i t mnemonic under the e x i t menu item i n the f i l e menu. JMenuItem e x i t = new JMenuItem("Exit".KeyEvent.VK_X); fileMenu.add(exit); 49 //This creates an i n s t r u c t i o n manual. JMenuItem programHelp = new JMenuItemC'Manual", KeyEvent.VK_M); helpMenu.add(programHelp); //This creates an about mnemonic under the about //menu item i n the help menu. JMenuItem about = new JMenuItem("About".KeyEvent.VK_A); helpMenu.add(about); //This a l s o allow the about d i a l o g box t o pop up //when the F3 key i s pressed. about.setAccelerator(Keystroke.getKeyStroke(KeyEvent.VK_F3, //This i s the a c t i o n l i s t e n e r that pops up the d i a l o g box //and e x i t when the e x i t button i s pressed, exit.addActionListener(new A c t i o n L i s t e n e r ( ) { p u b l i c void actionPerformed(ActionEvent e) { JOptionPane exitFrame = new JOptionPaneO; JOptionPane.showMessageDialog(exitFrame,"Good Bye", "Exit AntCol Steiner", JOptionPane.INF0RMATI0N_MESSAGE); System.exit(0); > »; //This i s the a c t i o n l i s t e n e r that pops up the about / / d i a l o g box and d i s p l a y s the about information 50 0, f a l s e ) ) ; / / w h e n the about menu b u t t o n i s p r e s s e d , about.addActionListener(new ActionListener() { p u b l i c v o i d a c t i o n P e r f o r m e d ( A c t i o n E v e n t e) { JOptionPane aboutFrame = new J O p t i o n P a n e ( ) ; JOptionPane.showMessageDialog(aboutFrame, " A n t C o l S t e i n e r \ n V e r s i o n 2 . 0 \ n B y Anthony B l a c k m a n " , "About A n t C o l Steiner", JOptionPane.INF0RMATI0N_MESSAGE); } }); //This clears a l l text fields, clear.addActionListener(new ActionListener() { p u b l i c v o i d a c t i o n P e r f o r m e d ( A c t i o n E v e n t e) { N.setText(""); M.setText(""); timeTaken.setText(""); steinerLength.setText(""); > »; //This clears a l l text fields. defaultSettings.addActionListener(new ActionListener() { p u b l i c v o i d a c t i o n P e r f o r m e d ( A c t i o n E v e n t e) alphaBox.setSelectedIndex(4); bataBox.setSelectedlndex(O); rhoBox.setSelectedlndex(l); maxloopBox.setSelected!ndex(4); 51 { gammaBox.setSelectedlndex(O); qBox.setSelectedlndex(0); N.setText(""); M.setText(""); timeTaken.setTextC") ; steinerLength.setText(""); } »; //This sets the defaultSettings when the F2 key i s pressed, defaultSettings.setAccelerator(Keystroke.getKeyStroke (KeyEvent.VK_F2, 0, f a l s e ) ) ; //This displays the help manual when F l i s pressed. programHelp.setAccelerator(Keystroke.getKeyStroke (KeyEvent!VK_F1, 0, f a l s e ) ) ; //This displays the help manual a l l text f i e l d s . programHelp.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { JFrame textFrame = new JFrame("AntCol JPanel textPanel = new JPaneK); JLabel t e x t T i t l e = new JLabelO'Help textPanel.setLayout(new JTextArea t a = new Steiner Help"); Manual"); BorderLayout()); JTextAreaO; ta.setText("\nFirst select the parameter values from the parameter panel.\n" + "The default values are recommended f o r the best performance. Then\n" + " c l i c k the Start button and the program w i l l run with the currently \n" + "selected parameter values and the g r i d size and terminal number unless\n" + "otherwise s p e c i f i e d . The default g r i d size and terminal numbers are N = 25\n" 52 + "and M = 9 r e s p e c t i v e l y . This values produces a N x N (25 x 25) g r i d \n" + "with M = 9 terminals. The user can also,enter t h e i r preferred values \n" + "of N and M. However, the Value of M enter must always be l e s s than N \n" + "squared.\n\nThe Edit -> Clear menu button, clears a l l input and output \n" + "fields.\n\nThe Constants panel " + "displays a l l of the constant parameter \nvalues used to perform the Ant Colony Optimization " + "on the XnHanan's Grid\n\n\nAuthor: Anthony Blackman"); ta.setSize(500,500); JScrollPane h e l p S c r o l l = new JScrollPane (ta,ScrollPaneConstants.VERTICAL_SCROLLBAR_ALWAYS, ScrollPaneConstants.H0RIZ0NTAL_SCR0LLBAR_ALWAYS ); //just getting a l i t t l e Font font = new fancy... FontC'Arial Bold", Font.ITALIC, 18); textTitle.setFont(font); textTitle.setOpaque(true); textTitle.setForeground(Color.WHITE); textTitle.setBackground(Color.BLUE.darker()); textTitle.setPreferredSize(new Dimension(400, 24)); textTitle.setBorder(BorderFactory.createEmptyBorder(0, //Add T e x t T i t l e and HelpScroll to TextPanel. textPanel.add(textTitle, BorderLayout.NORTH); textPanel.add(helpScroll, BorderLayout.CENTER); //Add T e x t T i t l e to the Frame. textFrame.add(textPanel, BorderLayout.CENTER); textFrame.setSize(330,330); textFrame.setLocationRelativeTo(null); textFrame.setVisible(true); 53 10, 0, 10)); } // This adds the main menu bar to the panel f.setJMenuBar(mainMenuBar); JPanel t i t l e = new JPanelO; JLabel programTitle = new JLabel("AntCol Steiner"); t i t l e . setLayout (new BorderLayoutO); // just getting a l i t t l e fancy... Font font = new FontC'Arial Bold", Font.ITALIC, 24); programTitle.setFont(font); programTitle.setOpaque(true); programTitle.setForeground(Color.WHITE); programTitle.setBackground(Color.BLUE.darker()); programTitle.setPreferredSize(new Dimension(400, 40)); programTitle.setBorder(BorderFactory.createEmptyBorder(0, // create the course t i t l e bar title.add(programTitle, BorderLayout.CENTER); JPanel constantsPanel = new constantsPanel.setLayout(new JLabel alpha = new JLabel rho = new JLabel bata = new JPanelO; GridLayout(3,5)); JLabel("Alpha = " ) ; JLabel ("Rho = "); JLabel ("Bata = " ) ; 54 10, 0, 10)); JLabel gamma = new JLabel ("Gamma = " ) ; JLabel Q = new JLabel ("Q = " ) ; JLabel maxLoop = new JLabel ("MAXLOOP = " JLabel spacel = new JLabel(" "); JLabel space2 = new JLabel(" "); JLabel space3 =. new JLabel (" "); String [] alphaValues = {"1.0","2.0","3.0","4.0","5.0" }; S t r i n g [] bataValues = {"1.0","2.0","3.0","4.0","5.0" >; String [] gammaValues = {"1","2","3","4","5" >; S t r i n g [] maxloopValues = {"1","2","3","4","5","6","7","8", "9","10","20", "30", "40", "50" >; S t r i n g [] qValues = {"100","1000","10000" >; String [] rhoValues = {"0.0","0.1","0.2","0.3","0.4","0.5", "0.6","0.7","0.8","0.9","1.0"}; alphaBox = new JComboBox(alphaValues); bataBox = new JComboBox(bataValues); rhoBox = new JComboBox(rhoValues); maxloopBox = new JComboBox(maxloopValues); gammaBox = new JComboBox(gammaValues) ; qBox = new JComboBox(qValues); alphaBox.setBackground(Color.WHITE); bataBox.setBackground(Color.WHITE); rhoBox.setBackground(Color.WHITE); maxloopBox.setBackground(Color.WHITE); gammaBox.setBackground(Color.WHITE); 55 qBox.setBackground(Color.WHITE); alphaBox.setSelectedIndex(4); bataBox.setSelectedlndex(O); rhoBox.setSelectedlndex(l); maxloopBox.setSelectedIndex(4); gammaBox.setSelectedlndex(0); qBox.setSelectedlndex(O); constantsPanel.add(alpha); constantsPanel.add(alphaBox); constantsPanel.add(spacel); constantsPanel.add(rho); constantsPanel.add(rhoBox); constantsPanel.add(bata); constantsPanel.add(bataBox); constantsPanel.add(space2); constantsPanel.add(gamma); constantsPanel.add(gammaBox); constantsPanel.add(Q); constantsPanel.add(qBox); constantsPanel.add(space3); constantsPanel.add(maxLoop); constantsPanel.add(maxloopBox); //This puts a Border around the constants panel with //the words Marks on the border. constantsPanel.setBorder( BorderFactory. createTitledBorder ( BorderFactory. createLineBorder( Color.BLACK), 56 "Parameters")); JPanel maihPanel = new JPaneK); JPanel inputPanel = new JPanel outputPanel JPaneK); = new JPaneK); inputPanel.setLayout(new GridLayout(2,3)); outputPanel.setLayout(new GridLayout(2,3)); mainPanel.setLayout(new BorderLayout()); mainPanel.add(constantsPanel, BorderLayout.NORTH); JLabel gridSize = new N = new JLabel ("Grid Length (N) " ) ; JTextField (15); defaultN = new JLabel(" Default (N = 25)"); defaultM = new JLabel (" Default (M = JLabel terminalNum = new M = new JLabel ("# 9)"); of Terminals JTextField (15); JLabel time = new timeTaken = new JLabel ("Total Time = " ) ; JTextField (10); JLabel length = new JLabelC'Tree steinerLength = new JTextField (10); JLabel ms = new Length = " ) ; JLabeK" millseconds"); JLabel units = new JLabel (" u n i t s " ) ; inputPanel.add(gridSize); inputPanel.add(N); inputPanel.add(defaultN); inputPanel.add(terminalNum); 57 (M)" inputPanel.add(M); inputPanel.add(defaultM); inputPanel.setBorder( BorderFactory. createTitledBorder ( BorderFactory. createLineBorder( Color.BLACK), "Inputs")); outputPanel.add(time); outputPanel.add(timeTaken); outputPanel.add(ms); outputPanel.add(length); outputPanel.add(steinerLength); outputPanel.add(units); outputPanel.setBorder( BorderFactory. createTitledBorder ( BorderFactory. createLineBorder( Color.BLACK), JPanel iOPanel = new iOPanel.setLayout(new JPanelO; GridLayout(2,1)); iOPanel.add(inputPanel); iOPanel.add(outputPanel); run = new JButton("Start"); JPanel buttonPanel = new JPanelO; buttonPanel.add(run); mainPanel.add(iOPanel, BorderLayout.CENTER); f . a d d ( t i t l e , BorderLayout.NORTH); f.add(mainPanel, BorderLayout.CENTER); 58 "Outputs")) f.add(buttonPanel, BorderLayout.SOUTH); f.setSize(380,380); f.setResizable(false); f.setVisible(true); //f.setLocationRelativeTo(null); //This puts the AntCol Steiner screen i n the center, f.setDefaultCloseOperation(JFrame.EXIT_0N_CL0SE); return gridLTermN; y /** •Description: This methods looks f o r the run button *to be c l i c k e d and creates a seperate thread *for the execution of the program. */ public void actionPerformed(ActionEvent Steiner s = new e) { SteinerO; Thread runAnt = new Thread(s'); runAnt.start(); > /** * Description: This methods extracts the information * from the text f i e l d s i f values were entered * else the method would create default values * to be used with i n the program. */ public s t a t i c void e x t r a c t ( M ac = new AntCol(); ac.setTook(O); try { gridLTermN [0] = Integer.parselnt(N.getText0); //This converts the s t r i n g from the Text F i e l d //into an integer. gridLTermN [1] = Integer.parseInt(M.getText()); //This converts the s t r i n g from the Text F i e l d / / i n t o an integer. > catch (NumberFormatException n f e l H gridLTermN [0] = 25; gridLTermN [1] =9; } parameters = new String [6]; parameters [0] = (String)alphaBox.getSelectedltemO; parameters[1] = (String)bataBox.getSelectedltemO ; parameters [2] = (String)rhoBox.getSelectedltemO; parameters[3] = parameters[4] = (String)gammaBox.getSelectedltemO; parameters [5] = (String)maxloopBox.getSelectedltemO (String)qBox.getSelectedltemO; ac.test(gridLTermN [0], gridLTermN [1]); timeTaken.setText(ac.getTook() +""); steinerLength.setText(ac.getBestSlength() + " " ) ; /** Oparam args 60 */ p u b l i c s t a t i c void main(String[] args) { // TODO Auto-generated method stub u i = new InputUI(); ui.run.addActionListener(ui); > } /** * This class implements the Runnable Interface. This makes * the s t u f f i n the run method excute using a separte thread. * This thread was used because sometimes the excution time of * the program can be very long and using a seperate thread * allow the user access to the GUI controls while the programs * i s executing. */ class Steiner implements Runnable{ /** * This i s the overloaded run method associated with the thread. */ public void run(){ { try { InputUI.extract(); Thread.sleep(5); } catch(InterruptedException e) 61 {}}}} Appendix C Source Code for AntCol.java package AntSteiner; import A n t S t e i n e r . u t i l . * ; import AntSteiner.ui.*; /** * Class: AntCol.java * ©author Anthony Blackman * ©version A p r i l 10, 2006 */ p u b l i c class AntCol { /**This data structure store the l i s t of the terminals * i n the Hanan's Grid*/ p r i v a t e i n t [] [] terminals; /**This data structure was used to store the Hanan's g r i d . * / private S t r i n g [] [] g r i d ; /**This data sturture was used to store the current 62 Steiner tree.*/ private String [] [] steinerTree; /**This data sturture was used to store the best Steiner t r e e . * / private String [][] bestSteinerTree; /**This data sturture was used to store i n t e n s i t y l e v e l s of the * edges of the Hanan's Grid.*/ private double [][] i n t e n s i t y ; /**This variable was used to store the number of i t e r a t i o n s of the system.*/ p r i v a t e i n t maxLoop; /**This variable was used to store the q u a l i t y of the t r a i l * / private i n t Q; /**This variable was used to store the length of the current steiner t r e e . * / private i n t sLength = 0; /**This variable was used to store the length of the best steiner tree*/ private i n t bestSlength = 0; 63 /**This variable was used to determine whether or not * a better Steiner tree was found*/ private i n t indicate; /**This variable was used to record the s t a r t time.*/ private long s t a r t ; /**This variable was used to record the f i n i s h time.*/ private long end; /**This v a r i a b l e was used to record the time taken to execute the program*/ private long took; /**This variable was used to determine the l e v e l s of phermone evaporation*/ private double rho; /**This variable was used to reference the input display*/ private Display d; /**This variable was used as a reference private HananGrid hg; 64 to the Hanan Grid.*/ /**This variable was used as a reference to the TreeConstruct class.*/ private TreeConstruct tree; /**This data structure was used to store the boundary values the Hanan Grid.*/ p r i v a t e i n t [] gridLimits; public AntCol(){ } public void t e s t ( i n t n, i n t m){ rho = Double.parseDouble(InputUI.parameters [2]); maxLoop = Integer.parselnt(InputUI.parameters[3]); Q = Integer.parselnt(InputUI.parameters[5]); int count =0; // This i s the number of loops. double pheromone = 1000; gridLimits = new i n t [4]; steinerTree = new String[n][n]; bestSteinerTree = new String [n] [n]; g r i d = new String[n][n]; 65 i n t e n s i t y = new double[n][n]; • terminals = new hg = new HananGridO; tree = new d = new i n t [m][2]; TreeConstructO; Display(); s t a r t = System.currentTimeMillisO; // Start the clock. g r i d = hg.gridGenerator(n, m, gridLimits); //This generates the Hanan g r i d . i n t e n s i t y = h g . i n i t i a l _ i n t e n s i t y ( g r i d , pheromone); //This array contains the t r a i l intensity, terminals = hg.getPointsO ; // This array contains the terminal points. //This i s the f i r s t steiner tree i t w i l l be used as //a t e s t standard to compare the other trees. bestSteinerTree = tree.constructSteinerTreeByACO (terminals, g r i d , i n t e n s i t y , g r i d L i m i t s ) ; bestSlength = tree.getTLengthO; // Here at the other steiner trees, while (count < maxLoopH //These loops updates the t r a i l i n t e n s i t y f o r a l l of the paths that where crossed. f o r ( i n t row = 0; row < steinerTree.length; row++){ 66 f o r ( i n t c o l = 0; c o l < steinerTree.length; col++) { if(bestSteinerTree[row][col]== "*" II bestSteinerTree[row][col]== "a" //This increases the l e v e l of pheromones. i n t e n s i t y [row] [col] = updatelntensity(sLength, row, col, intensity); //This updates the edges //which have been crossed. > else { intensity[row] [col] = ((double)1 - r h o ) * i n t e n s i t y [ r o w ] [ c o l ] ; > } steinerTree = tree.constructSteinerTreeByACO(terminals, grid, intensity, gridLimits); sLength = tree .getTLengthO ; //This indicates i f the f i r s t S l e n g t h i s l e s s than sLength. / / i f indicate = 1 f i r s t S l e n g t h i s shorter than sLength. / / i f indicate = 0 f i r s t S l e n g t h i s longer //than sLength. If indicate = -1 the test f a i l e d , indicate = chooseBestSoKbestSlength, / / I f the bestSteinerTree sLength); i s longer we copy the better tree / / ( i e . steinerTree) into the bestSteinerTree. Then get i t s length, i f ( i n d i c a t e == 0){ 67 f o r ( i n t row = 0; row < steinerTree.length; row++){ f o r ( i n t c o l = 0; c o l < steinerTree.length; col++) { bestSteinerTree [row][col]= steinerTree[row][col]; > } System.out.println("\n\nA better Steiner Tree was found!"); bestSlength = sLength; //set the bestSlength to be the shorter d i s t } else i f (indicate == -1) i System.out.println("The comparsion test f a i l e d ! " ) ; } count++; // This increments the MAXL00P } // This i s the end of the MAXL00P. end = System.currentTimeMillis(); //Stop the clock took = end - s t a r t ; // Elapsed time. d.displayTree(bestSteinerTree, g r i d , bestSlength, took); System.out.println ("\nThe execution time was: " + took + " milliseconds. " ) ; } /** * Description: This method compares two numbers and then returns an 68 * indicator that indicates which number i s the bigger, i f indicate = 1 * f i r s t S l e n g t h i s shorter than sLength. i f indicate = 0 f i r s t S l e n g t h i s longer * than sLength. If indicate = -1 the test f a i l e d . * * ©param bestSlength The * ©param sLength The shortes steiner tree that was current * ©return indicator This was * the current steiner tree which was generated. j u s t generated. used to indicate whether or not steiner tree * i s better than the current best steiner tree. */ public int chooseBestSoKint bestSlength, int sLength){ int i n d i c a t o r = -1; if(bestSlength < sLength){ i n d i c a t o r = 1; } else { indicator = 0; > return indicator; > /** * Description: This method was used to update the t r a i l i n t e n s i t y . * ©param sLength This i s the length of the steiner tree. * ©param row This i s a x coorinate of a point on the steiner tree. * ©param c o l This i s a y coorinate of a point on the steiner tree 69 * Qparam i n t e n s i t y This i s the i n t e n s i t y matrix. * ©return intensityValiie This the value of the i n t e n s i t y at * that point on the t r a i l . * * */ public double updatelntensity(int sLength, i n t row, i n t c o l , double [] [] i n t e n s i t y ) { double intensityValue = 0.0; double delta_tau; if (sLength == 0.0) { delta_tau = 0.0; } else { delta_tau = Q / sLength; } intensityValue = (1 - rho)*intensity[row][col] + rho * delta_tau; //This i s the t r a i l i n t e n s i t y . return intensityValue; } /** * ©return Returns the i n t e n s i t y . */ public double [][] getlntensityO 70 { return i n t e n s i t y ; } /** * ©param i n t e n s i t y The i n t e n s i t y to set. */ public void setIntensity(double[][] this.intensity = intensity; } /** * ©return Returns the bestSlength'. */ public i n t getBestSlengthO { return bestSlength; } /** * ©return Returns the took. */ public long getTookO { return took; } /** * ©param took The took to set. */ public void setTook(long took) { 71 intensity) { t h i s . t o o k = took; Appendix D Source Code for HananGrid.java package A n t S t e i n e r . u t i l ; import j a v a . u t i l . * ; import AntSteiner.ui.*; /** * Class: HananGrid.java * ©author Anthony Blackman * ©version A p r i l 10, 2006 */ public c l a s s HananGrid { /**This data structure was used to store the Hanan's Grid*/ private S t r i n g [] [] g r i d ; /**This data structure was used to store the t r a i l intensities.*/ private double [][] i n t e n s i t y ; /**This reference was used to access the input user i n t e r f a c e . * / 73 private Display d; /**This data structure was used to store the points terminals of the system.*/ private i n t [] [] points; /**This variable was used to store the x coordinate of the Hanan's grid*/ private i n t x; /**This variable was used to store the y cooridinate of the Hanan's grid*/ p r i v a t e i n t y; /**This variable was.used to store the smallest x cooridinate of the Hanan's g r i d * / private i n t xmin; /**This variable was used to store the largest x cooridinate of the Hanan's g r i d * / private i n t xmax; /**This variable was used to store the smallest y cooridinate of the Hanan's g r i d * / 74 p r i v a t e i n t ymin; /**This variable was used to store the largest y cooridinate of the Hanan's g r i d * / private i n t ymax; /**This variable was used to store the reference to the random number generator*/ p r i v a t e Random ran; /**HananGrid Constructor*/ public HananGridQ{ x = 0; y = 0; xmin = 0; xmax = 0; ymin = 0; ymax = 0; > /**This method was design to generate a Hanan Grid from a random * set of n integer v e r t i c e s . The "x" represents the terminal points * The "o" represents the possible steiner points. The "I" * and "-" represents the edges of the g r i d and the " " are places * that the ant cant walk * ©param n * ©return g r i d Which i s a representation */ 75 of the Hanan' Grid. p u b l i c S t r i n g [][] gridGenerator(int n, i n t m, i n t [] gridLimits){ g r i d = new S t r i n g [n][n]; //Size of the g r i d i s n by n. points = new int[m] [2]; d = new D i s p l a y ( ) ; ran = new RandomO; // Creates a new random number generator. f o r ( i n t i = 0; i < grid.length; i++) { f o r ( i n t j = 0; j < grid.length; j++H g r i d [ i ] [j] = " "; // I n i t i l i z e the g r i d array with blank spaces. > > f o r ( i n t i = 0; i < points.length; i++M x = ran.nextInt(n); //generates a random number between 0 and n. y = ran.nextInt(n); //generates a random number between 0 and n. x = 2*x; // This makes sure that the x coordinates i s always even y = 2*y; // This makes sure that the y coordinates i s always even if (x < g r i d . l e n g t h kk y < for(int grid.length){ k = 0; k < g r i d . l e n g t h ; k++){ i f ( g r i d [ x ] [k]== " I " I I g r i d [ x ] [ k ] = = g r i d [ x ] [ k ] = "o"; } else { g r i d [ x ] [k]= "-"; > 76 "o" H i f (grid[k] [y]== "-" I I grid[k][y]== "o" H grid[k][y] = "o"; } else { grid[k][y] = "I"; > } p o i n t s [ i ] [0] = x; // This stores the x points p o i n t s [ i ] [ l ] = y; //This stores the y points. } else i i — ; > } //This f o r loop was used to look f o r the point just generated and plac //an X at the point. f o r ( i n t i = 0; i < points.length; i++) { g r i d [ p o i n t s [ i ] [0]] [points[i][1]]= "x"; > xmin = grid.length; ymin = grid.length; f o r ( i n t s = 0; s < points.length; i f ( p o i n t s [s] [0] <= xmin ) { 77 s++){ xmin = points [s] [0]; // This f i n d the lowest x point > i f ( p o i n t s [s][1] <= ymin ) { ymin = points[s] [1];// This f i n d the lowest y point. > if (xmax <= points [s] [0] ) { xmax: = points[s] [0];// This f i n d the highest x point } if(ymax <= points[s] [1] ) { ymax = points [s] [1]; // This f i n d the higest y point } } //Trims off excess g r i d from the top. if (xmin > OH f o r ( i n t k = 0; k < xmin; k++ H f o r (int i = 0; i < grid, length; i++H grid[k] [i]= " "; } . } > //This trim excess of the g r i d on the l e f t side, if (ymin > OH f o r ( i n t k = 0; k < ymin; k++ H f o r ( i n t i = 0; i < grid.length; i++H g r i d [ i ] [k]= " "; > > > 78 //This trim excess of the g r i d from the r i g h t side, if (ymax < grid.length){ f o r ( i n t k = ymax + 1; k < grid.length; k++ ){ f o r ( i n t i = 0; i < grid.length; i++){ g r i d f i ] [k]= " "; > > } // Trims o f f excess g r i d from the bottom, if (xmax < grid.length){ f o r ( i n t k = xmax + 1; k < grid.length; k++ ){ f o r ( i n t i = 0; i < grid.length; i++){ grid[k] [i]= " "; }• } gridLimits[0] = xmax; gridLimits[1] = ymax; gridLimits[2] = xmin; gridLimits[3] = ymin; d.displayGrid(grid); // This method c a l l displays the Hanan's Grid. return g r i d ; //This returns the Hanan's Grid. 79 } /** * D i s c r i p t i o n : The s t r i n g [][] i s a copy of the Hanan g r i d , the double * parameter i s f o r the i n i t i a l i n t e n s i t y of the t r a i l and the double * array i s a i n t e n s i t y matrix. If the there i s an edge i n the Hanan g r i d * then the i n t e n s i t y i s set to the i n i t i a l _ i n t e n s i t y . If there i s no edge * at p o s i t i o n i , j i n the Hanan g r i d then the i n t e n s i t y i s set to 0.0. After * a l l edges have been check we return the i n i t i a l edge i n t e n s i t y matrix. * * ©param g r i d * @param i n i t i a l _ i n t e n s i t y * ©return intensity * * */ public double [] [] i n i t i a l _ i n t e n s i t y ( S t r i n g [][] g r i d , double i n i t i a l _ i n t e n s i t y ){ int n = grid.length; //Dimensions of the Hanans g r i d . i n t e n s i t y = new double [n] [n] ; - f o r ( i n t i = 0; i < intensity.length; i++){ f o r ( i n t j = 0; j < intensity.length; i f ( g r i d [ i ] [ j ] = = " "){ i n t e n s i t y [ i ] [ j ] = 0.0; } else { 80 j++H i n t e n s i t y [ i ] [j] = i n i t i a l _ i n t e n s i t y ; } } return i n t e n s i t y ; } /** * ©return Returns the g r i d . */ p u b l i c String [] [] getGridC) { return g r i d ; y /** * ©param g r i d The g r i d to set. */ public void setGrid(String[] [] grid) { this.grid = grid; } /** * ©return Returns the points. */ public i n t [ ] [ ] getPointsO return { points; } /** * ©param points The points to set. */ p u b l i c i n t [] [] setPoints(int [] [] points) { t h i s . p o i n t s = points; 81 return points; y /** * ©return Returns the xmax */ public i n t getXmaxO { return xmax; } /** * ©return Returns the xmin */ public i n t getXminO { return xmin; > /** * ©return Returns the ymax */ public i n t getYmaxO { return ymax; > /** * ©return Returns the ymin */ public i n t getYminO return ymin; } /** } { Appendix E Source Code for TreeConstruct.java package A n t S t e i n e r . u t i l ; import java.util.*; import AntSteiner.*; /** * Class: TreeConstruct.java * ©author Anthony Blackman * ©version A p r i l 19th, 2006 */ p u b l i c class TreeConstruct { /**This variable was used to store the reference to the random number * generator*/ private Random rand; /**This variable was used to store length of the Steiner tree a f t e r prunning*/ private i n t tLength = 0; /**This variable was used to store the number of v e r t i c e s i n the Steiner t r e e * / 83 private i n t tPoints = 0; /**This data structure was used to store information regarding the type of vertex * an ant was currently at and whether the ant was confused at that vertex. */ private i n t [] info; //**This data structure was used to store the r e l o c a t i o n points of the •surviving ant.*/ //private i n t [] relocate; // This array stores the l i s t of ants i n the colony, //private i n t [] [] relocationPoints; /**This data structure was used to store the mortality of the ants i n the colony.*/ private i n t [] antID; /**This data sturcture was used to store the v e r t i c e s and edges of the Steiner tree, private S t r i n g [][] sTree; /**This data structure was used to store the a e r i a l view of the ant system.*/ private i n t [] [] globalArray; /**This t o o l i s used to access the methods i n the ant private Ant tool; /**This i s an array of ants i e the ant private Ant class.*/ colony.*/ [] colony; /**This variable was used to store the i d e n t i f i c a t i o n of the ant who * i f the current ant met an ant and i t stored -1 i f i t d i d not met was any met ants*/ private i n t i d ; /**This variable was used to indicate whether or not deconfusion had accorded*/ private i n t dCon; /**This variable was used to store the i d e n t i f i c a t i o n of the ant current ant.*/ private i n t m; /**This variable was used to store the number of ants s t i l l a l i v e i n the system.*/ private i n t ant_number = 0; /**This data structure was used to store the current cooridinates each ant was 84 at * during any instance of the program.*/ private i n t [] [] antPoints; /** * This i s the default constructor. */ public TreeConstruct(){ } /** * * @param terminals The terminals l i s t . * Oparam g r i d The Hanan's Grid * Oparam i n t e n s i t y The i n t e n s i t y matrix * Qreturn sTree The steiner tree. * */ public S t r i n g [] [] constructSteinerTreeByACO ( i n t [][]terminals, S t r i n g [] [] g r i d , double [] [] i n t e n s i t y , i n t [] gridLimits){ int n = terminals.length; t o o l = new Ant(grid.length); relocate = new i n t [3]; antID = new i n t [n]; rand = new Random(); antPoints = new i n t [n] [2]; colony = new Ant[n]; f o r ( i n t i = 0; i < colony.length;i++){ colony[i] = new Ant(n, grid.length); // This makes a c a l l to the 85 //Ant Class overloaded constructor.; /•/ This places a n 'by n String array i n each ant and V i s i t e d // c i t e s l i s t . It also places the t r a i l length of each ant also. } //This loops was used to store where the ants are at a given time. f o r ( i n t i = 0; i < terminals.length; forCirit j = 0; j < 2; i++){ j++){ antPoints[i] [j] = t e r m i n a l s [ i ] [ j ] ; } } // This loop was used to place an ant at there s t a r t i n g l o c a t i o n . f o r ( i n t i = 0; i < colony.length; i++){ t o o l = tool.placeAnt(tool, c o l o n y [ i ] . t e r m i n a l s [ i ] [ 0 ] , t e r m i n a l s [ i ] [ 1 ] , i ) ; } ant_number = antID.length; f o r ( i n t s = 0; s < antID.length; s++){ antID[s]= 1; //This one indicates weather an ant i s a l i v e . When //an ant at p o s i t i o n i dies then Then the i w i l l put a -1 / / i n p o s i t i o n i to indicate the ant i s dead. This //This would prevent me from choosing dead ants to move. } while (ant_number > 0) 86 { info = new i n t [3]; dCon = 0; m = rand.nextInt(antID.length); //generates a random number between 0 //and number of ants. while (antID[m]== -1){// Keeps generate a random number u n t i l a l i v e ant //is found. m = rand.nextInt(antID.length); //generates a random number between //0 and number of ants. > //Move an ant that i s s t i l l alive. info = tool.AntMove(tool, colony[m].antPoints[m][0], antPoints[m] [1], m, g r i d , i n t e n s i t y , terminals, colony, antID, gridLimits); id = i n f o [ 0 ] ; // This i d i s used to indicate i f an ant met another ant or not. // -1 means d i d not meet an ant. dCon = info [3]; //Indicates whether or not there was a deconfusion. //I means NO! and -1 means YES! while ( i d == -1){ //Move an ant that i s s t i l l alive. info = tool.AntMove(tool, colony[m],info[1], i n f o [ 2 ] , m, g r i d , terminals, colony, antID, intensity, gridLimits); id = info[0] ; dCon = info [3]; System.out.println("\nWork if now!!" + " i d : " + i d + " m: " + m); (dCon == -1){ break; } } 87 int count =0; while(dCon == -1 && i d != - 1 ){// i f the ant was deconfused then move him. count ++; antPoints[id] [0] = i n f o [ l ] ; //This now puts the ant on a new i n h i s f a b u l i s t antPoints [id] [1] = info[2]; //This now puts the ant on a new i n h i s t a b u l i s t //Move an ant that i s s t i l l a l i v e . info = tool.AntMove(tool, colony[m],info[1], i n f o [ 2 ] , i d , g r i d , terminals, colony, antID, gridLimits); dCon = info [3]; i d = info[0] ; if (count > terminals.length){ break; } System.out.printlnC'dCon i s : " + dCon); } // This l i n e says that i f the ant meets another ant // then he dies an copies h i s t r a i l into the anf. if ( i d != -1){// i d not equal to minus one means that //the ant has met another ant. colony[id]= tool.copyAntTour(colony[id], colony[m], grid.length); antID[m] = -1; // ant m i s that ant that was k i l l e d //by ant i d whom he met. //tool.mergeTours(tool.getGlobalView(), colony[id].getTourO,id); // This merges the tour of the ant with the global tour, //tool.updateGlobalView(tool.getGlobalViewO,m,id); 88 intensity, System.out.println("\nAnt " + m + " met System.out.println("\nAnt " + m + " just // relocate = tool.relocate (colony[id], ant " + i d ) ; died!\n"); antPoints, g r i d ) ; // antPoints [id] [0] = relocate [1]; //This now //on a new a new puts the ant_number—; + " " + ant_number); > } globalArray = new i n t [grid.length][grid.length]; globalArray = tool.getGlobalViewO; sTree = new S t r i n g [grid.length][grid.length] ; f o r ( i n t j = 0; j < sTree.length; j++){ for (int i = 0; i < sTree.length; i++){ sTree[j] [i] = " "; } } f o r ( i n t i = 0; i < grid.length; i++){ System.out.print("\n"); f o r (int j = 0; j < grid.length; j++M 89 ant i n his t a b u l i s t // i d = r e l o c a t e [ 0 ] ; //System.out.println(id ant i n his t a b u l i s t // antPoints [id] [1] = relocate [2]; //This now //on puts the if ( g l o b a l A r r a y [ i ] [ j ] != - i ) { System.out.print(globalArray[i][j]); > else{ System.out.print(" " ) ; } } > System.out.println("\nThis i s the Steiner Tree Before Pruning!\n\ri") f o r ( i n t i = 0 ; ' i < grid.length; i++H System.out.print("\n"); f o r ( i n t j = 0; j < grid.length; j++M if ( g l o b a l A r r a y [ i ] [ j ] != -1){ System.out.print(grid[i][j]); sTree[i] [j]= "*"; > else{ System.out.print(" " ) ; sTree[i] [j]= " "; > } } System.out.print("\n"); sTree = pRune(sTree, g r i d , g r i d L i m i t s ) ; //This method was used to remove a l l //leaves that were not terminals. tLength = 0; tPoints =0; 90 f o r (int j = 0; j < sTree. length; j++M f o r ( i n t i = 0; i < sTree.length; i++){ i f ( s T r e e L j ] [i] == "*"){ tLength++; > i f ( s T r e e H j ] [i] == "*" && (grid[j][i]== "o" II g r i d [ j ] [i] == "x")){ tPoints++; } } > tLength = tLength - tPoints; //This i s the length of the tree formed. //System.out.println("\nThe length a f t e r prunning i s : "+tLength); return sTree; }// End the tree construct. /** •Description: This method was used to erase a l l non-terminal leaves from •the steiner tree that was created. *@param sTree The steiner tree with non terminal leaves •Sparam g r i d The Hanan's g r i d •Oparam g r i d L i m i t s This array contains the values of the extremes of the •Hanan's g r i d *@return sTree The steiner tree with out non terminals leaves. */ public String [] [] pRune (String [] [] sTree, String [] [] g r i d , i n t [] g r i d L i m i t s ) { 91 /* gridLimits [0] = xmax This i s the value of the l a s t row of the Hanan's g r i d . gridLimits[1] = ymax This i s the value of the l a s t column of the Hanan's g r i d . gridLimits[2] = xmin This i s the value of the f i r s t row of the Hanan's g r i d . gridLimits[3] = ymin This i s the value of the f i r s t column of the Hanan's g r i d . */ i n t n = sTree.length * sTree.length; f o r ( i n t loops = 0; loops < n; loops++) { f o r ( i n t row = gridLimits[2]; row <= gridLimits[0]; row++){ f o r ( i n t c o l = gridLimits [3] ; c o l <= gridLimits [1] ; col++)-[ i n t degree =0; if((grid[row] [col] == "o" II grid[row][col] == g r i d [row] [col] == "I" ) && sTree[row][col] "-"II == "*"){ //This i s f o r the top l e f t had corner. if (row == gridLimits [2] && c o l == gridLimits [3]){ if (sTree[gridLimits[2]][gridLimits[3]+ 1]!= " "){ degree++; } if (sTree [gridLimits [2] +1] [gridLimits [3]] != " " H degree++; > > //This i s f o r the botton right had corner, else i f (row == gridLimits[0] && c o l == gridLimits [1] ){ if (sTree[gridLimits[0]] [gridLimits[1] - 1]!= " "){ degree++; 92 } if (sTree[gridLimits[0] - 1] [gridLimits[1]] != " "H degree++; > } //This i s f o r the botton l e f t hand corner, else i f (row == gridLimits[0] && c o l == gridLimits[3] ){ if (sTree[gridLimits[0] - 1][gridLimits[3]]!= " "){ degree++; > if (sTree [gridLimits[0]][gridLimits[3]+ 1]!= " "){ degree++; } > //This i s f o r the top right hand corner, else i f (row == gridLimits[2] kk c o l == gridLimits [1] ){ if (sTree[gridLimits[2] + 1][gridLimits[1]]!= " "){ degree++; } if (sTree[gridLimits[2]][gridLimits[1] - 1]!= " "){ degree++; } > //This i s f o r the center of row 0. else i f (row == gridLimits[2] && c o l <= gridLimits [1] ){ 93 if (sTree[gridLimits[2]][col - 1]!= " "){ degree++; } if (sTree[gridLimits[2]][col + 1]!= " "){ degree++; } if (sTree[gridLimits[2] + 1][col]!= " "){ degree++; } //This i s f o r the center of row sTree.length - 1. else i f (row == gridLimits[0] kk c o l <= gridLimits[1] ){ if (sTree[gridLimits [0]] [col - 1]!= " "){ degree++; } if (sTree[gridLimits[0]] [col + 1]!= " "){ degree++; } if (sTree[gridLimits[0] - 1][col]!= " "){ degree++; } } //This i s f o r the center of column 0. else i f (row <= gridLimits[0] && c o l == gridLimits[3] ){ if (sTree[row - 1][gridLimits[3]]!= " "){ degree++; ', 94 } if (sTree[row + 1][gridLimits[3]]!= " "){ degree++; > if (sTree[row] [gridLimits[3] + 1]!= " "){ degree++; > } //This i s f o r the center of column sTree.length - 1. else i f (row >= gridLimits[2] && c o l == gridLimits [1] if (sTree[row - l ] [ c o l ] ! = " "){ degree++; > if (sTree[row + l ] [ c o l ] ! = " "M degree++; } if (sTree [row] [gridLimits [1] - 1] != " "){ degree++; } } //This i s f o r the center of the g r i d else i f (row >= gridLimits[2] && c o l <= gridLimits[1] && c o l >= g r i d L i m i t s [3]){ if (sTree[row - 1] [col]!= " "){ degree++; > 95 if (sTreeLrow + 1] [col] != " "){ degree++; } if (sTree[row] [col - 1]!= " "){ degree++; > if (sTreeLrow] [col + 1]!= " "){ degree++; } } / / I f the degree of the node i s 1 put a space. //System.out.println("The degree i s : " + degree + " row: " +row+ " c o l : "+col) if (degree == 1){ //System.out.printlnC'The sTree [row] [col] = " "; } } > } return sTree; } /** * Oreturn Returns the tLength. 96 degree i s : " + degree); */ public i n t getTLengthO { return tLength; } /** * ©param length The tLength to set. */ public void setTLength(int length) •{ tLength = length; > /** * ©return Returns the i d . */ public i n t g e t l d O { return i d ; > /** * ©param i d The i d to set. */ public void s e t l d ( i n t id) { this.id = id; } }7/End the class 97 Appendix F Source Code for Ant .Java package AntSteiner; import A n t S t e i n e r . u t i l . * ; , import import java.lang.Math; java.util.*; /** * Class: Ant.Java * Oauthor Anthony Blackman * Oversion A p r i l 10, 2006 */ p u b l i c class Ant { /exposition represents the x coordinate of the vertex*/ private i n t xposition; /**xposition represents the y coordinate of the vertex*/ 98 private i n t yposition; /**This represents the length of an ants tour*/ private double tour_length = 0.0; /**This stores the length of the tour/tree just created.*/ private double max = -1.0; /**This stores the ants memory of i s i t s t r a i l . */ private S t r i n g [] [] tour; /**This stores the l i s t of terminals v i s i t e d by the ant.*/ p r i v a t e i n t [] v i s i t e d ; /**This stores the l i s t of a l l the v e r t i c e s i n the Hanan's Grid*/ private i n t [] [] s t a r L i s t ; /**This stores the l i s t of a l l the Steiner points i n the Hanan's Grid*/ private i n t [][] s t e i n e r L i s t ; /**This stores the p r o b a b i l i t i e s the ant would go i n the four different directions*/ private double [] p r o b a b i l i t y ; 99 /**This i s a reference to the U t i l i t i e s private U t i l i t i e s class*/ uTil; /**This was used to mark steps of the ants*/ private i n t step = 0; /**This return information r e l a t e d to the ants i n t e r a c t i o n at a vertex.*/ private i n t [] alabel; /**This return the cooridinates where the ant was deconfused and * whether i t i s s t i l l confused*/ p r i v a t e i n t [] confuse; /**This return the cooridinates where the ant was relocated*/ private i n t [] relocate; /**This i s a reference to a random v a r i a b l e * / private Random random; /**This i s the data structure used to store the a r i a l view of the ant system.*/ 100 private i n t [][] globalView; /** * This i s the default constructor. **/ public Ant (int m){ u T i l = new U t i l i t i e s ( ) ; globalView = new i n t [m][m]; //This array w i l l contain a global view //of the system, for ( i n t i = 0; i < globalView.length; f o r ( i n t j = 0; j < globalView.length; j++){ globalView[i][j] = -1; > } } /** * D i s c r i p t i o n : This i s the over ridden constructor. The copies the Hanan Grid * into the Ant Tour so that the ant would walk on h i s copy of the g r i d . This * would allow me to get the path of any ant. That way I can p r i n t the path of * the l a t e surviving ant's tour which would be the Steiner Tree f o r * that i t e r a t i o n . * * Oparam n This i s the number of c i t i e s or number of ants * Oparam m This i s the size of the g r i d . * */ public Ant (int n, i n t mM 101 tour_length = 0.0; tour = new S t r i n g [m][m]; v i s i t e d = new i n t [n] ; f o r ( i n t i = 0; i < tour.length; !++)•[ f o r ( i n t j = 0; j < tour.length; j++){ t o u r [ i ] [j]= " "; > f o r ( i n t j = 0; j < v i s i t e d . l e n g t h ; j++H v i s i t e d [ j ] = 0; //0 represents u n v i s i t e d terminals and 1 represents / / v i s i t e d terminals. } ** * D i s c r i p t i o n : This method was design to place an ant m to the s t a r t i n g * p o s i t i o n of h i s Hanan's Grid. How ever t h i s placement would be i n h i s * tabu l i s t . i e . This tour. * Oparam xposition This i s the x cooridnate where the ant w i l l be placed. * Oparam y p o s i t i o n This i s the y cooridnate where the ant w i l l be placed. * Oparam i t h i s indicates which c i t y got the ant. * Opararn t o o l This i s a reference to the ant system. * Qparam m This i s the ant number m that was place at the point (x,y) of * the Hanan's g i r d . * Oreturn This returns the reference to an ant. */ 102 public Ant placeAnt (Ant t o o l , Ant m, i n t xposition, i n t yposition, i n t i ) { t h i s . x p o s i t i o n = xposition; t h i s . y p o s i t i o n = yposition; • m.tour[xposition][yposition]= "a"; / / t h i s i s the tour f o r ant m. tool.globalView[xposition][yposition]= i ; m.setCity(i); return t o o l ; > * D i s c r i p t i o n : This method move an ant to an new p o s i t i o n j based on the d e s i r a b i l i t y and t r a i l i n t e n s i t y to move to j . This method moves one p o s t i t i o n at a t ime. @param x p o s i t i o n This i s the x cooridnate where the ant w i l l be placed. Oparam y p o s i t i o n This i s the y cooridnate where the ant w i l l be placed. Oparam antlndex This indicates which ant was moved. Oparam m This i s the ant number m that was place at the point (x,y) of the Hanan's g i r d . Oparam t o o l This i s a reference to the ant system. Oparam g r i d This the Hanan's g r i d . @param i n t e n s i t y This i s the i n t e n s i t y matrix or i n t e n s i t y t r a i l of the system. Oparam terminals T h i s . i s the terminal l i s t of the system. ©return a l a b e l This i s an array which indicates which vertex the ant move to and what type of vertex was i t . / 103 p u b l i c i n t [] AntMove(Ant t o o l , Ant m, i n t xposition, int yposition, i n t antIndex, String[] [] g r i d , double [] [] i n t e n s i t y , int [] [] terminals, Ant [] colony, i n t [] antID, i n t [ ] gridLimits){ int n = grid.length; int xPlus = xposition + 1; int yPlus = yposition + 1; int xMinus = xposition - 1; int yMinus = yposition - 1; random = new Random(); p r o b a b i l i t y = new double [4]; alabel = new i n t [4]; //This looks ahead i n the same column f o r the next vertex. while(xPlus < grid.length && g r i d [xPlus] [yposition] == "|")-[ xPlus++; } // This looks back i n the same column f o r the next vertex, while(xMinus >= 0 kk g r i d [xMinus][yposition] == xMinus—; > // This looks ahead i n the same row f o r the next while(yPlus vertex. < grid.length kk g r i d [xposition][yPlus] == "-"){ yPlus++; > // This looks back i n the same row f o r the next vertex. 104 whileCyMinus >= 0 && g r i d [xposition][yMinus] == "-"){ yMinus—; > f o r ( i n t k = 0; k < probability.length; k++){ p r o b a b i l i t y [ k ] = -1.0; // Some i n v a l i d p r o b a b i l i t y number. > //These i f ' s assign the p r o b a b l i l i t y of going i n the four d i f f e r e n t paths / / i f available. i f ( x P l u s < grid.length){//This makes sure that the ant does not run / / o f f the g r i d , if(m.tour[xPlus][yposition] != " " I I tool.globalView[xPlus] [yposition] == probability[0] =0.0; //if antlndex){ v i s i t e d p r o b a b i l i t y equals 0.0. > else -C ' probability[0] = uTil.selectionProMxPlus, y p o s i t i o n , i n t e n s i t y , m, n, terminals, g r i d , colony, antID); > } if(xMinus >= 0){//This makes sure that the ant does not run o f f the g r i d , if(m.tour[xMinus][yposition]!= "" 105 II tool.globalView[xMinus][yposition] == antIndex){ probability[1]= 0.0; } else { p r o b a b i l i t y [ 1 ] = uTil.selectionProb(xMinus, yposition, i n t e n s i t y , n, terminals,grid, colony, antID); } > i f ( y P l u s < grid.length){//This makes sure that the ant does not run off the g r i d , if(m.tour[xposition][yPlus]!= " " I I tool.globalView [xposition] [yPlus] == antlndex){ p r o b a b i l i t y [2]= 0.0; > else { p r o b a b i l i t y [ 2 ] = uTil.selectionProb(xposition, yPlus, i n t e n s i t y , m, n, terminals, g r i d , colony, antID); } } if(yMinus >= 0){//This makes sure that the ant //does not run off the g r i d . if(m.tour[xposition][yMinus] != " " II tool.globalView [xposition] [yMinus] == 106 antlndex){ probability[3]= 0.0; } else { p r o b a b i l i t y [ 3 ] = uTil.selectionProb(xposition, yMinus, i n t e n s i t y , m, n, terminals, g r i d , colony, antID); > > if (probability[0] < probability[0] = 0.0){ 0.0; } if (probability[1] < 0.0H probability[1] = 0.0; > if (probability[2] < probability[2] 0.0){ =0.0; > if (probability[3] < probability[3] ' ' 0.0){ =0.0; } double sum_probability = probability[0] + probability[1] + probability[2]+ probability[3] ; / / t h i s i s the t o t a l . 107 This section takes care of the case when the ant gets confuse, if (sum_probability == 0.0) { alabel = deconfuse(m,terminals, g r i d , antIndex); alabel[3] = -1; // // terminals[antlndex] [0] = alabel [1]; terminals[antlndex][1] = alabel[2]; System.out.println("\n\nAnt "+ antlndex + " had to be deconfused } else { p r o b a b i l i t y [0] = p r o b a b i l i t y [ 0 ] / sum_probability; p r o b a b i l i t y [1] = p r o b a b i l i t y [ 1 ] / sum_probability; p r o b a b i l i t y [2] = p r o b a b i l i t y [ 2 ] / sum_probability; probability[3] = p r o b a b i l i t y [ 3 ] / sum_probability; //This loop finds the maximum p r o b a b i l i t y , max = -1.0; int p = 0; while(p < 4){ if (max < p r o b a b i l i t y [p]){ max = p r o b a b i l i t y [ p ] ; p++; > else{ p++; } 108 > int choice = random.nextlnt(4); //This generates a random number //between 0 and 4 not including 4. while ( p r o b a b i l i t y [choice] != maxH choice = random.nextlnt(4); > //System.out.print("\n\npO= " + probability[0]+ " pl= " + probability[1]+ " p2= "+ "probability[2]+ " p3= " + p r o b a b i l i t y [3]); //These i f s move i n the d i r e c t i o n of the maximum p r o b a b i l i t y / / u n t i l u h i t an x, o or run of the grid, i f (choice == 0){ step = xposition +1; while (grid[step][yposition]== "I" && (step < grid.length)){ m.tour[step] [yposition]= "*"; tool.globalView[step][yposition]= antlndex; step++; } if (grid[step][yposition]== "o" && tool.globalView[step][yposition] m.tour[step] [yposition] = "*"; tool.globalView [step] [yposition] = antlndex; alabel[0]= -1; a l a b e l [ l ] = step; alabel[2] = yposition; }// At t h i s point we have to f i n d out which ant's t r a i l we j u s t met else i f ( g r i d [ s t e p ] [yposition]== "o" && 109 tool.globalView[step][yposition] != -1){ m.tour [step] [yposition] = "*"; alabel [0]= tool.globalView[step][yposition]; tool.globalView = mergeTours(tool.globalView, m.tour, antlndex); tool.globalView[step] [yposition]= antlndex; alabel[1] = step; alabel[2] = yposition; tool.globalView = updateGlobalView(tool.globalView, antlndex, a l a b e l [ 0 ] ) ; } // At t h i s point we have to f i n d out which ant we just met. else i f ( g r i d [ s t e p ] [yposition]== "x"){ m.tour[step][yposition] = "*"; alabel[0]= tool.globalView[step][yposition] ; //tool.globalView = mergeTours(tool.globalView, m.tour, antlndex); //alabel[0] = getTheAnt(step, yposition, terminals); alabel[1] = step; alabel[2] = yposition; tool.globalView = updateGlobalView(tool.globalView, antlndex, a l a b e l [ 0 ] ) ; > //System.out.println("\n\nThe maximum [0] i s : " + max); alabel[3]= 1; //Did not have a deconfuse. > else i f ( c h o i c e == 1){ step = xposition - 1; while (grid[step] [yposition]== "|" && (step >= 0)){ m.tour[step] [yposition]= "*"; 110 tool.globalView [step] [yposition]= antlndex; step—; } if (grid[step][yposition]== "o" kk tool.globalView[step][yposition] == -1){ m.tour [step] [yposition] = "*"; tool.globalView[step][yposition]= antlndex; alabel[0]= -1; a l a b e l [ l ] = step; alabel[2] = yposition; >// At t h i s point we have to f i n d out which ant's t r a i l we j u s t met. else i f ( g r i d [ s t e p ] [yposition]== "o" kk tool.globalView[step] [yposition] != -1){ m.tour [step] [yposition] = "*"; alabel[0]= tool.globalView[step][yposition]; tool.globalView = mergeTours(tool.globalView, m.tour, antlndex); tool.globalView[step][yposition]= antlndex; a l a b e l [ l ] = step; alabel[2] = yposition; tool.globalView = updateGlobalView(tool.globalView, antlndex, a l a b e l [ 0 ] ) ; > // At t h i s point we have to f i n d out which ant we just met. else if(grid[step][yposition]== "x" ){ m.tour[step][yposition] = "*"; alabel[0]= tool.globalView[step][yposition]; //tool.globalView = mergeTours(tool.globalView, m.tour, antlndex); //alabel[0] = getTheAnt(step, yposition, terminals); 111 alabel[1] = step; alabel[2] = yposition; tool.globalView = updateGlobalView(tool.globalView, antlndex, a l a b e l [ 0 ] ) ; } //System.out.println("\n\nThe maximum [1] i s : " + max); alabel[3]= 1; //Did not have a deconfuse. } else i f ( c h o i c e == 2){ step = y p o s i t i o n + 1; while (grid[xposition][step]== "-" && (step < grid.length)){ m.tour[xposition] [step]= "*"; tool.globalView[xposition][step]= antlndex; step++; > if(grid[xposition][step]== "o" kk tool.globalView[xposition] [step] m.tour[xposition][step] == -1) = "*"; tool.globalView [xposition] [step]= antlndex; alabel [0]= -1; alabel [1] = xposition; alabel[2] = step; }// At t h i s point we have to f i n d out which ant's t r a i l we just met. else if(grid[xposition][step]== "o" kk t o o l . globalView [xposition] [step] != -1){ m.tour [xposition] [step] = "*"; alabel [0] = tool.globalView[xposition][step]; 112 tool.globalView = mergeTours(tool.globalView, tool.globalView [xposition] [step]= m.tour, antlndex); antlndex; a l a b e l [ l ] = xposition; alabel[2] = step; tool.globalView = updateGlobalView(tool.globalView, antlndex, a l a b e l [ 0 ] ) ; > // At t h i s point we have to f i n d out which ant we just met. else if(grid[xposition][step]== "x" ){ m.tour[xposition] [step] = "*"; alabel[0] = tool.globalView[xposition][step]; //tool.globalView = mergeTours(tool.globalView, //alabel[0] = getTheAnt(xposition, m.tour, antlndex); step, terminals); a l a b e l [ l ] = xposition; alabel[2] = step; tool.globalView = updateGlobalView(tool.globalView, antlndex, a l a b e l [ 0 ] ) ; } //System.out.printlnC\n\nThe maximum [2] i s : " + max); alabel [3]= 1; //Did not have a deconfuse. } else i f ( c h o i c e == 3){ step = y p o s i t i o n - 1; while (grid[xposition][step]== "-" && (step >= 0)){ m.tour[xposition] [step] = "*"; tool.globalView [xposition][step]= antlndex; step—; > 113 i f ( g r i d [ x p o s i t i o n ] [step]== "o" && tool.globalView[xposition][step] == -1){ m.tour[xposition] [step] = "*"; tool.globalView[xposition] [step]= antlndex; alabel[0]= -1; a l a b e l [ l ] = xposition; alabel[2] = step; } // At t h i s point we have to f i n d out which ant's t r a i l we just met. else if(grid[xposition][step]== "o" && tool.globalView[xposition][step] != -1){ m.tour[xposition] [step] = "*"; alabel[0]= tool.globalView[xposition][step]; tool.globalView = mergeTours(tool.globalView, m.tour, antlndex); tool.globalView[xposition] [step]= antlndex; a l a b e l [ l ] = xposition; alabel[2] = step; tool.globalView = updateGlobalView(tool.globalView, antlndex, alabel[0]); // At t h i s point we have to f i n d out which ant we just met. else i f ( g r i d [ x p o s i t i o n ] [step]== "x" ){ m.tour[xposition] [step] = "*"; alabel[0]= tool.globalView[xposition][step]; //tool.globalView = mergeTours(tool.globalView, m.tour, antlndex); //alabel[0] = getTheAnt(xposition, step, terminals); a l a b e l [ l ] = xposition; alabel[2] = step; tool.globalView = updateGlobalView(tool.globalView, antlndex, a l a b e l [ 0 ] ) ; } 114 //System.out.println("\n\nThe maximum [3] i s : " + max); alabel[3]= 1; //Did not have a deconfuse. > m.setCity(antlndex); > //This i s f o r the else above, return alabel; > /** * Description: This methods was used to update the Global view of the system. * It replaced the tracks of the o l d or dead ant with the tracks f o r the new ant. * Oparam globalView This i s the globalView array * Oparam antlndex This i s the i d of the dead ant * Oparam alabel This i s the i d of the a l i v e ant * ©return globalView This i s the updated globalView array. */ public i n t [] [] updateGlobalView(int [] [] globalView, i n t antlndex, i n t a l a b e l H f o r ( i n t i = 0; i < globalView.length; i++){ f o r ( i n t j = 0; j < globalView.length; if (globalView[i][j] == globalView[i][j] = j++){ antlndex){ alabel; } > > return globalView; } /** * Description: This Method sets a c i t y as v i s i t e d f o r a give 115 * ant tour. * Oparam c i t y The.city that was just v i s i t e d . * */ ' _ public void s e t C i t y ( i n t c i t y ) { v i s i t e d [ c i t y ] = 1; J /** * Description: This method look f o r the ant that i s at * l o c a t i o n (x,y) i n the terminal array. * Oparam x This i s the x cooridnate where the ant w i l l be placed * Oparam y This i s the y cooridnate where the ant w i l l be placed * Oparam terminals This i s the terminal l i s t of the system. * ©return index This indicates which ant was moved. * */ public i n t getTheAnt(int x, i n t y, i n t [][] terminals){ int index = -20; for(int if 1=0; 1 < terminals.length; l++){ (terminals [1] [0] == x && terminals [1] [1] == y){ index = 1; } > return index; > /** * Description: This method copies the tour of ant m * into the tour of ant ml. * Oparam ml The ant who w i l l do the copying * Oparam m The ant who got copied * Oparam n The number of rows of the ants tour 116 * ©return ml The ant who did the copying * */ public Ant copyAntTour(Ant ml, Ant m, i n t n)-[ f o r ( i n t p = 0; p < n; f o r ( i n t q = 0; q < n; if (m.tour[p][q] ml.tour[p][q]= p++){ q++){ == "*" I I m.tour[p][q] == "a" ){ "*";// This copies the ant m tour into ant id's tour. } } } // ml.tour_length = ml.tour_length + // This adds the lenght of ant m's m.tour_length; tour to ant mi's tour. return ml; } /** * Description: This method copies the tour of ant m into the * globalView (global Tour) * ©param globalView The system view of the of the tour * ©param tour The tour of the ant who connected with the system. * ©return globalView The system view of the of the tour */ p u b l i c i n t [] [] mergeTours (int []..[] globalView, String [] [] tour, i n t antlndex){ ' f o r ( i n t p = 0; p < globalView.length; p++M 117 f o r ( i n t q = 0; q < globalView.length; if q++){ (tour[p] [q] == "*" || tour[p][q] == "a" ){ globalView[p][q]= antlndex;// This copies the tour //into the global view //of the tours. } > > return globalView; /** * Descriptions: This method was used to deconfuse an ant * i f he got trapped on h i s t r a i l . * Oparam m This i s the ant who was confused and who w i l l be relocated. * Oparam g r i d This i s the Hanan's g r i d * Oparam terminals This i s the terminal set of the system. * ©return confuse This i s an array which contains the x and y * coordinates where the * ant was deconfused to * */ public i n t [] deconfuse (Ant m, i n t [] [] terminals, String [] [] g r i d , i n t antlndex){ int n = grid.length;int nSquared = n * n; // number of squares i n the tour array. s t a r L i s t = new i n t [nSquared][2]; confuse = new i n t [4]; //This i n i t i z e s the s t a r L i s t array. 118 for (int t = 0; t < s t a r L i s t . length; t++){ f o r ( i n t s = 0; s < 2; s++){ s t a r L i s t [ t ] [s] =0; } } int row =0; f o r ( i n t r = 0; r < grid.length; r++){ f o r ( i n t c = 0; c < grid.length; c++){ if ((grid[r] [c] == "o" I I g r i d f r ] [ c ] == "x") && (m.tour[r] [c] == "*" I I m.tourLr] [c] == " a " ) ) { s t a r L i s t [row] [0]= r ; / / This loop t r i e s to l i s t a l l of the steiner points starList[row][1]= c; / / i n the tour of ant m. row++; } } } //System.out.println(row); //if (row > O H int index = random.nextlnt(row); confuse [1]= s t a r L i s t [index][0]; confuse [2]= s t a r L i s t [ i n d e x ] [ 1 ] ; // } //else-C //confuse = closestPoint(confuse, s t a r L i s t , terminals, row); // This method finds the closest point. In the ants f a b u l i s t //to go to when i t i s confused. 119 // } System.out.println("\nThe deconfuse point i s " + "("+confuse[l] +","+ confuse [2]+")"); confuse [0]= globalView [confuse[1]][confuse[2]]; //confuse[0]= antlndex; confuse [3]= -1; return confuse; /** * Descriptions: This method was used to relocate an * ant to a steiner point on h i s t r a i l . * ©param m This i s the ant who was confused and who w i l l be relocated. * ©param g r i d This i s the Hanan's g r i d * ©param terminals This i s the terminal set of the system. * ©return relocate This i s an array which contains the x and * y coordinates where the ant was deconfused too * */ public i n t [] relocate (Ant m, i n t [][] terminals, String [] • gridM int n = grid.length; int nSquared = n * n; // number of squares i n the tour array. s t e i n e r L i s t = new i n t [nSquared][2]; relocate = new i n t [4]; //This i n i t i z e s the s t a r L i s t array, for (int t = 0; t < s t e i n e r L i s t . length; t++M f o r ( i n t s = 0; s < 2; s++H s t e i n e r L i s t [ t ] [ s ] = 0; 120 } } i n t row = 0; f o r ( i n t r = 0; r < grid.length; r++H f o r ( i n t c = 0; c < grid.length; c++H if (grid[r] [ c ] == "o" kk (m.tour[r][c] == " * " I I m.tour[r] [c] == "a")){ steinerList[row][0]= r ; / / This loop t r i e s t o l i s t a l l of the steiner points s t e i n e r L i s t [row] [1]= c; // i n the tour of ant m. row++; } } > relocate = c l o s e s t P o i n t ( r e l o c a t e , s t e i n e r L i s t , terminals, row); // This method finds the closest point In the ants t a b u l i s t // t o go t o when i t i s confused. System.out.println("\nThe r e l o c a t i o n point i s " + "("+relocate[l] +","+ relocate [2]+")"); relocate[0]= g l o b a l V i e w [ r e l o c a t e [ 1 ] ] [ r e l o c a t e [ 2 ] ] ; return relocate; > /** * Description: This method attempts t o f i n d a steiner point that * i s near to the other terminals. Then returns the s t e r i n e r point * i n the ant's t a b u l i s t nearest to the other 121 ants. * Oparam confuse This i s an array which contains the x and y coordinates * where the ant w i l l be moved to * Oparam s t a r L i s t This i s an array which store a l l of the points v i s i t e d * by the other ants. * Oparam terminals This i s the terminal set of the system. * Oparam row This i s the row that indicates the depth of the s t a r L i s t set. * Oreturn confuse This i s an array which contains the x and y coordinates * where the ant * w i l l be moved to */ public i n t [] c l o s e s t P o i n t ( i n t [] confuse, i n t [][] s t a r L i s t , i n t [] [] terminals, i n t rowM int d i s t ; int minDis = 1000000; f o r ( i n t f = 0; f < row; f++){ for (int g = 0; g < terminals.length; g++){ d i s t = Math.abs(terminals[g] [0] - s t a r L i s t [ f ] [0]) + Math.abs(terminals[g] [1] - s t a r L i s t [ f ] [ 1 ] ) ; if (dist <= minDis){ minDis = d i s t ; //looks f o r the min distance between the steiner //points and the terminals, confuse [1]= s t a r L i s t [ f ] [ 0 ] ; //This i s the x cooridinate f o r the min //distance. confuse [2]= s t a r L i s t [f] [1]; //This i s the y cooridinate f o r the min distance. > 122 } } return confuse; } /** * * ©return Returns the tour. */ public S t r i n g [][] getTourO { return tour; > /** * ©param tour The tour to set. */ public void setTour(String!][] tour) { t h i s . t o u r = tour; > /** * ©return Returns the tour_length. */ public double getTour_length() { return tour_length; } 123 /** * Oparam tour_length The tour_length to set. */ public void setTour_length(double tour_length) { this.tour_length = tour_length; } ' \, /** * Oreturn Returns the v i s i t e d . */ public i n t [ ] g e t V i s i t e d O return { visited; } /** * Oparam v i s i t e d The v i s i t e d to set. */ public void s e t V i s i t e d ( i n t [] v i s i t e d ) { this.visited = visited; y /** * Oreturn Returns the xposition. */ public i n t getXpositionO { return xposition; y /** * Oparam xposition The xposition to set. */ 124 p u b l i c void setXposition(int xposition) { t h i s . x p o s i t i o n = xposition; } /** * ©return Returns the yposition. */ public i n t getYpositionQ { return yposition; y /** * ©param yposition The yposition to set. */ p u b l i c void setYposition(int yposition) { t h i s . y p o s i t i o n = yposition; y /** * ©return Returns the max. */ public double getMaxO { return max; } /** * ©param max The max to set. */ p u b l i c void setMax(double max) this.max = { max; } /** * ©return Returns the globalView. */ public i n t [] [] getGlobalViewO { return globalView; y /** 125 * Qparam globalView The globalView to set. */ public void setGlobalView(int [][] globalView) { this.globalView = globalView; > } //Experiment!!!! /*if (sum_probability != 0.0) { * double randomSubSum = sum_probability * random.nextDouble0; //generates a random number between 0 and sum_probability. int j = 0; double p = 0.0; while(p <= randomSubSum){ p = p + probability [j]; System.out.printlnC This i s p: " + p + " This i s randomSubSum + randomSubSum + " when j = " + j ) ; j + + ; > */ //End Experiment!!!! 126 Appendix G Source Code for Utilities.Java package A n t S t e i n e r . u t i l ; import AntSteiner.*; import AntSteiner.ui.*; /** * Class: U t i l i t i e s . J a v a * @author Anthony Blackman * ©version A p r i l 10, 2006 */ p u b l i c class U t i l i t i e s { /**This i s the variable was used to store the d e s i r a b i l i t y the ant had to move to a given vertex.*/ private double d e s i r a b i l i t y ; /**This i s the variable was used to store the shortest distance * between the ant's current l o c a t i o n and the tabu l i s t of the other ants 127 private double p s i ; /**This i s the variable was used to store the i n t e n s i t y the of the t r a i l . * / private double intens; /**This i s the variable was used to store the change i n i n t e n s i t y of the * edge of the g r i d . * / private double delta_tau; /**This i s the variable was used to store the r e c t i l i n e a r distance between * v e r t i c e s on the g r i d . * / private double rec_distance; /**This data structure was used to store the current t r a i l i n an ant's tabu * list.*/ private S t r i n g [] [] tourTemp; /**This i s the variable was used to store the minimum distance between points i n * the ants tabu l i s t . * / private double minimum = 1000000.0; /**This i s the variable was used to store the combination of d e s i r a b i l i t y and * intensity*/ private double intense_desire; /**This i s the variable was used to store the power of the t r a i l i n t e n s i t y . * / private double alpha; 128 /**This i s variable was used to store the power of the d e s i r a b i l i t y . * / private double bata; /**This i s the variable was used to store the constant parameter i n the * d e s i r a b i l i t y formula.*/ private double gamma; /**This i s the variable was used to store the evaporation parameter f o r * the system.*/ private double rho; /**This i s the variable was used to store the q u a l i t y of the t r a i l . * / private i n t Q; /** * This i s the default constructor. */ p u b l i c U t i l i t i e s (){ alpha = Double .parseDoubleQnputUI .parameters [0]); bata= Double .parseDoubleQnputUI .parameters [1]); rho = Double .parseDoubleQnputUI .parameters [2]); gamma = Double .parseDoubleQnputUI .parameters [4] ) ; Q = Integer.parselntQnputUI.parameters[5]); /** 129 D i s c r i p t i o n : This methods gets the i n t e r s i t y of the t r a i l from x to y. Oparam x c i t y ©param y c i t y ©param i n t e n s i t y array Oparam m The ant m Oreturn intense_desire s e l e c t i o n p r o b a b i l i t y f o r the s p e c i f i c edge. / public double selectionProb(int x, i n t y, double [] [] i n t e n s i t y , Ant m, int n, i n t [] [] terminals, String if [] [] g r i d , Ant [] colony, i n t [] antID) (m.getTour_length()== 0.0) { delta_tau = 0.0; > else { double c = m.getTour_length(); delta_tau = Q / c; } intens = ((double)l - rtio)*intensity[x] [y] + rho * delta_tau; //This i s the t r a i l intensity. psi = createPSI(colony, x, y, g r i d , antID); // This i s the shortest distance from vertex i to a l l // the v e r t i c e s i n the t a b u l i s t of the other ants. 130 d e s i r a b i l i t y = 1 / (1 + gamma * p s i ) ; intense_desire = Math.pow(intens, alpha)*Math.pow(desirability, return intense_desire; } /** * This Method calculates the r e c t i l i n e a r distance between * c i t y x and c i t y y. * Oparam x c i t y x * Oparam y c i t y y * Oparam row * Oparam c o l * ©return rec_distance */ public double recDistancednt x, i n t y, i n t row, i n t c o l ) { rec_distance = Math.abs(x - row)+ Math.abs(y - c o l ) ; return rec_distance; } /** * Descriptions: This method was used to relocate an ant to a * steiner point on h i s t r a i l . * Oparam colony The set of ants 131 bata) * Oparam g r i d The Hanan's g r i d * Oparam x cooridnate * Oparam y cooridnate * Oreturn minimum This i s the value of PSI * */ p u b l i c double createPSI(Ant [] colony, i n t x, i n t y, S t r i n g [][] g r i d , i n t [] antIDH int n = grid.length; double min; tourTemp = new String [n][n]; f o r ( i n t antnum = 0; antnum < colony.length; antnum++)-( if (antID[antnum]!= -1){ tourTemp = colony[antnum].getTourO; f o r ( i n t row = 0; row < grid.length; row++){ f o r ( i n t c o l = 0; c o l < grid.length; col++){ // This l i n e looks f o r a l l the x's and the o's i n the / / t a b u l i s t of the ant c a l l e d antnum if((tourTemp[row] [col] == "*" I I tourTemp [row][col]== (grid[row] [col] == "x" II g r i d [row] [col]== "a" )&& • "o")){ //This finds the r e c t i l i n e a r distance between (x, y) and (row, c o l ) min = recDistance(x, y, row, c o l ) ; if(min < minimum){ minimum = min; >}}}>} return minimum; }} 132 Appendix H Source Code for Display.java package AntSteiner.ui; import Java.awt.Color; import hsa.Console; /** * Class: Display.java * @author Anthony Blackman * Aversion A p r i l 10, 2006 */ p u b l i c class Display { /**This v a r i a b l e was used as a reference to the output console*/ private Console c; /** * This i s the default constructor. */ public Display(){ } 133 /** * Description: This method was used to display the Steiner Tree; * Oparam sTree The steiner tree * Oparam g r i d The Hanan's g r i d * Oparam tLength The length of the steiner tree. */ public void displayTree(String [][] sTree, String [][] g r i d , int tLength, long took){ / / i n t n = grid.length; c = new Console(45, 100, "Ant Tour" + " " ) ; // from the HSA Package. c.print("\nThe Steiner Tree length i s : " + tLength ); c.print("\n\nThe execution time was: " + took + " milliseconds. " ) ; f o r ( i n t i = 0; i < grid.length; i++M // System.out.print("\n"); c.print("\n"); f o r ( i n t j = 0; j < grid.length; // System.out.print(grid[i][j]+" " ) ; if ( s T r e e [ i ] [ j ] == " * " I I sTree[i] [j] == "a"){ c.setTextColor(Color.BLACK); c . p r i n t ( g r i d [ i ] [j]+ " " ) ; } else { c.setTextColor(Color.WHITE); 134 c.print(grid[i][j]+ " " ) ; > > > //c.drawString ("k",30, 400); > //c.drawLine(10,10,10, 300); } /** * Description: This method was used to display the Hanan's Grid; * Oparam g r i d The Hanan's g r i d . */ p u b l i c void d i s p l a y G r i d ( S t r i n g [][] grid){ // This p r i n t s the g r i d . c = new Console(45, 100, "Hanan Grid"); for ( i n t i = 0; i < grid.length; i++) { //System.out.print("\n"); c.print("\n"); f o r ( i n t j = 0; j < grid.length; j++){ //System.out.print(grid[i]"); if ( g r i d [ i ] [j]== "-" || g r i d [ i ] [j]== "|"){ c.setTextColor(Color.RED); //From the hsa Package . c.print(grid[i]"); > else {//System.out.print(grid[i]"); c.setTextColor(Color.BLACK); //From the hsa Packag c . p r i n t ( g r i d [i] [j]+" " ) ; > >> » 135 Appendix I Source Code for the MST_via_MatrixTree_Nu.m function tree_length = MST_via_MatrixTree_Nu (N) yName: Anthony Blackman o 7«Aim: The main purpose of t h i s function i s to calculate the length of the 7. generated by a set of N randomly generated v e r t i c e s . Using the 7. K i r c h o f f ' s Matrix-Tree Theorem. "/.Date: January 12th 2006 "/.Reason f o r Development: Algorithm f o r the author's Masters Thesis at UBC. MinTreeValues = zeros(5,2)7. This array w i l l store the points to plot generated VSet = zeros(N,3) % This array w i l l store the Vertices generated Tree_Vert = zeros(N,N)7. This array w i l l store the City Plan ( i e . graph layout) Distance_Matrix = zeros(N,N)7. This array w i l l store the r e c t i l i n e a r distance 7. between Vertex i 136 MST % and Vertex j i n p o s i t i o n ( i , j ) MTree = zeros(N,N)7„ This array w i l l store the expressions generated by the % Matrix-tree Theorem, temp = zeros(N,l) % W i l l be used the store the row sum. for k = 1:N x = randperm(N) % This function generates a random permutation of % numbers 1 to N i = x(l)°/ This function select the kth number i n the randomly generated 0 7. l i s t integers 7« 1 to N. The i represents the i t h row where the vertex will 7» be placed. y = randperm(N) 7, This function generates a random permutation of 7o numbers 1 to N j = y(D7» This function select the kth number i n the randomly 7» generated l i s t integers 7. 1 to N. The j represents the j t h column where the vertex 7o w i l l be placed. T r e e _ V e r t ( i , j ) = l °h Put a one i n p o s i t i o n ( i , j ) to indicate the presents 7o of a vertex. VSet(k,l)=k 7o This l i n e stores the vertex V_k i n row k column 1 7. of VSet 137 VSet(k,2)=i % This l i n e stores the row p o s i t i o n of V_k i n row k 7, column 2 of VSet VSet(k,3)=j % This l i n e stores the column p o s i t i o n of V_k i n row k % column 3 of VSet end % This ends the f o r loop. f o r alpha = 1:N for Beta = 1:N Distance_Matrix(alpha, Beta) = abs(VSet(alpha,2)-VSet(Beta,2)) + abs(VSet(alpha,3)-VSet(Beta,3)) Distance_Matrix(alpha, Beta)= -Distance_Matrix(alpha, Beta) 7. The two statements above calculates the r e c t i l i n e a r distance 7o between vertex alpha and vertex bata then stores the value at 7« p o s i t i o n (alpha, bata) of the Distance_Matrix. After t h i s 7o then multiply the value by -m where m i s a parameter that 7. w i l l be dealt with l a t e r , end 7o This ends the inner f o r loop end 7o This ends the outer f o r loop. for m = T= 1:5 Distance_Matrix Distance_Matrix = m*Distance_Matrix MTree = exp(Distance_Matrix) 7oThis raises each element of the 7o Distance_Matrix to the power e MTree = -MTree 7oThis puts the minus exp into the matrix for w = 1:N 138 we MTree(w,w) = 0 °/ Since distance between vertex one and vertex 0 % one i s zero we would have a minus one "L at each element of the main diagonal since we took °L the exp of the matrix then time -1 and -e~0 i s -1. % However we dont need a one i n that p o s i t i o n . end temp = sum(MTree) 7« This l i n e stores the column sums of the matrix MTree i n a % vector c a l l e d temp. % In the thesis I said that the row sums should be zero % but i n t h i s case the row sum = column sum because the °L the distance matrix i s a symmetric matrix and A transpose temp = -temp f o r p = 1:N MTree(p,p)= temp(p) % This l i n e places the some of row p i n p o s i t i o n % (p,p) of MTree. This makes the row sum of the % matrix MTree to be a l l zero, end °/ This l i n e ends the f o r loop. c MTree(1,1) = MTree(1,1) + 1 % This l i n e makes the sum of row one to be one. % While the row sums of rows 2 to N are s t i l l Tree_Polynomial zero = det(MTree) 7, This l i n e writes the determinant of % MTree. Tree_Polynomial= abs(Tree_Polynomial) °L This function take the absolute 7o of the determinant. 139 value Log_Tree_Polynomial = log(Tree_Polynomial) '/, This l i n e take the natural l o g % of the Tree polynomial MST_function = Log_Tree_Polynomial / m % t h i s l i n e s i s f o r the c a l c u l a t i o n for MinTreeValues(m,l)= MinTreeValues(m,2)= ln(det(A(m)))/m. m abs(MST_function) Distance_Matrix = T end maximum = max(MinTreeValues(m,2)) d=l:5 °L This plots f i v e points of the function f o r values of m = 1,2,3,4 and 5 plot(d,MinTreeValues(d,2)) xlabel('Value of M'), ylabeK'MST Value') t i t l e ( ' G r a p h 1: Graph of MST v i a Matrix Tree Results f o r N') Distance_Matrix = -Distance_Matrix % This gets back the a c t u a l l y distance matrix MST = xmst (Distance_Matrix) '/, This passes the r e c t i l i n e a r distance matrix into the % prim' algorithm length = size(MST,2) % This calculates the edges i n the array, f o r e = 1 : length Tree(e)= Distance_Matrix(MST(l,e),MST(2,e)) 1 This stores the lengths of °/ each edge i n an array 0 end 140 MSTree_length = sum(Tree) 7. This finds the length of the array by summing a l l '/, of the lengths of the edges. 7» This i s the end of to program. 141 Appendix J P r i m ' s A l g o r i t h m using M a t l a b function E=xmst(D); '/.Name: Anthony Blackman °/Aim: Minimum Spanning Tree using Prim's Algorithm. 0 '/.Date: January 12th 2006 %Reason f o r Development: Algorithm f o r the author's Masters Thesis at UBC. '/.Input: D R e c t i l i n e a r distance matrix '/, D ( i , j ) weight of edge i 7. D must be symmetric j 7 0utput: E indices of edges of MST 0 7»Prim's Algorithm. n=size(D,l); E=zeros(2,n-l); a=l:n-l; r=n; cnt=l; M=repmat(Inf,[2 n-1]); while length(a); [md,mi]=min([M(l,:);D(r,a)]); f=find(mi==2); M(l,f)=md(f); M(2.f)=r; [md,mi]=min(M(l,:)); 142 r=a(mi); E(:,cnt)=[r;M(2,mi)] a(mi) = [] ; M(: ,mi)=[] ; cnt=cnt+l; end; 143
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Ant colony optimization and rectilinear Steiner minimal...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Ant colony optimization and rectilinear Steiner minimal trees Blackman, Anthony Curtis 2006
pdf
Page Metadata
Item Metadata
Title | Ant colony optimization and rectilinear Steiner minimal trees |
Creator |
Blackman, Anthony Curtis |
Date Issued | 2006 |
Description | This paper consists of two distinct parts. In the first part, we introduce the Rectilinear Steiner Minimal Tree (RSMT) problem and describe the Ant Colony algorithm which we use to construct the RSMT. The development of an Ant Colony algorithm called AntCol Steiner is described and we create a working program of the algorithm using the Sun Microsystems Java programming language (see appendix A to H for details). We investigate the effectiveness of our algorithm by using AntCol Steiner to construct; and draw RSMT a given a random set of terminals. In the second part, we look at an application of the Kirchoff's Matrix Tree theorem. We find the length of a Rectilinear Minimal Spanning Tree (RMST) spanning a set of random terminals. We verify the accuracy of our results from the Kirchoff's Matrix Tree algorithm using Prim's RMST Algorithm. Our original plan was to develop an algorithm based on this theorem to determine the length of a RSTM. However, we were unable to modify the algorithm we used to find the length of the RMST, for the case of a RSMT. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-01-08 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0080128 |
URI | http://hdl.handle.net/2429/17733 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2006-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_2006-0155.pdf [ 4.34MB ]
- Metadata
- JSON: 831-1.0080128.json
- JSON-LD: 831-1.0080128-ld.json
- RDF/XML (Pretty): 831-1.0080128-rdf.xml
- RDF/JSON: 831-1.0080128-rdf.json
- Turtle: 831-1.0080128-turtle.txt
- N-Triples: 831-1.0080128-rdf-ntriples.txt
- Original Record: 831-1.0080128-source.json
- Full Text
- 831-1.0080128-fulltext.txt
- Citation
- 831-1.0080128.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080128/manifest