Automatic Tuning of GRASP with Evolutionary Path-Relinking

摘要

Heuristics for combinatorial optimization are often controlled by discrete and continuous parameters that define its behavior. The number of possible configurations of the heuristic can be large, resulting in a difficult analysis. Manual tuning can be time-consuming, and usually considers a very limited number of configurations. An alternative to manual tuning is automatic tuning. In this paper, we present a scheme for automatic tuning of GRASP with evolutionary path-relinking heuristics. The proposed scheme uses a biased random-key genetic algorithm (BRKGA) to determine good configurations. We illustrate the tuning procedure with experiments on three optimization problems: set covering, maximum cut, and node capacitated graph partitioning. For each problem we automatically tune a specific GRASP with evolutionary path-relinking heuristic to produce fast effective procedures.