Distance-Based Analysis of Crossover Operators for Many-Objective Knapsack Problems
Distance-Based Analysis of Crossover Operators for Many-Objective Knapsack Problems
复制标题
DOI：
10.1007/978-3-319-10762-2_59
复制
发表时间：
2014-09
期刊：
影响因子：
--
通讯作者：
H. Ishibuchi;Yuki Tanigaki;Hiroyuki Masuda;Y. Nojima
中科院分区：
文献类型：
--
作者：
H. Ishibuchi;Yuki Tanigaki;Hiroyuki Masuda;Y. Nojima
据报道，对于多目标背包问题，相似父代的重组通常可以提高进化多目标优化（EMO）算法的性能。最近还报道了通过在两个父母之间仅交换少量基因（即，基因交换概率非常小的交叉）而不选择相似的父母来提高性能。在本文中，我们通过计算实验检验这些性能改进方案，其中 NSGA-II 应用于具有 2-10 个目标的 500 项背包问题。我们在计算实验中测量亲本距离和亲子距离。当亲子距离很小时，可以观察到明显的性能改善。为了进一步检查这一观察结果，我们实现了一个基于距离的交叉算子，其中父代距离被指定为用户定义的参数。针对各种参数值检查 NSGA-II 的性能。实验结果表明，合适的参数值（亲子距离）小得惊人。还表明非常小的参数值有利于多样性维护。
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.