Hybrid evolutionary algorithms on minimum vertex cover for random graphs

ABSTRACT

This paper analyzes the hierarchical Bayesian optimization algorithm (hBOA) on minimum vertex cover for standard classes of random graphs and transformed SAT instances. The performance of hBOA is compared with that of the branch-and-bound problem solver (BB), the simple genetic algorithm (GA) and the parallel simulated annealing (PSA). The results indicate that BB is significantly outperformed by all the other tested methods, which is expected as BB is a complete search algorithm and minimum vertex cover is an NP-complete problem. The best performance is achieved with hBOA; nonetheless, the performance differences between hBOA and other evolutionary algorithms are relatively small, indicating that mutation-based search and recombination-based search lead to similar performance on the tested problem instances.

REFERENCES

• 1: F. N. Abu-Khzam, R. L. Collins, M. R. Fellows, M. A. Langston, W. H. Suters, and C. T. Symons. Kernelization algorithms for the vertex cover problem: Theory and experiments. In Proceedings ACM-SIAM Workshop on Algorithm Engineering and Experiments (ALENEX '04), New Orleans, LA, 2004.
• 2: Shummet Baluja, Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning, Carnegie Mellon University, Pittsburgh, PA, 1994
• 3: M. Bauer and O. Golinelli. Core percolation in random graphs: a critical phenomena analysis. Eur. Phys. J. B, 24:339, 2001.
• 4: B. Bollobas. Random Graphs. Cambridge University Press, Cambridge, UK, 2nd edition, 2001.
• 5: D. M. Chickering, D. Heckerman, and C. Meek. A Bayesian approach to learning Bayesian networks with local structure. Technical Report MSR--TR--97--07, Microsoft Research, Redmond, WA, 1997.
• 6: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 7: A. Das and B. K. Chakrabarti, editors. Quantum Annealing and Related Optimization Methods, volume 679. Springer, New York, 2005.
• 8: P. Erdos and A. Renyi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci., 5:17, 1960.
• 9: Nir Friedman , Moises Goldszmidt, Learning Bayesian networks with local structure, Learning in graphical models, MIT Press, Cambridge, MA, 1999
• 10: 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
• 11: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 12: Dan Gusfield , Satish Eddhu , Charles Langley, Efficient Reconstruction of Phylogenetic Networks with Constrained Recombination, Proceedings of the IEEE Computer Society Conference on Bioinformatics, p.363, August 11-14, 2003
• 13: Georges R. Harik, Finding Multimodal Solutions Using Restricted Tournament Selection, Proceedings of the 6th International Conference on Genetic Algorithms, p.24-31, July 15-19, 1995
• 14: Alexander K. Hartmann , Heiko Rieger, New Optimization Algorithms in Physics, John Wiley & Sons, 2004
• 15: AK Hartmann, Phase Transitions in Combinatorial Optimization Problems - Basics, Algorithms and Statistical Mechanics, Wiley-VCH, 2005
• 16: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 17: H. Hongwei, X. Xuezhou, X. Jin, and B. Zheng. Solving vertex covering problems using hybrid genetic algorithms. In Proceedings of the 5th International Conference on Signal Processing, pages 1663--1666, 2000.
• 18: X. Huang, J. Lai, and S. F. Jennings. Maximum common subgraph: Some upper bound and lower bound results. BMC Bioinformatics, 7(Suppl 4):S6, 2006.
• 19: R. M. Karp. Reducibility among combinatorial problems. In Symposium on the Complexity of Computer Computations, pages 85--103, Yorktown Heights, NY, 1972. Plenum, NY.
• 20: S. Khuri and T. Büack. An evolutionary heuristic for the minimum vertex cover problem. Genetic Algorithms within the Framework of Evolutionary Computation: Proceedings of the KI94 Workshop, pages 86--90, 1994.
• 21: S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220:671--680, 1983.
• 22: K. Kotecha and N. Gambhava. A hybrid genetic algorithm for minimum vertex cover problem. In B. Prasad, editor, The First Indian International Conference on Artificial Intelligence, pages 904--913, Hyderabad, 2003. IICAI.
• 23: P. Larrañaga and J. A. Lozano, editors. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer, Boston, MA, 2002.
• 24: E. L. Lawler and D. E. Wood. Branchandbound methods: a survey. Operational Research 14:699, University of Michigan, Ann Arbor, Ann Arbor, MI, 1966.
• 25: Reinhard Lüling , Burkhard Monien, Load Balancing for Distributed Branch and Bound Algorithms, Proceedings of the 6th International Parallel Processing Symposium, p.543-548, March 01, 1992
• 26: M. Mézard, G. Parisi, and R. Zecchina. Analytic and algorithmic solution of random satisfiability problems. Science, 297:812, 2002.
• 27: R. Monasson and S. Cocco. rajectories in phase diagrams, growth processes, and computational complexity: How search algorithms solve the 3satisfiability problem. Phys. Rev. Lett., 86:1654, 2001.
• 28: R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky. Determining computational complexity from characteristic phase transitions. Nature, 400:133, 1999.
• 29: Heinz Mühlenbein , Gerhard Paass, From Recombination of Genes to the Estimation of Distributions I. Binary Parameters, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.178-187, September 22-26, 1996
• 30: M. Pelikan. Hierarchical Bayesian optimization algorithm: Toward a new generation of evolutionary algorithms. SpringerVerlag, 2005.
• 31: M. Pelikan and D. E. Goldberg. Escaping hierarchical traps with competent genetic algorithms. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO2001), pages 511--518, 2001. Also IlliGAL Report No. 2000020.
• 32: Martin Pelikan , David E. Goldberg , Fernando G. Lobo, A Survey of Optimization by Building and Using Probabilistic Models, Computational Optimization and Applications, v.21 n.1, p.5-20, January 2002 [doi>10.1023/A:1013500812258]
• 33: M. Pelikan and A. Hartmann. Searching for ground states of Ising spin glasses with hierarchical BOA and cluster exact approximation. In E. CantúPaz, M. Pelikan, and K. Sastry, editors, Scalable optimization via probabilistic modeling: From algorithms to applications. Springer, 2006.
• 34: Martin Pelikan , Kumara Sastry , Erick Cantú-Paz, Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications (Studies in Computational Intelligence), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 35: K. Sastry. Evaluationrelaxation schemes for genetic and evolutionary algorithms. Master's thesis, University of Illinois at UrbanaChampaign, Department of General Engineering, Urbana, IL, 2001. Also IlliGAL Report No. 2002004.
• 36: E. Tsang. Foundations of Constraint Satisfaction. Academic Press, London, 1993.
• 37: P.J. Wan, L. Liu, and O. Frieder. Optimal placement of wavelength converters in trees and trees of rings. In Proceedings. Eight International Conference on Computer Communications and Networks, pages 392--397, 1999.
• 38: M. Weigt and A. K. Hartmann. Minimal vertex covers on finite connectivity random graphs ------ A hardsphere lattice gas picture. Phys. Rev. E, 63:056127, 2000.
• 39: M. Weigt and A. K. Hartmann. The number guards needed by a museum ---- a phase transition in vertex covering of random graphs. Phys. Rev. Lett., 84:6118, 2000.
• 40: M. Weigt and A. K. Hartmann. The typicalcase complexity of a vertex covering algorithm on finite connectivity random graphs. Phys. Rev. Lett., 86:1658, 2001.
• 41: K. Xu, F. Boussemart, F. Hemery, and C. Lecoutre. A simple model to generate hard satisfiable instances. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI), pages 337--342, Edinburgh, Scotland, 2005.
• 42: K. Xu and W. Li. Exact phase transitions in random constraint satisfaction problems. Artificial Intelligence Research, 12:93103, 2000.
• 43: K. Xu and W. Li. Many hard examples in exact phase transitions with application to generating hard satisfiable instances. Technical Report cs.CC/0302001, 2003.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms

Keywords:
branch and bound, genetic algorithm, hierarchical BOA, minimum vertex cover, simulated annealing