A Kernighan-Lin local improvement heuristic that softens several hard problems in genetic algorithms

摘要

We present a local improvement heuristic for genetic algorithms, and term it a Kernighan-Lin style heuristic. We analyze the runtime cost of the heuristic, and show that it can be affordable. We then demonstrate through experiments that the heuristic provides very quick solutions to several problems which have been touted in the literature as especially hard ones for genetic algorithms. We suggest explanations for why the heuristic works so well on these problems.