Multiobjective genetic programming approach to evolving heuristics for the bounded diameter minimum spanning tree problem: MOGP for BDMST

ABSTRACT

The bounded-diameter (or diameter-constrained) minimum spanning tree (BDMST) problem is a well-studied combinatorial optimization problem for which several heuristics such as: one-time tree construction (OTTC), center based tree construction(CBTC), iterative refinement (IR) and randomized greedy heuristics (RGH) have been developed. Very little work, however, has been done on producing heuristics for BDMSTs using evolutionary algorithms. In this paper we have used multiobjective genetic programming (MOGP) to explore the evolution of a set of heuristics for the BDMST problem. The quality of the Pareto fronts obtained from the MOGP-evolved heuristics is comparable to, or in some cases better than, the Pareto fronts generated by established, hand-crafted heuristics. MOGP is thus a very promising technique for finding heuristics for BDMSTs and more general multiobjective combinatorial optimizations.

REFERENCES

• 1: Judit Bar-Ilan , Guy Kortsarz , David Peleg, Generalized submodular cover problems and applications, Theoretical Computer Science, v.250 n.1-2, p.179-200, Jan 6, 2001 [doi>10.1016/S0304-3975(99)00130-9]
• 2: T. Bickle and L. Thiele. Genetic programming and redundancy. In J. Hopf, editor, Genetic Algorithms Within the Framework of Evolutionary Computation (Workshop at KI-94, Saarbrcken), pages 33--38, 1994.
• 3: S. Bleuler, M. Brack, L. Thiele, and E. Zitzler. Multiobjective genetic programming: Reducing bloat using SPEA2. In Congress on Evolutionary Computation CEC2001, pages 536--543. IEEE Press, 2001.
• 4: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 5: 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
• 6: Anikó Ekárt , S. Z. Németh, Selection Based on the Pareto Nondomination Criterion for Controlling Code Growth in Genetic Programming, Genetic Programming and Evolvable Machines, v.2 n.1, p.61-73, March 2001 [doi>10.1023/A:1010070616149]
• 7: Carlos M. Fonseca , Peter J. Fleming, Genetic Algorithms for Multiobjective Optimization: FormulationDiscussion and Generalization, Proceedings of the 5th International Conference on Genetic Algorithms, p.416-423, June 01, 1993
• 8: Bryant A. Julstrom, Greedy heuristics for the bounded diameter minimum spanning tree problem, Journal of Experimental Algorithmics (JEA), 14, August 2009
• 9: J. Knowles and D. Corne. On metrics for comparing nondominated sets. In Congress on Evolutionary Computation (CEC'2002), volume 1, pages 711--716, Piscataway, New Jersey, May 2002. IEEE Press.
• 10: Guy Kortsarz , David Peleg, Approximating shallow-light trees, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.103-110, January 05-07, 1997, New Orleans, Louisiana, United States
• 11: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 12: Rajeev Kumar , Peter Rockett, Improved sampling of the Pareto-front in multiobjective genetic optimizations by steady-state evolution: a Pareto converging genetic algorithm, Evolutionary Computation, v.10 n.3, p.283-314, Fall 2002 [doi>10.1162/106365602760234117]
• 13: Rajeev Kumar , Pramod Kumar Singh, On quality performance of heuristic and evolutionary algorithms for biobjective minimum spanning trees, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277394]
• 14: Sean Luke , Liviu Panait, Fighting Bloat with Nonparametric Parsimony Pressure, Proceedings of the 7th International Conference on Parallel Problem Solving from Nature, p.411-421, September 07-11, 2002
• 15: Madhav V. Marathe , R. Ravi , Ravi Sundaram , S. S. Ravi , Daniel J. Rosenkrantz , Harry B. Hunt, III, Bicriteria network design problems, Journal of Algorithms, v.28 n.1, p.142-171, July 1, 1998 [doi>10.1006/jagm.1998.0930]
• 16: Nicholas Freitag McPhee , Justin Darwin Miller, Accurate Replication in Genetic Programming, Proceedings of the 6th International Conference on Genetic Algorithms, p.303-309, July 15-19, 1995
• 17: 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]
• 18: S. Silva and L. Almeida. Dynamic maximum tree depth -- A simple technique for avoiding bloat in tree-based GP. In E. Cantú-Paz, J. A. Foster, and K. Deb, editors, GECCO-2003, pages 1776--1787, LNCS, Chicago, IL, USA, 2003. Springer.
• 19: S. Silva and E. Costa. Dynamic limits for bloat control: Variations on size and depth. In Genetic and Evolutionary Computation (GECCO-2004), pages 666--677. Springer, 2004.
• 20: Terence Soule , James A. Foster, Effects of code growth and parsimony pressure on populations in genetic programming, Evolutionary Computation, v.6 n.4, p.293-309, Winter 1998 [doi>10.1162/evco.1998.6.4.293]
• 21: Walter Alden Tackett, Genetic Programming for Feature Discovery and Image Discrimination, Proceedings of the 5th International Conference on Genetic Algorithms, p.303-311, June 01, 1993
• 22: E. Zitzler and L.Thiele. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach. IEEE Trans. Evolutionary Computation, 3:257--271, 1999.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Stochastic programming

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program synthesis

General Terms:
Algorithms, Design, Experimentation

Keywords:
bloat, combinatorial optimization, genetic algorithm, genetic programming, heuristics, multiobjective optimization, optimization methods, pareto front