A bounded diameter minimum spanning tree evolutionaryalgorithm based on double chromosome

ABSTRACT

The Bounded Diameter Minimum Spanning Tree problem (BDMST) is a classical combinatorial optimization problem. In this paper,we propose a double chromosome evolutionary algorithm based on level coding and permutation coding for the BDMST problem. Double chromosome coding achieves the correspondences of the code and the solution of BDMST problem, so that the local search can be implemented more efficiently. A new crossover operator is design based on the double chromosome coding. The proposed algorithm keeps diversity and preferable convergence, because The offspring not only inherit the parent's some sub-tree, but also generate some new edges. Designed a novel decoding strategy to the level code chromosome, might find the predecessor that associated with smaller costs. The proposed algorithm is empirically compared to edge-set coded genetic algorithm and a variable neighborhood search implementation on Euclidean instances based on complete graphs with up to 1000 nodes considering either solution quality as well as computation time. It turns out that the evolutionary algorithm used double chromosome performs best the edge-set EA and the variable neighborhood search implementation concerning computation time.

REFERENCES

• 1: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 2: Narsingh Deo , Ayman Abdalla, Computing a Diameter-Constrained Minimum Spanning Tree in Parallel, Proceedings of the 4th Italian Conference on Algorithms and Complexity, p.17-31, March 01, 2000
• 3: K. Bala, K. Petropoulos, and T. E. Stern. Multicasting in a linear lightwave network. In IEEE Conference on Computer Communications, pages 1350--1358, 1993.
• 4: A. Bookstein , S. T. Klein, Compression of correlated bit-vectors, Information Systems, v.16 n.4, p.387-400, 1991 [doi>10.1016/0306-4379(91)90030-D]
• 5: Kerry Raymond, A tree-based algorithm for distributed mutual exclusion, ACM Transactions on Computer Systems (TOCS), v.7 n.1, p.61-77, Feb. 1989 [doi>10.1145/58564.59295]
• 6: Günther R. Raidl , Bryant A. Julstrom, Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida [doi>10.1145/952532.952678]
• 7: Julstrom, B.A., Raidl, G.R.: A permutation-coded evolutionary algorithm for the bounded-diameter minimum spanning tree problem {J}. 2003 Genetic and Evolutionary Computation Conference Workshop Program, 2003:2--7
• 8: Alok Singh , Ashok K. Gupta, Improved heuristics for the bounded-diameter minimum spanning tree problem, Soft Computing - A Fusion of Foundations, Methodologies and Applications, v.11 n.10, p.911-921, May 2007 [doi>10.1007/s00500-006-0142-y]
• 9: Julstrom B.A.. Encoding bounded-diameter spanning trees with permutations and with random keys.Lecture Notes in Computer Science, 2004, 3102: 1272--1281
• 10: Martin Gruber, G, agunther R. Raidl Variable Neighborhood Search for the Bounded Diameter Minimum Spanning Tree Problem 18th Mini Euro Conference on VNS, 2005
• 11: Jano van Hemert, Hard problem instances of Bounded Diameter Minimum Spanning Tree, Generalised Minimum Spanning Tree, and Multidimensional Knapsack Problems. Dissertanten Seminar 2005/12/15 (http://www.vanhemert.co.uk.)
• 12: Günther R. Raidl , Bryant A. Julstrom, Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida [doi>10.1145/952532.952678]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

General Terms:
Algorithms

Keywords:
double chromosome, evolutionary algorithm, local search, the bounded diameter minimum spanning tree