Grammar-based Genetic Programming for evolving variable ordering heuristics

Genetic Programming has been used for the automatic creation of heuristics to address problems of boolean satisfiability and other complex computational problems. This paper presents a methodology to evolve variable ordering heuristics for constraint satisfaction problems, though a hyper-heuristic model based on genetic programming and a context-free grammar. We present an analysis of the efficiency of new heuristics generated against human-design heuristics and the generality level reached by solving instances with different parameterization, as well as an analysis of the behavior of heuristics generated with different training instances over the problem domain. The results show that in most of cases, the heuristics generated by our approach overcome the performance of human-design heuristic.