The two-stage recombination operator and its application to the multiobjective 0/1 knapsack problem: A comparative study

Abstract

In this paper, we first propose a new recombination operator called the two-stage 
recombination and then we 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 following 
two 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. Initially, we propose two different approaches for the 
second stage: the general version and the restricted version. However, the application 
of the restricted version to the MOKP leads to an improved version which is more 
specific to this problem. The general and the MOKP-specific versions of the two-stage 
recombination are compared against three traditional crossovers using two well-known 
multiobjective evolutionary algorithms. Promising results are obtained. We also provide a 
comparison between the general version and the MOKP-specific version. (C) 2009 Elsevier 
Ltd. All rights reserved.