用遗传算法求解多目标0/1背包问题

Solving multiobjective 0/1 knapsack problems by genetic algorithms

扼要介绍多目标优化的Pareto最优性概念 ,研究搜索多目标 0 1背包问题Pareto最优解集的快速遗传算法 (FPGA :fastParetogeneticalgorithms) .FPGA采用种群中非支配解的层次评价可行解的适应值 ,提出了一种快速非支配解层次辨识算法 ,辨识算法仅有O(n2 )数量级的计算复杂性 ;采用基于聚类概率排挤的小生态技术维持种群多样度和Pareto最优解集的分布均匀性。对多种多目标 0 1背包问题的仿真优化实验结果表明 ,FPGA能够以有效的计算成本搜索到精度高的、分布均匀的高质量Pareto非劣解集 ,其收敛速度和收敛准确性一致地优于代表性的强度Pareto进化算法 (SPEA) .

This paper briefly describes Pareto optimality in multiobjective optimization, investigates a kind of fast Pareto genetic algorithms (FPGA) searching Pareto optima of multiobjective 0/1 knapsack problems. FPGA evaluates fitness of individuals using nondominated ranking. A kind of fast algorithm identifying nondominated ranking is proposed. It only has a computationae complexity of order O(n2). The niching method using probabilistic crowding based on clustering analysis is used to improve the population diversity and the distribution of Pareto nondominated solutions. Simulation optimization on various multiobjective 0/1 knapsack problems shows that FPGA is capable of finding out the evenly distributed nondominated solutions approximating to Pareto front, and the convergence rate as well as the accuracy is uniformly superior to that of the representative multiobjective evolutionary algorithms, the strength Pareto evolutionary approach (SPEA).