An Hierarchic Genetic Algorithm for Computing (near) Optimal Euclidean Steiner Trees

Authors

Abstract

In this paper we present an algorithm for finding an approximation
to the Euclidean Steiner Tree for a given set of terminal points. This
is defined as the shortest length geometric construction that unites all
the terminals. Our algorithm dynamically partitions the point set into
multiple, separately optimized subsets. The Steiner tree for these subsets
is constructed by running a highly modified genetic algorithm.

Keywords

Gentic Algorithms; Steiner Tree; Geometric Algorithms

Subject

Evolutionary Optimization

Conference

Workshop on Application of Hybrid Evolutionary Algorithms to NP-Complete Problems (GECCO2003), July 2003

PDF File

Cited by

Year 2007 : 1 citations

Ian Frommer and Bruce Golden (2007): A Genetic Algorithm for Solving the Euclidean Non-Uniform Steiner Tree Problem. Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies, Operations Research/Computer Science Interfaces, Vol 37, pp. 31-48, Springer 2007.

Year 2006 : 2 citations

Byounghak Yang (2006): Hybrid Evolutionary Algorithms for the Rectilinear Steiner Tree Problem Using Fitness Estimation. Computational Science and Its Applications - ICCSA 2006, LNCS 3982/2006, pp. 582-589, Springer 2006.

Byounghak Yang (2006): A Hybrid Evolutionary Algorithm for the Euclidean Steiner Tree Problem Using Local Searches. Knowledge-Based Intelligent Information and Engineering Systems, Lecture Notes in Computer Science 4251/2006, pp. 60-67, Springer 2006.

Year 2005 : 3 citations

Ian Frommer, Bruce Golden, and Guruprasad Pundoor, "Heuristic Methods for Solving Euclidean
Non-uniform Steiner Tree Problems", The Next Wave in Computing, Optimization, and Decision Technologies (B. Golden, S. Raghvan, and E. Wasil, eds.), Springer, 133-148, 2005.

MODELING AND OPTIMIZATION OF TRANSMISSION NETWORKS, Ian Frommer, Ph. D. Dissertation, University of Maryland, 2005

Byounghak Yang (2005). A Hybrid Evolution Strategy on the Rectilinear Steiner Tree. DBPIA, pp. 27-37, 2005.