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

一种求解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为染色体长度）位基因置为