Abstract
In the Steiner Tree Problem in Graphs, a subset of nodes, called terminals, must be efficiently interconnected. The graph is undirected and weighted, and candidate solutions can include additional nodes called Steiner vertices. The problem is NP-complete, and optimization algorithms based on population metaheuristics, e.g., Genetic Algorithms (GAs), have been proposed. However, traditional recombination operators may produce inefficient solutions for graph-based problems. We propose a new recombination operator for the Steiner Tree Problem based on the graph representation. The new operator is a kind of partition crossover: it breaks the graph formed by the union of two parents solutions and decomposes the evaluation function by finding connected subgraphs. We also investigate two soft-repair operators that produce small changes in candidate solutions: an MST transformation and a pruning repair. The GA with the proposed crossover operator was able to find the global optimum solution for all tested instances and has a success rate of 28% in the worst case. The experiments with the proposed crossover presented a quick convergence to optimal solutions, and an average solution cost lower in most cases than other approaches.
Keywords
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsReferences
Beasley, J.E.: OR-library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11), 1069–1072 (1990)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Algoritmos: Teoria e Prática. Editora Elsevier (2012)
Esbensen, H.: Computing near-optimal solutions to the Steiner problem in a graph using a genetic algorithm. Networks 26(4), 173–185 (1995). https://doi.org/10.1002/net.3230260403
Hakimi, S.L.: Steiner’s problem in graphs and its implications. Networks 1(2), 113–133 (1971). https://doi.org/10.1002/net.3230010203
Kapsalis, A., Rayward-smith, V.J., Smith, G.D.: Solving the graphical Steiner tree problem using genetic algorithms. J. Oper. Res. Soc. 44(4), 397–406 (1993)
Karp, R.M.: Reducibility among Combinatorial Problems, pp. 85–103. Springer, Boston (1972). https://doi.org/10.1007/978-1-4684-2001-2_9
Kou, L., Markowsky, G., Berman, L.: A fast algorithm for Steiner trees. Acta Inf. 15(2), 141–145 (1981). https://doi.org/10.1007/BF00288961
Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7(1), 48–50 (1956). http://www.jstor.org/stable/2033241
Ljubić, I.: Solving Steiner trees: recent advances, challenges, and perspectives. Networks 77(2), 177–204 (2021)
Prim, R.C.: Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36(6), 1389–1401 (1957)
Raidl, G.R., Julstrom, B.A.: Edge sets: an effective evolutionary coding of spanning trees. IEEE Trans. Evol. Comput. 7(3), 225–239 (2003). https://doi.org/10.1109/TEVC.2002.807275
Tinós, R., Whitley, D., Ochoa, G.: Generalized Asymmetric Partition Crossover (GAPX) for the asymmetric TSP. In: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, GECCO 2014, pp. 501–508. ACM, New York (2014)
Tinós, R., Whitley, D., Ochoa, G.: A new generalized partition crossover for the traveling salesman problem: tunneling between local optima. Evol. Comput. 28(2), 255–288 (2020). https://doi.org/10.1162/evco_a_00254, pMID: 30900928
Whitley, D.: Next generation genetic algorithms: a user’s guide and tutorial. In: Gendreau, M., Potvin, J.-Y. (eds.) Handbook of Metaheuristics. ISORMS, vol. 272, pp. 245–274. Springer, Cham (2019). https://doi.org/10.1007/978-3-319-91086-4_8
Whitley, D., Hains, D., Howe, A.: Tunneling between optima: partition crossover for the traveling salesman problem. In: Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, GECCO 2009, pp. 915–922. ACM, New York (2009)
Whitley, D., Hains, D., Howe, A.: A hybrid genetic algorithm for the traveling salesman problem using generalized partition crossover. In: Schaefer, R., Cotta, C., Kołodziej, J., Rudolph, G. (eds.) PPSN 2010. LNCS, vol. 6238, pp. 566–575. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15844-5_57
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
de Godoi, G.A., Tinós, R., Sanches, D.S. (2021). A Graph-Based Crossover and Soft-Repair Operators for the Steiner Tree Problem. In: Britto, A., Valdivia Delgado, K. (eds) Intelligent Systems. BRACIS 2021. Lecture Notes in Computer Science(), vol 13073. Springer, Cham. https://doi.org/10.1007/978-3-030-91702-9_8
Download citation
DOI: https://doi.org/10.1007/978-3-030-91702-9_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-91701-2
Online ISBN: 978-3-030-91702-9
eBook Packages: Computer ScienceComputer Science (R0)