A parallel genetic algorithm for the Steiner Problem in Networks
Di Fatta, G., Lo Presto, G. and Lo Re, G. (2003) A parallel genetic algorithm for the Steiner Problem in Networks. In: The 15th IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS 2003), 3-5 Nov 2003, Marina del Rey, CA, USA, pp. 569-573.
This paper presents a parallel genetic algorithm to the Steiner Problem in Networks. Several previous papers have proposed the adoption of GAs and others metaheuristics to solve the SPN demonstrating the validity of their approaches. This work differs from them for two main reasons: the dimension and the characteristics of the networks adopted in the experiments and the aim from which it has been originated. The reason that aimed this work was namely to build a comparison term for validating deterministic and computationally inexpensive algorithms which can be used in practical engineering applications, such as the multicast transmission in the Internet. On the other hand, the large dimensions of our sample networks require the adoption of a parallel implementation of the Steiner GA, which is able to deal with such large problem instances.
 E. Cant-Paz, A summary of research on parallel genetic algorithms, Technical Report 950076, Illinois Genetic Algorithm Lab., Univ. Illinois Urbana- Champaign, Urbana, IL, July 1995.  G. Di Fatta, G. Lo Re, Efficient tree construction for the multicast problem, Special issue of the Journal of the Brazilian Telecommunications Society, 1999.  G. Di Fatta, G. Lo Presti, G. Lo Re, Computer Network Topologies: Models and Generation Tools, CE.R.E. Technical Report 5, July 2001.  K. A. Dowsland, Hill-climbing, Simulated Annealing and the Steiner Problem in Graphs, Engineering Optimisation, 17, 1991, pp. 91-107.  H. Esbensen, Computing Near-Optimal Solutions to the Steiner Problem in a Graph Using a Genetic Algorithm, Networks: An International Journal, 26, 1995.  M. Faloutsos, P. Faloutsos, C. Faloutsos, On Power- Law Relationships of the Internet Topology, ACM SIGCOMM, 1999.  M. Gendreau, J. F. Larochelle, B. Sanso, A Tabu Search Heuristic for the Steiner Tree Problem, Networks, 34, 1999, 162-172.  D. E. Goldberg, Genetic algorithm in Search, Optimization, and Machine Learning (Reading, MA: Addison Wesley, 1989).  R. Govindan, H. Tangmunarunkit, Heuristics for Internet Map Discovery, Proc IEEE Infocom 2000, Tel Aviv, Israel.  R. M. Karp, Reducibility among Combinatorial Problems, in R. E. Miller, J. W. Thatcher (Eds.), Complexity of Computer Computations (Plenum Press, New York, 1972, 85-103).  L. Kou, G. Markowsky, L. Berman, A fast algorithm for Steiner trees, Acta Inform., 15, 1981, 141-145.  J. Kruskal, On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem, Proc. Amer. Math. Soc., 7, 1956, 48-50.  A. Medina, A. Lakhina, I. Matta, J. Byers, BRITE Universal Topology Generator, 2001, cs-pub.bu.edu/brite.  A. Medina, I. Matta, J. Byers, On the Origin of Power Laws in Internet Topologies, ACM SIGCOMM 2000, 30(2), April 2000.  Message Passing Interface Forum. MPI: A new message-passing interface standard (version 1.1), Technical Report, University of Tennessee, 1995.  V. J. Rayward-Smith, The computation of nearly minimal Steiner trees in graphs, Int. Math. Ed. Sci. Tech. 14, 1983, 15-23.  V. J. Rayward-Smith, A. Clare, On Finding Steiner Vertices, Networks, 16, 1986, 283-294.  H. Tangmunarunkit, R. Govindan, S. Jamin, et al., Network Topologies, Power Laws, and Hierarchy, SIGCOMM 2001, June 2001.  H. Takahashi, A Matsuyama, An approximate solution for the Steiner problem in graphs, Math. Japan, 1980, 573-577.  M. Tomassini, Parallel and distributed evolutionary algorithms: A review, in K. Miettinen, M. Mkel, P. Neittaanmki, J. Periaux, Evolutionary Algorithms in Engineering and Computer Science (Eds. New York: Wiley, 1999, 113-133).  S. Voss, A. Martin, T. Koch, SteinLib Testdata Library, February 2001, elib.zib.de/steinlib/steinlib.php.  P. Winter, Steiner problem in networks: a survey, Networks, 17, 1987, 129-167.
Repository Staff Only: item control page