Variable space diversity, crossover and mutation in MOEA solving many-objective knapsack problems

• Published in: Annals of mathematics and artificial intelligence 2013-08, Vol.68 (4), p.197-224
• Main Authors: Sato, Hiroyuki, Aguirre, Hernán, Tanaka, Kiyoshi
• Format: Article
• Language: English
• Subjects: Artificial Intelligence; Complex Systems; Computer Science; Crossovers; Effectiveness; Genes; Knapsack problem; Mathematical analysis; Mathematical models; Mathematics; Multiple objective analysis; Mutation; Mutations; Operators; Searching
• ISSN: 1012-2443; 1573-7470
• DOI: 10.1007/s10472-012-9293-y

In this work, we analyze variable space diversity of Pareto optimal solutions (POS) and study the effectiveness of crossover and mutation operators in evolutionary many-objective optimization. First we examine the diversity of variables in the true POS on many-objective 0/1 knapsack problems with up to 20 items (bits), showing that variables in POS become noticeably diverse as we increase the number of objectives. We also verify the effectiveness of conventional two-point and uniform crossovers, Local Recombination that selects mating parents based on proximity in objective space, and two-point and uniform crossover operators which Controls 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 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. In addition, the contribution of CCG and mutation operators for the solutions search is analyzed and discussed.