一种求解0-1背包问题的退火贪婪遗传算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇一种求解0-1背包问题的退火贪婪遗传算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：将贪婪算法和退火算法融入遗传算法，结合各自算法的优点形成了一种混合遗传算法。通过实验表明，运用此算法求解0-1背包问题，搜索能力明显优于基本遗传算法和贪婪算法。

关键词：0-1背包问题；遗传算法；贪婪算法；模拟退火

中图分类号：TP301.6

0-1背包问题（Knapsack Problem）是一个典型的NP完全（NondeterministicPolynomia Completeness）问题[1]，在现实生活中有着广泛应用，如生产安排、资源分配、投资决策等都可建模为背包问题。因此，对该问题求解方法的研究，在理论上和实践中都有着重要的意义。求解0-1背包问题的方法有多种，如枚举法、动态规划法、回溯法、贪婪算法、遗传算法等。其中，遗传算法作为智能搜索算法的一种，具有全局寻优、智能搜索以及收敛速度快等特性，在求解0-1背包问题中显现了一定的优势。遗传算法基于“优胜劣汰”自然选择机制，通过选择、交叉、变异等操作使群体中的个体不断朝着最优解的方向移动[2]。本文在各种算法对背包问题研究的基础上，将贪婪算法和模拟退火算法引入遗传算法，给出了一种混合遗传算法求解0-1背包问题。

1背包问题数学模型

背包问题的一般描述为：已知n个物品的重量wi（wi＞0）和价值ci（ci＞0）（i=1，2，…，n），给定一个背包，容量限制为v（v＞0），问如何选择物品装入背包，使得在背包容量限制之内，装入的物品总价值最大，且单个物品不能多次装入、不能分割。0-1背包问题的数学模型可表示为[3]：

目标函数：

约束条件：

xi∈{0，1} （i=1，2，…，n）

式中，xi为0-1决策变量，xi=1时表示物品i装入背包中，xi=0时表示其未装入。

2混合遗传算法设计

2.1染色体编码方法

根据0-1背包问题的特点，采用与问题物品个数等长的二进制编码方法。编码串中1表示对应的物品放入背包中，0表示不放入。如110110101000……0001表示第1、2、4、5、7、9、n号物品放入背包中，其他的则不放入。

2.2贪婪算法在解码中的应用

上述编码方案虽然比较直观，但随机生成的编码串，或是交叉、变异操作产生的新个体，不一定满足约束条件，即在这种编码方案下会产生一些无效染色体。可引入贪婪算法的思想解决这一问题，这里采用单位价值贪婪策略[4]，这种策略为：从剩余物品中选择可装入包的价值密度ρi=ci/wi值最大的物品，直到超出背包容量为止。具体步骤如下：

①对所有xi=1的物品，按它们的价值密度ρi=ci/wi（i=1，2，…，n）形成一个从大到小排序的队列q（i），即价值密度最高的物品序号为q（1），次之为q（2），以此类推。

②置k=1。

③引入贪婪算法解码变换：如果 ，则将q（k）所对应的物品装入背包，置xq（k）=1，k=k+1，转向第③步；如果 ，则转向第④步。

④往后的队列序号j，即从k到n对应的物品不放入背包，置xq（j）=0。

2.3适应度函数

因为背包问题求的是目标函数的最大值，所以可用目标函数值作为适应度函数值，即适应度函数为：

2.4选择、交叉和变异算子

遗传算法通过使用选择算子对个体进行优胜劣汰操作。这里采用遗传算法常用到的比例选择算子，即是轮赌盘选择，这种选择方法个体被选中的概率与它的适应度大小成正比，保证了适应度较高的个体被选择到下一代的几率更高。考虑到交叉、变异操作可能会破坏当代最优个体，最终选择算子采用比例选择基础上的最优保存策略（最优保存策略能让适应度最好的个体不被破坏，尽可能保留到下一代群体中）。

由于采用二进制编码方案，因此交叉算子采用较为简单的单点交叉算子，即在编码串中随机设置一个交叉点，然后在该点处按交叉概率pc交换两个个体的部分染色体。变异算子采用基本位变异，即以变异概率pm将随机指定的基因座上的值由1变为0，或由0变为1。

2.5模拟退火过程

模拟退火算法是基于金属退火的机理而创建的一种通用优化算法，它依据Metropolis准则接受新解，其在接受优质解的同时，在一定限制范围内接受劣质解，因此能够有效跳出局部最优的“陷阱”[5]。模拟退火算法与遗传算法相比较，模拟退火算法具有较强的局部搜索能力，而遗传算法则能更好的把握全局搜索，将两种算法相结合，可以互相取长补短。步骤如下：

①设置初始温度Tk（k=0），迭代次数num（num∈N+）。

②置ni=1。

③进行第ni次迭代，将染色体的第ni位的基因置为0，第chromlength-ni+1（chromlength为染色体长度）位基因置为1，以此提高模拟退火的局部搜索能力，并计算函数差值Δf=f（j）-f（i），其中j为新生成的个体，i为原来的个体。

如果Δf≥0，则新生成个体复制到下一代群体；

如果Δf

④若ni

⑤令Tk+1=a×Tk，kk+1，其中a∈（0，1），若满足收敛条件，退火过程结束，否则，转向第②步。

为防止退火操作对最优个体的破坏，每次退火操作后，都要保存到目前为止最优个体的信息。

2.6算法基本流程图

混合遗传算法的基本流程如图1所示：

图1算法流程图

3实例仿真

为了验证混合遗传算法的有效性，通过实验对改进的混合算法与传统的贪婪算法、基本遗传算法进行对比。考虑有50件物品组成的0-1背包问题，物品的价值C、物品的重量W、背包的容积v分别为：

C={ci}={200，198，198，185，184，174，165，160，160，158，155，130，125，121，120，118，115，110，108，102，100，99，99，96，95，92，88，82，80，77，75，74，72，70，69，65，65，63，60，58，56，52，30，22，21，11，9，6，3，1}

W={wi}={65，82，85，90，72，72，66，50，45，25，60，55，40，40，50，32，22，72，30，32，55，34，35，32，25，28，30，31，50，30，45，33，60，50，20，60，20，25，30，10，20，25，15，11，9，9，4，4，2，1}

v=1000

实验环境：PC机：CPU：Intel Core i5-2400；内存：2GB；硬盘：500GB；操作系统：Windows XP。

参数设置：种群规模popsize＝100；最大迭代代数为200；交叉概率pc=0.6，变异概率pm=0.03；染色体长度chromlength＝50；初始温度T＝100；降温系数：a＝0.8；退火终止温度为1；每个温度内的迭代次数num＝25。以上参数通过参考常见的文献和多次实验而得。实验数据如表1所示：

表1实验结果

算法 最好个体 总价值 总重量 100次实验结果超过贪婪算法的次数

贪婪算法 1000111111101101101101111

1110100001011011000000000 3084 991

基本遗传算法 1000111111101101101101111

1110100001011011000001100 3099 999 4

混合遗传算法 1000111111101101101101111

1110100001011011000100000 3105 1000 100

通过表中的数据可知，融入了贪婪算法和模拟退火算法思想的混合遗传算法，在求解0-1背包问题时，比单纯贪婪算法和基本遗传算法都要优越。

4结语

本文根据遗传算法的基本思路来求解0-1背包问题，在解码过程中引入贪婪算法，提高了遗传算法解决背包问题的效果。并且融合了模拟退火算法，克服遗传算法容易陷入局部最优的缺陷，提高了算法的求解性能。今后要以此为借鉴，将遗传算法应用到更多的组合优化问题的求解中。

参考文献：

[1]贺毅朝,刘冲起,张翠军.求解背包问题的贪心遗传算法及其应用[J].计算机工程与设计,2007,11:2655-2657.

[2]周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,1999.

[3]张盛意,蔡之华,占志刚.基于改进模拟退火的遗传算法求解0-1背包问题[J].微电子学与计算机,2011,2:61-64.

[4]严太山.用基于贪婪算法的混合遗传算法求解0/1背包问题[J].现代计算机(专业版),2007,8:14-17.

[5]吕晓峰,张勇亮,马羚.一种求解0-1背包问题的改进遗传算法[J].计算机工程与应用用,2011,1:44-46.

作者简介：余梅（1980-），女，蒙古族，贵州贵阳人，贵州师范学院教育信息网络中心，讲师，硕士，研究方向：计算机应用技术。