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

Solving multiobjective 0/1 knapsack problems by genetic algorithms

作　　者：郭观七[1] 杨观赐[1] 黄韬[1] 岳继红[1] 

机构地区：[1]湖南理工学院计算机与信息工程系,湖南岳阳414000

出　　处：《湖南理工学院学报（自然科学版）》2004年第4期18-22,共5页Journal of Hunan Institute of Science and Technology(Natural Sciences)

基　　金：国家自然科学基金 (5 0 2 75 170 );湖南省教育厅科学基金 (2 0 0 2A0 5 2 )

摘　　要：扼要介绍多目标优化的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).

关 键 词：多目标优化 遗传算法 PARETO最优性 快速分层 0/1背包问题 

分 类 号：O224[理学—运筹学与控制论]