Generating SAT Local-Search Heuristics Using a GP Hyper-Heuristic Framework

1. Abbass, H.A.: MBO: Marriage in honey bees optimization - A haplometrosis polygynous swarming approach. In: Proceedings of the, Congress on Evolutionary Computation CEC2001, COEX, World Trade Center, 159 Samseong-dong, Gangnam-gu, Seoul, Korea, 27-30. pp. 207–214, IEEE Press, Los Alamitos (2001)

   Google Scholar 

2. Boyan, J., Moore, A.: Learning evaluation functions to improve optimization by local search. Journal of Machine Learning Research 1, 77–112 (2000)

   Article  Google Scholar 

3. Burke, E.K., Hyde, M.R., Kendall, G.: Evolving bin packing heuristics with genetic programming. In: Runarsson, T.P., Beyer, H.-G., Burke, E.K., Merelo-Guervós, J.J., Whitley, L.D., Yao, X. (eds.) PPSN 2006. LNCS, vol. 4193, pp. 860–869. Springer, Heidelberg (2006)

   Chapter  Google Scholar 

4. Burke, E.K., Kendall, G., Newall, J., Hart, E., Ross, P., Schulenburg, S.: Hyper-heuristics: an emerging direction in modern search technology. In: Glover, F., Kochenberger, G. (eds.) Handbook of Metaheuristics, pp. 457–474. Kluwer Academic Publishers, Dordrecht (2003)

   Chapter  Google Scholar 

5. Burke, E.K., Kendall, G., Soubeiga, E.: A tabu-search hyperheuristic for timetabling and rostering. Journal of Heuristics 9(6), 451–470 (2003)

   Article  Google Scholar 

6. Burke, E.K., Petrovic, S., Qu, R.: Case-based heuristic selection for timetabling problems. Journal of Scheduling 9(2), 115–132 (2006)

   Article  MATH  Google Scholar 

7. Cowling, P., Kendall, G., Han, L.: An investigation of a hyperheuristic genetic algorithm applied to a trainer scheduling problem. In: Fogel, D.B., El-Sharkawi, M.A., Yao, X., Greenwood, G., Iba, H., Marrow, P., Shackleton, M. (eds.) Proceedings of the 2002 Congress on Evolutionary Computation CEC2002, pp. 1185–1190. IEEE Press, Los Alamitos (2002)

   Chapter  Google Scholar 

8. Davis, M., Logemann, G., Loveland, D.: A machine program for theorem-proving. Commun. ACM 5(7), 394–397 (1962)

   Article  MATH  MathSciNet  Google Scholar 

9. Fukunaga, A.: Automated discovery of composite SAT variable selection heuristics. In: Proceedings of the National Conference on Artificial Intelligence, pp. 641–648. AAAI, Menlo Park (2002)

   Google Scholar 

10. Fukunaga, A.: Evolving local search heuristics for SAT using genetic programming. In: Deb, K., al., e. (eds.) GECCO 2004. LNCS, vol. 3103, pp. 483–494. Springer, Heidelberg (2004)

    Google Scholar 

11. Gent, I.P., Walsh, T.: Towards an understanding of hill-climbing procedures for sat. In: Proc. of AAAI-1993, Washington, DC, pp. 28–33 (1993)

    Google Scholar 

12. Gottlieb, J., Marchiori, E., Rossi, C.: Evolutionary algorithms for the satisfiability problem. Evol. Comput. 10(1), 35–50 (2002)

    Article  Google Scholar 

13. Koza, J.R.: Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA (1992)

    MATH  Google Scholar 

14. Langdon, W.B., Poli, R.: Foundations of Genetic Programming. Springer, Heidelberg (2002)

    Book  MATH  Google Scholar 

15. Marchiori, E., Rossi, C.: A flipping genetic algorithm for hard 3-SAT problems. In: Banzhaf, W., Daida, J., Eiben, A.E., Garzon, M.H, Honavar, V., Jakiela, M., Smith, R.E., (eds). Proceedings of the Genetic and Evolutionary Computation Conference Orlando, Florida, USA, 13-17, 1999, vol. 1, pp. 393–400, Morgan Kaufmann, San Francisco (1999)

    Google Scholar 

16. Poli, R., Woodward, J., Burke, E.: A histogram-matching approach to the evolution of bin-packing strategies. In: Proceedings of the IEEE Congress on Evolutionary Computation, Singapore (accepted, 2007)

    Google Scholar 

17. Rossi, C., Marchiori, E., Kok, J.N.: An adaptive evolutionary algorithm for the satisfiability problem. SAC 1, 463–469 (2000)

    Article  Google Scholar 

18. Schuurmans, D., Southey, F.: Local search characteristics of incomplete SAT procedures. Artificial Intelligence 132(2), 121–150 (2001)

    Article  MATH  MathSciNet  Google Scholar 

19. Selman, B., Kautz, H.: Domain-independent extensions to GSAT: solving large structured satisfiability problems. In: Proceedings of the International Joint Conference on Artificial Intelligence(IJCAI-1993), Chambéry, France (1993)

    Google Scholar 

20. Selman, B., Kautz, H.A., Cohen, B.: Noise strategies for improving local search. In: Proceedings of the Twelfth National Conference on Artificial Intelligence (AAAI 1994), Seattle, pp. 337–343 (1994)

    Google Scholar 

21. Selman, B., Levesque, H.J., Mitchell, D.: A new method for solving hard satisfiability problems. In: Rosenbloom, P., Szolovits, P. (eds.) Proceedings of the Tenth National Conference on Artificial Intelligence, Menlo Park, California, pp. 440–446. AAAI Press, Menlo Park (1992)

    Google Scholar 

22. Silva, D.L., O’Brien, R., Soubeiga, E.: An ant algorithm hyperheuristic for the project presentation scheduling problem. In: Fogel, D.B., El-Sharkawi, M.A., Yao, X., Greenwood, G., Iba, H., Marrow, P., Shackleton, M. (eds.) Proceedings of the 2005 IEEE Congress on Evolutionary Computation, pp. 92–99 (2005)

    Google Scholar 

Download references