蚁群算法的运用及其优化分析

苏前义

摘 要：生物科学领域在快速的发展，人类善于从自然界中去学习，研究自然界，为自身的学习、工作、生活创造便利的条件。蚁群算法正是受到蚂蚁寻食所创造的一种启发性的算法。大量的研究证明，蚁群算法具有鲁棒性、并行性、正反馈性，是一种自组织的算法，但是它运行所需要的时间长，有时甚至会出现停滞的现象，但和遗传算法、模拟退火算法等其他算法相比依然具有不可忽视的优势。

蚁群算法没有强力的数学基础作为支撑，在实际运用中依然存在一些不足之处，希望有越来越多的人加入研究的行列，有越来越多的学者关注蚁群算法，推动蚁群算法的发展，更好地为人类的学习、工作、生活做贡献。

关键词：蚁群算法；蚁群算法的应用；粒子群算法；优化分析

中图分类号： TP301.6 文献标识码： A 文章编号： 1673-1069（2016）32-158-2

1 蚁群算法的提出

科学家们在研究群居性昆虫的时候发现，虽然它们单个只是简单的个体，但是它们一起合作却能一起完成复杂的工作。昆虫的这种群体生物智能特征，吸引了一些学者的目光。意大利学者M.Dorigo等人在研究蚂蚁的觅食过程中发现，蚂蚁似乎有一种本能，总能找到食物，总能找到巢穴与食物之间的最短路径。蚂蚁作为一种群居性昆虫，它们本身的视线很差，却能找到大量的食物。经过长期的观察与研究，于1991年M.Dorigo等人首次提出蚁群算法。

2 蚁群算法的应用

如今蚁群算法已经深入到我们生活的方方面面，在交通、智能、通信技术方面有着广泛的运用，在求解优化组合、网络路由问题、连续性空间优化问题、聚类分析、图像识别、电网故障分析等领域的应用已经取得了良好的效果。具体包括以下几种：

2.1 旅行商问题

蚁群算法最早是应用旅行商问题的解决，该问题的核心就是要求经过所有的城市，每个城市经过一次，还要返回到原来的出发点，这条线路要求是最短的。众多的实验研究结果表明，蚁群算法远远高于遗传算法、模拟退火法等其他优化算法。

2.2 二次分配问题

最开始的二次分配问题指的是，把m个工厂分配在m个城市，要求分配的时候所用的花费是最少的。这是蚁群算法在旅行商问题后的又一大应用。

2.3 车间任务调度问题

车间任务调度问题指的是一定数量的机器在一定的时间里完成一定的任务量，要求所有的机器同时运行，有序的操作，但所要的时间是最短的。

2.4 大规模集成电路问题

电路是错综复杂的，需要有一个点来支撑所有的电路，确保电路有序。

2.5 连续对象优化问题

蚂蚁一旦选择了一条目标，会一直向着目标前进，选择的路线是固定的，空间不是完整的，是分散的，局部的，若空间是线性的或非线性的连续空间，则相对较弱。使用蚁群算法解决连续对象优化问题，还要求信息素的浓度函数等循环过程。

3 蚁群算法的优化分析

蚁群算法是一种智能化算法，被广泛运用到各个方面，而且性能优良。但也看到蚁群算法要花费大量的时间，有时甚至会出现停滞的现象。在蚁群算法中起着关键作用的就是参数的选择，下面将基于粒子群参数优化，提出一种新的改进蚁群算法的算法。

粒子群优化算法通常也被称作粒子群算法、微粒群算法。这是一种模仿鸟类捕食的算法。鸟类在寻找食物的时候，目的是随机地，也是多样的，但区域里只有一块食物，并且它们也不知道食物在哪里。应如何找到食物，肯定是在食物附近的鸟类最先找到的，所以说在食物附近的鸟类是最有利的。这引起了一些学者的注意，由Kennedy等博士提出，认为这是一种群体智能。在粒子群算法中把区域里的每只鸟都看作是一个粒子。每个粒子还有一个速度决定他们飞翔的方向和距离，然后粒子们就追随当前的最优粒子在解空间中搜索。在初始化中，一群随机无序的粒子，要通过迭代才能找到最优解。要想找到最优解，每个粒子在迭代时通过更新两个极值来更新自己的信息素。第一个得到的解就是粒子本身所要寻找的最优解，另一个极值就是相对于整个种群來说最优解。第一个就是另外也可以不用整个种群而只是用其中一部分最优粒子的邻居，那么在所有邻居中的极值就是局部极值。要想找到这两个最优值时，粒子要及时更新自己的速度和新的位置，根据如下的公式：

v[] = v[] + c1 * rand（） * （pbest[] - present[]） + c2 * rand（） * （gbest[] - present[]） （a）

present[] = persent[] + v[] （b）

v[] 是粒子的速度， persent[] 是当前粒子的位置. pbest[] and gbest[] 如前定义 rand （） 是介于（0， 1）之间的随机数. c1， c2 是学习因子. 通常 c1 = c2 = 2.

程序的伪代码可以用如下的表示：

For each particle

____Initialize particle

END

Do

____For each particle

________Calculate fitness value

________If the fitness value is better than the best fitness value （pBest） in history

____________set current value as the new pBest

____End

____Choose the particle with the best fitness value of all the particles as the gBest

____For each particle

________Calculate particle velocity according equation （a）

________Update particle position according equation （b）

____End

While maximum iterations or minimum error criteria is not attained

利用粒子群優化蚁群算法的基本步骤：

步骤一：设立初始值，一定数量的粒子；

步骤二：将每个粒子所对应的参数值对应到相对应的蚁群算法中去，新的参数值会要求蚁群算法做出新的调整，在把这时的蚁群算法的参数值设定为初始值；

步骤三：根据蚁群算法的计算方式判断是优值还是差值；

步骤四：根据公式v[] = v[] + c1 * rand（） * （pbest[] - present[]） + c2 * rand（） * （gbest[] - present[]） （a）present[] = persent[] + v[] （b）改变粒子的速度和位置；

步骤五：若是得到的结果已经是最优解了，或者已经没有最优解了，则算法结束，反之，继续步骤二的操作。

信息素的更新决定了蚁群算法的求解质量。改进后的信息素只是用与每个粒子的一次移动，并且相互间是独立的，没有关联的，一旦结束后，所有的数据会消失掉，不会有所保留。粒子群优化算法作为一种启发式算法，具有下面的众多优点：

①描述简单，来自生活，理解起来也相对来说比较容易；

②相互间是独立的，打破了要求优化问题需要是连续性的问题；

③算法实施起来很容易，并且求解速度快；

④和其他的算法相比，不需要庞大的个体，小众的个体即可实现算法；

⑤大部分的参数是不需要去调整的，只有小部分的参数是需要去调整的；

⑥和其他算法相比，算法具有很强的收敛性；

⑦没有什么特殊的约束条件，个体间是独立的，不会影响到其他的粒子，具有很强的鲁棒性。

4 结束语

蚁群算法最先是用来解决旅行商问题，如今蚁群算法在各个方面被运用，得到了一定的效果。但是和遗传算法、模拟退火算法、微粒子算法相比，虽然得到的解更加优化，但是蚁群算法没有系统的分析方法，同时它的数学基础也不是很强大。在实际的操作过程中，参数的选取比较复杂。虽然在一些领域运用，但运用技术不成熟，还是习惯采用传统的方式。

参 考 文 献

[1] 石华瑀.改进的蚁群算法在实际VRP中的应用研究[D].山东大学，2012.

[2] 孟凡聪.优化的蚁群算法在快速公交系统中的应用研究[D].湖南大学，2011.