基于贪婪算法的改进自适应遗传算法及其应用

摘要： 本文将改进的自适应遗传算法和贪婪算法相结合用于0-1背包问题的求解。此算法对交叉率和变异率进行了优化，实现了交叉率和变异率的非线性自适应调整，并对不可行解进行了贪婪修复。实验结果表明，相比传统的自适应遗传算法，新算法收敛速度快，寻优能力强，具有更可靠的稳定性。

Abstract： This paper combines the improved adaptive genetic algorithm with greedy algorithm to solve the 0-1 knapsack problem. By optimizing the cross-over rate and mutation rate， this algorithm has realized non-linear adaptive adjustment， and has done greedy repair to the non-feasible solution. The result shows that， compared with traditional adaptive genetic algorithm， the new algorithm has faster convergence speed and stronger searching ability and more reliable stability.

关键词： 背包问题；遗传算法；鲁棒性；贪婪算法

Key words： knapsack problem；genetic algorithm；robustness；greedy algorithm

中图分类号：TP301.6 文献标识码：A 文章编号：1006-4311（2013）22-0231-02

0 引言

1975年，Holland等人基于自然界的遗传和自然选择，提出了全局优化算法——遗传算法[1]。遗传算法具有鲁棒性强，适用于并行计算以及高效性、实用性等显著特点，在各领域得到了广泛应用，取得了良好效果，并逐渐成为重要的智能算法之一。随后，自适应调整交叉率和变异率被应用到遗传算法中，较好地提高了算法的收敛速度，但算法的鲁棒性仍十分具有挑战性[5]。

本文将自适应遗传算法应用于求解0-1背包问题，并利用贪婪算法对不可行解和背包资源利用不足的问题进行修复，提出了一种基于贪婪算法的改进的自适应遗传算法。数值实验表明此算法在求解0-1背包问题时非常有效。

1 背包问题

若有n个不同的物体，对于物体j，其重量为wi，价值为pj，b是背包的最大容量，背包问题就是要在不超过背包承受重量的前提下，使装入背包的物品价值最大，则背包问题的数学模型如下：

max■xipi

s.t.■wixi？燮bxi=0或1，i=1，2，……，n

其中xj为0-1决策变量（当物品j被选择时xj=1，否则xj=0）。

2 价值密度及贪婪算法

第j个物体的价值密度midu（j）定义为：midu（j）=pj/wj。按价值密度的次序逐一选取物体装入背包，若两个物体的价值密度相同则重量大的排在前面，由此背包价值增大，直到背包不能装入任一物体为止，此种排序方法还可以提高贪婪算法的质量。

3 改进的自适应遗传算法

3.1 编码修复 算法采用二进制编码，不可行性的初始解主要有：第一，构造初始种群时产生的不可行解；第二，自适应遗传操作（如交叉和变异算子）导致的不可行解。

修复不可行解的贪婪算法[4]：将已装入背包中的物品按照价值与重量之比的升序排列，依此顺序去掉物品，保证背包不超重。

3.2 适应度函数 由于适应度值是群体中个体生存机会选择的唯一确定性指标，所以适应度函数的形式直接决定着群体的行为进化。为了直接将适应度函数与群体中的个体优劣度量相联系，在遗传算法中规定适应度为非负，并且在任何情况下总是越大越好。由于本算法对每个个体使用了贪婪算法修正，即保证了不会产生无效染色体，所以在进行个体适应度评价时无须引用惩罚函数项，而是直接用目标函数值作为适应度函数值，即fitness（x）=■xipi。

3.3 初始种群的产生 随机产生初始群体p=（p1，p2，…，ppopsize），popsize是种群规模，并对不可行解进行修复，再用贪婪算法产生一个近似最优解代替初始种群中适应度最小的个体，得到初始种群p′=（p′1，p′2，…p′popsize）。

3.4 选择操作 先计算群体中个体所对应的适应度总和■fi，再计算个体相对的适应度fi/■fi，即个体遗传到下一代的概率，最后产生一个0到1之间的随机数，根据此随机数来确定各个个体被选中的次数，并将上一代的最优个体直接进入下一代，这样，每进化一代，下一代的最优个体一定不劣于上一代[6]。

3.5 自适应的交叉和变异算子 在遗传算法中，交叉和变异是影响GA行为和性能的关键。本文所使用的交叉与变异率公式如下：

pc=■，f′？叟favgk2，f′？燮favg（1）

pc=■，f？叟favgk4，f？燮favg（2）

fmax为群体中适应度的最大值，favg为每代群体适应度的平均值，f′为要交叉的两个个体中适应度的较大值，f为要变异个体的适应度。

4 算法流程

在新算法中，当进行交叉和变异操作后就要进行不可行解的修复，由此可以保证父代产生的子代都是比较优秀的，也可以加快算法向最优解的方向前进。

5 仿真实验

背包容量为1000，50个物品的重量为

W=[80 82 85 70 72 70 66 50 55 25 50 55 40 48 50 32 22 60 30 32 40 38 35 32 25 28 30 22 50 30 45 30 60 50 20 65 20 25 30 10 20 25 15 10 10 10 4 4 2 1]，

对应的价值为V=[220 208 198 192 180 180 165 162 160 158 155 130 125 122 120 118 115 110 105 101 100 100 98 96 95 90 88 82 80 77 75 73 72 70 69 66 65 63 60 58 56 50 30 20 15 10 8 5 3 1]；

设定为群体大小M=50，终止进化代数T=200，各种参数设定为k1=0.8，k2=0.6，k3=0.50，k4=0.07，数值结果如表1所示。

从表可以得出，新算法在解的质量和求解速度方面都有较大改进。

6 结束语

本文对基本的自适应遗传算法加以改进，引入了新的交叉算子和变异算子，并利用贪婪算法对不可行解进行修复。通过算例的数值试验，新算法在解决背包问题时获得了较好的解的质量和较快的求解速度。因此，采用上述改进的交叉率和变异率无论在收敛速度上还是在对最佳适应度的搜索上均保持了较高的鲁棒性。因此，将此算法应用于求解0-1背包问题，是一次十分有意义的尝试。

参考文献：

[1]王小华，曹立明.遗传算法—理论，应用与软件实现[M].西安：西安交通大学出版社，2002.

[2]金晶，苏勇.一种改进的自适应遗传算法[J].计算机工程与应用，2005（18）：64-69.

[3]严太山.用基于贪婪算法的混合遗传算法求解0/1背包问题[J].研究与开发，2007（8）.

[4]黄与林.0-1背包问题的贪心算法[J].鄂州大学学报，2006，13（6）：38-40.

[5]李肯立，李庆华，戴光明等.背包问题的一种自适应算法[J].计算机研究与发展，2004，41（7）.

[6]赵朝卿，胡小兵.一种新的求解0-1背包问题的混合算法[J].计算机工程与应用，2008，44（18）：61-63.