蚁群算法在0-1背包问题中的研究与实现

摘要：蟻群算法也称为蚂蚁算法，即模拟蚂蚁从居住地出发去寻找食物源的过程，它在一定程度上可以看成是一种用来在图中寻找最优路径的算法。该算法已成功地应用于许多离散问题。随着研究的深入与应用领域的逐步扩展，蚁群算法已经在智能领域显示出了较为重要的地位，对于解决各种复杂优化问题都显示出了它的优点。0-1背包问题是一个经典算法，在实际生活中应用较为广泛，例如在材料切割、货物装箱、车间调度等问题中都有相关的应用。本文主要实现了蚁群算法解决0-1背包问题，首先研究了蚁群算法的基本原理及算法思想，然后在MATLAB下实现了蚁群算法求解0-1背包问题。实验表明，算法运行结果正确，稳定性好。

关键词：蚁群算法;0-1背包;信息素;挥发因子

中图分类号：TP 391

引言

蚁群算法是一种群体智能理论的优化算法，蚁群算法的基本思想是根据蚂蚁从蚁巢出发去寻找食物源的过程得出的。蚁群算法如今也多用于求解旅行商问题，随着网络科技的发展，网购等在人们的生活中所占比重越来越大，还有近几年流行的‘UU跑腿’等，这些实际生活中的问题都会用到蚁群算法，该算法已经成功地应用到了许多离散问题中，在国际群体智能计算领域，蚁群算法已经成为一个热门的研究方向。

背包问题最早是由 Dantzing在 20 世纪50 年代首次提出的，应用已经越来越广泛。背包问题是指：对于n个物品和一个背包，当知道每个物品的重量和价值以及背包所能承受的最大重量时，从这些物品中选出若干件放入背包中，使得背包的重量小于背包所能承受的最大重量，并且背包的总价值能够达到最大。背包的总价值等于装入背包的物品价值之和，找出一种放入物品的方案能同时满足上述两个条件。

记背包的总重量为为total_weight，总价值为total_value，x（i）=1表示将第i个物品放入背包，x（i）=0表示未放入，根据0-1背包问题的算法原理，可将其数学模型表示为如下：

1  蚁群算法的算法思想

蚁群算法是指蚂蚁从蚁巢出发去寻找食物的过程中，当蚁巢到食物源的距离越短，则蚂蚁从巢到食物源，然后再返回巢的时间越短。这相当于在相同的时间内，路径越短蚂蚁会分泌和积累越多的信息素，而随后去寻找食物的蚂蚁会根据前面蚂蚁分泌的信息素来判断哪条路径最短，以便能够快速准确的选择哪条路径。所以某条路径上的信息素越多，蚂蚁选择这条路的可能性就越大。

2  蚁群算法实现0-1背包的算法步骤

蚁群算法的算法步骤如下：

（1）初始化参数：设置蚁群参数，背包相关的参数，路径信息素等参数;

（2）蚂蚁移动：后续出发的蚂蚁根据前面蚂蚁留下的信息素含量和一定的概率来选择要行走的路径，在实现0-1背包问题中计算某个物品被选择的概率;

（3）蚂蚁要行走的路线信息更新：根据（2）中计算的概率，蚂蚁将选择某条路径，同时将对应的物品添加到路径中;

（4）判断是否满足条件：判断将物品添加到背包后是否满足条件，并更新背包的价值的重量;

（5）评价蚁群：计算一次循环结束后的最优值，将其与全局最优值比较，判断是否需要更新全局最优值。

3  算法实现

（1）初始化参数：定义物品的价值，重量以及背包能承受的最大重量;定义信息素挥发因子为r，全局最优解为Jie_best，全局最优值为value_best，定义最大迭代次数为count ;

（2）从i=1到count循环遍历：定义一个零矩阵用以存储m只蚂蚁的路径，j从1到n开始循环，根据信息素的重要因子（a）及吸引因子（b）计算每个物品被选择的概率。

for j=1：n

d=d+t（j）^a*（value（j）/weight（j））^b;

end

for j=1：n

q（j）=t（j）^a*（value（j）/weight（j））^b/d;

end

（3）选择物品放入背包：先随机选取一个物品放入背包，并将其添加到当前对应蚂蚁的路径中，修改背包当前的容量。

x=floor（rand*9）+1;

D（k，x）=1;

W_now=weight（x）;

（4）更新路径及背包信息：利用轮盘赌法，信息素挥发系数计算下一个物品被选择的概率，如果满足背包容量限制条件则将其加入背包中，并更新当前蚂蚁的路径信息和背包信息。

j=roulette_wheel（u，temp）;

u=u-temp（j）;

Temp（j）=0;

if（W_now+weight（j）<=W）

D（k，j）=1;

W_now=W_now+weight（j）;

（5）更新全局最优值：一次迭代完成后将本次迭代的最优值与全局最优值对比，根据对比结果重新定义全局最优值。

[p_best（i），J]=max（D*value’）;

if（value_best<p_best（i））

value_best=p_best（i）;

Jie_best=D（J，：）;

4  运行结果

图1是输入5个物品时的运行结果，随机输入5个物品的价值和重量可由蚁群算法求出背包的最大价值，最大重量以及装入背包的物品序号。由图1可知，对于给定的物品价值和物品重量，背包的最大容量以及其他相关参数，图2算法求得背包的最大价值，最大重量以及装入背包的物品序号，在改变相关参数时背包的价值和重量，最优解不会改变，但是达到最有解的迭代次数会发生相应的变化。在一定的范围内，当挥发系数增加时，达到最优解的迭代次数越大。这一结果在理论上也可以解释，因为当信息素挥发系数越大时，后续蚂蚁在寻找食物时选到最短路径的概率就会越小，因此全局找到最短路径的时间就越长，这一原理体现在0-1背包问题中就是选择下一个物品装入背包时，选到使背包最终价值最大的物品的时间会越长。

5  结语

蚁群算法的研究现在已经达到了相对成熟的水平，已有不少学者进行了大量的研究，提出了很多研究结论和宝贵经验，本文基于蚁群算法实现了0-1背包问题。针对蚁群算法，虽然它可以应用到货物配送等问题中，但是在实际的配送中可能需要考虑更多的因素，例如当有物品需要特殊处理或优先配送时需要对蚁群算法进行一定的改进，体现在蚁群算法中就是优先处理有特殊需求的城市顶点，后面将对这一点进行进一步的研究。

参考文献：

[1]M. Dorigo，V. Maniezzo，A. Colorni，“Ant system optimization by a colony of cooperating agents，” IEEE Transactions on System，Man，and Cybernetics-Part B，1996，26（1）. 8- 41.

[2]M. Dorigo，L.M. Gambardella. “Ant colony system：a cooperative learning approach to the traveling salesman problem，” IEEE Transactions on Evolutionary Computing，1997，1（1）. 53- 56.

[3]胡小兵. 蚁群优化原理、理论及其应用研究[D]. 重庆大学，2004

[4]鄢莉. 0-1背包问题的算法决策分析[J]. 电脑知识与技术，2020，16（04）：259-260+264.

[5]田峰楠，王于. 求解0-1背包问题算法综述[J]. 软件导刊，2009，8（01）：59-61.

[6]宋志飞. 基于蚁群算法的TSP问题研究[D]. 江西理工大学，2013.

[7]弓英瑛. 蚁群算法的改进研究与应用[D]. 安徽理工大学，2014.

作者简介：宇亚卫（1979-），女，陕西乾县人，硕士，讲师，主要从事图形图像处理方面的教学和研究工作。