 |
    |
Distance-Based Analysis of Crossover Operators for Many-Objective Knapsack Problems
Hisao Ishibuchi, Yuki Tanigaki, Hiroyuki Masuda, and Yusuke Nojima
Department of Computer Science and Intelligent Systems, Graduate School of Engineering, Osaka Prefecture University, 1-1 Gakuen-cho, Naka-ku, Sakai, Osaka 599-8531, Japanhisaoi@cs.osakafu-u.ac.jp
yuki.tanigaki@ci.cs.osakafu-u.ac.jp
hiroyuki.masuda@ci.cs.osakafu-u.ac.jp
nojima@cs.osakafu-u.ac.jp
Abstract. It has been reported for multi-objective knapsack problems that the recombination of similar parents often improves the performance of evolutionary multi-objective optimization (EMO) algorithms. Recently performance improvement was also reported by exchanging only a small number of genes between two parents (i.e., crossover with a very small gene exchange probability) without choosing similar parents. In this paper, we examine these performance improvement schemes through computational experiments where NSGA-II is applied to 500-item knapsack problems with 2-10 objectives. We measure the parent-parent distance and the parent-offspring distance in computational experiments. Clear performance improvement is observed when the parent-offspring distance is small. To further examine this observation, we implement a distance-based crossover operator where the parent-offspring distance is specified as a user-defined parameter. Performance of NSGA-II is examined for various parameter values. Experimental results show that an appropriate parameter value (parent-offspring distance) is surprisingly small. It is also shown that a very small parameter value is beneficial for diversity maintenance.
Keywords: Mating schemes, evolutionary multiobjective optimization (EMO), many-objective optimization, knapsack problems, NSGA-II
LNCS 8672, p. 600 ff.
lncs@springer.com
© Springer International Publishing Switzerland 2014