An Empirical Study on the Effect of Mating Restriction on the Search Ability of EMO Algorithms

摘要

This paper examines the effect of mating restriction on the search ability of EMO algorithms. First we propose a simple but flexible mating restriction scheme where a pair of similar (or dissimilar) individuals is selected as parents. In the proposed scheme, one parent is selected from the current population by the standard binary tournament selection. Candidates for a mate of the selected parent are winners of multiple standard binary tournaments. The selection of the mate among multiple candidates is based on the similarity (or dissimilarity) to the first parent. The strength of mating restriction is controlled by the number of candidates (i.e., the number of tournaments used for choosing candidates from the current population). Next we examine the effect of mating restriction on the search ability of EMO algorithms to find all Pareto-optimal solutions through computational experiments on small test problems using the SPEA and the NSGA-II. It is shown that the choice of dissimilar parents improves the search ability of the NSGA-II on small test problems. Then we further examine the effect of mating restriction using large test problems. It is shown that the choice of similar parents improves the search ability of the SPEA and the NSGA-II to efficiently find near Pareto-optimal solutions of large test problems. Empirical results reported in this paper suggest that the proposed mating restriction scheme can improve the performance of EMO algorithms for many test problems while its effect is problem-dependent and algorithm-dependent.