Hybrid Greedy Genetic Algorithm for the Euclidean Steiner Tree Problem
Resumo
This paper presents a genetic algorithm for the Euclidean Steiner tree problem. This is an optimization problem whose objective is to obtain a minimum length tree to interconnect a set of fixed points, and for this purpose to be achieved, new auxiliary points, called Steiner points, can be added. The proposed heuristic uses a genetic algorithm to manipulate spanning trees, which are then transformed into Steiner trees by inserting and repositioning the Steiner points. Greedy genetic operators and evolutionary strategies are tested. Results of numerical experiments for benchmark library problem (OR-Library) are presented and discussed.This paper presents a genetic algorithm for the Euclidean Steiner tree problem. This is an optimization problem whose objective is to obtain a minimum length tree to interconnect a set of fixed points, and for this purpose to be achieved, new auxiliary points, called Steiner points, can be added. The proposed heuristic uses a genetic algorithm to manipulate spanning trees, which are then transformed into Steiner trees by inserting and repositioning the Steiner points. Greedy genetic operators and evolutionary strategies are tested. Results of numerical experiments for benchmark library problem (OR-Library) are presented and discussed.
Referências
Beasley, J. E. (1990). OR-Library: distributing test problems by electronic mail. Journal of the Operational Research Society.
Beasley, J. E. and Goffnet, F. (1994). A Delaunay triangulation-based heuristic for the Euclidean Steiner problem. Networks.
Bereta, M. (2018). Baldwin effect and lamarckian evolution in a memetic algorithm for Euclidean Steiner tree problem. Memetic Computing.
Brazil, M., Graham, R. L., Thomas, D. A., and Zachariasen, M. (2013). On the Story of Euclidian Steiner Tree Problem. Archive for History of Exact Sciences.
De Jong, K. A. (1975). An Analysis of the Behavior of a Class of Genetic Adaptive Systems. PhD thesis, University of Michigan. AAI7609381.
Deza, M. M. and Deza, E. (2009). Encyclopedia of Distances. Springer Berlin Heidelberg.
Dreyer, D. and Overton, M. (1998). Two heuristics for the Euclidean Steiner tree problem. Journal of Global Optimization.
Fampa, M. and Anstreicher, K. M. (2008). An improved algorithm for computing Steiner minimal trees in Euclidean d-space. Discrete Optimization.
Forte, V. L. d., Montenegro, F. M. T., Brito, J. A. d. M., and Maculan, N. (2015). Iterated local search algorithms for the Euclidean Steiner tree problem in n dimensions. International Transactions in Operational Research.
Gilbert, E. N. and Pollak, H. O. (1968). Steiner minimal trees. SIAM Journal on Applied Mathematics.
Goldberg, D. E. (1989). Genetic algorithms in search, optimization and machine learning. Addison Wesley.
Hanan, M. (1966). On Steiner’s problem with rectilinear distance. SIAM Journal on Applied Mathematics.
Hwang, F. K., Richards, D. S., and Winter, P. (1992). The Steiner Tree Problem. Elsevier Science Publishers B. V.
Jesus, M., Jesus, S., and Márquez, A. (2004). Steiner trees optimization using genetic algorithms. In Technical report. Centro de Simulação e Cálculo.
Jong, K. A. D. and Sarma, J. (1992). Generation gaps revisited. In FOGA.
Koch, T. and Martin, A. (1998). Solving Steiner tree problems in graphs to optimality. Networks.
Kruskal, Jr., J. B. (1956). On the shortest spanning tree of a graph and the traveling salesman problem. Proc. Amer. Math. Soc.
Laarhoven, J. W. and Ohlmannn, J. W. (2010). A randomized Delaunay triangulation heuristic for the Euclidean Steiner tree problem in Rd . Journal of Heuristics.
Luke, S. (2013). Essentials of Metaheuristics. Lulu.
Mitchell, M. (1998). An Introduction to Genetic Algorithms. MIT Press.
Prim, R. (1957). Shortest connection networks and some generalizations. Bell System Tech. J.
Raidl, G. R. and Julstrom, B. A. (2003). Edge sets: an effective evolutionary coding of spanning trees. IEEE Transactions on Evolutionary Computation.
Smith, W. D. (1992). How to find Steiner minimal trees in Euclidean d-space. Algorithmica.
Thompson, E. A. (1973). The method of minimum evolution. Annals of human genetics.
Wang, L. and Du, D.-Z. (2002). Approximations for a bottleneck Steiner tree problem. Algorithmica.
Whitley, D. (1988). Genitor : a different genetic algorithm. Proceedings of the Rocky Mountain conference on artificial intelligence, 1988.
Winter, P. and Zachariasen, M. (1997). Euclidean Steiner minimum trees: An improved exact algorithm. Networks.
Yang, B. (2006). A hybrid evolutionary algorithm for the Euclidean Steiner tree problem using local searches. In Knowledge-Based Intelligent Information and Engineering Systems.
