research-article

New heuristic and hybrid genetic algorithm for solving the bounded diameter minimum spanning tree problem

Authors:

Thanh Thi Huynh Binh,

Robert I. McKay,

Nguyen Xuan Hoai,

Nguyen Duc NghiaAuthors Info & Claims

GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

Pages 373 - 380

https://doi.org/10.1145/1569901.1569953

Published: 08 July 2009 Publication History

Abstract

In this paper, we propose a new heuristic, called Center-Based Recursive Clustering - CBRC, for solving the bounded diameter minimum spanning tree (BDMST) problem. Our proposed hybrid genetic algorithm [12] is also extended to include the new heuristic and a multi-parent crossover operator. We test the new heuristic and genetic algorithm on two sets of benchmark problem instances for the Euclidean and Non-Euclidean cases. Experimental results show the effectiveness of the proposed heuristic and genetic algorithm.

References

[1]

A. Abdalla, N. Deo, and P. Gupta, Random-tree Diameter and the Diameter Constrained MST, in Proceedings of Congress on Numerantium, 2000, pp. 161--182.

[2]

A. Abdalla, Computing a Diameter-constrained Minimum Spanning Tree, PhD Dissertation, The School of Electrical Engineering and Computer Science, University of Central Florida, 2001.

Digital Library

[3]

N.R.Achuthan, L.Caccetta, P.Caccetta, and A. Geelen, Computational Methods for the Diameter Restricted Minimum Weight Spanning Tree Problem, Australian Journal of Combinatorics, 10, 1994, pp.51--71.

[4]

A. Bookstein and S. T. Klein, Compression of Correlated Bit-Vectors, Information Systems, 16 (4), 1996, pp. 387--400.

Digital Library

[5]

K. Bala, K. Petropoulos, and T. E. Stern, Multicasting in a linear Lightwave Network, in Proceedings of IEEE INFOCOM'93, 3 (1993), pp. 1350--1358.

[6]

M.R. Garey and D.S.Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H.Freeman, New York, 1979, 206.

Digital Library

[7]

J.Gottlieb, B.A.Julstrom, F.Rothlauf, and G.R.Raidl, Prufer Numbers: A Poor Representation of Spanning Trees for Evolutionary Search, in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'2001), 2001, pp.343--350.

[8]

L Gouveia, T.L. Magnanti and C. Requejo, A 2-Path Approach for Odd Diameter Constrained Minimum Spanning and Steiner Trees, Network, 44 (4), 2004, pp. 254--265.

Digital Library

[9]

M. Gruber and G.R. Raidl, A New 0-1 ILP Approach for the Bounded Diameter Minimum Spanning Tree Problem, in Proceedings of the 2nd International Network Optimization Conference, 2005.

[10]

M. Gruber and G.R. Raidl, Variable Neighbourhood Search for the Bounded Diameter Minimum Spanning Tree Problem, in Proceedings of the 18th Mini Euro Conference on Variable Neighborhood Search, Spain, 2005.

[11]

M. Gruber, J. Hemert, and G.R. Raidl, Neighbourhood Searches for the Bounded Diameter Minimum Spanning Tree Problem Embedded in a VNS, EA and ACO, in Proceedings of Genetic and Evolutionary Computational Conference (GECCO'2006), 2006.

Digital Library

[12]

Huynh Thi Thanh Binh, Nguyen Xuan Hoai, R.I McKay, A New Hybrid Genetic Algorithm for Solving the Bounded Diameter Minimum Spanning Tree Problem, in Proceedings of IEEE World Congress on Computational Intelligence (CEC'2008), 2008, pp.3127--3133.

[13]

Huynh Thi Thanh Binh, Nguyen Duc Nghia, New multi-parent Recombination in Genetic Algorithm for Solving Bounded Diameter Minimum Spanning Tree Problem, in Proceedings of 1st Asian Conference on Intelligent Information and Database Systems, 2009, pp.283--288.

Digital Library

[14]

B.A. Julstrom, G.R. Raidl, A Permutation Coded Evolutionary for the Bounded Diameter Minimum Spanning Tree Problem, in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'2003), 2003, pp.2--7.

[15]

B.A. Julstrom, Encoding Bounded Diameter Minimum Spanning Trees with Permutations and Random Keys, in Proceedings of Genetic and Evolutionary Computational Conference (GECCO'2004), 2004.

[16]

B.A Julstrom BA, Greedy heuristics for the bounded-diameter minimum spanning tree problem, ACM Journal of Experimental Algorithmics, vol 14, 2009.

Digital Library

[17]

G. Kortsarz and D. Peleg, Approximating Shallow-light Trees, in Proceedings of the 8th Symposium on Discrete Algorithms, 1997, pp. 103--110.

Digital Library

[18]

G. Kortsarz and D. Peleg, Approximating the Weight of Shallow Steiner Trees, Discrete Application Mathematics, 93, 1999, pp. 265--285.

Digital Library

[19]

Nguyen Duc Nghia and Huynh Thi Thanh Binh, A New Recombination Operator for Solving Bounded Diameter Minimum Spanning Tree Problem, in Proceedings of RIVF'2007, LNCS, 2007.

[20]

C.C. Palmer and A. Kershenbaum, Representing Trees in Genetic Algorithms, in Proceedings of The First IEEE Conference on Evolutionary Computation, 1994, pp. 379--384.

[21]

R. Prim, Shortest Connection Networks and Some Generalization, Bell System Technical Journal, 36, 1957, pp. 1389--1401.

[22]

G.R. Raidl and B.A. Julstrom, Edge-sets: An Effective Evolutionary Coding of Spanning Trees, IEEE Transactions on Evolutionary Computation, 7, 2003, pp.225--239.

Digital Library

[23]

G.R. Raidl and B.A. Julstrom, Greedy Heuristics and an Evolutionary Algorithm for the Bounded-Diameter Minimum Spanning Tree Problem, in Proceeding of the ACM Symposium on Applied Computing, 2003, pp. 747--752.

Digital Library

[24]

K. Raymond, A Tree-based Algorithm for Distributed Mutual Exclusion, ACM Transactions on Computer Systems, 7 (1), 1989, pp. 61--77.

Digital Library

[25]

F. Rothlauf, Representations for Genetic and Evolutionary Algorithms, 2nd Edition, Springer-Verlag, 2006.

Digital Library

[26]

A. Singh and A.K. Gupta, Impoved Heuristics for the Bounded Diameter Minimum Spanning Tree Problem, Journal Soft Computing, 11, 2007, pp. 911--921.

Digital Library

Cited By

Gouveia LLeitner MLjubić I(2024)Common-Flow Formulations for the Diameter Constrained Spanning and Steiner Tree ProblemsCombinatorial Optimization and Applications10.1007/978-3-031-57603-4_3(37-58)Online publication date: 28-Jun-2024
https://doi.org/10.1007/978-3-031-57603-4_3
Pathak NKumar R(2023)Entropy guided evolutionary search for solving SudokuProgress in Artificial Intelligence10.1007/s13748-023-00297-7Online publication date: 25-Jan-2023
https://doi.org/10.1007/s13748-023-00297-7
Binh NNgoc NBinh HVan NYu S(2022)A family system based evolutionary algorithm for obstacle-evasion minimal exposure path problem in Internet of ThingsExpert Systems with Applications10.1016/j.eswa.2022.116943200(116943)Online publication date: Aug-2022
https://doi.org/10.1016/j.eswa.2022.116943
Show More Cited By

Index Terms

New heuristic and hybrid genetic algorithm for solving the bounded diameter minimum spanning tree problem
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

New Heuristic Approaches for the Bounded-Diameter Minimum Spanning Tree Problem

<P>Given a bound, the bounded-diameter minimum spanning tree BDMST problem seeks a spanning tree of minimum total weight with a diameter not exceeding the given diameter bound. Depending on the tightness of the bound, optimal solutions have different ...
New Heuristic Approaches for the Bounded-Diameter Minimum Spanning Tree Problem

<P>Given a bound, the bounded-diameter minimum spanning tree (BDMST) problem seeks a spanning tree of minimum total weight with a diameter not exceeding the given diameter bound. Depending on the tightness of the bound, optimal solutions have different ...
New Multi-parent Recombination in Genetic Algorithm for Solving Bounded Diameter Minimum Spanning Tree Problem
ACIIDS '09: Proceedings of the 2009 First Asian Conference on Intelligent Information and Database Systems

Given a connected, weighted, undirected graph G=(V, E) and a bound D, Bounded Diameter Minimum Spanning Tree problem (BDMST) seeks spanning tree on G with smallest weight in which no path between two vertices contains more than D edges. This problem is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

July 2009

2036 pages

ISBN:9781605583259

DOI:10.1145/1569901

General Chair:
Franz Rothlauf
University of Mainz, Germany

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO09

Sponsor:

GECCO09: Genetic and Evolutionary Computation Conference

July 8 - 12, 2009

Québec, Montreal, Canada

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
266
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gouveia LLeitner MLjubić I(2024)Common-Flow Formulations for the Diameter Constrained Spanning and Steiner Tree ProblemsCombinatorial Optimization and Applications10.1007/978-3-031-57603-4_3(37-58)Online publication date: 28-Jun-2024
https://doi.org/10.1007/978-3-031-57603-4_3
Pathak NKumar R(2023)Entropy guided evolutionary search for solving SudokuProgress in Artificial Intelligence10.1007/s13748-023-00297-7Online publication date: 25-Jan-2023
https://doi.org/10.1007/s13748-023-00297-7
Binh NNgoc NBinh HVan NYu S(2022)A family system based evolutionary algorithm for obstacle-evasion minimal exposure path problem in Internet of ThingsExpert Systems with Applications10.1016/j.eswa.2022.116943200(116943)Online publication date: Aug-2022
https://doi.org/10.1016/j.eswa.2022.116943
Vuppuluri PChellapilla P(2020)Serial and parallel memetic algorithms for the bounded diameter minimum spanning tree problemExpert Systems10.1111/exsy.1261038:2Online publication date: Aug-2020
https://doi.org/10.1111/exsy.12610
Steitz W(2015)New Heuristic Approaches for the Bounded-Diameter Minimum Spanning Tree ProblemINFORMS Journal on Computing10.1287/ijoc.2014.061727:1(151-163)Online publication date: Feb-2015
https://doi.org/10.1287/ijoc.2014.0617
Babar ZWaqas MHalim ZIslam M(2013)Genetic programming based degree constrained spanning tree extractionEighth International Conference on Digital Information Management (ICDIM 2013)10.1109/ICDIM.2013.6693966(241-246)Online publication date: Sep-2013
https://doi.org/10.1109/ICDIM.2013.6693966
Saha SKumar RJena SKumar RTuruk ADash M(2011)Improvement of bounded-diameter MST instances with hybridization of multi-objective EAProceedings of the 2011 International Conference on Communication, Computing & Security10.1145/1947940.1948036(468-473)Online publication date: 12-Feb-2011
https://dl.acm.org/doi/10.1145/1947940.1948036
Wu CTseng Y(2011)Data Compression by Temporal and Spatial Correlations in a Body-Area Sensor NetworkIEEE Transactions on Mobile Computing10.1109/TMC.2010.26410:10(1459-1472)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.1109/TMC.2010.264
Singh PVaid A(2011)Property Analysis and Enhancement in Recombination Operator of Edge-Set Encoding for Spanning TreeContemporary Computing10.1007/978-3-642-22606-9_20(169-179)Online publication date: 2011
https://doi.org/10.1007/978-3-642-22606-9_20

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents