第２帝基本蚁群优化算法及已有的改进算法

时，蚂蚁不仅利用了路径上的信息素，而且用到了城市间距离的倒数作为启发式因子。Ｍ．Ｄｏｒｉｇｏ通过仿真实验表明，ａｎｔ－ｃｙｃｌｅ模型比ａｎｔ—ｑｕａｎｔｉｔｙ和ａｎｔ—ｄｅｎｓｉｔｙ模型有更好的性能。这是因为ａｎｔ－ｃｙｃｌｅ模型利用全局信息更新路径上的信息素量，而ａｎｔ－ｑｕａｎｔｉｔｙ和ａｎｔ－ｄｅｎｓｉｔｙ模型使用局部信息。ＡＳ算法的时间复杂度为Ｏ（ＮＣ．门３），其中Ⅳｃ表示迭代的次数，，７为城市数。

２．２蚁群系统

蚁群系统（即ＡＣＳ）是ＡＳ算法的改进版本，与ＡＳ算法的主要区别在于：（１）使用伪随机比率选择规则来选择选择下一座城市；（２）只在全局最优解所属的边上增加信息素；（３）每次当蚂蚁从城市ｉ转移到城市Ｊ时，边ｉｊ上的信息素将会适当的减少。

在ＡＣＳ算法中，蚂蚁使用伪随机比率选择规则（Ｐｓｅｕｄｏ

ｐｒｏｐｏｒｔｉｏｎａｌａｃｔｉｏｎｃｈｏｉｃｅｒａｎｄｏｍｒｕｌｅ）选择下一座城市。ｍ是蚁群中蚂蚁的数量，６』（ｆ）表示ｔ时刻位于城市ｖｉ的蚂蚁的个数，则肌＝∑６ｆ（ｆ）。令乃（ｆ）表示ｔ时刻在城市Ｅ，１，，路径上的信息素浓度，并设初始时刻各条路径上的信息素浓度均为Ｃ（常数）。蚂蚁ｋ在自己周游的过程中，根据可行的候选路径上的信息素浓度选择自己前进的方向。蚂蚁将按如下状态变迁规则来选择下一个城市：

。一ｊａｒｇ。ｍ”ａｘ｛［ｒｑ（，）】‘【嘞ｒ），１，ｉ＝气７矿ｑ＜ｑ。（利用’

ｏｔｈｅｒｗｉｓｅＨ∈“（２—７）、一‘７Ｖ（开发）

式中巩为路径～的能见度，表示该路径的启发信息，一般取，７口＝１／ｄ∥：∥分别表示路径口玎的启发信息对蚂蚁选路的影响权重；Ｕｋ表示蚂蚁ｋ在本次周游中在当前位置允许选择的城市列表，以＝｛Ｖ一禁忌列表Ｔａｂｕ。｝，该列表随着蚂蚁的周游过程作动态变化。ｑ。为设定的进行利用和开发的分界点参数，ｑ为使用均匀概率随机选取的概率值，ｑ。和ｑ的取值范围为［０，１］。Ｊ是一个按下面概率分布随机选择的一个城市变量，其值偏向于距离较短且信息素浓度较高的城市。

瓣ｊ拦器，Ｍ‘Ｉ，ＥＶ●治８，

ｌｏ’其他

ｐ：（力表示在ｔ时刻蚂蚁ｋ从城市Ｈ走向匕的概率。