Skip to main content
Erschienen in: Soft Computing 3/2020

14.05.2019 | Methodologies and Application

A hybrid genetic algorithm for the degree-constrained minimum spanning tree problem

verfasst von: Kavita Singh, Shyam Sundar

Erschienen in: Soft Computing | Ausgabe 3/2020

Einloggen

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

search-config
loading …

Abstract

Given an undirected, connected, edge-weighted graph G and a positive integer d, the degree-constrained minimum spanning tree (dc-MST) problem aims to find a minimum spanning tree T on G subject to the constraint that each vertex is either a leaf vertex or else has degree at most d in T, where d is a given positive integer. The dc-MST is \(\mathcal {NP}\)-hard problem for d\(\ge \) 2 and finds several real-world applications. This paper proposes a hybrid approach (\(\mathcal {H}\)SSGA) combining a steady-state genetic algorithm and local search strategies for the this problem. An additional step (based on perturbation strategy at a regular interval of time) in the replacement strategy is applied in order to maintain diversity in the population throughout the search process. On a set of available 107 benchmark instances, computational results show the superiority of our proposed \(\mathcal {H}\)SSGA in comparison with the state-of-the-art metaheuristic techniques.

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!

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!

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!

Literatur
Zurück zum Zitat Bau Y, Ho CK, Ewe HT (2005) An ant colony optimization approach to the degree-constrained minimum spanning tree problem. In: Proceedings of the computational intelligence and security, international conference (CIS 2005), Xi’an, China, December 15–19, 2005, Part I, pp 657–662 Bau Y, Ho CK, Ewe HT (2005) An ant colony optimization approach to the degree-constrained minimum spanning tree problem. In: Proceedings of the computational intelligence and security, international conference (CIS 2005), Xi’an, China, December 15–19, 2005, Part I, pp 657–662
Zurück zum Zitat Beasley JE, PC C (1996) A genetic algorithm for the set covering problem. Eur J Oper Res 94:394–404 Beasley JE, PC C (1996) A genetic algorithm for the set covering problem. Eur J Oper Res 94:394–404
Zurück zum Zitat Binh HTT, Nguyen TB (2008) New particle swarm optimization algorithm for solving degree constrained minimum spanning tree problem. In: Proceedings of the PRICAI 2008: trends in artificial intelligence, 10th Pacific rim international conference on artificial intelligence, Hanoi, Vietnam, December 15–19, 2008, pp 1077–1085 Binh HTT, Nguyen TB (2008) New particle swarm optimization algorithm for solving degree constrained minimum spanning tree problem. In: Proceedings of the PRICAI 2008: trends in artificial intelligence, 10th Pacific rim international conference on artificial intelligence, Hanoi, Vietnam, December 15–19, 2008, pp 1077–1085
Zurück zum Zitat Boldon B, Deo N, Kumar N (1996) Minimum-weight degree-constrained spanning tree problem: heuristics and implementation on an SIMD parallel machine. Parallel Comput 22(3):369–382CrossRef Boldon B, Deo N, Kumar N (1996) Minimum-weight degree-constrained spanning tree problem: heuristics and implementation on an SIMD parallel machine. Parallel Comput 22(3):369–382CrossRef
Zurück zum Zitat Bui TN, Zrncic CM (2006) An ant-based algorithm for finding degree-constrained minimum spanning tree. In: Proceedings of the genetic and evolutionary computation conference, GECCO 2006, Seattle, Washington, USA, July 8–12, 2006, pp 11–18 Bui TN, Zrncic CM (2006) An ant-based algorithm for finding degree-constrained minimum spanning tree. In: Proceedings of the genetic and evolutionary computation conference, GECCO 2006, Seattle, Washington, USA, July 8–12, 2006, pp 11–18
Zurück zum Zitat Bui TN, Deng X, Zrncic CM (2012) An improved ant-based algorithm for the degree-constrained minimum spanning tree problem. IEEE Trans Evol Comput 16(2):266–278CrossRef Bui TN, Deng X, Zrncic CM (2012) An improved ant-based algorithm for the degree-constrained minimum spanning tree problem. IEEE Trans Evol Comput 16(2):266–278CrossRef
Zurück zum Zitat Cerrone C, Cerulli R, Raiconi A (2014) Relations, models and a memetic approach for three degree-dependent spanning tree problems. Eur J Oper Res 232(3):442–453MathSciNetCrossRef Cerrone C, Cerulli R, Raiconi A (2014) Relations, models and a memetic approach for three degree-dependent spanning tree problems. Eur J Oper Res 232(3):442–453MathSciNetCrossRef
Zurück zum Zitat Davis L (1991) Handbook of genetic algorithms. Van Nostrand Reinhold, New York Davis L (1991) Handbook of genetic algorithms. Van Nostrand Reinhold, New York
Zurück zum Zitat Doan MN (2007) An effective ant-based algorithm for the degree-constrained minimum spanning tree problem. In: Proceedings of the IEEE congress on evolutionary computation (CEC 2007), 25–28 September 2007, Singapore, pp 485–491 Doan MN (2007) An effective ant-based algorithm for the degree-constrained minimum spanning tree problem. In: Proceedings of the IEEE congress on evolutionary computation (CEC 2007), 25–28 September 2007, Singapore, pp 485–491
Zurück zum Zitat Ernst AT (2010) A hybrid Lagrangian particle swarm optimization algorithm for the degree-constrained minimum spanning tree problem. In: Proceedings of the IEEE congress on evolutionary computation, CEC 2010, Barcelona, Spain, 18–23 July 2010, pp 1–8 Ernst AT (2010) A hybrid Lagrangian particle swarm optimization algorithm for the degree-constrained minimum spanning tree problem. In: Proceedings of the IEEE congress on evolutionary computation, CEC 2010, Barcelona, Spain, 18–23 July 2010, pp 1–8
Zurück zum Zitat Gao X, Jia L, Kar S (2017) Degree-constrained minimum spanning tree problem of uncertain random network. J Ambient Intell Humaniz Comput 8(5):747–757CrossRef Gao X, Jia L, Kar S (2017) Degree-constrained minimum spanning tree problem of uncertain random network. J Ambient Intell Humaniz Comput 8(5):747–757CrossRef
Zurück zum Zitat García S, Molina D, Lozano M, Herrera F (2009) A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behaviour: a case study on the CEC’2005 special session on real parameter optimization. J Heuristics 15(6):617–644CrossRef García S, Molina D, Lozano M, Herrera F (2009) A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behaviour: a case study on the CEC’2005 special session on real parameter optimization. J Heuristics 15(6):617–644CrossRef
Zurück zum Zitat Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San FranciscoMATH Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San FranciscoMATH
Zurück zum Zitat Gargano L, Hell P, Stacho L, Vaccaro U (2002) Spanning trees with bounded number of branch vertices. In: Proceedings of 29th international colloquium, ICALP 2002 Malaga, Spain, vol 2380, pp 355–365 Gargano L, Hell P, Stacho L, Vaccaro U (2002) Spanning trees with bounded number of branch vertices. In: Proceedings of 29th international colloquium, ICALP 2002 Malaga, Spain, vol 2380, pp 355–365
Zurück zum Zitat Goldberg DE (1989) Genetic algorithms in search optimization and machine learning. Addison-Wesley, ReadingMATH Goldberg DE (1989) Genetic algorithms in search optimization and machine learning. Addison-Wesley, ReadingMATH
Zurück zum Zitat Holland JH (1975) Adaptation in natural and artificial systems: an introductory analysis with applications in biology, control, and artificial intelligence. University of Michigan Press, Ann ArborMATH Holland JH (1975) Adaptation in natural and artificial systems: an introductory analysis with applications in biology, control, and artificial intelligence. University of Michigan Press, Ann ArborMATH
Zurück zum Zitat Iordache GV, Boboila MS, Pop F, Stratan C, Cristea V (2007) A decentralized strategy for genetic scheduling in heterogeneous environments. Multiagent Grid Syst 3(4):355–367CrossRef Iordache GV, Boboila MS, Pop F, Stratan C, Cristea V (2007) A decentralized strategy for genetic scheduling in heterogeneous environments. Multiagent Grid Syst 3(4):355–367CrossRef
Zurück zum Zitat Knowles JD, Corne D (2000) A new evolutionary approach to the degree-constrained minimum spanning tree problem. IEEE Trans Evol Comput 4(2):125–134CrossRef Knowles JD, Corne D (2000) A new evolutionary approach to the degree-constrained minimum spanning tree problem. IEEE Trans Evol Comput 4(2):125–134CrossRef
Zurück zum Zitat Krishnamoorthy M, Ernst AT, Sharaiha YM (2001) Comparison of algorithms for the degree constrained minimum spanning tree. J Heuristics 7(6):587–611CrossRef Krishnamoorthy M, Ernst AT, Sharaiha YM (2001) Comparison of algorithms for the degree constrained minimum spanning tree. J Heuristics 7(6):587–611CrossRef
Zurück zum Zitat Marín A (2015) Exact and heuristic solutions for the minimum number of branch vertices spanning tree problem. Eur J Oper Res 245(3):680–689MathSciNetCrossRef Marín A (2015) Exact and heuristic solutions for the minimum number of branch vertices spanning tree problem. Eur J Oper Res 245(3):680–689MathSciNetCrossRef
Zurück zum Zitat Moreno J, Frota Y, Martins S (2018) An exact and heuristic approach for the d-minimum branch vertices problem. Comput Opt Appl 71(3):829–855MathSciNetCrossRef Moreno J, Frota Y, Martins S (2018) An exact and heuristic approach for the d-minimum branch vertices problem. Comput Opt Appl 71(3):829–855MathSciNetCrossRef
Zurück zum Zitat Narula SC, Ho CA (1980) Degree-constrained minimum spanning tree. Comput OR 7(4):239–249CrossRef Narula SC, Ho CA (1980) Degree-constrained minimum spanning tree. Comput OR 7(4):239–249CrossRef
Zurück zum Zitat Pop F, Cristea V, Bessis N, Sotiriadis S (2013) Reputation guided genetic scheduling algorithm for independent tasks in inter-clouds environments. In: 27th International conference on advanced information networking and applications workshops, WAINA 2013, Barcelona, Spain, March 25–28, 2013, pp 772–776 Pop F, Cristea V, Bessis N, Sotiriadis S (2013) Reputation guided genetic scheduling algorithm for independent tasks in inter-clouds environments. In: 27th International conference on advanced information networking and applications workshops, WAINA 2013, Barcelona, Spain, March 25–28, 2013, pp 772–776
Zurück zum Zitat Prim R (1957) Shortest connection networks and some generalizations. Bell Syst Tech J 36:1389–1401CrossRef Prim R (1957) Shortest connection networks and some generalizations. Bell Syst Tech J 36:1389–1401CrossRef
Zurück zum Zitat Raidl GR, Julstrom BA (2000) A weighted coding in a genetic algorithm for the degree-constrained minimum spanning tree problem. In: Proceedings of the 2000 ACM symposium on applied computing, Villa Olmo, Via Cantoni 1, 22100 Como, Italy, March 19–21, 2000, vol 1, pp 440–445 Raidl GR, Julstrom BA (2000) A weighted coding in a genetic algorithm for the degree-constrained minimum spanning tree problem. In: Proceedings of the 2000 ACM symposium on applied computing, Villa Olmo, Via Cantoni 1, 22100 Como, Italy, March 19–21, 2000, vol 1, pp 440–445
Zurück zum Zitat Raidl GR, Julstrom BA (2003) Edge sets: an effective evolutionary coding of spanning trees. IEEE Trans Evol Comput 7:225–239CrossRef Raidl GR, Julstrom BA (2003) Edge sets: an effective evolutionary coding of spanning trees. IEEE Trans Evol Comput 7:225–239CrossRef
Zurück zum Zitat Ravi R, Marathe M, Ravi S, Rosenkrantz D, Hunt H III (1993) Many birds with one stone: multi-objective approximation algorithms. In: Proceedings of the 25th annual ACM STOCS, pp 438–447 Ravi R, Marathe M, Ravi S, Rosenkrantz D, Hunt H III (1993) Many birds with one stone: multi-objective approximation algorithms. In: Proceedings of the 25th annual ACM STOCS, pp 438–447
Zurück zum Zitat Savelsbergh MWP, Volgenant T (1985) Edge exchanges in the degree-constrained minimum spanning tree problem. Comput OR 12(4):341–348CrossRef Savelsbergh MWP, Volgenant T (1985) Edge exchanges in the degree-constrained minimum spanning tree problem. Comput OR 12(4):341–348CrossRef
Zurück zum Zitat Silvestri S, Laporte G, Cerulli R (2017) A branch-and-cut algorithm for the minimum branch vertices spanning tree problem. Comput Oper Res 81:322–332MathSciNetCrossRef Silvestri S, Laporte G, Cerulli R (2017) A branch-and-cut algorithm for the minimum branch vertices spanning tree problem. Comput Oper Res 81:322–332MathSciNetCrossRef
Zurück zum Zitat Sundar S (2014) A steady-state genetic algorithm for the dominating tree problem. In: Proceedings of the simulated evolution and learning—10th international conference, SEAL 2014, Dunedin, New Zealand, December 15–18, 2014, pp 48–57 Sundar S (2014) A steady-state genetic algorithm for the dominating tree problem. In: Proceedings of the simulated evolution and learning—10th international conference, SEAL 2014, Dunedin, New Zealand, December 15–18, 2014, pp 48–57
Zurück zum Zitat Sundar S, Singh A (2015) Metaheuristic approaches for the blockmodel problem. IEEE Syst J 9(4):1237–1247CrossRef Sundar S, Singh A (2015) Metaheuristic approaches for the blockmodel problem. IEEE Syst J 9(4):1237–1247CrossRef
Zurück zum Zitat Sundar S, Singh A (2017) Two grouping-based metaheuristics for clique partitioning problem. Appl Intell 47(2):430–442CrossRef Sundar S, Singh A (2017) Two grouping-based metaheuristics for clique partitioning problem. Appl Intell 47(2):430–442CrossRef
Zurück zum Zitat Zhou G, Gen M (1997) A note on genetic algorithms for degree-constrained spanning tree problems. Networks 30(2):91–95CrossRef Zhou G, Gen M (1997) A note on genetic algorithms for degree-constrained spanning tree problems. Networks 30(2):91–95CrossRef
Metadaten
Titel
A hybrid genetic algorithm for the degree-constrained minimum spanning tree problem
verfasst von
Kavita Singh
Shyam Sundar
Publikationsdatum
14.05.2019
Verlag
Springer Berlin Heidelberg
Erschienen in
Soft Computing / Ausgabe 3/2020
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI
https://doi.org/10.1007/s00500-019-04051-x

Weitere Artikel der Ausgabe 3/2020

Soft Computing 3/2020 Zur Ausgabe