In this paper, we propose a new recombination operator and test its performance in the context of the multiobjective 0/1 knapsack problem (MOKP). The proposed recombination operator generates only one offspring solution from a selected pair of parents according to the two following stages. In the first stage, called genetic shared-information stage or similarity-preserving stage, the generated offspring inherits all parent similar genes (i.e.; genes or decision variables having the same positions and the same values in both parents). In the second stage, called problem fitness-information stage, the parent non-similar genes (i.e.; genes or decision variables having the same positions but different values regarding the two parents) are selected from one of the two parents using some fitness information. In fact, we propose three different approaches (i.e.; versions) for the second stage. The first approach (i.e.; the general approach) can be applied to any multiobjective combinatorial problem and can be summarized as follows: each parent non-similar gene is selected from the first parent (respectively the second parent) according to a probability which depends on some fitness function (e.g., the linear scalarizing function) evaluating the fitness of the first parent (respectively the second parent). The second approach (i.e.; the restricted approach) can only be applied to the multiobjective combinatorial problems for which each gene has its own fitness called the gene's fitness and can be summarized as follows: each parent non-similar gene is selected from the first parent (respectively the second parent) according to a probability which depends on the gene's fitness value induced by the value of this gene in the first parent (respectively the second parent). The third approach (i.e.; the MOKP-specific approach) is specific to the MOKP and can be summarized as follows: the parent non-common items (i.e.; items included in one and only one parent solution regarding the current pair of parents) undergo a greedy insertion heuristic which gives priority to the best fitting parent non-common items (i.e.; those having a high quality and ensuring the offspring feasibility regarding the MOKP structure). The two-stage recombination operator is compared against three traditional crossovers (in fact, the one-point, the two-point and the uniform crossovers) using two well-known multiobjective evolutionary algorithms (MOEAs); namely SPEA and NSGA-II. The experimental results show that all the three versions of the proposed recombination operator (i.e.; the general version, the restricted version and the MOKP-specific version) significantly outperform both the one-point and the two-point crossovers in terms of convergence. The convergence performance of the general version (respectively the restricted version) in comparison with the uniform crossover is however sensitive to the number of generations (respectively the MOKP instance and the MOEA context), whereas the MOKP-specific version always outperforms the uniform crossover. As for the diversity performance, both the restricted and the MOKP-specific versions outperform all the three traditional crossovers. However, the diversity performance of the general version is essentially sensitive to the MOEA context.
Citation
Rapport N°:01/02/08 Lab. Informatique & Aide à la Décision, Faculté des Sciences, Université Hassan II-Ain Chock, Casablanca, Morocco.