Automatic Grammar-Based Design of Heuristic Algorithms for Unconstrained Binary Quadratic Programming

摘要

Automatic methods have been applied to find good heuristic algorithms to combinatorial optimization problems. These methods aim at reducing human efforts in the trial-and-error search for promising heuristic strategies. We propose a grammar-based approach to the automatic design of heuristics and apply it to binary quadratic programming. The grammar represents the search space of algorithms and parameter values. A solution is represented as a sequence of categorical choices, which encode the decisions taken in the grammar to generate a complete algorithm. We use an iterated F-race to evolve solutions and tune parameter values. Experiments show that our approach can find algorithms which perform better than or comparable to state-of-the-art methods, and can even find new best solutions for some instances of standard benchmark sets.