混合二进制差异演化算法解0-1背包问题

作     者：邓长寿 赵秉岩 梁昌勇 DENG Chang-shou;ZHAO Bing-yan;LIANG Chang-yong

作者机构：九江学院信息科学与技术学院江西九江332005 合肥工业大学网络系统研究所安徽合肥230009 九江学院商学院江西九江332005 

基　　金：国家自然科学基金项目(70771037 50705039) 江西省教育厅科技基金项目(GJJ09347) 

出 版 物：《计算机工程与设计》 (Computer Engineering and Design)

年 卷 期：2010年第31卷第8期

页      码：1795-1798页

摘      要：为了有效求解0-1背包问题,提出一种混合二进制差异演化算法。该算法基于差异演化算法框架,采用二进制编码,通过增加映射操作、S型变换操作和逆映射操作等3种新的操作,将差异演化算法从实数优化领域推广至离散优化领域,成功解决了差异演化算法直接求解离散优化问题时的计算不封闭问题。此外,在每次迭代求解时,利用贪婪变换法对违反约束条件的不可行解进行变换,使其成为可行解。不同规模的背包问题的数值实验结果表明了该算法的有效性与适用性。

主 题 词：0-1背包问题 二进制差异演化 映射操作 S型变换操作 逆映射操作 贪婪变换 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 081104[081104] 08[工学] 0835[0835] 0811[工学-水利类] 0812[工学-测绘类] 

D　O　I：10.16208/j.issn1000-7024.2010.08.018

馆 藏 号：203702804...