遗传蚁群算法解决背包问题

1、解决0/1背包问题的改进遗传蚁群混合算法，报告者：宋灵智要点：计算机院软化工训练室时间：2013年11月15日，研究背景，背包问题(Knapsack Problems)是运行研究中典型的优化难点问题，对背包问题研究具有非常重要的理论和现实意义在现实生活中，资源分配、投资决策、装载问题、网络资源分配等问题可以概括为背包问题。为了解决背包问题，出现了多种优化算法。其中遗传算法是基于自然选择和群体遗传机制的搜索算法，模拟了自然选择和自然遗传过程中的繁殖、杂交、突变现象。这属于随机搜索算法，具有强大的全局搜索功能，但遗传算法的个人对每个选择没有反馈，因此遗传算法的收敛速度慢，优化精度不高。蚁群算法在解

2、决0/1背包问题时，主要通过项目中的信息素进行选择，在一个项目中信息素越高，选择的概率就越高。蚁群算法使用积极反馈机制快速收敛到问题的局部最优解决方案中，但具有全局搜索能力低、搜索时间长的缺点。由于两种算法的优点和缺点，近年来很多学者致力于两种算法的混合研究。本文提出了基于两种新的混合方法解决0/1背包问题的算法。主要内容，背包问题的数学模型，一般来说，0/1背包问题有一个背包和n个项目。其中背包的最大重量为c，项目j的重量为Wj，价值为Pj，0/1背包问题解决的目标是从n个项目中选择部分项目装入背包。如果选定项目的总重量不超过c，则可以最大限度地提高背包装载项目的总价值。其中xj=1表示已选

3、取项目j，xj=0表示未选取项目j。改进的遗传蚁群混合算法的混合方式，在现实中，自然的蚂蚁分工很明显，大约四分之一的蚂蚁专门努力寻找新的食物来源，受到了启发，我们提出了一种新的混合方式：一些优秀的人工蚂蚁使用遗传算法进行优化，并利用此结果对蚂蚁系统的信息素进行整体更新，指导蚁群选择最佳方向；剩下的蚂蚁使用蚁群算法进行优化，利用结果在本地更新蚁群系统的信息素，指导下一只蚂蚁的优化方向。像这样，一方面在遗传算法中使用交叉、突变操作生成新对象，扩大人口多样性，加强算法的全局搜索能力，另一方面利用蚁群算法提高优化精度。为了说明自然界中蚂蚁是如何随着环境变化的，在这个算法中，使用两种不同优化方法的蚂蚁的

4、数量随着迭代次数而变化。在每次迭代过程中，蚂蚁数量固定为m，选择k只优秀的蚂蚁，用遗传算法优化，优化结束后执行全局信息素更新，剩下的蚂蚁用蚁群算法优化，优化结束后执行本地信息素更新。世代优化结束后，m只蚂蚁找到的解和上一代的上层k解一起参与序列，该序列的上层k解在下一次迭代中用作遗传算法的初始种群。为了确保蚂蚁的优化能力和优化效率，k值根据进化代数进行适应变化，k值使用最小-最大策略，k值介于间隔1/4，3/4之间。A1:用遗传算法优化的实体集A2:用蚁群算法优化的解决方案集Allowed:蚂蚁I后允许的项目顺序集Tabu:蚂蚁I已选定的项目顺序集Over:下一次选择时Allowed不满足约束

5、的项目顺序编号集g:最大迭代数m:蚂蚁总数k:用遗传算法优化的蚂蚁数代码L:算法过程(算法1):第一阶段参数初始化阶段2随机生成矩阵A1(k，CodeL)，第三阶段迭代周期(g=g 1)阶段4确定k小于m/4，如果是，则k=m/4， 否则，在步骤k=3m/42 (g1)步骤5中，k蚂蚁的遗传算法优化(1)复制矩阵A1(B=A1) (2)根据交叉概率Pc交叉操作A1(3)根据变异概率Pm对A1进行变异操作(4) ，算法阶段，6对(MK)蚂蚁使用蚁群算法优化(1)Allowed=1:CodeL，Tabu=，Over=A2=zeros(MK)，CCS 否则，在步骤6(-1)7中，根据自适应值大小按降

6、序对矩阵b、A1、A2进行排序，在第一个k实体配置A1步骤8中，检查是否满足最佳值选择步骤9中的终止条件(gG)，如果满足，则输出最佳结果，否则，执行步骤3，算法策略(1)交叉操作() 相交的第二个对象是与第一个对象的解明距离(两个代码的对应位称为这两个词的解明距离)不同的最大对象，交叉起始位置是两个对象的第一个不同基因位x，交叉基因位数在1和(nX)(n是项目数，即染色体的长度)之间生成。这可以最大限度地生成新的对象，增加个体数量的多样性。(2)在变异操作(步骤5(3)中，变异的基因数随机生成时，每个基因变异的概率由表示现代群体中每个基因座1和0的比率差异的绝对值确定，差异越大，变异概率越小

7、，变异概率越大。按从大到小的顺序排列每个基因座的变异概率，根据随机生成的基因座数量选择要变异的前几个基因座进行变异。这种变异工作方式最大限度地保证了算法寻找的最优解是全局最优解。(3)恢复操作(步骤5(步骤4)。本文使用最常用的启发式维修策略，通过违反约束条件来修复它，在维修时根据物料的价值重量比递增，然后按此顺序删除背包中的物料，直到满足约束条件为止。算法策略，(4)在Allowed中选择物料j的概率(步骤6(步骤3)为：其中TJ是项目j的信息素浓度，原始描述浓度TJ相同，本文档中tj=1/sum(P)(P是项目的价值集)，QJ是项目j的价值重量比。(5)任务选择(步骤7)所有蚂蚁和上一代的

8、前k个对象共同参与排序的排序方法。遗传算法和蚁群算法都使用0，1编码和统一信息素更新公式。其中tj(g)使用g代项目j的信息素浓度，信息素挥发系数，tj使用项目j的信息素变化量，t是蚂蚁I在项目j中留下的信息素量，Q是值，本论文使用Q=1/m*sum(P)Li作为现代蚂蚁I选择的项目价值对比之和，分析了仿真实验结果，为了验证本文算法的有效性，本文测试了文献4中的3个0/1背包问题实例。其中蚂蚁数量m=200、Pc=0.8、Pm=0.15、信息素权重a=1、估计权重b=1、信息挥发性系数=0.7。每个算法执行20次，例如表(算法1和算法2是本文中的两种算法，算法3是文献2的混合方式，算法4是文献

9、3的混合方式，算法5的结果来自参考文献4)。附注：在表1的表3中，-表示没有达到最佳解决方案，* * *表示文献中没有此结果。在表1中，算法1、2获得的最优解明显优于其他算法，在示例2中，算法2略优于算法1。仿真实验结果分析，表2中，对于算法的收敛速度，算法2略优于算法1，算法4比4慢，算法3最慢。表3中，对于程序执行速度，算法2最快，其次是算法1和3，算法4最慢。结论，仿真结果在0/1背包故障诊断中，本文提出的两种算法，无论是最佳解决方案还是解决速度，都大大提高了，算法2在程序执行速度上也大大提高了，显示了该算法的有效性。通过对遗传算法和蚁群算法的优缺点分析以及对两种算法混合方式的研究，提出了设计两种算法的新混合方式。为了提高算法的优化性能和优化速度，对两种算法进行了混合，进一步改进了传统遗传算法中的交叉操作数和变异操作数，并对蚁群算法的分配等进行了一些改进。通过实例的仿真证明，所提出的算法在解决背包问题时，算法的优化性能、优化速度和程序运行速度有了很大提高。参考文献，1王娜，凤红，毛剑林。解决0/1背包问题的改进遗传蚁群混合算法j .计算机工程和应用，(2013)09-0054-03 2姜兰，曹文良。混合遗传蚁群算法的改进及其在TSP问题上的应用研究j .科技