基于二进制改进遗传算法的0_1背包问题求解方法  

An Improved Genetic Algorithm Based on Binary Coding for 0_1 Knapsack Problem

作　　者：帅训波[1] 周相广[1] 李树铁[2] 陈东[3] 田鸿鹏[1] 

机构地区：[1]中国石油勘探开发研究院廊坊分院地球物理与信息研究所,河北廊坊065007 [2]中国石油勘探开发研究院渗流流体力学研究所,河北廊坊065007 [3]中国石油勘探开发研究院人事劳资处,北京100083

出　　处：《德州学院学报》2010年第2期63-67,共5页Journal of Dezhou University

摘　　要：一般遗传算法求解0_1背包问题时,存在着搜索速度和求解质量之间的矛盾.针对此问题,文中在逆序算子、对偶算子和矩阵遗传算子的研究基础之上,将其进行组合应用,构造了一种基于二进制编码的改进遗传算法,用于求解0_1背包问题,保证了算法的全局收敛性.仿真实验结果表明,该求解方法具有良好搜索效率和求解质量.It is difficulty for general genetics algorithm to avoid prematurely convergence and raise the speed of algorithm convergence in solving the 0-1 Knapsack Problem. In this paper, using the research result of Matrix genetic operator.inverse and dual combination operator, an improved genetic algorithm based on binary coding is proposed for solving the 0-1 Knapsack Problem. It is proved to be convergence, and the better efficiency of the solving algorithm has been shown by simulative experiments.

关 键 词：背包问题 遗传算法 逆序与对偶算子 矩阵遗传算子 

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