基于遗传算法的多目标0-1背包问题优化模型  

Optimization Model Based on Genetic Algorithm for Multi-Objective 0-1 Knapsack Problems

作　　者：敖友云[1] 迟洪钦[1] 

机构地区：[1]上海师范大学数理学院,上海200234

出　　处：《计算机工程与应用》2006年第25期44-45,共2页Computer Engineering and Applications

摘　　要：多目标0-1背包问题是一个NP-complete的多目标优化问题,基于群体搜索机制的遗传算法非常适合多目标优化问题的求解。在著名的多目标优化遗传算法NSGA-II中,引入邻域搜索机制,并将其应用于多目标0-1背包问题的求解。数值实验表明,引入邻域搜索机制的NSGA-II算法在求解多目标0-1背包问题时表现出更好的性能。Multi-objective 0-1 knapsack problem is an NP-complete multi-objective optimization problem.Population- based genetic algorithm is well-suited for multi-objective optimization problems.In the famous algorithm NSGA-II,the neighborhood search is introduced.The numerical experimental results show that NSGA-II with the neighborhood search can outperform NSGA-II applied to multi-objective 0-1 knapsack problems.

关 键 词：遗传算法 多目标优化 背包问题 PARETO 最优 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]