蚁群算法在旅行商问题中的应用及流程解析

蚁群算法（Ant Colony Algorithm）是由意大利学者多里科（Dorigo M）等在1991年的首届欧洲人工生命会议上提出的[Colorni et al.1991]，该算法利用群体智能解决组合优化问题。多里科等将蚁群算法先后应用于旅行商问题（TSP）、资源二次分配问题等经典优化问题，得到了较好的效果。蚁群算法在动态环境下也表现出高度的灵活性和健壮性，如其在电信路由控制方面的应用被认为是较好的算法应用实例之一。

（一）蚁群算法模型

自然界中的蚂蚁觅食是一种群体行为，并非单只蚂蚁自行寻找食物源。蚂蚁在寻找食物的过程中，会在其经过的路径上释放信息素（Pheromone），信息素是容易挥发的，随着时间推移遗留在路径上的信息素会越来越少。蚂蚁在从巢穴出发时如果路径上已经有了信息素，那么蚂蚁会随着信息素浓度高的路径运动，然后又使它所经过的路径上的信息、素浓度进一步加大，这样会形成-个正向的催化。经过一段时间的搜索后，蚂蚁最终可以找到一条从巢穴到食物源的最短路径。

德纳伯格（Deneubourg J L）及其同事为了验证蚂蚁觅食的特性，在阿根廷进行了实验。实验中建造了一座有两个分支的桥，其中一个分支的长度是另一个分支的两倍，同时把蚁巢和食物源分隔开来。实验发现，蚂蚁通常在几分钟内就选择了较短的那条分支。

蚁群算法首先成功应用于TSP 问题。下面简单介绍其基本算法。已知一组城市N， TSP问题可表述为寻找一条访问每一个城市且仅访问一次的最短长度闭环路径。设dij为城市i到j 之间欧氏距离路径长度。TSP 的实例是已知一个图G（N，E）， N 是一组城市， E 是一组城市间的边。下面以TSP问题为例说明蚁群算法流程。

1.nc=O（nc为迭代步数或搜索次数）；将各Tij和ΔTij初始化；将m只蚂蚁置于n个顶点上。

2.将各蚂蚁的初始出发点置于当前解集中；对每个蚂蚁k，按伪随机比例规则式移至下一顶点j；将顶点j置于当前解集。

式中，q0∈[0，1］为常数；q∈[O，l］为随机数；J是根据概率公式给出的概率分布产生出来的一个随机变量。

式中， allowedk表示蚂蚁k 下一步允许选择的城市集合；ηij=1/dij。

3.计算各蚂蚁的目标函数值；记录当前的最好解。

4.按更新式修改轨迹强度。

5.对各边弧（i，j），置nc=nc +1。

6.如果nc ＜预定的迭代次数且无退化行为（即找到的都是相同解），则转步骤2。

7.输出目前最好解。

（二）基于群体智能的混合聚类算法CSIM

基于群体智能的聚类算法的主要思想是将待测对象随机分布在一个二维网格的环境中，简单个体如蚂蚁测量当前对象在局部环境的群体相似度，并通过概率转换函数得到拾起或放下对象的概率，以这个概率行动，经过群体大量的相互作用，得到若干聚类中心。最后，采用递归算法收集聚类结果。

群体相似度是一个待聚类模式（对象）与其所在一定的局部环境中所有其他模式的综合相似度，基本测量公式如下：

式中，Neigh（r）表示局部环境，在二维网格环境中通常表示以r为半径的圆形区域；表示对象属性空间里的对象oi与oj之间的距离，常用方法是欧氏距离；α定义为群体相似系数，是群体相似度测量的关键系数。α直接影响聚类中心的个数，同时也影响聚类算法的收敛速度；α最终影响聚类的质量，若群体相似系数过大，不相似的对象可能会聚为一类，若群体相似系数过小，相似的对象可能分散为不同的类。

概率转换函数是将群体相似度转换为简单个体移动待聚类模式（对象）概率的函数。它是以群体相似度为变量的函数，函数的值域是［0，1］。同时，概率转换函数也可称为概率转换曲线。它通常是两条相对的曲线，分别对应模式拾起转换概率和模式放下转换概率。概率转换函数制定的主要原则是群体相似度越大，模式拾起转换概率越小，群体相似度越小，模式拾起转换概率越大，而模式放下转换概率遵循大致相反的规律。按照概率转换函数制定的主要原则，采用了一条简单曲线，即斜率为k 的直线，如下所示：

基于群体智能的混合聚类算法CSIM主要包括两个阶段：第一阶段是实现基于群体智能的聚类过程；第二阶段是以第一阶段得到的聚类中心均值模板和聚类中心个数为参数，实现K均值聚类过程。

基于群体智能的混合聚类算法CSIM：

（1）初始化α、ant_number、k、R、size、最大循环次数n、标注类别值clusterno等。(www.xing528.com)

（2）将待聚类模式随机分散于一个平面上，即随机赋给每一个模式一对（x，y）坐标。

（3）给一组蚂蚁赋初始模式值，初始状态为无负载。

（4）for i＝1，2，…，n；

①for j=1，2，…，ant_number；

a.以蚂蚁初始模式对应坐标为中心，r为观察半径，利用上式计算此模式在观察半径范围内的群体相似度。

b.若蚂蚁无负载，则用上式计算拾起概率PP。

c.与一随机概率Pr相比较，若PP＜Pr，则蚂蚁不拾起此模式，再随机赋给蚂蚁一个模式值，否则蚂蚁拾起此模式，蚂蚁状态改为有负载，随机赋给蚂蚁一个新坐标。

d.若本只蚂蚁有负载，则计算放下概率Pd，即

e.与一随机概率Pr相比较，若Pd＞Pr，则蚂蚁放下此模式，将蚂蚁的坐标赋给此模式，蚂蚁状态改为无负载，再随机赋给蚂蚁一个模式值，否则蚂蚁继续携带此模式，蚂蚁状态仍为有负载，再次随机给蚂蚁一个新坐标。

（5）for i=1，2，…，pattern_num；

①若此模式未被标注类别，则

a.标注此模式的类别。

b.用同一类别标注值递归标注所有相距小子dist的模式，即在平面上收集所有属于同一集簇的模式。

c.If同一集簇模式数＞1，类别标注值clustemo++；

Else标注此模式为例外。

（6）生成聚类中心模板，即计算不包括例外的每一个聚类中心的平均值。

（7）Repeat

①（再次）将每一个模式以距离最近的规则划分到所属聚类中心。

②更新聚类中心模板。

（8）Until聚类中心模板没有变化。

可以看出，步骤1～3是算法初始阶段，它的主要作用是程序初始化和在平面上随机分布模式；步骤的是基于群体智能的聚类过程，是算法的主要过程；步骤5是模式类别标注过程，也就是聚类结果收集过程。