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


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.