多目标0/1背包问题MOEA求解中的修复策略  

Repair Strategies for Multiobjective 0/1 Knapsack Problem in MOEA

作　　者：黄林峰[1] 罗文坚[1,2] 王煦法[1,2] 

机构地区：[1]中国科学技术大学计算机科学与技术系自然计算与应用实验室,合肥230027 [2]中国科学技术大学安徽省计算与通讯软件重点实验室,合肥230027

出　　处：《模式识别与人工智能》2009年第4期519-526,共8页Pattern Recognition and Artificial Intelligence

基　　金：国家自然科学基金委海外青年学者合作研究基金资助项目(No.60428202)

摘　　要：多目标进化算法在求解多目标0/1背包问题时常使用修复策略来满足容量约束.文中更全面地考虑物品对各个背包的不同影响,提出两种加权修复策略,分别基于背包容量和容量约束违反程度,并应用于经典算法SPEA2中.在9个标准MOKP测试实例上的实验结果表明,采用该修复策略的SPEA2算法能更有效地收敛到Pareto最优前沿.A repair strategy is often adopted to guarantee feasibility of the muhiobjective evolutionary algorithms for muhiobjective 0/1 knapsack problem （MOKP）. In this paper, impacts of each item on all knapsacks are much considered and two novel repair strategies are proposed based on the knapsack capacities and constraint violations, respectively. The two novel strategies are applied to SPEA2 to solve MOKP. The experimental results on 9 standard test cases of MOKP demonstrate that SPEA2 with the proposed repair strategies has better convergence to the Pareto-optimal front.

关 键 词：多目标进化算法(MOEA) 多目标0/1背包问题(MOKP) 进化多目标优化 加权修复策略 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]