Repair Strategies for Multiobjective 0/1 Knapsack Problem in MOEA
HUANG Lin-Feng1, LUO Wen-Jian1,2, WANG Xu-Fa1,2
1.Nature Inspired Computation and Applications Laboratory, Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230027 2. Anhui Province Key Laboratory of Software in Computing and Communication, University of Science and Technology of China, Hefei 230027
Abstract：A repair strategy is often adopted to guarantee feasibility of the multiobjective evolutionary algorithms for multiobjective 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.
黄林峰，罗文坚，王煦法. 多目标0/1背包问题MOEA求解中的修复策略*[J]. 模式识别与人工智能, 2009, 22(4): 519-526.
HUANG Lin-Feng, LUO Wen-Jian, WANG Xu-Fa. Repair Strategies for Multiobjective 0/1 Knapsack Problem in MOEA. , 2009, 22(4): 519-526.
[1] Deb K. Multi-Objective Optimization Using Evolutionary Algorithms. Chicester, UK: John Wiley & Sons, 2001 [2] Xie Tao, Chen Huowang, Kang Lishan. Evolutionary Algorithms of Multi-Objective Optimization Problems. Chinese Journal of Computers, 2003, 26(8): 997-1003 (in Chinese) (谢 涛,陈火旺,康立山.多目标优化的演化算法.计算机学报, 2003, 26(8): 997-1003) [3] Zhao Shuguang, Jiao Licheng, Wang Yuping, et al. Uniform Design Based Multi-Objective Adaptive Genetic Algorithm and Its Application in Evolutionary Design of Analog Circuits. Acta Electronica Sinica, 2004, 32(10): 1723-1725 (in Chinese) (赵曙光,焦李成,王宇平,等.基于均匀设计的多目标自适应遗传算法及应用.电子学报, 2004, 32(10): 1723-1725) [4] Coello C C A. Evolutionary Multi-Objective Optimization: A Historical View of the Field. IEEE Computational Intelligence Magazine, 2006, 1(1): 28-36 [5] Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the Strength Pareto Evolutionary Algorithm. TIK-Report, 103, Zurich, Switzerland: Swiss Federal Institute of Technology. Computer Engineering and Networks Laboratory (TIK), 2001 [6] Deb K, Pratap A, Agarwal S, et al. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Trans on Evolutionary Computation, 2002, 6(2): 182-197 [7] Knowles J D, Corne D W. Approximating the Nondominated Front Using the Pareto Archived Evolution Strategy. Evolutionary Computation, 2000, 8(2): 149-172 [8] Zitzler E, Thiele L. Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach. IEEE Trans on Evolutionary Computation, 1999, 3(4): 257-271 [9] Chu P C, Beasley J E. A Genetic Algorithm for the Multidimensional Knapsack Problem. Journal of Heuristics, 1998, 4(1): 63-86 [10] Knowles J D, Corne D W. M-PAES: A Memetic Algorithm for Multiobjective Optimization // Proc of the Congress on Evolutionary Computation. La Jolla, USA, 2000, Ⅰ: 325-332 [11] Ishibuchi H, Kaige S. An Empirical Study on the Effect of Mating Restriction on the Search Ability of EM0 Algorithms // Proc of the 2nd International Conference on Evolutionary Multi-Criterion Optimization. Faro, Portugal, 2003: 433-447 [12] Jaszkiewicz A. On the Performance of Multiple-Objective Genetic Local Search on the 0/1 Knapsack Problem—A Comparative Experiment. IEEE Trans on Evolutionary Computation, 2002, 6(4): 402-412 [13] Ishibuchi H, Kaige S. Effects of Repair Procedures on the Performance of EMO Algorithms for Multiobjective 0/1 Knapsack Problems // Proc of the Congress on Evolutionary Computation. Canberra, Australia, 2003, Ⅳ: 2254-2261 [14] Zitzler E, Thiele L, Laumanns M, et al. Performance Assessment of Multiobjective Optimizers: An Analysis and Review. IEEE Trans on Evolutionary Computation, 2003, 7(2): 117-132 [15] Fieldsend J E, Everson R M, Singh S. Using Unconstrained Elite Archives for Multiobjective Optimization Evolutionary Computation. IEEE Trans on Evolutionary Computation, 2003, 7(3): 305-323
2009, Vol. 22 
