Generating meta-heuristic optimization code using ADATE

Local Search based meta-heuristic methods for finding good solutions to hard combinatorial optimization problems have attained a lot of success, and a plethora of methods exist, each with its own successes, and also with its own parameter settings and other method-specific details. At the same time, experience is needed to implement highly competitive code, and some of the experience applied is not easy to quantify. ADATE is a system to automatically generate code based on a set of input-output specifications, and can work in vastly different domains. It generates code in a subset of the programming language ML and works by searching for transformations of purely functional ML programs. Code automatically generated by the ADATE system compares with state-of-the-art handcrafted meta-heuristic optimization code. In particular, the programs generated by ADATE target the move selection part of BOOP–Boolean Optimization Problems. The baseline is a highly successful Tabu Search implementation. Comparisons are made for versions running for a limited number of iterations, being suitable for applications needing a short response time. The computational results show that the ADATE system is able to generate highly competitive code that produces more optimal solutions to hard BOOP instances within given iteration limits than the previously published Tabu Search implementation. The automatically generated code also gives new insights into the general design of meta-heuristic mechanisms, and contains novel search mechanisms.