基于ε支配的MOGA在0/1背包问题中的应用  

MOGA Based On ε-Dominated Method for knapsack problems

作　　者：刘瑞[1] 许峰[1] 

机构地区：[1]安徽理工大学理学院,安徽淮南232001

出　　处：《软件导刊》2013年第3期31-33,共3页Software Guide

基　　金：安徽省教育厅自然科学基金项目(2010kb236)

摘　　要：多目标遗传算法NSGA-Ⅱ是解决0/1背包问题[1]的有效算法,但是它还存在一定的缺陷,当0/1背包问题的规模较大时,这种方法很难收敛到Pareto最优边界,因此解的分布性不是很好,解集也很难收敛。针对此问题,提出基于ε支配的MOGA来求解0/1背包问题,通过实验验证该算法在求解分布性上优于NSGA-Ⅱ。Multi-objective genetic algorithm NSGA-Ⅱ is an effective mean to solve 0/1 knapsack problem, but it has certain defects when scales of 0/1 knapsack problems is large and this method is hard to convergence to the pareto optimal setboundary and unsatisfactory distribution. In response to this problem, we propose ε dominated MOGA to solve 0/1 knapsack problem. The experiments demonstrate that this method is superior to compare to NSGA-Ⅱ.

关 键 词：多目标遗传算法 ε支配 背包问题 

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