an analysis on recombination in multi-objective evolutionary optimization
Recombination (or called crossover ) operators are a kind of characterizing feature of evolutionary algorithms (EAs). The usefulness of recombination operators has been verified empirically in many practical applications, and has also been theoretically studied in single-objective optimization. For multi-objective optimization, however, there lacks strong evidence on whether the recombination operators can lead to a better running time. In this paper, we establish some theoretical support to the use of recombination in multi-objective optimization. We analyze the running time of REMO, a simple multi-objective EA with a recombination operator, on two well-studied bi-objective problems, i.e., the LOTZ and the COCZ problems. Our analysis results disclose that the average running time of REMO on LOTZ and COCZ is ?(n 2 ) and ?(n log n), respectively, improved from ?(n 3 ) and ?(n 2 ) as when the recombination operator is turned off, respectively. These results imply that the recombination operator is crucial for the efficiency of REMO on these two problems. The analysis also suggests that, generally, recombination operators can be helpful to multi-objective optimization as they may accelerate the filling of the Pareto front through recombining diverse solutions.
recombination crossover evolutionary algorithms multi-objective optimization