nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Optimizing Least-Cost Steiner Tree in Graphs via an Encoding-Free Genetic Algorithm

verfasst von : Qing Liu, Rongjun Tang, Jingyan Kang, Junliang Yao, Wenqing Wang, Yali Wu

Erschienen in: Advances in Swarm Intelligence

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Most bio-inspired algorithms for solving the Steiner tree problem (STP) require the procedures of encoding and decoding. The frequent operations on both encoding and decoding inevitably result in serious time consumption and extra memory overhead, and then reduced the algorithms’ practicability. If a bio-inspired algorithm is encoding-free, its practicability will be improved. Being motivated by this thinking, this article presents an encoding-free genetic algorithm in solving the STP. To verify our proposed algorithm’s validity and investigate its performance, detailed simulations were carried out. Some insights in this article may also have significance for reference when solving the other problems related to the topological optimization.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Improving Jaccard Index Using Genetic Algorithms for Collaborative Filtering

Nächstes Kapitel An Energy Minimized Solution for Solving Redundancy of Underwater Vehicle-Manipulator System Based on Genetic Algorithm

Liu, Q., Odaka, T., Kuroiwa, J., et al.: An artificial fish swarm algorithm for the multicast routing problem. IEICE Trans. Commun. E97-B(5), 996–1011 (2014)CrossRef

Zhou, Z., Jiang, C., Huang, L., et al.: On optimal rectilinear shortest paths and 3-Steiner tree routing in presence of obstacles. J. Softw. 14(9), 1503–1514 (2003). (in Chinese with an English abstract)MathSciNetMATH

Li, Z., Shi, H.: A data-aggregation algorithm based on minimum Steiner tree in wireless sensor networks. J. Northwest. Polytech. Univ. 27(4), 558–564 (2009). (in Chinese with an English abstract)

Hwang, F.K., Richards, D.S., Winter, P.: The Steiner Tree Problem, vol. 53. Elsevier, Amsterdam (1992)MATH

Takahashi, H., Matsuyama, A.: An approximate solution for the Steiner problem in graphs. Math. Jpn. 24(6), 573–577 (1980)MathSciNetMATH

Kou, L., Markowsky, G., Berman, L.: A fast algorithm for Steiner trees. Acta Informatica 15, 141–145 (1981)MathSciNetCrossRefMATH

Rayward-Smith, V.J.: The computation of nearly minimal Steiner trees in graphs. Int. J. Math. Educ. Sci. Tech. 14(1), 15–23 (1983)MathSciNetCrossRefMATH

Gary, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness (1979)

Plesník, J.: Worst-case relative performances of heuristics for the Steiner problem in graphs. Acta Math. Univ. Comen. LX(2), 269–284 (1991)MathSciNetMATH

10.

Fan, Y., Jianjun, Yu., Fang, Z.: Hybrid genetic simulated annealing algorithm based on niching for QoS multicast routing. J. Commun. 29(5), 65–71 (2008). (in Chinese with an English abstract)

11.

Ma, X., Liu, Q.: A particle swarm optimization for Steiner tree problem. In: Proceedings of the 6th International Conference on Natural Computation (ICNC), pp. 2561–2565 (2010)

12.

Zhong, W.L., Huang, J., Zhang, J.: A novel particle swarm optimization for the Steiner tree problem in graphs. In: IEEE World Congress on Evolutionary Computation, pp. 2460–2467 (2008)

13.

Ma, X., Liu, Q.: An artificial fish swarm algorithm for Steiner tree problem. In: IEEE-FUZZ, pp. 59–63 (2009)

14.

Prim, R.C.: Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36(6), 1389–1401 (1957)CrossRef

15.

Koza, J.: Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge (1992)MATH

Titel: Optimizing Least-Cost Steiner Tree in Graphs via an Encoding-Free Genetic Algorithm
verfasst von: Qing Liu
Rongjun Tang
Jingyan Kang
Junliang Yao
Wenqing Wang
Yali Wu
Verlag: Springer International Publishing
Buch: Advances in Swarm Intelligence
Print ISBN: 978-3-319-61823-4

Electronic ISBN: 978-3-319-61824-1

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-61824-1_42

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner