基于区域分割的差分进化算法求解0-1背包问题

作     者：钟培华 吴志远 胡建根 朱丽 

作者机构：江西农业大学理学院江西南昌330045 

出 版 物：《江西师范大学学报（自然科学版）》 (Journal of Jiangxi Normal University(Natural Science Edition))

年 卷 期：2012年第36卷第4期

页      面：364-369页

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：江西省教育厅省级教改基金(JXJG-10-4-22) 江西农业大学青年基金(1574 2971)资助项目 

主　　题：背包问题 差分进化算法 分割 

摘      要：为了更有效地求解0-1背包问题,提出了基于区域分割的差分进化算法(PDE).为保证变异算子的封闭性,对传统差分进化算法(DE)的变异算子进行了修改.引入区域分割算法以后,解空间中一些没有希望的点被移除,缩小了最优解的搜索范围,增加了找到最优解的概率.将区域分割和贪婪算法相结合,用搜索到的最好解替换了种群中目标函数值最差的个体,保证了种群的多样性.数值实验表明:该算法比文献中的DE算法更稳健,全局搜索能力更强,能以更大的概率找到背包问题的最优解.