蚁群算法及其应用研究(13)

北京Ｔ业大学Ｔ学硕十学位论文

己周游的过程中，将根据目前可行的候选路径上滞留的信息素浓度随机地选择自己前进的方向。具体地说，从城市ｉ走向城市ｊ的转移概率为：枷ｊ器，Ｍ

ｌＩＥＵｋ治 ，

１０，其他

其中，Ｕ。表示蚂蚁ｋ在本次周游中在当前位置允许选择的城市列表，Ｕ。＝｛Ｎ一已访问过的城市列表Ｔａｂｕｔ），ｒ／，ｊ为路径％的能见度，可理解为该路径的启发信息，一般取％＝Ｉ／ｄ∥；硼∥分别表示路径％上的残留信息和启发信息对蚂蚁选择转移方向时的影响权重。

蚁群在觅食过程中，一方面蚂蚁会在行走的路径上留下新的信息素，另一方面随着时间的推移已有的信息素会逐渐挥发。蚁群中的每只蚂蚁从出发城市开始，经过ｎ次路径选择后，回到出发点并完成一次周游。这时，对蚁群所经过的每条路径上的信息素按照下式进行一次更新：

ｆｐ（ｆ＋一）＝ｐ ｆ∥Ｏ）＋△乃，（２—２）ＡｒＦ＝∑△ｆ；，（２—３）纠：倦黼绷蚁在本次周游叭Ｈ…帜）经过路径口口时【０否则（２－４）

式中参数Ｐ表示信息素的挥发程度（可视为残留系数），△ｆ！表示在本次周游中蚂蚁ｋ留在路径％上的信息素，而△％表示整个蚁群在本次周游后路径％上的信息素增量。Ｑ为常数，Ｌｋ为蚂蚁ｋ在本次周游中所经过的旅行长度。

Ｍ．Ｄｏｒｉｇｏ提出了３种增量模型，式（２－４）为ａｎｔ－ｃｙｃｌｅ模型；另外两个模型分别称为ａｎｔ—ｑｕａｎｔｉｔｙ和ａｎｔ－ｄｅｎｓｉｔｙ，其差别主要在（２—４）式，

其中ａｎｔ—ｑｕａｎｔｉｔｙ模型表示为：

△苟：塄当第七只蚂蚁在（㈩＋ｌ时段）经过路砜时

【０否则（２＿５）

而ａｎｔ—ｄｅｎｓｉｔｙ模型表示为：

峥摇喜≯蚂蚁引ＨＨ！时段炀过路鲍时

（２－６）ＡＳ算法实际上是正反馈原理和启发式算法相结合的一种算法。在选择路径