Evolutionary algorithms with local search for combinatorial optimization
Mark Land, Richard K. Belew · 1998
The goal of global optimization is to minimize (or maximize) an objective function over its entire domain. Heuristic methods such as evolutionary algorithms and simulated annealing are often employed. Alternatively, it is sometimes acceptable to find a local optimum, which is as good as all solutions in its neighborhood. Local search methods are comparatively well-understood, and local optima can often be found efficiently even for problems in which global optimization is difficult [66]. Global/local hybrid algorithms combine aspects of both global and local optimization to search more effectively than either global or local optimization by themselves. Evolutionary algorithms using local search have frequently been applied to problems in continuous optimization with great success. Not only does the addition of local search substantially improve the performance of the evolutionary algorithm, but the hybrid often outperforms other global optimization techniques such as simulated annealing. In this dissertation we explore the effectiveness of evolutionary algorithms with local search in the combinatorial domain. We show that the EA+LS hybrid is more effective for graph bisection than either the EA or LS alone, and that it is competitive with simulated annealing. A new variant of the EA+LS is presented which interleaves the global and local search operators. We find that while crossover is valuable to an EA without LS in this problem, the addition of LS obviates the need for crossover. We also show how appropriate mutation sizes in an EA+LS depend on the size of local basins. These insights point to the possibility of instance-specific heuristics, in which the search algorithm is tailored to specific features of the instances under consideration. We show that Darwinian evolution is as effective as Lamarckian, and is more robust under changes to the genetic operators. In addition, we explore the effectiveness of steady-state vs. generational EAs, different local search lengths, and various local/global ratios.