Genetic Diversity and Effective Crossover in Evolutionary Many-Objective Optimization


Abstract

In this work, we analyze genetic diversity of Pareto optimal solutions (POS) and study effective crossover operators in evolutionary many-objective optimization. First we examine the diversity of genes in the true POS on many-objective 0/1 knapsack problems with up to 20 items (bits), showing that genes in POS become noticeably diverse as we increase the number of objectives. We also verify the effectiveness of conventional two-point crossover, Local Recombination that selects mating parents based on proximity in objective space, and two-point and uniform crossover operators Controlling the maximum number of Crossed Genes (CCG). We use NSGA-II, SPEA2, IBEA ε+ and MSOPS, which adopt different selection methods, and many-objective 0/1 knapsack problems with n = {100,250,500,750,1000} items (bits) and m = {2,4,6,8,10} objectives to verify the search performance of each crossover operator. Simulation results reveal that Local Recombination and CCG operators significantly improve search performance especially for NSGA-II and MSOPS, which have high diversity of genes in the population. Also, results show that CCG operators achieve higher search performance than Local Recombination for m ≥ 4 objectives and that their effectiveness becomes larger as the number of objectives m increases.