Analyzing the Performance of Hybrid Evolutionary Algorithms for the Multiobjective Quadratic Assignment Problem

It is now generally accepted that the performance of evolutionary algorithms can nearly always be significantly improved through the inclusion of some form of local search. Most often, practitioners have developed hybrid algorithms in which all individuals created during the evolutionary process are subjected to a local improvement operator. This form of algorithm can be viewed as an evolutionary search for good starting points from which to apply the local search procedure and has proven very successful over a wide range of combinatorial optimization problems. However, a large number of possible implementation strategies exist for how best to incorporate the local search into the evolutionary process. In this work, we extend some commonly used static (fitness landscape) and dynamic (incorporating information concerning the run-time behavior of a particular search algorithm) analysis techniques into the multiobjective realm, and analyze the structure of the widely-studied multiobjective quadratic assignment problem. In particular, we show that the advantages of a state-of-the-art hybrid evolutionary algorithm over a simpler iterated local search algorithm can be explained reasonably well through a random walk analysis of the effects of recombination.