Open Collections

Ant colony optimization and rectilinear Steiner minimal trees

University of British Columbia

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.

Text

2010-01-08

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.

http://hdl.handle.net/2429/17733

Mathematics

University of British Columbia

UBCV

DSpace