求解多选择背包问题的改进差分演化算法  

A Modified Differential Evolution Algorithm for Multiple-choice Knapsack Problem

作　　者：贺毅朝[1] 寇应展[2] 陈致明[2] 

机构地区：[1]石家庄经济学院信息工程系,河北石家庄050031 [2]中国人民解放军军械工程学院计算机工程系,河北石家庄050003

出　　处：《小型微型计算机系统》2007年第9期1682-1685,共4页Journal of Chinese Computer Systems

基　　金：国家自然科学基金重点项目(60471022)资助

摘　　要：首先将差分演化算法(DEA)的演化机制归结为差异算子(DO)和选择算子(SO)的作用,然后基于离散域上的多选择背包问题(MCKP),通过重新定义DEA算法的差异算子中的三种基本运算,并采用个体正整数编码方法和处理非正常编码的快速微调策略,提出了一种求解MCKP问题的改进差分演化算法(MDEA),第一次将DEA用于求解组合最优化问题.对经典MCKP问题实例的计算表明:MDEA算法不但是可行的,而且是高效的.In this paper, at first conclude the evolution mechanism of differential evolution algorithm （DEA） to the function of differential operator and select operator. Then, advanced a modified differential evolution algorithm （MDEA） for multiple- choice knapsack problem （MCKP） over discrete space, which use individual positive coding method and combine with the subtle adjusting strategy of non-normal coding through newly defining three basic operations of differential operator（DO） in DEA. First apply DEA to solve combinatorial optimization problems. Calculations of instances to classical MCKP show that MDEA is not only feasible, but also have a high efficiency.

关 键 词：差分演化算法 多选择背包问题 个体编码 差异算子 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]