第３帝蚁群算法中信息素增量和扩散模型的研究

时ｄ。＞２ｒ，则信息素扩散的浓度场及扩散范围可如图３—１（ａ）中灰色区域所示，图中小圆点●表示城市位置，黑色圆点●表示受扩散影响的城市，以ｉ、ｊ为中心的同心圆表示扩散场内不同位置浓度场强的等势线。从图可见，城市信源作为信息素扩散浓度场的中心，离信源越近，浓度场的场强越强（等势线越密）。除所经过的城市ｉ和ｊ外，蚂蚁ｋ在本次行走中还会影响位于城市Ｃ。、Ｃ：、Ｃ。、Ｃ。上蚂蚁选路的行为。然而，根据假设ｌ，信息素是滞留在蚂蚁所经过的整条路径上的，所以信息素应以所依附的路径ａ口为中心向外扩散，因而，图３—１（ａ）中的扩散模型存在一定的局限。因此，可对其进行改进，将扩散模型修正为以路径为信源向周边扩散，如图３－１（ｂ）所示，蚂蚁ｋ在从城市ｊ走到ｉ的过程中所留下的信息素将形成更大范围的浓度场，影响的城市集合也扩大为Ｃ．、Ｃ：、Ｃ。、Ｃ。、Ｃ。、Ｃ。、Ｃ，、Ｃ。。这种变化更客观地反映了信息素扩散的浓度场，扩大了信息素扩散的作用范围。

ｌ（ｘｏ，ｙＯ

ⅨＩ，ＹＯ“１（ｘ２，ｙｏ

图３－２在信息素扩散浓度场内扩散距离求解的示意图

Ｆｉｇｕｒｅ３－２Ｔｈｅｓｋｅｔｃｈｍａｐｏｆｐｈｅｒｏｍｏｎｅｄｉｆｆｕｓｉｏｎｉｎｉｎｔｅｎｓｉｔｙｆｉｅｌｄ

设蚂蚁刚走过路径ａＦ，基于路径为信源的信息素扩散模型，下面推导由蚂蚁的此次行走所影响到的相邻路径上的信息素浓度。为了求城市１到路径％的垂直距离ｄ，我们分两种情况讨论：

１）当ＴＳＰ问题中的城市位置用坐标给出时，如图３—２所示，城市ｉ、

ｌ的坐标分别为（ｘ。，ｙ。）、（ｘ：，ｙ：）和（ｘ。，ｙ。），推导如下：

当Ｘ１＝ｘ：时，由ｉ、ｊ两点形成的直线Ｌ垂直于ｘ轴，Ｌ的方程为：ｘ＝ｘ－；

＾２一＾Ｊ和当ｘ。≠ｘ：时，由ｉ、ｊ两点形成的直线Ｌ的方程为：ｙ－ｙ。＝警（ｘ一而）；

将直线Ｌ的表达式化为形如锻＋砂＋ｃ＝０的标准形式，依据点到直线的距离公式，可以得到１点到直线Ｌ的距离：ｄ：一ｌａｘｏ＋ｂｙｏ＋ｃｌ。√口２＋６２

２）当ＴＳＰ问题中城市间的距离已知时，即在图３—２中已知吻、％、嘞，此时，可以利用海伦公式求垂直距离ｄ，方法如下：令ｓ＝（ａｕ＋即＋口ｆＩ）／９．，则三角形ｉｊｌ的面积为Ａ＝√ｓｏ一～）（ｓ－ａｊ，）ｏ—ａｉｒ），又因为Ａ＝（ｄ 口｛『）／２，所以ｄ＝２Ａ／ａ扩。

在得到城市ｌ离路径信源的距离ｄ后，我们就可判断城市ｌ是否位于蚂蚁ｋ在本次行走中所形成的信息素浓度场的扩散范围内，如果在扩散半径内，就依据