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 I N P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F Master of Science in T H E F A C U L T Y OF G R A D U A T E S T U D I E S (Mathematics) The University of British Columbia Apr i l 2006 © Anthony Curtis Blackman, 2006 Abstract This paper consists of two distinct parts. In the first part, we introduce the Rectilin-ear Steiner Minimal Tree (RSMT) problem and describe the Ant Colony algorithm which we use to construct the RSMT. The development of an Ant Colony algo-rithm 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 Abstrac t i i Contents i i i Lis t of Tables v i Lis t of Figures v i i Acknowledgements ix Dedicat ion x 1 Introduction 1 1.1 Rectilinear Steiner Problem 1 1.2 Hanan's Grid 4 2 The A n t Colony 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, gridLim-its) Method 13 iii 2.4.3 The AntMove(colony[m],info[l], info[2], id, grid, intensity, ter-minals, colony, antID, gridLimits) Method 15 2.4.4 The pRime(sTree, grid, gridLimits) Method 16 2.5 Formulas used in the AntCol Steiner Algorithm 18 3 Kirchoff's Matrix Steiner Tree Formula 21 3.1 An 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 A n Interesting Observation 29 4 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 Results from MST_via_MatrixTree_Nu(N) with N = 5 . . . . 32 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 v i List of Figures 1.1 An example of a RSMT constucted using GeoSteiner 3.1 [14]. . . . 2 1.2 An example of a Hanan grid for a set T with N = 20 points 5 2.1 Arrow thickness represents probability of ants choosing one path over another. (t=0) Foraging ant chooses the path based on a 50% prob-ability; (t=l) Follower ants also choose their path on a 50% proba-bility; (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 the probability of ants choosing the longer path is very small 7 A . l The Graphical User Interface of the AntCol Steiner Program 41 A.2 This Screen show the Steiner Tree before and after Priming. The pre-pruned 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 43 vii .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 pa-tience 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 C U R T I S B L A C K M A N The University of British Columbia April 2006 ix To my family Anthony, Beverley and Kristle Blackman. x C h a p t e r 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 so-lutions 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 which is a solution of GeoSteiner 3.1 [14]. . . . An .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: An example of a RSMT 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 s w a r m intelligence [ 2 ] , 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=NP). 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), which is the Manhattan distance between vertex i andj. 3 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 I + I ii - J2 I . (1-1) 1.2 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 * i 1 i ! J i i^ - | | - < | > " ' — — • — ! — — , • > j t 1 i Figure 1.2: A n example of a Hanan grid for a set T wi th N = 20 points. 5 C h a p t e r 2 The Ant Colony Idea The Ant System algorithm is biologically inspired by the foraging pattern of ants. Natural ants when following a pheromone trai l 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 trai l leading from the ant's nest to a food source. Along 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. The 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 wi l l also choose with roughly equal probability. When the first ant is coming back from the food location towards the nest, it again wi l l randomly choose one of the trails because the amount of pheromone in the two trails wi l l be very similar. The next experiment, known as double bridge made things very clear. Again, the ants are in an artificial controlled environment where there is a path from their nest to a food source. This time, there are two bifurcations in sequence as in figure 2.1, but unlike the first experiment, one branching path is shorter than the others. Initially the situation wi l l 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) From the conclusion of the experiments of Deneubourg an algorithm based on these observation seems to be a natural approach to obtaining an approximate time effi-cient solution to the Steiner problem. Algorithms which mimic this natural behavior of ants are called Ant Colony Optimization meta-heuristic algorithms. 2.2 Development of ACO Algorithms for the Steiner Problem The 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. Good solutions are an emergent property of the artificial ants cooperative interaction. Art if icial ants have a double nature. First , they are an abstraction of real ants found in 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 in software to solve difficult discrete optimization problems, it, is reasonable to give the ants some capabilities, which while not found in real ant behavior, make them more efficient and effective. We wi l l comment on this more later. First , in a paper called "Ant Colony Algorithms for Steiner Trees: A n A p -plication to Routing in Sensor Networks" an algorithm based on Ant Colony Op-timization was developed by Gurdip Singh, Sanjoy Das, Shekhar V . Gosavi, and Sandeep Pujar. This algorithm can be found in [4]. In this paper, the authors verified their results using various problem in-stances taken from Beasley [1]. The test, cases described in 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 RSMT 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. An 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 expla-nation 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, AntMove and pRune. AntColSteiner is used to select the best of a l l possible trees. constructSteinerTree-B 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. AntMove is used to determine which direction the ant should move via the Hanan grid. Finally, the pRune method removes all non terminal leaves from the tree obtained from constructSteinerTree-B y A C O . 2 . 4 . 1 The AntColSteiner(N, M) Method INPUT ARGUMENTS: N : This 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. They 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 in the grid was at least one space away from the other points. The only reason vertices were placed in rows r and columns c with even indexes was to make our output easier to understand. 11 4. A t each ve r tex ( r , c) the le t te r x is p laced o n the g r i d t o ind ica te t h a t a t e r m i n a l ver tex is c reated. 5. U s i n g the t e r m i n a l vert ices a H a n a n G r i d is generated. D u r i n g the cons t ruc -t i o n o f the g r i d each t i m e a ve r t i ca l edge and a h o r i z o n t a l edge crossed, the le t te r o is p laced o n the g r i d to represent a possible Steiner p o i n t . 6. A n equa l a m o u n t o f pheromone is p laced o n each edge o f the Ha,nan G r i d . T h i s represents the i n i t i a l t r a i l in tens i ty . 7. A n an t d a t a s t r u c t u r e is created and M instances o f t he data, s t r u c t u r e axe dec lared a n d i n i t i a l i zed . These are ou r a r t i f i c i a l ants . 8. I n i t i a l i ze the bestSteinerTree = const ructSte inerTreeByACO(terminals , gr id, intensity, gr idLimits) see the descr ip t ion o f th is m e t h o d be low. 9. bestSlength = getTLengthQ T h i s m e t h o d gets the l e n g t h o f t he Ste iner tree j u s t generated. 10. B E G I N W H I L E 11. w h i l e ( c o u u t < M A X L O O P ) • F O R each edge i n the H a n a n g r i d - I F * T h e a n t wa lked o n edge o f t h e g r i d d u r i n g t h e prev ious i te r -a t ions , u p d a t e the pheromone in tens i t y a long t h a t edge us ing updateIntensity(sLength, row, col, intensity) - E L S E reduce the level o f pheromone in tens i ty . - E N D I F • E N D F O R 12. steinerTree = constructSteinerTreeByACO(terminals , gr id, inten-sity, gr idLimi ts ) 12 13. sLength = 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. • E L S E — copy the content of steiner Tree into bestSteinerTree. • ENDIF 15. count = count + 1. 16. END WHILE. 17. After M A X L O O P iterations bestSteinerTree was displayed. 18. END. 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 , g r i d , intensi ty , g r i d L i m i t s ) M e t h o d . I N P U T A R G U M E N T S : 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. gr idLimits : This is an integer array used to store the border values of the grid in the following manner: gr idLimits [0] = xmax This is the value of the last row of the Hanan's grid. gr idLimits[ l ] = ymax This is the value of the last column of the Hanan's grid. gr idLimits [2] =. x m i n This is the value of the first row of the Hanan's grid. gr idLimits [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. WHILE • 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 = An tMove( too l , colony[m],info[l], info[2], i d , gr id, intensity, terminals, colony, antID, gr idLimits) 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 = An tMove( too l , colony[m],info[l], info[2], i d , gr id, intensity, terminals, colony, antID, g r i d L i m -its) method. • E N D W H I L E • 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, gr id, gr idLimits) 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 , intensi ty , t e rmina l s , colony, a n t I D , g r i d L i m i t s ) M e t h o d . I N P U T A R G U M E N T S : 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, id 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 id would store the identification number of the ant it met. Else, id would have the value of — 1. antID 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 im-mediate nearest neighbors vertices (possible Steiner points as well as terminal vertices). An 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 decon-fuse(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. ENDIF 6. Return info 7. END 2.4.4 The pRune(sTree, grid, gridLimits) Method I N P U T A R G U M E N T S : 16 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. FOR loops = 0 to loops = NSquared • FOR, row = gridLimits[2] to gridLimits[0] - FOR col = gridLimits[3] to gridLimits[l] * IF grid [row] [col] is NOT "x" A N D sTree[row][col] is NOT " " • 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 - E N D F O R row = row + 1 • E N D F O R 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. An 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 RMST 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!71. = - (o I) \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). TlJ(t) + 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 Sm i f (*, j) € E(t) Ar,d(t) = I c ( S ( i ) ) V u" K ' (2.3) I 0 o t h e r w i s e w h e r e c(S(t)) 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 se t o f S(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 t h e s u r v i v i n g a n t h a s t o d i s t r i b u t e t h r o u g h i t s t r a i l . T h e w e i g h t o f a n a n t a t i t o m o v e o n e d g e is d e n n e d as follows: i f j 6 A a n d k t a b u - l i s t (rn) Pid(t) = l Efch . f c W l -Ki l" 7 * ( 2 . 4 ) [ 0 o t h e r w i s e w h e r e A is t h e se 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 is 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 i m p o r t a n c e o f e a c h v a r i a b l e 77.7- a n d ij™ i n ( 2 . 4 ) . 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 i n s e c t i o n 4 . 1 . 1 20 C h a p t e r 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(N3) 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 NP 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 Aap be a symmetric N x N matrix whose row sums are zero except for the first row which sums to one. Theorem 3.0.1 Kirchoff's matrix-tree theorem [12]. detA = ^2 Y[ Aa0 21 where T is summed over all tree graphs with vertex set {1,2,-means {a, (3} is in the edge set of T. ,N] and a,peT 3.1 An Application of Kirchoff's Matrix-Tree Theorem Let Vertex.set = {A" a} be a finite set of points in the plane. These are the terminals. We are about to describe a way to calculate the length of a minimal spanning tree. Note there are no Steiner points. Let Ka and Kp e Vertex.set. If Ka = (ia,ja) and Kp = {ip,jp) for any a, (3 = 1, 2. • • • , JV, the Manhattan distance c(Ka,Kp) between Ka and Kp is given by definition 1.1.4. Define the matrix A ( m ) by Aap{m) = _e-m-c(Ka,Kp) if a ^ (3 E A - m . C ( K A , 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 ' An(m) i4 1 2(m) . . . Ai/v(?n) \ A / , A2\(m) A22(m) ... A2N(m) A(m) = \ ANy(m) AN2(m) ... ANN(m) J with -Ay(m) = Aji(m), that is (A(m)) T = A(m) . Further all of the row sums of A(m) are zero except for the first row which sums to one. That is E/tLi ^ i / .-(m) = 1 and EALI Ajk(m) = 0 for each row j = 2, • • • ,N. Using this definition and the Matrix-Tree Theorem 3.0.1 we obtain. 22 det A(m) = Y/ II e~m<Kc T a,f)eT T -m(Totat.J.engUi(T)) Further, we can fix A?" and take m —* oo and consider — In det A ( m ) We obtain 1_ m In det A ( m l 1 m 1 m ,-m-(TolalJength,(T)) j n g—m(M inimumJength(T)) = — Minimum Jength(T) From this we have a formula for calculating the length of the minimum spanning tree T v ia 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\, V 2 ) = 2, c(V*i, V 3 ) = 3 and c ( V 2 , 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). The distance matrix D for the example above is given below. In this matrix D an element in row % and column j represents the rectilinear distance between vertex Vi and vertex Vj. D ( 0 2 3 ^ 2 0 6 \ 3 6 0 j 23 From this we obtain: A(m) = (1 + e-2m + e -'im\ —e -2m - 3 m -e -2m _ —e -2m - e~ - 6 m . . e - 3 m - 6 m / e - 3 m + e - 6 m A Therefore. detA(m) = {1 + e-Am + e-im) (e-2m + e - 6 m ) ( e - 3 m + e"6m) - e - 1 2 m —2m —e - 3 ? n -e-9"1 - e _ 2 m ( e - 3 m + e _ 6 m ) - 8 m . „—Zmi„—2m , 6 ? r « - 5 » n 2e- 7 m + e- 8 m + e- y m + 2e- i u m + 4e 9 m . - 1 0 m -11m = e - 5 m 1 + 2e~2m + e~3m + e"4m + 2e"5m + 4e- 6 m Now if we take natural logs on both sides we obtain, In det A(m) = —5m + In 1 + 2e~2m + e~3m + e • 4 m + 2 e - 5 m + ^-Sn. which implies that, 1 m In det A(m) In = -5 + 1 + 2e - 2 m . - 3 m + < l!" + 2e~5m + 4e — 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 a formula that 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,:i). The main idea behind this algorithm is Gaussian Elimination. 3.2.1 T i m e C o m p l e x i t y of C a l c u l a t i n g the D e t e r m i n a n t 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-triangular form, 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. Theorem 3.2.1 The cost of calculating det(A) for a general n x n matrix using Gaussian Elimination is 0(nA). Proof. Let C(n) be the cost to calculate the det(A) for a general n x n matrix A then, 25 7 7 7— 1 7 1 ,'=2 j=\ k=j 7 1 7—1 7=2 J = ] 7=2 7 7 i - 1 = / r £ | ( „ + i ) ( i - i ) - £ ; j 7=2 7 7 K 7=1 77 r ( n + l ) ( i - l ) (n + l ) ( i - l ) »(» - 1) 2 i ( i - 1) i=l -i2 - (2n + 3)i - 2{n + 1) •n(n + l)(2ra + 1) + n(n + l ) (2n + 3) = A' 6 n(??,+ 1) 2??.(?7, + 1) 1 + 2n + 2n + 3 _ O K n(n + 1) 4 ( n - 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 matrix is just O(n) , it is correct to say that the cost C(n) of the whole procedure is 0(n3). 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 D e s c r i p t i o n In this section, a detailed algorithm for determining the length of a minimum span-ning tree T with N vertices is outlined. The algorithm is based on Kirchoff's Matrix-Tree theory and has a time complexity of 0(Nii). 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 (Matrix JTree) and the other one TREE.VERT (Tree-Vertex). 5. Set all of the elements of MTREE 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 Example 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 TREE.VERT i/j 1 2 3 4 5 6 1 1 0 0 0 0 0 2 0 0 0 1 0 0 3 0 1 0 0 0 1 4 0 0 0 0 0 0 5 0 0 1 0 0 0 6 0 1 0 0 0 0 Table 3.1: The TREEJVERT data structure. VSET k i j 1 1 1 2 2 4 3 3 2 4 3 6 5 5 3 6 6 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 EK^Ka e~m<K^K^ + 6i(a)8) {(3) * ELSE • SET MTREE{a}[[3](m) TO -e-m<K°>Kp) * 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. ENDFOR 9. Choose the max{MTREE(m)} to estimate the value of c(MST) 10. Print the results. 11. END. 3.3 An Interesting Observation Remark 3.3.1 Proof. Since, we have which implies, Hence, c(MST) > MTREE(m) V m > 1 detA(m) = £ J] e-m-c(*a T a,/3eT KB) > n < a,/3er -mc(Ka,Kfi) lndetA(m)> ^ I n e - ' " c ( A ' - A » a,/3eT 1 m In det A(m) -771 ]P c ( K a J < l 3 ) , T c(Ka,Kp) > - -z — ' 777, a,/3GT In det A(m) c(MST) = nun ^ c(Ka,Kp) L a , / 3 e T > m In det A(m) MTREE(m) Vm > 1 29 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 C h a p t e r 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 R E S U L T S M N Avg. Steiner Tree Length Avg. Time (s) Best Steiner Length Best Time 9 25 38 0.750 32 0.554 - 12 30 71 1.062 69 0.996 15 30 73 1.203 71 0.998 20 30 103 1.812 97 1.132 25 30 129 1.907 113 1.787 30 40 170 4.390 167 3.980 40 40 182 4.557 175 4.012 50 40 220 6.915 215 5.788 70 50 340 20.127 305 15.876 100 50 370 25.266 343 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 Mat-lab programming language. We called our program MSTJuia-MatrixTreeJVu(N) where Ar is the dimension of the matrix. In'the next section one will find step by step execution of the program. The source code for MSTjvia.MatrixTree-Nu(N) can be found in. Appendix I. 4.2.1 Resu l t s f rom M S T _ v i a J V I a t r i x T r e e J N u ( N ) w i t h N = 5 This represents the set of random v e r t i c e s generated by the program. VSet = 1 5 2 2 1 3 3 2 3 32 4 5 3 5 2 4 The next table displays the values of MTREE(m) for different values of m. As you can see in this case the value of MTREE(m) when m = 10 is 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 original distance matrix. 33 Dis tance_Mat r i x 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 the edges of the MST. Th is l i s t i s genera u s i n g P r i m ' s A l g o r i t h m . MST = 3 2 4 1 5 3 3 4 Th is l e n g t h i s the exact l e n g t h of the MST generated by P r i m ' A l g o r i t h m . MSTree_length = 6 34 C h a p t e r 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 Aik{m) = 1 and Ajk{in) = 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, Net-works, 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 Devel-opments 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 Self-Organizing Exploratory Pattern of the Argentine ant, Journal of Insect Behav-ior, 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 Jour-nal 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 Con-struction, 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 Determi-nants, 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 A p p e n d i x 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 Fi le Ed i t Help AntCol Steiner - P a r a m e t e r s ^ — A l p h a s ' ' 15.0 B a t a = / j 1.0 Q•='•• . lioo L R ! i o = G a m m a = M A X L O O P = 0.1 1 r - l npu ts — G r i d L e n g t h ( H K # o f T e r m i n a l s ( M ) ; . D e f a u l t (N .= -25 ) D e f a u l t ( M = 9) r O i i t p u t s — — T o t a l ' . t i m e = Tree Length = m i l l s e c o n d s u n i t s S t a r t Figure A. l : The Graphical User Interface of the AntCol Steiner Program. 41 »••' O • % • 0 * S - i * AntCol Steiner -Parameters Alpha • Bata = W w -Gail»IM -MAXLOOP -Of Ml Length (NS p o f ! es mtnats (M) Default m • 25) M a m IM - 9) Total Time • Tree Lenutti -nmaendi i units j This i s che Ste iner Tree Before Pruning ;The Steiner Tree length Is: 40 |The execution time M i l 484 m i l l i s e c o n d s . Figure A.2: This Screen show the Steiner Tree before and after Pruning. The pre-pruned 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 Grid Finished Fxecutton S a v e ) Print C l o s e 1 x - o - o - o ••• 0 - D - o -i l l ! o - o - o - o j • 1 - 0 • o " 0 1 1 - 0 - o - X - o - o - - " o \ i 1 j 1 1 - 0 o - O ~ O '" o - o - x - o - o -1 ! 1 o - o - o 1 i 1 • o • O - B _ 0 1 1 • : - o -1 o - - - o o •• o - • * o - o - o - • - x - o - o - o • o O 0 - o - o - o - o - -• - o - a -• o ~ o - o - o - a - o - • - o - X - X - 0 f 1 1 o 1 i • - -o - o • x - o - o -- o -- o - x - O " O • o 0 • - O - X 0 - o - o - -o o - o .. j 1 1 o o o o o - O X o * 0 0 o 1 1 • o o • o • o • -a - o - x • • - o - a - o •-• • • o - o - o 0 o • o • o o - o - o " o -o - o - o [ • - -0 o - x - o - • " o - o o - o o - o 0 X ' • - o - n -0 - o - o - -j o - o o ••• o - o - 0 o o -o - 0 " 0 0 0 ~ 0 • o 0 ... 0 ... o •• -0 - X - o -] j ; j O - X - O Q ' o ~ o •• o •• • X x - 0 - o 0 o - Q - -o - o - o 0 ~ 0 " o • O ' o - 0 - Q - O 0 O 0 - 0 0 x - o - -o - o -• • - o - o - o • o • o o x x • o o o • ... 0 „ 0 i o - o - o - 0 - 0 O ' X ' Q •• o 0 ' 0 0 " o • Q .. 0 u •• O o - -o •- x - o - o - o - b - o " 0 - x - o • 0 • - o • X ... Q X ... Q ... • - -) \ O - Q - x - o - o - o - o - o ~ o ~ o - o o - o - o • - O " x - -O ~ O " U o - x ••• x •••• 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_ IrputUljav while(coun file Edit Help MCo/ Sfemer Parameters-|Bata = 1.0 |»| Ciamma = 1 1000 !»| MMOOP=M GndLengiKH) 2 of lermiMls (M) =; Delat* (N-251 MaiHiM 9| vjuiiiuia Total lime • IteelenjIM 14016 mtlsecoiuls i s : m«s The Steiner Tree length is: 162 The execution time was: 14016 miliseconds, x - o I I 0 o-o-x-x-o-o-o-x-o 1 I I I o - o - X I o-o-o I o-o-o-o x - x - 0 I x - X I x - o - 0 I 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. Remark A.0.1 The solution presented in figure A.4 is not an optimal solution. 11 A p p e n d i x B Source Code for InputUI.java Remark 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 in figure A.l. This class does not contain any ACO algorithm properties. package An t S t e i n e r . u i ; import j avax.swing.*; import AntSteiner.*; import j ava.awt.*; import java.awt.event.*; /** * D e s c r i p t i o n : This c l a s s handles a l l of the imput GUI s t u f f . * C l a s s : InputUI.j ava * ©author Anthony Blackman * ©version A p r i l 10, 2006 */ p u b l i c c l a s s InputUI extends JFrame implements Actio n L i s t e n e r { 45 /**This v a r i a b l e was used as a reference to the AntCol c l a s s * / p r i v a t e s t a t i c AntCol ac; /**This v a r i a b l e was used to store the number of terminals generated*/ p r i v a t e s t a t i c J T e x t F i e l d M; /**This v a r i a b l e was used to store the dimension of the generated*/ p r i v a t e s t a t i c J T e x t F i e l d N; /**This v a r i a b l e was used to store M and N*/ p r i v a t e s t a t i c i n t [] gridLTermN; /**This i s a reference to the J T e x t F i e l d * / p r i v a t e s t a t i c J T e x t F i e l d timeTaken; /**This i s a reference to the J T e x t F i e l d * / p r i v a t e s t a t i c J T e x t F i e l d steinerLength; /**This i s a reference to the JLabel*/ p r i v a t e JLabel defaultN; /**This i s a reference to the JLabel*/ . 46 p r i v a t e J L a b e l defaultM; /**This i s a reference t o the S t a r t button*/ p r i v a t e JButton run; /**This i s a reference t o the JComboBox*/ p r i v a t e s t a t i c JComboBox alphaBox; /**This i s a re f e r e n c e t o the JComboBox*/ p r i v a t e s t a t i c JComboBox bataBox; /**This i s a reference t o the JComboBox*/ p r i v a t e s t a t i c JComboBox rhoBox; /**This i s a reference t o the JComboBox*/ p r i v a t e s t a t i c JComboBox maxloopBox; /**This i s a reference t o the JComboBox*/ p r i v a t e s t a t i c JComboBox gammaBox; /**Tnis i s a re f e r e n c e t o the 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 ui; /**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 edit 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 clear menu item under the Edit menu. JMenuItem clear = new JMenuItemC'Clear", KeyEvent.VK_C); editMenu.add(clear); //This creates a default menu item under the Edit menu. JMenuItem defaultSettings = new JMenuItem("Default Settings", KeyEvent.VK_D); editMenu.add(defaultSettings); //This creates an exit mnemonic under the exit menu item i n the f i l e menu. JMenuItem exit = new JMenuItem("Exit".KeyEvent.VK_X); fileMenu.add(exit); 49 //This creates an instruction 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 also allow the about dialog box to pop up //when the F3 key i s pressed. about.setAccelerator(Keystroke.getKeyStroke(KeyEvent.VK_F3, 0, f a l s e ) ) ; //This i s the action l i s t e n e r that pops up the dialog box //and ex i t when the exit button i s pressed, exit.addActionListener(new ActionListener() { public 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 action l i s t e n e r that pops up the about //dialog box and displays the about information 50 / /when the about menu bu t ton i s p ressed , abou t . addAc t ionL i s t ene r (new A c t i o n L i s t e n e r ( ) { p u b l i c v o i d ac t ionPer fo rmed(Act ionEven t e) { JOptionPane aboutFrame = new JOpt ionPane( ) ; 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 \nBy Anthony Blackman" , "About A n t C o l S t e i n e r " , JOptionPane.INF0RMATI0N_MESSAGE); } }) ; / / T h i s c l e a r s a l l t e x t f i e l d s , c l e a r . a d d A c t i o n L i s t e n e r ( n e w A c t i o n L i s t e n e r ( ) { p u b l i c v o i d ac t ionPer fo rmed(Act ionEven t e) { N . s e t T e x t ( " " ) ; M . s e t T e x t ( " " ) ; t i m e T a k e n . s e t T e x t ( " " ) ; s t e i n e r L e n g t h . s e t T e x t ( " " ) ; > » ; / / T h i s c l e a r s a l l t e x t f i e l d s . d e f a u l t S e t t i n g s . a d d A c t i o n L i s t e n e r ( n e w A c t i o n L i s t e n e r ( ) { p u b l i c v o i d ac t ionPer fo rmed(Act ionEven t e) { a l p h a B o x . s e t S e l e c t e d I n d e x ( 4 ) ; b a t a B o x . s e t S e l e c t e d l n d e x ( O ) ; r h o B o x . s e t S e l e c t e d l n d e x ( l ) ; max loopBox . se tSe lec t ed !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 is pressed, defaultSettings.setAccelerator(Keystroke.getKeyStroke (KeyEvent.VK_F2, 0, false)); //This displays the help manual when Fl i s pressed. programHelp.setAccelerator(Keystroke.getKeyStroke (KeyEvent!VK_F1, 0, false)); //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 Steiner Help"); JPanel textPanel = new JPaneK); JLabel textTitle = new JLabelO'Help Manual"); textPanel.setLayout(new BorderLayout()); JTextArea ta = new JTextAreaO; ta.setText("\nFirst select the parameter values from the parameter panel.\n" + "The default values are recommended for the best performance. Then\n" + "click the Start button and the program w i l l run with the currently \n" + "selected parameter values and the grid size and terminal number unless\n" + "otherwise specified. The default grid size and terminal numbers are N = 25\n" + 52 "and M = 9 respectively. This values produces a N x N (25 x 25) grid \n" + "with M = 9 terminals. The user can also,enter their preferred values \n" + "of N and M. However, the Value of M enter must always be less 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 helpScroll = new JScrollPane (ta,ScrollPaneConstants.VERTICAL_SCROLLBAR_ALWAYS, ScrollPaneConstants.H0RIZ0NTAL_SCR0LLBAR_ALWAYS ); //just getting a l i t t l e fancy... Font font = new 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, 10, 0, 10)); //Add TextTitle and HelpScroll to TextPanel. textPanel.add(textTitle, BorderLayout.NORTH); textPanel.add(helpScroll, BorderLayout.CENTER); //Add TextTitle to the Frame. textFrame.add(textPanel, BorderLayout.CENTER); textFrame.setSize(330,330); textFrame.setLocationRelativeTo(null); textFrame.setVisible(true); 53 } // 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, 10, 0, 10)); // create the course t i t l e bar title.add(programTitle, BorderLayout.CENTER); JPanel constantsPanel = new JPanelO; constantsPanel.setLayout(new GridLayout(3,5)); JLabel alpha = new JLabel("Alpha = "); JLabel rho = new JLabel ("Rho = "); JLabel bata = new JLabel ("Bata = "); 54 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" }; String [] bataValues = {"1.0","2.0","3.0","4.0","5.0" >; String [] gammaValues = {"1","2","3","4","5" >; String [] maxloopValues = {"1","2","3","4","5","6","7","8", "9","10","20", "30", "40", "50" >; String [] 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), "Parameters")); 56 JPanel maihPanel = new JPaneK); JPanel inputPanel = new JPaneK); JPanel outputPanel = 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 JLabel ("Grid Length (N) " ) ; N = new JTextField (15); defaultN = new JLabel(" Default (N = 25)"); defaultM = new JLabel (" Default (M = 9)"); JLabel terminalNum = new JLabel ("# of Terminals (M)" M = new JTextField (15); JLabel time = new JLabel ("Total Time = " ) ; timeTaken = new JTextField (10); JLabel length = new JLabelC'Tree Length = "); steinerLength = new JTextField (10); JLabel ms = new JLabeK" millseconds"); JLabel units = new JLabel (" units"); inputPanel.add(gridSize); inputPanel.add(N); inputPanel.add(defaultN); inputPanel.add(terminalNum); 57 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), "Outputs")) JPanel iOPanel = new JPanelO; iOPanel.setLayout(new 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.add(title, BorderLayout.NORTH); f.add(mainPanel, BorderLayout.CENTER); 58 f.add(buttonPanel, BorderLayout.SOUTH); f.setSize(380,380); f.setResizable(false); f.setVisible(true); //f.setLocationRelativeTo(null); //This puts the AntCol Steiner screen in the center, f.setDefaultCloseOperation(JFrame.EXIT_0N_CL0SE); return gridLTermN; y /** •Description: This methods looks for the run button *to be clicked and creates a seperate thread *for the execution of the program. */ public void actionPerformed(ActionEvent e) { Steiner s = new SteinerO; Thread runAnt = new Thread(s'); runAnt.start(); > /** * Description: This methods extracts the information * from the text fields i f values were entered * else the method would create default values * to be used with in the program. */ public static void extract(M ac = new AntCol(); ac.setTook(O); try { gridLTermN [0] = Integer.parselnt(N.getText0); //This converts the string from the Text Field //into an integer. gridLTermN [1] = Integer.parseInt(M.getText()); //This converts the string from the Text Field //into 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] = (String)maxloopBox.getSelectedltemO parameters[4] = (String)gammaBox.getSelectedltemO; parameters [5] = (String)qBox.getSelectedltemO; ac.test(gridLTermN [0], gridLTermN [1]); timeTaken.setText(ac.getTook() + " " ) ; steinerLength.setText(ac.getBestSlength() + " " ) ; /** Oparam args 60 */ public static void main(String[] args) { // TODO Auto-generated method stub ui = new InputUI(); ui.run.addActionListener(ui); > } /** * This class implements the Runnable Interface. This makes * the stuff in 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 A p p e n d i x C Source Code for AntCol.java package AntSteiner; import AntSteiner.util.*; import AntSteiner.ui.*; /** * Class: AntCol.java * ©author Anthony Blackman * ©version April 10, 2006 */ public class AntCol { /**This data structure store the l i s t of the terminals * in the Hanan's Grid*/ private int [] [] terminals; /**This data structure was used to store the Hanan's grid.*/ private String [] [] grid; /**This data sturture was used to store the current Steiner 62 tree.*/ private String [] [] steinerTree; /**This data sturture was used to store the best Steiner tree.*/ private String [][] bestSteinerTree; /**This data sturture was used to store intensity levels of the * edges of the Hanan's Grid.*/ private double [][] intensity; /**This variable was used to store the number of iterations of the system.*/ private int maxLoop; /**This variable was used to store the quality of the t r a i l * / private int Q; /**This variable was used to store the length of the current steiner tree.*/ private int sLength = 0; /**This variable was used to store the length of the best steiner tree*/ private int bestSlength = 0; 63 /**This variable was used to determine whether or not * a better Steiner tree was found*/ private int indicate; /**This variable was used to record the start time.*/ private long start; /**This variable was used to record the fi n i s h time.*/ private long end; /**This variable was used to record the time taken to execute the program*/ private long took; /**This variable was used to determine the levels 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 to the Hanan Grid.*/ private HananGrid hg; 64 /**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.*/ private int [] gridLimits; public AntCol(){ } public void test(int n, int m){ rho = Double.parseDouble(InputUI.parameters [2]); maxLoop = Integer.parselnt(InputUI.parameters[3]); Q = Integer.parselnt(InputUI.parameters[5]); int count =0; // This is the number of loops. double pheromone = 1000; gridLimits = new int [4]; steinerTree = new String[n][n]; bestSteinerTree = new String [n] [n]; grid = new String[n][n]; 65 intensity = new double[n][n]; • terminals = new int [m][2]; hg = new HananGridO; tree = new TreeConstructO; d = new Display(); start = System.currentTimeMillisO; // Start the clock. grid = hg.gridGenerator(n, m, gridLimits); //This generates the Hanan grid. intensity = hg.initial_intensity(grid, pheromone); //This array contains the t r a i l intensity, terminals = hg.getPointsO ; // This array contains the terminal points. //This is the f i r s t steiner tree i t w i l l be used as //a test standard to compare the other trees. bestSteinerTree = tree.constructSteinerTreeByACO (terminals, grid, intensity, gridLimits); bestSlength = tree.getTLengthO; // Here at the other steiner trees, while (count < maxLoopH //These loops updates the t r a i l intensity for a l l of the paths that where crossed. for(int row = 0; row < steinerTree.length; row++){ 66 for(int col = 0; col < steinerTree.length; col++) { if(bestSteinerTree[row][col]== "*" II bestSteinerTree[row][col]== "a" //This increases the level of pheromones. intensity [row] [col] = updatelntensity(sLength, row, col, intensity); //This updates the edges //which have been crossed. > else { intensity[row] [col] = ((double)1 - rho)*intensity[row][col]; > } steinerTree = tree.constructSteinerTreeByACO(terminals, grid, intensity, gridLimits); sLength = tree .getTLengthO ; //This indicates i f the firstSlength is less than sLength. / / i f indicate = 1 firstSlength is shorter than sLength. / / i f indicate = 0 firstSlength is longer //than sLength. If indicate = -1 the test failed, indicate = chooseBestSoKbestSlength, sLength); //If the bestSteinerTree is longer we copy the better tree / / ( i e . steinerTree) into the bestSteinerTree. Then get i t s length, if(indicate == 0){ 67 for(int row = 0; row < steinerTree.length; row++){ for(int col = 0; col < 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 dist } else i f (indicate == -1) i System.out.println("The comparsion test failed!"); } count++; // This increments the MAXL00P } // This i s the end of the MAXL00P. end = System.currentTimeMillis(); //Stop the clock took = end - start; // Elapsed time. d.displayTree(bestSteinerTree, grid, 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 is the bigger, i f indicate = 1 * firstSlength is shorter than sLength. i f indicate = 0 firstSlength i s longer * than sLength. If indicate = -1 the test failed. * * ©param bestSlength The shortes steiner tree that was generated. * ©param sLength The current steiner tree which was just generated. * ©return indicator This was used to indicate whether or not * the current steiner tree * is better than the current best steiner tree. */ public int chooseBestSoKint bestSlength, int sLength){ int indicator = -1; if(bestSlength < sLength){ indicator = 1; } else { indicator = 0; > return indicator; > /** * Description: This method was used to update the t r a i l intensity. * ©param sLength This is the length of the steiner tree. * ©param row This is a x coorinate of a point on the steiner tree. * ©param col This is a y coorinate of a point on the steiner tree 69 * Qparam intensity This is the intensity matrix. * ©return intensityValiie This the value of the intensity at * that point on the t r a i l . * * */ public double updatelntensity(int sLength, int row, int col, double [] [] intensity) { double intensityValue = 0.0; double delta_tau; i f (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 intensity. return intensityValue; } /** * ©return Returns the intensity. */ public double [][] getlntensityO { 70 return intensity; } /** * ©param intensity The intensity to set. */ public void setIntensity(double[][] intensity) { this.intensity = intensity; } /** * ©return Returns the bestSlength'. */ public int getBestSlengthO { return bestSlength; } /** * ©return Returns the took. */ public long getTookO { return took; } /** * ©param took The took to set. */ public void setTook(long took) { 71 t h i s . t o o k = took; A p p e n d i x D Source Code for HananGrid.java package AntSteiner.util; import java.util.*; import AntSteiner.ui.*; /** * Class: HananGrid.java * ©author Anthony Blackman * ©version April 10, 2006 */ public class HananGrid { /**This data structure was used to store the Hanan's Grid*/ private String [] [] grid; /**This data structure was used to store the t r a i l intensities.*/ private double [][] intensity; /**This reference was used to access the input user interface.*/ 73 private Display d; /**This data structure was used to store the points terminals of the system.*/ private int [] [] points; /**This variable was used to store the x coordinate of the Hanan's grid*/ private int x; /**This variable was used to store the y cooridinate of the Hanan's grid*/ private int y; /**This variable was.used to store the smallest x cooridinate of the Hanan's grid*/ private int xmin; /**This variable was used to store the largest x cooridinate of the Hanan's grid*/ private int xmax; /**This variable was used to store the smallest y cooridinate of the Hanan's grid*/ 74 private int ymin; /**This variable was used to store the largest y cooridinate of the Hanan's grid*/ private int ymax; /**This variable was used to store the reference to the random number generator*/ private 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 vertices. The "x" represents the terminal points * The "o" represents the possible steiner points. The "I" * and "-" represents the edges of the grid and the " " are places * that the ant cant walk * ©param n * ©return grid Which is a representation of the Hanan' Grid. */ 75 public String [][] gridGenerator(int n, int m, int [] gridLimits){ grid = new String [n][n]; //Size of the grid i s n by n. points = new int[m] [2]; d = new Display(); ran = new RandomO; // Creates a new random number generator. for (int i = 0; i < grid.length; i++) { for(int j = 0; j < grid.length; j++H grid[i] [j] = " "; // I n i t i l i z e the grid array with blank spaces. > > for (int 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 i f (x < g r i d . l e n g t h kk y < grid.length){ f o r ( i n t k = 0; k < grid.l e n g t h ; k++){ i f (grid[x] [k]== " I " I I grid[x][k]== "o" H gri d [ x ] [ k ] = "o"; } else { grid[x] [k]= "-"; > 76 i f (grid[k] [y]== "-" I I grid[k][y]== "o" H grid[k][y] = "o"; } else { grid[k][y] = "I"; > } points[i] [0] = x; // This stores the x points points[i][l] = y; //This stores the y points. } else i i — ; > } //This for loop was used to look for the point just generated and plac //an X at the point. for (int i = 0; i < points.length; i++) { grid[points[i] [0]] [points[i][1]]= "x"; > xmin = grid.length; ymin = grid.length; for(int s = 0; s < points.length; s++){ if(points [s] [0] <= xmin ) { 77 xmin = points [s] [0]; // This find the lowest x point > if(points [s][1] <= ymin ) { ymin = points[s] [1];// This find the lowest y point. > i f (xmax <= points [s] [0] ) { xmax: = points[s] [0];// This find the highest x point } if(ymax <= points[s] [1] ) { ymax = points [s] [1]; // This find the higest y point } } //Trims off excess grid from the top. i f (xmin > OH for(int k = 0; k < xmin; k++ H for (int i = 0; i < grid, length; i++H grid[k] [i]= " "; } . } > //This trim excess of the grid on the l e f t side, i f (ymin > OH for(int k = 0; k < ymin; k++ H for(int i = 0; i < grid.length; i++H grid[i] [k]= " "; > > > 78 //This trim excess of the grid from the right side, i f (ymax < grid.length){ for(int k = ymax + 1; k < grid.length; k++ ){ for(int i = 0; i < grid.length; i++){ gridfi] [k]= " "; > > } // Trims off excess grid from the bottom, i f (xmax < grid.length){ for(int k = xmax + 1; k < grid.length; k++ ){ for(int 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 grid; //This returns the Hanan's Grid. 79 } /** * Discription: The string [][] i s a copy of the Hanan grid, the double * parameter i s for the i n i t i a l intensity of the t r a i l and the double * array is a intensity matrix. If the there is an edge in the Hanan grid * then the intensity is set to the i n i t i a l _ i n t e n s i t y . If there is no edge * at position i , j in the Hanan grid then the intensity 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 intensity matrix. * * ©param grid * @param i n i t i a l _ i n t e n s i t y * ©return intensity * * */ public double [] [] initial_intensity(String [][] grid, 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 grid. intensity = new double [n] [n]-; for (int i = 0; i < intensity.length; i++){ for (int j = 0; j < intensity.length; j++H if(grid[i][j]== " "){ intensity[i][j]= 0.0; } else { 80 intensity[i] [j] = i n i t i a l _ i n t e n s i t y ; } } return intensity; } /** * ©return Returns the grid. */ public String [] [] getGridC) { return grid; y /** * ©param grid The grid to set. */ public void setGrid(String[] [] grid) { this.grid = grid; } /** * ©return Returns the points. */ public int[][] getPointsO { return points; } /** * ©param points The points to set. */ public int [] [] setPoints(int [] [] points) { this.points = points; 81 return points; y /** * ©return Returns the xmax */ public int getXmaxO { return xmax; } /** * ©return Returns the xmin */ public int getXminO { return xmin; > /** * ©return Returns the ymax */ public int getYmaxO { return ymax; > /** * ©return Returns the ymin */ public int getYminO { return ymin; } /** } A p p e n d i x E Source Code for TreeConstruct.java package AntSteiner.util; import java.util.*; import AntSteiner.*; /** * Class: TreeConstruct.java * ©author Anthony Blackman * ©version April 19th, 2006 */ public 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 after prunning*/ private int tLength = 0; /**This variable was used to store the number of vertices in the Steiner tree*/ 83 private int 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 int [] info; //**This data structure was used to store the relocation points of the •surviving ant.*/ //private int [] relocate; // This array stores the l i s t of ants in the colony, //private int [] [] relocationPoints; /**This data structure was used to store the mortality of the ants in the colony.*/ private int [] antID; /**This data sturcture was used to store the vertices and edges of the Steiner tree, private String [][] sTree; /**This data structure was used to store the aerial view of the ant system.*/ private int [] [] globalArray; /**This tool is used to access the methods in the ant class.*/ private Ant tool; /**This is an array of ants ie the ant colony.*/ private Ant [] colony; /**This variable was used to store the identification of the ant who was met * i f the current ant met an ant and i t stored -1 i f i t did not met any ants*/ private int id; /**This variable was used to indicate whether or not deconfusion had accorded*/ private int dCon; /**This variable was used to store the identification of the ant current ant.*/ private int m; /**This variable was used to store the number of ants s t i l l alive in the system.*/ private int ant_number = 0; /**This data structure was used to store the current cooridinates each ant was at 84 * during any instance of the program.*/ private int [] [] antPoints; /** * This i s the default constructor. */ public TreeConstruct(){ } /** * * @param terminals The terminals l i s t . * Oparam grid The Hanan's Grid * Oparam intensity The intensity matrix * Qreturn sTree The steiner tree. * */ public String [] [] constructSteinerTreeByACO (int [][]terminals, String [] [] grid, double [] [] intensity, int [] gridLimits){ int n = terminals.length; tool = new Ant(grid.length); relocate = new int [3]; antID = new int [n]; rand = new Random(); antPoints = new int [n] [2]; colony = new Ant[n]; for(int 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 in each ant and Visited // cites 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. for(int i = 0; i < terminals.length; i++){ forCirit j = 0; j < 2; j++){ antPoints[i] [j] = terminals[i][j]; } } // This loop was used to place an ant at there starting location. for(int i = 0; i < colony.length; i++){ tool = tool.placeAnt(tool, colony[i].terminals[i][0], terminals[i][1], i ) ; } ant_number = antID.length; for(int s = 0; s < antID.length; s++){ antID[s]= 1; //This one indicates weather an ant i s alive. When //an ant at position i dies then Then the i w i l l put a -1 / / i n position i to indicate the ant is dead. This //This would prevent me from choosing dead ants to move. } while (ant_number > 0) 86 { info = new int [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 live ant / / i s found. m = rand.nextInt(antID.length); //generates a random number between //0 and number of ants. > //Move an ant that is s t i l l alive. info = tool.AntMove(tool, colony[m].antPoints[m][0], antPoints[m] [1], m, grid, intensity, terminals, colony, antID, gridLimits); id = info[0]; // This id is used to indicate i f an ant met another ant or not. // -1 means did not meet an ant. dCon = info [3]; //Indicates whether or not there was a deconfusion. //I means NO! and -1 means YES! while (id == -1){ //Move an ant that is s t i l l alive. info = tool.AntMove(tool, colony[m],info[1], info[2], m, grid, intensity, terminals, colony, antID, gridLimits); id = info[0] ; dCon = info [3]; System.out.println("\nWork now!!" + " id: " + id + " m: " + m); i f (dCon == -1){ break; } } 87 int count =0; while(dCon == -1 && id != - 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 in his fabulist antPoints [id] [1] = info[2]; //This now puts the ant on a new in his tabulist //Move an ant that i s s t i l l alive. info = tool.AntMove(tool, colony[m],info[1], info[2], id, grid, intensity, terminals, colony, antID, gridLimits); dCon = info [3]; id = info[0] ; i f (count > terminals.length){ break; } System.out.printlnC'dCon is : " + dCon); } // This line says that i f the ant meets another ant // then he dies an copies his t r a i l into the anf. i f (id != -1){// id 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 is that ant that was k i l l e d //by ant id 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 System.out.println("\nAnt " + m + " met ant " + id); System.out.println("\nAnt " + m + " just died!\n"); // relocate = tool.relocate (colony[id], antPoints, grid); // antPoints [id] [0] = relocate [1]; //This now puts the ant //on a new in his tabulist // antPoints [id] [1] = relocate [2]; //This now puts the ant //on a new in his tabulist // id = relocate[0]; ant_number—; //System.out.println(id + " " + ant_number); > } globalArray = new int [grid.length][grid.length]; globalArray = tool.getGlobalViewO; sTree = new String [grid.length][grid.length] ; for(int j = 0; j < sTree.length; j++){ for (int i = 0; i < sTree.length; i++){ sTree[j] [i] = " "; } } for(int i = 0; i < grid.length; i++){ System.out.print("\n"); for (int j = 0; j < grid.length; j++M 89 i f (globalArray[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") for(int i = 0;'i < grid.length; i++H System.out.print("\n"); for (int j = 0; j < grid.length; j++M i f (globalArray[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, grid, gridLimits); //This method was used to remove a l l //leaves that were not terminals. tLength = 0; tPoints =0; 90 for (int j = 0; j < sTree. length; j++M for (int i = 0; i < sTree.length; i++){ if(sTreeLj] [i] == "*"){ tLength++; > i f (sTreeHj] [i] == "*" && (grid[j][i]== "o" II grid[j] [i] == "x")){ tPoints++; } } > tLength = tLength - tPoints; //This is the length of the tree formed. //System.out.println("\nThe length after 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 grid The Hanan's grid •Oparam gridLimits This array contains the values of the extremes of the •Hanan's grid *@return sTree The steiner tree with out non terminals leaves. */ public String [] [] pRune (String [] [] sTree, String [] [] grid, int [] gridLimits){ 91 /* gridLimits [0] = xmax This i s the value of the last row of the Hanan's grid. gridLimits[1] = ymax This is the value of the last column of the Hanan's grid. gridLimits[2] = xmin This is the value of the f i r s t row of the Hanan's grid. gridLimits[3] = ymin This is the value of the f i r s t column of the Hanan's grid. */ int n = sTree.length * sTree.length; for(int loops = 0; loops < n; loops++) { for(int row = gridLimits[2]; row <= gridLimits[0]; row++){ for(int col = gridLimits [3] ; col <= gridLimits [1] ; col++)-[ int degree =0; if((grid[row] [col] == "o" II grid[row][col] == "-"II grid [row] [col] == "I" ) && sTree[row][col] == "*"){ //This i s for the top l e f t had corner. i f (row == gridLimits [2] && col == gridLimits [3]){ i f (sTree[gridLimits[2]][gridLimits[3]+ 1]!= " "){ degree++; } i f (sTree [gridLimits [2] +1] [gridLimits [3]] != " "H degree++; > > //This is for the botton right had corner, else i f (row == gridLimits[0] && col == gridLimits [1] ){ i f (sTree[gridLimits[0]] [gridLimits[1] - 1]!= " "){ degree++; 92 } i f (sTree[gridLimits[0] - 1] [gridLimits[1] ] != " " H degree++; > } //This i s for the botton l e f t hand corner, else i f (row == gridLimits[0] && col == gridLimits[3] ){ i f (sTree[gridLimits[0] - 1][gridLimits[3]]!= " "){ degree++; > i f (sTree [gridLimits[0]][gridLimits[3]+ 1]!= " "){ degree++; } > //This is for the top right hand corner, else i f (row == gridLimits[2] kk col == gridLimits [1] ){ i f (sTree[gridLimits[2] + 1][gridLimits[1]]!= " "){ degree++; } i f (sTree[gridLimits[2]][gridLimits[1] - 1]!= " "){ degree++; } > //This i s for the center of row 0. else i f (row == gridLimits[2] && col <= gridLimits [1] ){ 93 i f (sTree[gridLimits[2]][col - 1]!= " "){ degree++; } i f (sTree[gridLimits[2]][col + 1]!= " "){ degree++; } i f (sTree[gridLimits[2] + 1][col]!= " "){ degree++; } //This i s for the center of row sTree.length - 1. else i f (row == gridLimits[0] kk col <= gridLimits[1] ){ i f (sTree[gridLimits [0]] [col - 1]!= " "){ degree++; } i f (sTree[gridLimits[0]] [col + 1]!= " "){ degree++; } i f (sTree[gridLimits[0] - 1][col]!= " "){ degree++; } } //This is for the center of column 0. else i f (row <= gridLimits[0] && col == gridLimits[3] ){ i f (sTree[row - 1][gridLimits[3]]!= " "){ degree++; ' , 94 } i f (sTree[row + 1][gridLimits[3]]!= " "){ degree++; > i f (sTree[row] [gridLimits[3] + 1]!= " "){ degree++; > } //This i s for the center of column sTree.length - 1. else i f (row >= gridLimits[2] && col == gridLimits [1] i f (sTree[row - l][col]!= " "){ degree++; > i f (sTree[row + l][col]!= " "M degree++; } i f (sTree [row] [gridLimits [1] - 1] != " "){ degree++; } } //This i s for the center of the grid else i f (row >= gridLimits[2] && col <= gridLimits[1] && col >= gridLimits [3]){ i f (sTree[row - 1] [col]!= " "){ degree++; > 95 i f (sTreeLrow + 1] [col] != " "){ degree++; } i f (sTree[row] [col - 1]!= " "){ degree++; > i f (sTreeLrow] [col + 1]!= " "){ degree++; } } //If the degree of the node is 1 put a space. //System.out.println("The degree i s : " + degree + " row: " +row+ " col: "+col) i f (degree == 1){ //System.out.printlnC'The degree i s : " + degree); sTree [row] [col] = " "; } } > } return sTree; } /** * Oreturn Returns the tLength. 96 */ public int getTLengthO { return tLength; } /** * ©param length The tLength to set. */ public void setTLength(int length) •{ tLength = length; > /** * ©return Returns the id. */ public int getldO { return id; > /** * ©param id The id to set. */ public void setld(int id) { th i s . i d = id; } }7/End the class 97 A p p e n d i x F Source Code for Ant .Java package AntSteiner; import AntSteiner.util.*;, import java.lang.Math; import java.util.*; /** * Class: Ant.Java * Oauthor Anthony Blackman * Oversion April 10, 2006 */ public class Ant { /exposition represents the x coordinate of the vertex*/ private int xposition; /**xposition represents the y coordinate of the vertex*/ 9 8 private int 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 String [] [] tour; /**This stores the l i s t of terminals visited by the ant.*/ private int [] visited; /**This stores the l i s t of a l l the vertices in the Hanan's Grid*/ private int [] [] starList; /**This stores the l i s t of a l l the Steiner points in the Hanan's Grid*/ private int [][] steinerList; /**This stores the probabilities the ant would go in the four different directions*/ private double [] probability; 99 /**This is a reference to the U t i l i t i e s class*/ private U t i l i t i e s u T i l ; /**This was used to mark steps of the ants*/ private int step = 0; /**This return information related to the ants interaction at a vertex.*/ private int [] alabel; /**This return the cooridinates where the ant was deconfused and * whether i t i s s t i l l confused*/ private int [] confuse; /**This return the cooridinates where the ant was relocated*/ private int [] relocate; /**This i s a reference to a random variable*/ private Random random; /**This is the data structure used to store the a r i a l view of the ant system.*/ 100 private int [][] globalView; /** * This is the default constructor. **/ public Ant (int m){ uTil = new U t i l i t i e s ( ) ; globalView = new int [m][m]; //This array w i l l contain a global view //of the system, for (int i = 0; i < globalView.length; for(int j = 0; j < globalView.length; j++){ globalView[i][j] = -1; > } } /** * Discription: This i s the over ridden constructor. The copies the Hanan Grid * into the Ant Tour so that the ant would walk on his copy of the grid. This * would allow me to get the path of any ant. That way I can print the path of * the late surviving ant's tour which would be the Steiner Tree for * that iteration. * * Oparam n This i s the number of ci t i e s or number of ants * Oparam m This i s the size of the grid. * */ public Ant (int n, int mM 101 tour_length = 0.0; tour = new String [m][m]; visited = new int [n] ; for (int i = 0; i < tour.length; !++)•[ for(int j = 0; j < tour.length; j++){ tour[i] [j]= " "; > for(int j = 0; j < visited.length; j++H visited[j]= 0; //0 represents unvisited terminals and 1 represents //visited terminals. } ** * Discription: This method was design to place an ant m to the starting * position of his Hanan's Grid. How ever this placement would be in his * tabu l i s t . ie. This tour. * Oparam xposition This i s the x cooridnate where the ant w i l l be placed. * Oparam yposition This is the y cooridnate where the ant w i l l be placed. * Oparam i this indicates which city got the ant. * Opararn tool 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 gird. * Oreturn This returns the reference to an ant. */ 102 public Ant placeAnt (Ant tool, Ant m, int xposition, int yposition, int i){ this.xposition = xposition; this.yposition = yposition; • m.tour[xposition][yposition]= "a"; //this is the tour for ant m. tool.globalView[xposition][yposition]= i ; m.setCity(i); return tool; > * Discription: This method move an ant to an new position j based on the desir a b i l i t y and t r a i l intensity to move to j . This method moves one postition at a t ime. @param xposition This is the x cooridnate where the ant w i l l be placed. Oparam yposition 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 is the ant number m that was place at the point (x,y) of the Hanan's gird. Oparam tool This is a reference to the ant system. Oparam grid This the Hanan's grid. @param intensity This is the intensity matrix or intensity t r a i l of the system. Oparam terminals This.is the terminal l i s t of the system. ©return alabel This i s an array which indicates which vertex the ant move to and what type of vertex was i t . / 103 public int [] AntMove(Ant tool, Ant m, int xposition, int yposition, int antIndex, String[] [] grid, double [] [] intensity, int [] [] terminals, Ant [] colony, int [] antID, int[] gridLimits){ int n = grid.length; int xPlus = xposition + 1; int yPlus = yposition + 1; int xMinus = xposition - 1; int yMinus = yposition - 1; random = new Random(); probability = new double [4]; alabel = new int [4]; //This looks ahead in the same column for the next vertex. while(xPlus < grid.length && grid [xPlus] [yposition] == "|")-[ xPlus++; } // This looks back in the same column for the next vertex, while(xMinus >= 0 kk grid [xMinus][yposition] == xMinus—; > // This looks ahead in the same row for the next vertex. while(yPlus < grid.length kk grid [xposition][yPlus] == "-"){ yPlus++; > // This looks back in the same row for the next vertex. 104 whileCyMinus >= 0 && grid [xposition][yMinus] == "-"){ yMinus—; > for (int k = 0; k < probability.length; k++){ probability[k] = -1.0; // Some invalid probability number. > //These i f ' s assign the probablility of going in the four different paths / / i f available. if(xPlus < grid.length){//This makes sure that the ant does not run //off the grid, if(m.tour[xPlus][yposition] != " " I I tool.globalView[xPlus] [yposition] == antlndex){ probability[0] =0.0; / / i f visited probability equals 0.0. > else -C ' probability[0] = uTil.selectionProMxPlus, yposition, intensity, m, n, terminals, grid, colony, antID); > } if(xMinus >= 0){//This makes sure that the ant does not run off the grid, if(m.tour[xMinus][yposition]!= " " 105 II tool.globalView[xMinus][yposition] == antIndex){ probability[1]= 0.0; } else { probability[1] = uTil.selectionProb(xMinus, yposition, intensity, n, terminals,grid, colony, antID); } > if(yPlus < grid.length){//This makes sure that the ant does not run off the grid, if(m.tour[xposition][yPlus]!= " " I I tool.globalView [xposition] [yPlus] == antlndex){ probability [2]= 0.0; > else { probability[2] = uTil.selectionProb(xposition, yPlus, intensity, m, n, terminals, grid, colony, antID); } } if(yMinus >= 0){//This makes sure that the ant //does not run off the grid. if(m.tour[xposition][yMinus] != " " II tool.globalView [xposition] [yMinus] == antlndex){ 106 probability[3]= 0.0; } else { probability[3] = uTil.selectionProb(xposition, yMinus, intensity, m, n, terminals, grid, colony, antID); > > i f (probability[0] < 0.0){ probability[0] = 0.0; } i f (probability[1] < 0.0H probability[1] = 0.0; > i f (probability[2] < 0.0){ probability[2] =0.0; > i f (probability[3] < 0.0){ probability[3] =0.0; ' ' } double sum_probability = probability[0] + probability[1] + probability[2]+ probability[3] ; //this is the total. 107 This section takes care of the case when the ant gets confuse, i f (sum_probability == 0.0) { alabel = deconfuse(m,terminals, grid, 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 { probability [0] = probability[0]/ sum_probability; probability [1] = probability[1]/ sum_probability; probability [2] = probability[2]/ sum_probability; probability[3] = probability[3]/ sum_probability; //This loop finds the maximum probability, max = -1.0; int p = 0; while(p < 4){ i f (max < probability [p]){ max = probability[p]; p++; > else{ p++; } 108 > int choice = random.nextlnt(4); //This generates a random number //between 0 and 4 not including 4. while (probability [choice] != maxH choice = random.nextlnt(4); > //System.out.print("\n\npO= " + probability[0]+ " pl= " + probability[1]+ " p2= "+ "probability[2]+ " p3= " + probability [3]); //These i f s move in the direction of the maximum probability / / u n t i l u hit 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++; } i f (grid[step][yposition]== "o" && tool.globalView[step][yposition] m.tour[step] [yposition] = "*"; tool.globalView [step] [yposition] = antlndex; alabel[0]= -1; alabel[l] = step; alabel[2] = yposition; }// At this point we have to find out which ant's t r a i l we just met else if(grid[step] [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, alabel[0]); } // At this point we have to find 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); alabel[1] = step; alabel[2] = yposition; tool.globalView = updateGlobalView(tool.globalView, antlndex, alabel[0]); > //System.out.println("\n\nThe maximum [0] i s : " + max); alabel[3]= 1; //Did not have a deconfuse. > else if(choice == 1){ step = xposition - 1; while (grid[step] [yposition]== "|" && (step >= 0)){ m.tour[step] [yposition]= "*"; 110 tool.globalView [step] [yposition]= antlndex; step—; } i f (grid[step][yposition]== "o" kk tool.globalView[step][yposition] == -1){ m.tour [step] [yposition] = "*"; tool.globalView[step][yposition]= antlndex; alabel[0]= -1; alabel[l] = step; alabel[2] = yposition; >// At this point we have to find out which ant's t r a i l we just met. else if(grid[step] [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; alabel[l] = step; alabel[2] = yposition; tool.globalView = updateGlobalView(tool.globalView, antlndex, alabel[0]); > // At this point we have to find 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, alabel[0]); } //System.out.println("\n\nThe maximum [1] i s : " + max); alabel[3]= 1; //Did not have a deconfuse. } else if(choice == 2){ step = yposition + 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] == -1) m.tour[xposition][step] = "*"; tool.globalView [xposition] [step]= antlndex; alabel [0]= -1; alabel [1] = xposition; alabel[2] = step; }// At this point we have to find out which ant's t r a i l we just met. else if(grid[xposition][step]== "o" kk tool. globalView [xposition] [step] != -1){ m.tour [xposition] [step] = "*"; alabel [0] = tool.globalView[xposition][step]; 112 tool.globalView = mergeTours(tool.globalView, m.tour, antlndex); tool.globalView [xposition] [step]= antlndex; alabel[l] = xposition; alabel[2] = step; tool.globalView = updateGlobalView(tool.globalView, antlndex, alabel[0]); > // At this point we have to find 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, m.tour, antlndex); //alabel[0] = getTheAnt(xposition, step, terminals); alabel[l] = xposition; alabel[2] = step; tool.globalView = updateGlobalView(tool.globalView, antlndex, alabel[0]); } //System.out.printlnC\n\nThe maximum [2] i s : " + max); alabel [3]= 1; //Did not have a deconfuse. } else if(choice == 3){ step = yposition - 1; while (grid[xposition][step]== "-" && (step >= 0)){ m.tour[xposition] [step] = "*"; tool.globalView [xposition][step]= antlndex; step—; > 113 if(grid[xposition] [step]== "o" && tool.globalView[xposition][step] == -1){ m.tour[xposition] [step] = "*"; tool.globalView[xposition] [step]= antlndex; alabel[0]= -1; alabel[l] = xposition; alabel[2] = step; } // At this point we have to find 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; alabel[l] = xposition; alabel[2] = step; tool.globalView = updateGlobalView(tool.globalView, antlndex, alabel[0]); // At this point we have to find 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, m.tour, antlndex); //alabel[0] = getTheAnt(xposition, step, terminals); alabel[l] = xposition; alabel[2] = step; tool.globalView = updateGlobalView(tool.globalView, antlndex, alabel[0]); } 114 //System.out.println("\n\nThe maximum [3] i s : " + max); alabel[3]= 1; //Did not have a deconfuse. > m.setCity(antlndex); > //This is for the else above, return alabel; > /** * Description: This methods was used to update the Global view of the system. * It replaced the tracks of the old or dead ant with the tracks for the new ant. * Oparam globalView This is the globalView array * Oparam antlndex This is the id of the dead ant * Oparam alabel This is the id of the alive ant * ©return globalView This i s the updated globalView array. */ public int [] [] updateGlobalView(int [] [] globalView, int antlndex, int alabelH for(int i = 0; i < globalView.length; i++){ for (int j = 0; j < globalView.length; j++){ i f (globalView[i][j] == antlndex){ globalView[i][j] = alabel; } > > return globalView; } /** * Description: This Method sets a city as visited for a give 115 * ant tour. * Oparam city The.city that was just visited. * * / ' _ public void setCity(int city){ visited[city]= 1; J /** * Description: This method look for the ant that is at * location (x,y) in 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 is the terminal l i s t of the system. * ©return index This indicates which ant was moved. * */ public int getTheAnt(int x, int y, int [][] terminals){ int index = -20; for(int 1 = 0 ; 1 < terminals.length; l++){ i f (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, int n)-[ for (int p = 0; p < n; p++){ for(int q = 0; q < n; q++){ i f (m.tour[p][q] == "*" I I m.tour[p][q] == "a" ){ ml.tour[p][q]= "*";// This copies the ant m tour into ant id's tour. } } } // ml.tour_length = ml.tour_length + m.tour_length; // This adds the lenght of ant m's 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 */ public int [] [] mergeTours (int []..[] globalView, String [] [] tour, int antlndex){ ' for (int p = 0; p < globalView.length; p++M 117 for(int q = 0; q < globalView.length; q++){ i f (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 his t r a i l . * Oparam m This is the ant who was confused and who w i l l be relocated. * Oparam grid This is the Hanan's grid * Oparam terminals This is the terminal set of the system. * ©return confuse This is an array which contains the x and y * coordinates where the * ant was deconfused to * */ public int [] deconfuse (Ant m, int [] [] terminals, String [] [] grid, int antlndex){ int n = grid.length;-int nSquared = n * n; // number of squares in the tour array. starList = new int [nSquared][2]; confuse = new int [4]; //This i n i t i z e s the starList array. 118 for (int t = 0; t < starList. length; t++){ for(int s = 0; s < 2; s++){ starList[t] [s] =0; } } int row =0; for(int r = 0; r < grid.length; r++){ for(int c = 0; c < grid.length; c++){ i f ((grid[r] [c] == "o" I I gridfr][c] == "x") && (m.tour[r] [c] == "*" I I m.tourLr] [c] == " a " ) ) { starList [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); / / i f (row > OH int index = random.nextlnt(row); confuse [1]= starList [index][0]; confuse [2]= starList[index][1]; // } //else-C //confuse = closestPoint(confuse, starList, terminals, row); // This method finds the closest point. In the ants fabulist //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 his t r a i l . * ©param m This is the ant who was confused and who w i l l be relocated. * ©param grid This is the Hanan's grid * ©param terminals This is the terminal set of the system. * ©return relocate This is an array which contains the x and * y coordinates where the ant was deconfused too * */ public int [] relocate (Ant m, int [][] terminals, String [] • gridM int n = grid.length; int nSquared = n * n; // number of squares in the tour array. steinerList = new int [nSquared][2]; relocate = new int [4]; //This i n i t i z e s the starList array, for (int t = 0; t < steinerList. length; t++M for(int s = 0; s < 2; s++H steinerList[t][s] = 0; 120 } } int row = 0; for(int r = 0; r < grid.length; r++H for(int c = 0; c < grid.length; c++H i f (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 to l i s t a l l of the steiner points steinerList [row] [1]= c; // in the tour of ant m. row++; } } > relocate = closestPoint(relocate, steinerList, terminals, row); // This method finds the closest point In the ants tabulist // to go to when i t i s confused. System.out.println("\nThe relocation point i s " + "("+relocate[l] +","+ relocate [2]+")"); relocate[0]= globalView[relocate [1 ] ][relocate[2]] ; return relocate; > /** * Description: This method attempts to find a steiner point that * i s near to the other terminals. Then returns the steriner point * in the ant's tabulist nearest to the other ants. 121 * 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 starList This is an array which store a l l of the points visited * by the other ants. * Oparam terminals This is the terminal set of the system. * Oparam row This is the row that indicates the depth of the starList set. * Oreturn confuse This is an array which contains the x and y coordinates * where the ant * w i l l be moved to */ public int [] closestPoint(int [] confuse, int [][] starList, int [] [] terminals, int rowM int dist; int minDis = 1000000; for(int f = 0; f < row; f++){ for (int g = 0; g < terminals.length; g++){ dist = Math.abs(terminals[g] [0] - starList[f] [0]) + Math.abs(terminals[g] [1] - starList[f][1]); i f (dist <= minDis){ minDis = dist; //looks for the min distance between the steiner //points and the terminals, confuse [1]= starList [f][0]; //This is the x cooridinate for the min //distance. confuse [2]= starList [f] [1]; //This is the y cooridinate for the min distance. > 122 } } return confuse; } /** * * ©return Returns the tour. */ public String [][] getTourO { return tour; > /** * ©param tour The tour to set. */ public void setTour(String!][] tour) { this.tour = 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 visited. */ public int[] getVisitedO { return visited; } /** * Oparam visited The visited to set. */ public void setVisited(int [] visited) { this.visited = visited; y /** * Oreturn Returns the xposition. */ public int getXpositionO { return xposition; y /** * Oparam xposition The xposition to set. */ 124 public void setXposition(int xposition) { this.xposition = xposition; } /** * ©return Returns the yposition. */ public int getYpositionQ { return yposition; y /** * ©param yposition The yposition to set. */ public void setYposition(int yposition) { this.yposition = yposition; y /** * ©return Returns the max. */ public double getMaxO { return max; } /** * ©param max The max to set. */ public void setMax(double max) { this.max = max; } /** * ©return Returns the globalView. */ public int [] [] getGlobalViewO { return globalView; y /** 125 * Qparam globalView The globalView to set. */ public void setGlobalView(int [][] globalView) { this.globalView = globalView; > } //Experiment!!!! / * i f (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 is p: " + p + " This is randomSubSum + randomSubSum + " when j = " + j ) ; j + + ; > */ //End Experiment!!!! 126 Appendix G Source Code for Utilities.Java package AntSteiner.util; import AntSteiner.*; import AntSteiner.ui.*; /** * Class: Utilities.Java * @author Anthony Blackman * ©version April 10, 2006 */ public class U t i l i t i e s { /**This is the variable was used to store the desirability the ant had to move to a given vertex.*/ private double desirability; /**This i s the variable was used to store the shortest distance * between the ant's current location and the tabu l i s t of the other ants 127 private double psi; /**This is the variable was used to store the intensity the of the t r a i l . * / private double intens; /**This i s the variable was used to store the change in intensity of the * edge of the grid.*/ private double delta_tau; /**This i s the variable was used to store the rectilinear distance between * vertices on the grid.*/ private double rec_distance; /**This data structure was used to store the current t r a i l in an ant's tabu * l i s t . * / private String [] [] tourTemp; /**This i s the variable was used to store the minimum distance between points in * the ants tabu l i s t . * / private double minimum = 1000000.0; /**This is the variable was used to store the combination of desirability and * intensity*/ private double intense_desire; /**This is the variable was used to store the power of the t r a i l intensity.*/ private double alpha; 128 /**This i s variable was used to store the power of the des i r a b i l i t y . * / private double bata; /**This is the variable was used to store the constant parameter in the * desirability formula.*/ private double gamma; /**This i s the variable was used to store the evaporation parameter for * the system.*/ private double rho; /**This i s the variable was used to store the quality of the t r a i l . * / private int Q; /** * This is the default constructor. */ public 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 Discription: This methods gets the intersity of the t r a i l from x to y. Oparam x city ©param y city ©param intensity array Oparam m The ant m Oreturn intense_desire selection probability for the specific edge. / public double selectionProb(int x, int y, double [] [] intensity, Ant m, int n, int [] [] terminals, String [] [] grid, Ant [] colony, int [] antID) i f (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, grid, antID); // This i s the shortest distance from vertex i to a l l // the vertices in the tabulist of the other ants. 130 desirability = 1 / (1 + gamma * psi); intense_desire = Math.pow(intens, alpha)*Math.pow(desirability, bata) return intense_desire; } /** * This Method calculates the rectilinear distance between * city x and city y. * Oparam x city x * Oparam y city y * Oparam row * Oparam col * ©return rec_distance */ public double recDistancednt x, int y, int row, int col){ rec_distance = Math.abs(x - row)+ Math.abs(y - col); return rec_distance; } /** * Descriptions: This method was used to relocate an ant to a * steiner point on his t r a i l . * Oparam colony The set of ants 131 * Oparam grid The Hanan's grid * Oparam x cooridnate * Oparam y cooridnate * Oreturn minimum This is the value of PSI * */ public double createPSI(Ant [] colony, int x, int y, String [][] grid, int [] antIDH int n = grid.length; double min; tourTemp = new String [n][n]; for(int antnum = 0; antnum < colony.length; antnum++)-( i f (antID[antnum]!= -1){ tourTemp = colony[antnum].getTourO; for(int row = 0; row < grid.length; row++){ for(int col = 0; col < grid.length; col++){ // This line looks for a l l the x's and the o's in the //tabulist of the ant called antnum if((tourTemp[row] [col] == "*" I I tourTemp [row][col]== "a" )&& • (grid[row] [col] == "x" II grid [row] [col]== "o")){ //This finds the rectilinear distance between (x, y) and (row, col) min = recDistance(x, y, row, col); 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 April 10, 2006 */ public class Display { /**This variable was used as a reference to the output console*/ private Console c; /** * This is the default constructor. */ public Display(){ } 133 /** * Description: This method was used to display the Steiner Tree; * Oparam sTree The steiner tree * Oparam grid The Hanan's grid * Oparam tLength The length of the steiner tree. */ public void displayTree(String [][] sTree, String [][] grid, int tLength, long took){ //int 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. " ) ; for(int i = 0; i < grid.length; i++M // System.out.print("\n"); c.print("\n"); for(int j = 0; j < grid.length; // System.out.print(grid[i][j]+" " ) ; i f (sTree[i][j] == " * " I I sTree[i] [j] == "a"){ c.setTextColor(Color.BLACK); c.print(grid[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 grid The Hanan's grid. */ public void displayGrid(String [][] grid){ // This prints the grid. c = new Console(45, 100, "Hanan Grid"); for (int i = 0; i < grid.length; i++) { //System.out.print("\n"); c.print("\n"); for(int j = 0; j < grid.length; j++){ / / S y s t e m . o u t . p r i n t ( g r i d [ i ] " ) ; i f (grid[i] [j]== "-" || grid[i] [j]== "|"){ c.setTextColor(Color.RED); //From the hsa Package . c . p r i n t ( g r i d [ i ] " ) ; > else { / / S y s t e m . o u t . p r i n t ( g r i d [ i ] " ) ; c.setTextColor(Color.BLACK); //From the hsa Packag c.print(grid [i] [j]+" " ) ; > > > » 135 Appendix I Source Code for the MST_via_MatrixTree_Nu.m function tree_length = MST_via_MatrixTree_Nu (N) yoName: Anthony Blackman 7«Aim: The main purpose of this function i s to calculate the length of the MST 7. generated by a set of N randomly generated vertices. Using the 7. Kirchoff's Matrix-Tree Theorem. "/.Date: January 12th 2006 "/.Reason for Development: Algorithm for 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 (ie. graph layout) Distance_Matrix = zeros(N,N)7. This array w i l l store the rectilinear distance 7. between Vertex i 136 % and Vertex j in position ( 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) % Will 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)°/0 This function select the kth number in the randomly generated 7. l i s t integers 7« 1 to N. The i represents the i t h row where the vertex w i l l 7» be placed. y = randperm(N) 7, This function generates a random permutation of 7o numbers 1 to N j = y ( D 7 » This function select the kth number in the randomly 7» generated l i s t integers 7. 1 to N. The j represents the jth column where the vertex 7o w i l l be placed. Tree_Vert(i,j)=l °h Put a one in position ( i , j ) to indicate the presents 7o of a vertex. VSet(k,l)=k 7o This line stores the vertex V_k in row k column 1 7. of VSet 137 VSet(k ,2)=i % This line stores 7, column 2 of VSet VSet(k,3)=j % This line stores % column 3 of VSet end % This ends the for loop. the row position of V_k in row k the column position of V_k in row k for 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 rectilinear distance 7o between vertex alpha and vertex bata then stores the value at 7« position (alpha, bata) of the Distance_Matrix. After this we 7o then multiply the value by -m where m i s a parameter that 7. w i l l be dealt with later, end 7o This ends the inner for loop end 7o This ends the outer for loop. for m = 1:5 T= 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 MTree(w,w) = 0 °/0 Since distance between vertex one and vertex % one is 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 is -1. % However we dont need a one in that position. end temp = sum(MTree) 7« This line stores the column sums of the matrix MTree in a % vector called temp. % In the thesis I said that the row sums should be zero % but in this case the row sum = column sum because the °L the distance matrix is a symmetric matrix and A transpose temp = -temp for p = 1:N MTree(p,p)= temp(p) % This line places the some of row p in position % (p,p) of MTree. This makes the row sum of the % matrix MTree to be a l l zero, end °/c This line ends the for loop. MTree(1,1) = MTree(1,1) + 1 % This line makes the sum of row one to be one. % While the row sums of rows 2 to N are s t i l l zero Tree_Polynomial = det(MTree) 7, This line writes the determinant of % MTree. Tree_Polynomial= abs(Tree_Polynomial) °L This function take the absolute value 7o of the determinant. 139 Log_Tree_Polynomial = log(Tree_Polynomial) '/, This line take the natural log % of the Tree polynomial MST_function = Log_Tree_Polynomial / m % this lines is for the calculation for ln(det(A(m)))/m. MinTreeValues(m,l)= m MinTreeValues(m,2)= abs(MST_function) Distance_Matrix = T end maximum = max(MinTreeValues(m,2)) d=l:5 °L This plots five points of the function for values of m = 1,2,3,4 and 5 plot(d,MinTreeValues(d,2)) xlabel('Value of M'), ylabeK'MST Value') title('Graph 1: Graph of MST via Matrix Tree Results for N') Distance_Matrix = -Distance_Matrix % This gets back the actually distance matrix MST = xmst (Distance_Matrix) '/, This passes the rectilinear distance matrix into the % prim' algorithm length = size(MST,2) % This calculates the edges in the array, for e = 1 : length Tree(e)= Distance_Matrix(MST(l,e),MST(2,e)) 1 This stores the lengths of °/0 each edge in an array 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 Pr im's Algor i thm using Mat lab function E=xmst(D); '/.Name: Anthony Blackman °/0Aim: Minimum Spanning Tree using Prim's Algorithm. '/.Date: January 12th 2006 %Reason for Development: Algorithm for the author's Masters Thesis at UBC. '/.Input: D Rectilinear distance matrix '/, D(i,j) weight of edge i j 7. D must be symmetric 700utput: E indices of edges of MST 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
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Ant colony optimization and rectilinear Steiner minimal trees |
Creator |
Blackman, Anthony Curtis |
Publisher | University of British Columbia |
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 |
GraduationDate | 2006-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | 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}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0080128/manifest