Finding critical backbone structures with genetic algorithms

ABSTRACT

This paper introduces the concept of a critical backbone as a minimal set of variable or part of the solution necessary to be within the basin of attraction of the global optimum. The concept is illustrated with a new class of test problems Backbone in which the critical backbone structure is completely transparent. The performance of a number of standard heuristic search methods is measure for this problem. It is shown that a hybrid genetic algorithm that incorporates a descent algorithm solves this problem extremely efficiently. Although no rigorous analysis is given the problem is sufficiently transparent that this result is easy to understand. The paper concludes with a discussion of how the emergence of a critical backbone may be the salient feature in a phase transition from typically easy to typically hard problems.

References

1. R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky. Determining computational complexity from characteristic 'phase transisition'. Nature, 400:133--137, 1999.
2. R. Williams, C. Gomes, and B. Selman. Backdoors to typical case complexity.
3. P. Kilby, J. Slaney, and T. Walsh S. Thiebaux. Backbones and backdoors in satisfiability. In 2005, editor, Proceedings of the 20th National conference on artificial intelligence and the 17th innovative appllications of artificial intelligence conference, pages 1368--1373, Menlo park, CA. AAAI/MIT Press.
4. W. Zhang, A. Rangan, and M. Looks. Backbone guided local search for maximum satisfiability. In Proc. of the 18th Intern. Joint Conference on Artifical Intelligence, pages 1179--84, 2003.
5. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220:671--680, 1983.
6. A. Prügel-Bennett and J. L. Shapiro. The dynamics of a genetic algorithm for simple random Ising systems. Physica D, 104:75--114, 1997.
7. J. E. Baker. Reducing bias and inefficiency in the selection algorithm. In Proceedings of the Second International Conference on Genetic Algorithms. Lawrence Erlbaum Associates (Hillsdale), 1987.
8. A. Prügel-Bennett. The mixing rate of different crossover operators. In W. N. Martin and W. M. Spears, editors, Foundations of Genetic Algorithms 6, pages 261--274. Morgan Kaufmann, San Francisco, 2001.
9. P. Galinier and J. K. Hao. Hybrid evolutionary algorithms for graph coloring. Journal of Combinatorial Optimization, 3(4):379--397, 1999.
10. C. A. Glass and A. Prügel-Bennett. Genetic algorithms for graph colouring: Exploration of Galinier and Hao's algorithm. Journal of Combinatorial Optimization, 7:229--236, 2003.
11. O. C. Martin, R. Monasson, and R. Zecchina. Statistical mechanics methods and phase transitions in optimization problems. Theoretical Computer Science, 265(1-2):3--67, 2001.
12. A. Prügel-Bennett. Symmetry breaking in population-based optimization. IEEE Transactions on Evolutionary Computation, 8(1):63--79, 2004.

Index Terms

• Theory of computation

  • Design and analysis of algorithms