・1418・
系 统 仿 真 学 报 Vol. 15 No. 10
JOURNAL OF SYSTEM SIMULATION October 2003
具有感觉和知觉特征的蚁群算法
陈 崚1,2, 秦 玲1, 陈宏建1, 徐晓华1
（1扬州大学信息学院计算机系, 江苏扬州 225009; 2南京大学软件新技术国家重点实验室, 江苏南京 210093）
摘 要：针对传统蚁群算法加速收敛与早熟、停滞现象的矛盾，模仿蚂蚁感觉和知觉行为提出一种新的蚁群优化算法, 使蚂蚁受显意识和潜意识的相互作用选择路径，同时自适应地修改路径上的信息量.以多种不同规模的对称和不对称旅行商问题（TSP）为例进行的仿真结果表明算法具有较好的收敛速度和稳定性，比较适合求解城市数目较多的TSP问题。 关键词：蚁群算法；感觉；意识；旅行商问题
文章编号：1004-731X (2003) 10-1418-08 中图分类号：TP37 文献标识码：A
Ant Colony Algorithm with Characteristics of Sensation and Consciousness
(1 Department of Computer Science, Yangzhou University, 225009, China; 2 National Key Lab of Novel Software Tech, Nanjing 210093, China)
CHEN Ling1,2, QIN Ling1, CHEN Hong-jian1, XU Xiao-hua1
Abstract：A new ant colony optimization algorithm which simulates the ants’ behavior according to the laws of sensation and consciousness is presented in order to make balance between accelerating convergence and averting precocity as well as stagnation. The algorithm selects path by the mixed influence of consciousness and subconsciousness, and updates the trail information of each path adaptively in each step. The results of simulation on several symmetric and asymmetric TSPs with different sizes indicate that the algorithm has much higher convergence speed and stability than that of classical ant colony algorithm, and is more suitable for solving large scale TSP.
Keywords：ant colony algorithm; sensation; consciousness; traveling salesman problem
引 言
蚁群算法是近来出现的一种新型的模拟进化算法。它是由意大利学者M.Dorigo等人首先提出来的[1]，他们充分利用蚁群搜索食物的过程与旅行商问题（TSP）之间的相似性,解决了TSP问题[2]，取得了很好的结果.随后,蚁群算法被用来求解分配问题、图论问题[3]、指派问题[4,5], 电力系统故障诊断[6]等NP完全问题,显示出蚁群算法在求解复杂优化问题方面的优越性。
在蚁群算法中，蚂蚁总是依赖于其它蚂蚁的反馈信息来强化学习，而不去考虑自身经验积累。这样的盲从行为，容易导致早熟、停滞现象，使收敛速度变慢。为了解决此问题，本文提出一种新的蚁群算法，该算法模拟蚂蚁感觉和知觉行为，并受显意识和潜意识的相互作用选择路径，使之在初始阶段接受自己经验的影响, 此后逐步有条件地接受信息量的影响，同时自适应地修改路径上的信息量。这样，可在加速收敛和防止早熟、停滞现象之间取得很好的平衡。我们从通用的TSPLIB[20] 中选用不同大小的对称和不对称TSP问题为例所进行的计算结果表明，该方法比一般蚁群算法具有
更好的收敛速度和稳定性，比较适合求解城市数目较多的TSP问题。
1 基本蚁群算法
实验观察表明, 蚂蚁在觅食过程中会留下一种分泌物（pheromone）即信息素，若蚂蚁从巢穴到食物源所走的路径较短，则该蚂蚁从巢穴到食物源后再返回到巢穴的时间就短，从而相同时间内较短路径上蚂蚁所分泌的信息素较多。由于其后面的蚂蚁要根据前面走过的蚂蚁所留下的分泌物的多少选择其要走的路径，一条路径上的分泌物越多，蚂蚁选择这条路径的概率就越大。因此，蚂蚁群体的集体行为实际上构成了一种学习信息的正反馈机制，蚂蚁之间通过这种信息交流寻求通向食物的最短路径。蚁群算法正是模拟了这样的优化机制, 即通过个体之间的信息交流与相互协作最终找到最优解。
我们以TSP问题为例说明基本蚁群算法的框架。设有n个城市，dij ( i,j =1,2,…, n) 表示城市i和 j 间的距离,τij(t) 表示在t时刻城市i和 j 之间的信息量，我们以此来模拟实际蚂蚁的分泌物。设共有m只蚂蚁，用pijk (t) 表示在t时刻蚂蚁k由城市i转移到城市 j 的概率，则
β
ταij(t)ηijαβpkij(t)=∑r∈allowedτir(t)ηir
k
0
收稿日期：2002-06-28 修回日期：2003-03-10
基金项目：国家自然科学基金(60074013)、国家高性能计算基金(00219 )、江苏省教育厅自然科学基金和南京大学软件新技术国家重点实验室开放基金。
作者简介：陈 崚(1951-), 男, 江苏宝应人, 教授, 研究方向为并行计算和算法设计与分析；秦 玲(1979-), 女, 江苏泰兴人, 硕士生, 研究方向为并行计算和优化算法；陈宏建(1968-), 男, 江苏海安人, 讲师；徐晓华(1979-), 男, 江苏通州人, 硕士生。
j∈allowedk否则
(1)
其中，allowedk 表示蚂蚁k
下一步允许走过的城市的集合,
α表示路径上的信息量对蚂蚁选择路径所起的作用大小。
Vol. 15 No. 10
October 2003 陈 崚, 等：具有感觉和知觉特征的蚁群算法 ηij 为由城市i转移到城市 j 的期望程度，例如可以取ηij＝1/dij，β表示ηij的作用大小程度。当α=0时, 算法就是传统的贪心算法；而当β=0时, 就成了纯粹的正反馈的启发式算法。 经过n 个时刻，蚂蚁可走完所有的城市，完成一次循环。每只蚂蚁所走过的路径就是一个解。此时，要根据下式对各路径上的信息量作更新：
τij(t＋1)＝（1-ρ）*τij(t)+Δτij (2) 其中ρ∈(0,1), 为蒸发因子，表示信息量τij(t) 随时间的推移而衰减的程度。信息增量Δτij 可表示为：
m
k
・1419・
率，实现了选择概率的自适应，提高了算法的速度和性能。
2 具有感觉和知觉特征的蚁群算法
科学研究表明，蚂蚁对于外界刺激物有着惊人的感觉和知觉能力。在蚁群中，单只蚂蚁的能力和智力非常有限，但是整个蚁群可以有足够的能力来完成筑巢、觅食、迁徙、清扫蚁穴等复杂行为。它们可以在各自的感觉和知觉能力的支配下，很好地相互协调、分工、合作并完成任务。因此，我们可以在蚁群算法中模拟蚂蚁的这种感知现象，让蚂蚁根据知觉和感觉规律选路，以在加快收敛速度的同时保证解的多样性。根据感知规律，我们将蚁群算法中蚂蚁的搜索过程分为如下三个阶段:
∆τij=∑∆τij (3)
k=1
Δτijk表示蚂蚁k在本次循环中在城市i和 j之间留下的信息量, 它的计算公式根据计算模型而定, 例如在最常用的ant circle system 模型中
Q/Lk∆τk=ij
0
若蚂蚁k经过城市i和城市j之间否则
2.1 蚂蚁搜索的初始阶段
心理学研究指出[17]，感觉和知觉是客观事物作用于神经系统引起神经系统的活动而产生的。产生感觉和知觉的神
(4) 经机构叫分析器，感受性是分析器对适宜刺激的感觉能力。感觉是大脑对当前直接作用于感觉器官的客观事物的个别属性的反映，而知觉是其整体属性的反映，两者紧密相关。但是不是所有的刺激都能引起人或者动物的感觉，只有达到一定量的刺激才能引起相应的感觉。现实中，往往会出现这样的情况：同是一种刺激，这个人感觉到了，另一个人感觉不到，就说明了他们的感受性不同。感受性是用感觉阈限的大小来度量的，感觉阈限是能引起感觉的、持续了一定时间的刺激量。心理学上把刚刚能引起感觉的最小刺激量，称为绝对感觉阈限（Absolute Sensor Threshold）。
在蚁群算法中，蚂蚁搜索过程的起始阶段，有的路径上有蚂蚁走过，有的路径还未来得及被走过。而蚂蚁选路的策略是一旦路径上有刺激物，即信息量多于其它路径，哪怕是很微弱的优势，它就以较大的概率选择该路径。这使得蚂蚁从搜索的一开始就以很大的概率集中到几条长度较短的路径上。实践中我们观察到，蚂蚁在搜索的初始阶段所得到的这些路径的整体长度往往都偏大，导致了搜索所得的结果是局部最优而不是全局最优。
为了避免蚂蚁从搜索的一开始就失去解的多样性，我们受绝对感觉阈限原理的启发，在路径上信息量的刺激量未达到蚂蚁的绝对感觉阈限时，让蚂蚁忽视该刺激物的存在，也就是让蚂蚁在搜索初始阶段的选路不受信息量的影响。这里我们记蚂蚁的绝对感觉阈限为AST，只有当信息量积累到超过AST时，蚂蚁才在信息量的刺激下趋于选择信息量较大的路径。这样，可以让蚂蚁在初始阶段选择较多的不同路径，以获得多样化的解，避免蚂蚁陷入局部最优，让蚂蚁尽量少走“冤枉路”。大量的实验表明，这种方法有利于让蚂蚁向最优方向进行搜索并很快收敛，大大节约了计算时间。
其中，Q 为常数，Lk 为蚂蚁k在本次循环中所走路径的长度。在经过若干次循环以后, 可以根据适当的停止条件来结束计算。
蚁群算法通过蚂蚁之间的信息量来实现选择机制、更新机制和协调机制，这些机制使得蚁群算法具有很强的发现较好解的能力。但是，蚁群算法也有一些缺陷。例如，由于蚁群中多个个体的运动是随机的，当群体规模较大时，要找出一条较好的路径需较长的搜索时间。为此,吴庆洪等人提出了具有变异特征的蚁群算法[7]，有机结合了2-opt方法提高了算法的性能。M.Dorigo 等人在基本的蚁群算法的基础上提出称之为Ant-Q System的更一般的蚁群算法[8,9]，每次让信息量最大的路径以较大的概率被选中，以充分利用学习机制，强化最优信息的反馈。为了克服在Ant-Q中可能出现的停滞现象，T. Stutzle等人提出了MAX－MIN 蚁群系统[10]，允许各个路径上的信息量在一个限定的范围内变化。L.M.Gambardella等人提出了一种混合型蚁群算法HAS[11]，在每次循环中蚂蚁建立各自的解后，再以各自的解为起点用某种局部搜索算法求局部最优解，作为相应蚂蚁的解，这样可以迅速提高解的质量。H.M.Botee 等人对参数m、α、β、ρ的选择进行了深入的研究，用遗传算法求得这些参数最优组合[12]。另外，G. Bilchev 等人曾在使用遗传算法解决工程设计中连续空间的优化问题时，使用了蚁群算法对遗传算法所得到的初步结果进行精确化，取得了较好的效果[13]。我们也曾经直接将蚁群算法改进使其能够直接求解线性和非线性规划等连续空间的优化问题[14]。吴斌、史忠植提出了基于蚁群算法的分段求解算法[15] 提高了蚂蚁搜索的速度，为蚁群算法的并行化奠定了基础。由于蚁群算法构造解的过程中，选择策略一般是随机的，进化速度较慢。张纪会等人提出了自适应的蚁群算法[16]，采用确定性选择和随机选择相结合的策略，在搜索的过程中动态地调整选择的概
2.2 蚂蚁搜索的中间阶段
刺激物引起感觉之后，如果刺激量发生了变化（增多或减少），也会引起感觉的变化。但是，并不是刺激的所有变
・1420・
Vol. 15 No. 10
系 统 仿 真 学 报 October 2003
按照自己的潜意识作用选路。此时，如果蚂蚁k在某一条路径上走过的次数越多，它对这条路径越熟悉，其潜意识作用下选择该路径的概率就大；反之，当一条路径上其它蚂蚁的信息量越多，则潜意识中蚂蚁k对该路径就越排斥，该路径被选择的概率就小。这种机制有效地防止了蚂蚁一味相信他者而造成的盲从现象，大大的降低了大量蚂蚁聚集于少数局部较优路径上造成早熟、停滞现象的可能性。当信息量变化较大时，蚂蚁在显意识作用下受整体信息量的影响而选路，遵循路径上走过的蚂蚁越多选择该路径的概率越大的原则，趋向于选优势较大的路径（这里的优势主要指其信息量较大和长度较短），保证了所选路径的优越性而且加快了收敛速度。
化量都能引起感觉[18]。例如，在100克的重量上如果只增加1克的重量，我们感受不到两者的差异。由于经验和潜意识的作用，当刺激条件的改变幅度仅局限于一定的范围内时，包括特定感觉的知觉的映象仍然保持相对不变，这就是知觉的“恒常性”。只有当刺激变化到一定量时才能使我们感觉到差别，能引起差别感觉的刺激物的最小变化量，称为差别感觉阈限（Contrast Sensor Threshold），记作CST。早在19世纪前半期，德国心理学家韦伯在研究差别感觉阈限时发现，差别感觉阈限随原来刺激量的变化而变化，而且表现为一定的规律性。在一定的范围内差别感觉阈限与原来的量的比值是一个常数。如果将它用公式来表示，设I表示原来刺激物的强度，△I表示差别感觉阈限，那么在I小于某个特定的限度IT（intensity-threshold）时，就有
∆=K
2.3 蚂蚁搜索的结束阶段
由于韦伯定律只能在刺激物的强度I小于某个特定的限度IT时才能适用，在超过IT时并不适用，故当路径上信息量达到相当大的程度时，我们应改变蚂蚁的选路策略。为了确定IT的值，我们首先估计各个路径上可能的最大信息量τmax 。由于一条路径上的信息量取得最大只能是在所有蚂蚁每次迭代都走该路径的情况下，若预定蚂蚁搜索的最大遍历次数为NC，蚂蚁总数为m，则此时的最大信息量可以表示为
τmax=NC×m×适应度的数量级
此处K是一个常数，称为韦伯系数。这就是著名的韦伯定律（Weber’s Law），重量感觉的韦伯系数为1/30，听觉为1/10，视觉为1/100。
由于各条路径上的信息量也是在不断变化的，我们将上述定律应用到蚁群算法的搜索过程中。我们改变传统蚁群算法中信息量一旦变化就直接影响蚁群选路的做法，认为蚁群在一定刺激强度范围内也存在一个差别感觉阈限。当路径上信息量的增加或减少的量在差别感觉阈限CST之下时，蚂蚁遵循知觉的恒常性规律，感受不到该路径上信息量的变化，该条路径被选择的概率主要依据于以前迭代中蚂蚁选路经验形成的潜意识作用；反之，蚂蚁受其显意识控制，按照路径上所有蚂蚁信息量高低决定选路概率的大小。根据韦伯定律，在具体实现此过程时，我们取
CST=τij(t)×K
这里，K为蚂蚁对信息量感觉的韦伯系数，本文取值为1/50。若记
k
αijθijk=βijk
τ(t)η
ijij
从AST的定义可知，此处适应度的数量级应该和AST相当，所以我们取
IT = h·τmax = h×NC×m×AST
这里h为一常数，可取1/2、2/3或3/4等。应该看到，某路径上信息量强度较大，可能是因为进入了局部最优的状态，或者是因为整个蚂蚁的群体遍历行为已经接近尾声。但由于上述的搜索的中间阶段的选路策略已经有效地避免了停滞现象的产生，所以此时不大可能是因为陷入局部最优，而是因为这些路径占有绝对优势。为加快收敛，此时我们引用Ant-Q中的选路策略[8,9]来选择下一城市j：
∆τij≤CST否则
τij(t)−τk(t)ij
h∈allowedk
其中：α=
k
k
ij
kτij(t)h∈allowedk
∑
τihtk
β=k
ij
∑
τt−τtih
kij
argmax{τtj∈allowed}
ijk
j=
蚂蚁k以公式(7)的概率选择城市j
()
q≤q0否则
(6)
τij(t)表示至t时刻蚂蚁k在路径(i, j)上历次遗留的总信
息量，ηij＝1/dij 。这里，我们用αij表示蚂蚁k的潜意识作用下路径(i, j)对它的吸引程度，βij 表示该路径对其他蚂蚁的吸引作用。实际上，当蚂蚁k按照其潜意识选择路径时，βij包含了所有其它蚂蚁所留信息量的作用，干扰了蚂蚁k的潜意识，构成了潜意识作用下蚂蚁k对路径(i, j)的排斥作用。蚂蚁k选择路径(i, j)的概率为：
k
θijkk
pij=∑θih
h∈allowedk0
τij(t)ηij(t)
pij(t)=∑r∈alloedτir(t)ηir(t)
k
0
k
j∈allowedk
否则
(7)
其中ηij(t)=1/dij，q为产生的随机数，q0为一常数。通过大量的实验，我们选取q0的值在0.7左右。
2.4 算法框架
综上所述，算法的框架可以描述如下：
main( ) {
j∈allowedk
否则
(5)
(a). 初始化
随机产生m个初始解，计算这m个初始解的适应度，即m只蚂蚁遍历完成的路径长度的倒数，记其最大适应度为
当路径(i, j)上的信息量变化Δτij小于CST时，蚂蚁则
Vol. 15 No. 10
October 2003 陈 崚, 等：具有感觉和知觉特征的蚁群算法
fmax 。取AST=C*fmax ，这里C为常数，我们取其值为5。设经过路径（i,j）的初始解有s个，它们的总长度分别为L1, L2, …, Ls , 则路径（i,j）上的初始信息量为
・1421・
同一路径后，信息量增加的幅度太大就容易使多只蚂蚁集中到该路径，所以我们取1/di为增加的信息量；若选择该路径的蚂蚁达到m/2，或有m/4的蚂蚁选择该路径后因当前距离超过上一次的最优路径长度而终止遍历，则减少5/dij的信息量，以使其趋于各条路径信息量的平均值，从而使蚂蚁选择其它路径的可能性增加，让搜索得到的解趋于多样化。
上述算法的1.2和3.1行分别按（9）和（10）式整体更新信息量:
τ
ij
(0)=∑1
Lkk=1
s
(b). 迭代过程
while not 结束条件 do
for i=1 to n do (对n个城市循环) {
for k=1 to m do (对m个蚂蚁循环)
if (以城市i为起点的各条路径的平均信息量未达到AST) then {
1.1蚂蚁在当前城市随机产生下一次访问的城市序号; 1.2按(9)式更新蚂蚁 k的信息量; } else {
2.1.if ( 以城市i为起点的各条路径上的平均信息量小
于IT ) then
根据概率选择公式（5）选择下一城市j else 根据公式（6）选择下一城市j； 2.2根据(8)式局部更新 (i,j)上的信息量； }
end for k
m只蚂蚁中若有当前已遍历的路径长度已经超过上一次迭代得到的最优路径长度的，则停止该蚂蚁对下一城市的遍历； }
end for i
3.1按公式(10)对所有蚂蚁的路径整体更新其信息量；
end while }
τk(t+1)=(1−ρ)×τijk(t)+ψk∗∆τkij(t) (9) ij
k
τij(t+1)=(1−ρ)×τij(t)+∑ψk∆τij(t) (10)
k=1m
其中,Δτijk为蚂蚁k在本次循环中在路径(i,j)留下的信息量,由(4)式定义.L k (t)为本次迭代中第k只蚂蚁遍历的路径全长.ψk为第k只蚂蚁所对应的解对该路径上信息量更新的影响程度。ψk 的计算方法如下：设对经过路径(i,j)的总数为s的蚂蚁在本次迭代中遍历的路径全长由小到大进行排序，所得序号存于数组rank中, rank[s]表示第s只蚂蚁对应的序号，取：
ψk =s/2-rank[k]+1
上式中，若rank[k]值比较大, 即第k只蚂蚁遍历时路径总长度较长，超过了其它一半以上蚂蚁的路径长度，那么ψk 就为负值，整体更新时该蚂蚁则减小相应路径上的信息量强度，而且rank[k] 越大，即长度越长, 路径上信息量减小的程度越大，从而使得越差路径上的信息量保留得越少，有利于保持较好路径上信息；反之，若rank[k]值较小，ψk 就为正值，则蚂蚁在（i,j）上增强信息量，且rank[k] 越小，即路径越短，则ψk 越大，信息量增加的强度就越大，有效地强化了短路径上的信息。这种自适应的信息量更新机制可以动态地调整信息量，有效地实现蚂蚁的搜索速度和解的多样性之间的平衡。
3 自适应的信息量更新策略
本文引言中所涉及的一些典型算法在更新信息量时，要么采取只要蚂蚁遍历时经过该条路径就增加其信息量的方法[1,2]；要么只让最优适应度的路径上的信息量得以增加，其余路径上的信息量被削减；要么就是基于等级的算法，让适应度相对较好的固定若干条路径根据其解的优劣程度决定信息量的增加幅度[19]。这些做法都采用了固定的信息量增减的比例，忽视了解的分布情况。为此，我们提出自适应的更新策略，根据信息量的分布情况进行信息量的更新，以动态地调整各路径上的信息量的分布，使之不至于过分集中或者分散，以在加速收敛的同时避免早熟。上述算法的2.2行的信息量的局部更新可根据以下策略：
()
τijt−5/dij
τij(t+1)=
τij(t)+1/dij
如果在此之前已经有m/2只
蚂蚁选择了同一城市j或有m/4只蚂蚁选择该城市后终止本次遍历
否则
[10]
4 实验结果及分析
我们对各种规模的对称和不对称TSP问题[20]用上述算法和传统蚁群算法在PC机上用C语言编程进行了测试。我们取蚂蚁的个数等于城市数目，C=5，K=1/50，h=0.7（具体分析见后），运行二十五次，每次运行迭代1500次，所测试的结果如表1、表2和表3所示。在表中“传统算法”指MMAS算法，“平均时间”指一次运行中找到最好解的平均时间，“允许时间”指每次运行所允许执行的最长时间。各问题名称中的数字即为所包含的城市数（kro124p为100个
(8)
城市）。
图1和图2分别给出了各个对称和不对称TSP问题逐代最优解进化曲线。为方便引用,在这里记传统算法为TA(Traditional Algorithm), 本文算法为SCA (Sensational and Consciousness Algorithm)，从图中不难看出，我们的算法不但收敛速度较快而且具有较高的稳定性，比较适合求解较大
我们认为一次迭代中蚂蚁在一个城市选择下一城市时间间隔内信息量尚未被蒸发，所以局部更新时不考虑蒸发因子。由于蚂蚁常常选择信息量较大的路径，当多只蚂蚁选中
15000
30000
[**************]
20000
・1422・
140050
550
1050
1550
2050
2550
3050
3550
40503550
4050
[1**********]0
1550
2050
105055050
2000ry48p(TA)
ry48p(SCA)
d198(TA)
d198(SCA)
[***********]10
[***********][1**********]250
50000
10
[***********][1**********]250
500038000
50
150550
1050
1550
2050
2550
3050
3550
4050
50000
50
50
250
350
450
550
650
750
850
950
1050
[1**********]00
ft70(TA)
50
550
1050
1550
2050
2550
3050
3550
4050
150
250
350
ft70(SCA)
450
550
650
lin318(TA)
lin318(SCA)
750
850
950
图1 对称TSP问题的最优解进化曲线
图2 不对称TSP问题的最优解进化曲线
50
550
1050
1550
2050
2550
3050
3550
4050
1050
50000
60000
60000
35000
kro124p (TA) kro124p(SCA)
50
[***********][***********]250
50
550
1050
1550
2050
2550
3050
3550
4050
50150
250350
450550650
pcb442(TA)
pcb442(SCA)
750850
Vol. 15 No. 10
系 统 仿 真 学 报 October 2003
9501050
Vol. 15 No. 10
October 2003 陈 崚, 等：具有感觉和知觉特征的蚁群算法
表1 对称TSP问题测试结果
问题 d198 lin318 pcb442 att532
算法 传统 本文 传统 本文 传统 本文 传统 本文
最优 15780 15780 42029 42029 50778
平均 15780.9 15780.3 42029.2 42029.0 50778.5
最差 15786 15783 42034 42029 50782 50781 27688 27689
命中最优次数 平均时间/s
19 22 24 25 19 24 22 23
113.5 109.7 198.6 151.2 584.1 376.8 537.0 469.2
・1423・
韦伯系数K (0
参数h在各种取值下对问题d198和ry48p所得到的不同最优解的比较如表6所示，(取C=5 、K=5，且0.5≤h
由上述各表及最优解进化过程图可见，本文算法找到最优解的平均时间较短，同时命中最优的次数也相对较高，从而证明了本文算法具有较好的收敛性和稳定性。我们让蚂蚁的搜索不完全依赖于信息量，而是由依赖自身经验积累，逐步过渡到依赖于信息量；在对路径的选择中，不是依赖路径上的信息量的绝对值，而是与路径上的信息量的变化程度有关。
由于在蚂蚁搜索的过程中，各个路径上信息量的变化不仅是在增加，有时候会在减少。这样，在任何时刻（不仅是在搜索的初期），一旦以某城市为起点的各条路径上的平均信息量低于AST ，蚂蚁的选路就会不受信息量的影响，而是随机选择下一次访问的城市，以增加解的多样性。同样，在任何时刻，一旦以某城市为起点的各条路径上平均信息量超过AST，蚂蚁就会按（5）式，根据信息量变化Δτij是否小于差别感觉阀限CST来决定选择概率。在任何时刻，如果以某城市为起点的各条路径上的平均信息量大于IT, 则按（6）式决定选择概率，强化对较优路径的选择。
这样，实际上就形成了一种自适应的机制，让蚂蚁根据路径上的信息量变化情况来不断改变路径选择策略，以调整所选路径的集中程度，在收敛速度和防止早熟之间取得了动态的平衡。又由于在信息量的更新中，采用基于蚂蚁分布情况的自适应的信息量更新，从而使得解具有较好的多样性﹑全局性，避免了早熟现象。因此本文的算法具有很强的发现最优解的能力、更快的进化速度，对于求解规模较大的优化问题十分有利。
64.2 42.3 78.4 58.7 103.5 67.8 109.9 87.6
50778 50778.1
27686 27686.2 27686
27686.2
表2 不对称TSP问题测试结果
问题 ry48p
算法 最优
平均
最差 命中最优次数 平均时间/s
18 24 22 24 21 23 25 25
传统 14422 14424.1 14431 本文 14422 14422.3 14430 传统 38673 38676.7 38702 本文 38673 38673.8 38779 传统 36230 36231.5 36244 本文 36230 36230.4 36237 传统 2755 本文 2755
2755.0 2755.0
2755 2755
ft70
kro124p
ftv170
表3 几个TSP问题达到最优解所需的平均迭代次数 问题 d198 lin318 pcb442 ry48p ft70 kro124p
传统算法 1659 2699 4023 201 737 1018
本文算法 1120 1833 2976 175 524 712
规模的TSP问题。
由于参数C、K和h决定了AST、CST和IT的取值，从而决定了蚂蚁的搜索何时从初始阶段进入中间阶段、何时在潜意识的影响下选择路径以及何时进入选路的结束阶段, 它们直接地影响了蚂蚁搜索的速度及所得到解的质量。为了分析这些参数对算法性能的影响，我们在对称和不对称TSP问题中各取一个实例在等同条件下运行10次，并在表4、表5和表6中用d198和ry48p两个实例对这三个参数作了详细的实验分析。
我们对参数C取介于0到10之间的不同值进行测试，其结果如表4所示。由表4可见，C取常数1时,虽然对实例d198运行算法消耗的时间较短, 但蚂蚁所搜寻得到的解的稳定性较差。显然，这是因为C值太小导致蚂蚁过早进入中间阶段，而造成了解的局部收敛。而当C值取9时, 算法收敛所需代数较多、时间较长，这是因为蚂蚁用于随机搜索的时间加长的缘故。从表中可以看出，当C=5时, 算法在解的稳定性和求解速度之间取得了较好的平衡，蚂蚁不会因AST取值较小而过早进入中间阶段，造成解的局部性; 也不会因AST取值太大，使蚂蚁徘徊于选路的初始阶段从而大大降低收敛速度。
5 结论
本文提出了一种具有感觉和知觉特征的蚁群算法，该方法模拟蚂蚁的感觉和知觉规律进行选路，并根据路径上信息
・1424・
Vol. 15 No. 10
系 统 仿 真 学 报 October 2003
还自适应地更新各条路径上的信息量，可以在取得更快的速度的同时使得解更具有多样性、全局性。我们以各种规模的TSP问题为例进行的实验结果表明，该方法尤其适用于规模比较大的优化问题。
平均时间(s)
156.3 195.6 166.9 201.5 293.9 123.5 117.2 72.6 128.3 139.0
平均迭代次数
1698 1872 1744 2143 2967 509 475 281 517 546
量的情况动态地、自适应地决定路径选择策略，成功地避免了完全受信息量影响的“道听途说”而造成的干扰和盲目选路，有效地缓解基本蚁群算法容易早熟、停滞和收敛速度之间的矛盾，使得蚁群算法具有更好的收敛性、稳定性。算法
问题
C 1 3
d198
5 7 9 1 3
ry48p
5 7 9
15780
15780 15862 15780 15794 15780 15780 15834 15932 15780 14532 14422 14542 14422 14422 14422 14422 14426 14428 14530
表4 在C的各种取值下d198和ry48p所得到的不同最优解 10次运行分别得到的最优解 方差 15794 15832 15910 15780
98.108
15780 15784 15780 16102 15780 15962 15780 15780
56.605
15782 15780 15780 15802 15882 15832 15780 15852
34.505
15822 15780 15780 15788 15882 15782 15780 15782
64.510
15988 15780 15780 15812 15782 15868 15780 15986
71.252
15798 15840 15794 15920 14422 14462 14428 14462
51.589
14422 14312 14422 14432 14422 14438 14464 14430
37.500
14422 14486 14422 14428 14508 14422 14484 14422
37.585
14516 14422 14422 14424 14422 14648 14422 14422
67.344
14464 14422 14422 14424 14422 14466
14426 14574
14422 14422
14552 14422
58.260
表5 在K的各种取值下d198和ry48p所得到的不同最优解
问题
K 1/20 1/30 1/40 1/50
d198
1/60 1/70 1/80 1/90 1/20 1/30 1/40 1/50
ry48p
1/60 1/70 1/80 1/90
15783
15825 15832 15780 15780 15834 15780 15805 15782 15780 15780 15794 15796 15780 15863 15825 14428 14422 14422 14704 14422 14424 14422 14422 14470 14422 14422 14486 14474 14428 14620 14422
10次运行分别得到的最优解 15910 15780 15780 15780 15780 15798 15782 15780 15780 15794 15816 15780 15902 15780 15780 15788 14486 14424 14422 14426 14422 14492 14432 14424 14422 14422 14432 14454 14422 14422 14422 14466
15782 15788 15796 15782 15784 15780 15780 15792 15780 15780 15780 15780 15780 15780 15982 15780 14472 14422 14422 14452 14422 14422 14422 14484 14422 14504 14538 14422 14482 14422 14516 14422
15780 15782 15812 15780 15798 15780 15780 15780 15780 15780 15780 15896 15786 15780 15780 15784 14422 14424 14488 14422 14428 14454 14422 14422 14436 14422 14422 14422 14524 14422 14422 14428
15780 15791 15780 15780 15780 15782 15787 15804 15780 15842 15780 15780 15780 15792 15814 15780 14512 14422 14422 14422 14422 14422 14422 14422 14422 14422 14428 14422 14422 14482 14422 14422
方差 38.842 17.169 16.317 9.529 18.535 34.917 35.898 60.676 31.875 83.788 21.804 18.440 26.740 36.761 35.361 61.900
平均时间(s) 197.2 168.3 152.1 126.9 129.4 127.2 149.0 142.2 69.1 70.6 62.4 56.0 61.5 65.3 59.4 58.8
平均迭代次数
2587 2149 1975 1572 1604 1583 1885 1799 286 307 252 205 241 263 230 212
Vol. 15 No. 10
October 2003 陈 崚, 等：具有感觉和知觉特征的蚁群算法
表6 在h的各种取值下d198和ry48p所得到的不同最优解
问题
h 0.5 0.6
d198
0.7 0.8 0.9 0.5 0.6
ry48p
0.7 0.8 0.9
15812 15788 15788 15792 15783 15780 15784 15780 15792 15786 14422 14422 14422 14442 14422 14422 14432 14422 14440 14422
10次运行分别得到的最优解 15780 15782 15780 15780 15788 15794 15780 15782 15784 15780 15780 15782 15780 15782 15780 15780 15780 15782 15782 15780 15780 15790 15780 15780 15780 15780 15804 15782 15780 15780 14512 14422 14454 14448 14432 14424 14436 14422 14422 14424 14434 14424 14434 14424 14424 14422 14422 14428 14442 14422 14424 14424 14422 14422 14424 14422 14422 14424 14422 14424
方差
15782
15780 15780 15788 15780 15781 15784 15798 15788 15780 14424 14422 14422 14422 14422 14422 14432 14422 14422 14422 656-665.
9.594 4.079 1.077 5.618 7.440 26.988 7.057 3.555 6.437 5.276
平均时间(S)
125.2 127.4 110.3 148.6 172.1 59.7 57.3 42.8 62.4 77.2
・1425・
平均迭代次数
1239 1273 1122 1495 1835 267 232 180 258 304
参考文献:
[1]
Dorigo M., Maniezzo V., Colorni A. Ant system: Optimization by a colony of coorperating agents [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 1996, 26(1): 29-41. [2] [3] [4]
Dorigo M., Gambardella L. M.Ant colonies for the traveling salesman problem [J]. BioSystems, 1997, 43(2): 73-81.
Gutjahr J.W. A Graph-based Ant System and its convergence [J]. Future Generation Computer Systems, 2000, 16(8): 873-888.
Talbi E.G., Roux O., Fonlupt C., Robillard D. Parallel Ant Colonies for the quadratic assignment problem [J]. Future Generation Computer Systems, 2001, 17(4): 441-449. [5]
Maniezzo V., Carbonaro A. An ANTS heuristic for the frequency assignment problem [J]. Future Generation Computer Systems, 2000, 16(8): 927-935. [6]
Chang C.S., Tian L., Wen F.S. A new approach to fault section in power systems using Ant System [J]. Electric Power Systems Research, 1999, 49(1): 63-70. [7] [8]
吴庆洪, 张纪会, 徐心和. 具有变异特征的蚁群算法[J]. 计算机研究与发展, 1999, 36(10): 1240-1245.
Dorigo M., Luca M. The Ant-Q algorithm applied to the nuclear reload problem [J]. Annals of Nuclear Energy, 2002, 29(12): 1455-1470. [9]
Dorigo M.,Gambardella L.M. A study of some properties of Ant-Q [A]. In:Voigt H.-M, Ebeling W., Rechenberg I., Schwefel H.-S(Eds.). Proceedings of PPSN IV-Fourth International Conference on Parallet Problem Solving From Nature [C]. Berlin:Springer-Verlag, 1996,
[10] Stützle T., Hoos H.H. MAX-MIN Ant System [J]. Future Generation
Computer Systems Journal. 2000, 16(8): 889-914.
[11] Gambardella L.M, Dorigo M. An Ant Colony System Hybridized
with a New Local Search for the Sequential Ordering Problem [J]. INFORMS Journal on Computing, 2000, 12(3): 237-255.
[12] Botee H.M, Bonabeau E. Evolving ant colony optimization [J].
Complex Systems, 1998, 1(2): 149-159.
[13] Bilchev G., Parmee I.C. Adaptive search strategies for heavily
constrained design spaces [A]. Proceedings of 22nd International Conference on Computer Aided Design ’95 Yelta [C]: Ukraine, 1995, 230-235.
[14] 陈崚, 沉洁, 秦玲. 蚁群算法求解连续型优化问题的一种新方法
[J]. 软件学报, 2002, 13(12): 2317-2322.
[15] 吴斌, 史忠植. 一种基于蚁群算法的TSP问题分段求解算法[J].
计算机学报, 2001, 24(12): 1328-1333.
[16] 张纪会, 高齐圣, 徐心和. 自适应蚁群算法[J]. 控制理论与应用,
2000, 17(1): 1-3.
[17] 陈录生, 马剑侠. 新编心理学 [M]. 北京: 北京师范大学出版社,
1996, 3: 53-61.
[18] 叶奕干, 祝蓓里. 心理学[M]. 华东师范大学出版社, 1996, 3: 84-85. [19] Bullnheimer B., Hartl R.F., Strauss C. A New Rank Based Version of
the Ant System-A Computational Study [J]. Central European Journal for Operations Research and Economics, 1999, 7(1): 25-38. http://citeseer.nj.nec.com/bullnheimer97new.html
[20] www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95
[EB/OL].
《第三届全国虚拟现实与可视化学术会议文集》征订启事
主要栏目有：(1)综述；(2)图形图象与可视化；(3)虚拟人、人机交互与界面；(4)网络与分布式虚拟现实；(5)建模与仿真技术；(6)虚拟博物馆与地理信息系统；(7)虚拟设计与虚拟制造；(8)虚拟现实系统、应用及其它。
共刊登172篇优秀论文。全册150元（含邮费）。请将汇款寄至编辑部。 地址：北京142信箱13分箱 邮编：100854 电话：010-68388709
・1418・
系 统 仿 真 学 报 Vol. 15 No. 10
JOURNAL OF SYSTEM SIMULATION October 2003
具有感觉和知觉特征的蚁群算法
陈 崚1,2, 秦 玲1, 陈宏建1, 徐晓华1
（1扬州大学信息学院计算机系, 江苏扬州 225009; 2南京大学软件新技术国家重点实验室, 江苏南京 210093）
摘 要：针对传统蚁群算法加速收敛与早熟、停滞现象的矛盾，模仿蚂蚁感觉和知觉行为提出一种新的蚁群优化算法, 使蚂蚁受显意识和潜意识的相互作用选择路径，同时自适应地修改路径上的信息量.以多种不同规模的对称和不对称旅行商问题（TSP）为例进行的仿真结果表明算法具有较好的收敛速度和稳定性，比较适合求解城市数目较多的TSP问题。 关键词：蚁群算法；感觉；意识；旅行商问题
文章编号：1004-731X (2003) 10-1418-08 中图分类号：TP37 文献标识码：A
Ant Colony Algorithm with Characteristics of Sensation and Consciousness
(1 Department of Computer Science, Yangzhou University, 225009, China; 2 National Key Lab of Novel Software Tech, Nanjing 210093, China)
CHEN Ling1,2, QIN Ling1, CHEN Hong-jian1, XU Xiao-hua1
Abstract：A new ant colony optimization algorithm which simulates the ants’ behavior according to the laws of sensation and consciousness is presented in order to make balance between accelerating convergence and averting precocity as well as stagnation. The algorithm selects path by the mixed influence of consciousness and subconsciousness, and updates the trail information of each path adaptively in each step. The results of simulation on several symmetric and asymmetric TSPs with different sizes indicate that the algorithm has much higher convergence speed and stability than that of classical ant colony algorithm, and is more suitable for solving large scale TSP.
Keywords：ant colony algorithm; sensation; consciousness; traveling salesman problem
引 言
蚁群算法是近来出现的一种新型的模拟进化算法。它是由意大利学者M.Dorigo等人首先提出来的[1]，他们充分利用蚁群搜索食物的过程与旅行商问题（TSP）之间的相似性,解决了TSP问题[2]，取得了很好的结果.随后,蚁群算法被用来求解分配问题、图论问题[3]、指派问题[4,5], 电力系统故障诊断[6]等NP完全问题,显示出蚁群算法在求解复杂优化问题方面的优越性。
在蚁群算法中，蚂蚁总是依赖于其它蚂蚁的反馈信息来强化学习，而不去考虑自身经验积累。这样的盲从行为，容易导致早熟、停滞现象，使收敛速度变慢。为了解决此问题，本文提出一种新的蚁群算法，该算法模拟蚂蚁感觉和知觉行为，并受显意识和潜意识的相互作用选择路径，使之在初始阶段接受自己经验的影响, 此后逐步有条件地接受信息量的影响，同时自适应地修改路径上的信息量。这样，可在加速收敛和防止早熟、停滞现象之间取得很好的平衡。我们从通用的TSPLIB[20] 中选用不同大小的对称和不对称TSP问题为例所进行的计算结果表明，该方法比一般蚁群算法具有
更好的收敛速度和稳定性，比较适合求解城市数目较多的TSP问题。
1 基本蚁群算法
实验观察表明, 蚂蚁在觅食过程中会留下一种分泌物（pheromone）即信息素，若蚂蚁从巢穴到食物源所走的路径较短，则该蚂蚁从巢穴到食物源后再返回到巢穴的时间就短，从而相同时间内较短路径上蚂蚁所分泌的信息素较多。由于其后面的蚂蚁要根据前面走过的蚂蚁所留下的分泌物的多少选择其要走的路径，一条路径上的分泌物越多，蚂蚁选择这条路径的概率就越大。因此，蚂蚁群体的集体行为实际上构成了一种学习信息的正反馈机制，蚂蚁之间通过这种信息交流寻求通向食物的最短路径。蚁群算法正是模拟了这样的优化机制, 即通过个体之间的信息交流与相互协作最终找到最优解。
我们以TSP问题为例说明基本蚁群算法的框架。设有n个城市，dij ( i,j =1,2,…, n) 表示城市i和 j 间的距离,τij(t) 表示在t时刻城市i和 j 之间的信息量，我们以此来模拟实际蚂蚁的分泌物。设共有m只蚂蚁，用pijk (t) 表示在t时刻蚂蚁k由城市i转移到城市 j 的概率，则
β
ταij(t)ηijαβpkij(t)=∑r∈allowedτir(t)ηir
k
0
收稿日期：2002-06-28 修回日期：2003-03-10
基金项目：国家自然科学基金(60074013)、国家高性能计算基金(00219 )、江苏省教育厅自然科学基金和南京大学软件新技术国家重点实验室开放基金。
作者简介：陈 崚(1951-), 男, 江苏宝应人, 教授, 研究方向为并行计算和算法设计与分析；秦 玲(1979-), 女, 江苏泰兴人, 硕士生, 研究方向为并行计算和优化算法；陈宏建(1968-), 男, 江苏海安人, 讲师；徐晓华(1979-), 男, 江苏通州人, 硕士生。
j∈allowedk否则
(1)
其中，allowedk 表示蚂蚁k
下一步允许走过的城市的集合,
α表示路径上的信息量对蚂蚁选择路径所起的作用大小。
Vol. 15 No. 10
October 2003 陈 崚, 等：具有感觉和知觉特征的蚁群算法 ηij 为由城市i转移到城市 j 的期望程度，例如可以取ηij＝1/dij，β表示ηij的作用大小程度。当α=0时, 算法就是传统的贪心算法；而当β=0时, 就成了纯粹的正反馈的启发式算法。 经过n 个时刻，蚂蚁可走完所有的城市，完成一次循环。每只蚂蚁所走过的路径就是一个解。此时，要根据下式对各路径上的信息量作更新：
τij(t＋1)＝（1-ρ）*τij(t)+Δτij (2) 其中ρ∈(0,1), 为蒸发因子，表示信息量τij(t) 随时间的推移而衰减的程度。信息增量Δτij 可表示为：
m
k
・1419・
率，实现了选择概率的自适应，提高了算法的速度和性能。
2 具有感觉和知觉特征的蚁群算法
科学研究表明，蚂蚁对于外界刺激物有着惊人的感觉和知觉能力。在蚁群中，单只蚂蚁的能力和智力非常有限，但是整个蚁群可以有足够的能力来完成筑巢、觅食、迁徙、清扫蚁穴等复杂行为。它们可以在各自的感觉和知觉能力的支配下，很好地相互协调、分工、合作并完成任务。因此，我们可以在蚁群算法中模拟蚂蚁的这种感知现象，让蚂蚁根据知觉和感觉规律选路，以在加快收敛速度的同时保证解的多样性。根据感知规律，我们将蚁群算法中蚂蚁的搜索过程分为如下三个阶段:
∆τij=∑∆τij (3)
k=1
Δτijk表示蚂蚁k在本次循环中在城市i和 j之间留下的信息量, 它的计算公式根据计算模型而定, 例如在最常用的ant circle system 模型中
Q/Lk∆τk=ij
0
若蚂蚁k经过城市i和城市j之间否则
2.1 蚂蚁搜索的初始阶段
心理学研究指出[17]，感觉和知觉是客观事物作用于神经系统引起神经系统的活动而产生的。产生感觉和知觉的神
(4) 经机构叫分析器，感受性是分析器对适宜刺激的感觉能力。感觉是大脑对当前直接作用于感觉器官的客观事物的个别属性的反映，而知觉是其整体属性的反映，两者紧密相关。但是不是所有的刺激都能引起人或者动物的感觉，只有达到一定量的刺激才能引起相应的感觉。现实中，往往会出现这样的情况：同是一种刺激，这个人感觉到了，另一个人感觉不到，就说明了他们的感受性不同。感受性是用感觉阈限的大小来度量的，感觉阈限是能引起感觉的、持续了一定时间的刺激量。心理学上把刚刚能引起感觉的最小刺激量，称为绝对感觉阈限（Absolute Sensor Threshold）。
在蚁群算法中，蚂蚁搜索过程的起始阶段，有的路径上有蚂蚁走过，有的路径还未来得及被走过。而蚂蚁选路的策略是一旦路径上有刺激物，即信息量多于其它路径，哪怕是很微弱的优势，它就以较大的概率选择该路径。这使得蚂蚁从搜索的一开始就以很大的概率集中到几条长度较短的路径上。实践中我们观察到，蚂蚁在搜索的初始阶段所得到的这些路径的整体长度往往都偏大，导致了搜索所得的结果是局部最优而不是全局最优。
为了避免蚂蚁从搜索的一开始就失去解的多样性，我们受绝对感觉阈限原理的启发，在路径上信息量的刺激量未达到蚂蚁的绝对感觉阈限时，让蚂蚁忽视该刺激物的存在，也就是让蚂蚁在搜索初始阶段的选路不受信息量的影响。这里我们记蚂蚁的绝对感觉阈限为AST，只有当信息量积累到超过AST时，蚂蚁才在信息量的刺激下趋于选择信息量较大的路径。这样，可以让蚂蚁在初始阶段选择较多的不同路径，以获得多样化的解，避免蚂蚁陷入局部最优，让蚂蚁尽量少走“冤枉路”。大量的实验表明，这种方法有利于让蚂蚁向最优方向进行搜索并很快收敛，大大节约了计算时间。
其中，Q 为常数，Lk 为蚂蚁k在本次循环中所走路径的长度。在经过若干次循环以后, 可以根据适当的停止条件来结束计算。
蚁群算法通过蚂蚁之间的信息量来实现选择机制、更新机制和协调机制，这些机制使得蚁群算法具有很强的发现较好解的能力。但是，蚁群算法也有一些缺陷。例如，由于蚁群中多个个体的运动是随机的，当群体规模较大时，要找出一条较好的路径需较长的搜索时间。为此,吴庆洪等人提出了具有变异特征的蚁群算法[7]，有机结合了2-opt方法提高了算法的性能。M.Dorigo 等人在基本的蚁群算法的基础上提出称之为Ant-Q System的更一般的蚁群算法[8,9]，每次让信息量最大的路径以较大的概率被选中，以充分利用学习机制，强化最优信息的反馈。为了克服在Ant-Q中可能出现的停滞现象，T. Stutzle等人提出了MAX－MIN 蚁群系统[10]，允许各个路径上的信息量在一个限定的范围内变化。L.M.Gambardella等人提出了一种混合型蚁群算法HAS[11]，在每次循环中蚂蚁建立各自的解后，再以各自的解为起点用某种局部搜索算法求局部最优解，作为相应蚂蚁的解，这样可以迅速提高解的质量。H.M.Botee 等人对参数m、α、β、ρ的选择进行了深入的研究，用遗传算法求得这些参数最优组合[12]。另外，G. Bilchev 等人曾在使用遗传算法解决工程设计中连续空间的优化问题时，使用了蚁群算法对遗传算法所得到的初步结果进行精确化，取得了较好的效果[13]。我们也曾经直接将蚁群算法改进使其能够直接求解线性和非线性规划等连续空间的优化问题[14]。吴斌、史忠植提出了基于蚁群算法的分段求解算法[15] 提高了蚂蚁搜索的速度，为蚁群算法的并行化奠定了基础。由于蚁群算法构造解的过程中，选择策略一般是随机的，进化速度较慢。张纪会等人提出了自适应的蚁群算法[16]，采用确定性选择和随机选择相结合的策略，在搜索的过程中动态地调整选择的概
2.2 蚂蚁搜索的中间阶段
刺激物引起感觉之后，如果刺激量发生了变化（增多或减少），也会引起感觉的变化。但是，并不是刺激的所有变
・1420・
Vol. 15 No. 10
系 统 仿 真 学 报 October 2003
按照自己的潜意识作用选路。此时，如果蚂蚁k在某一条路径上走过的次数越多，它对这条路径越熟悉，其潜意识作用下选择该路径的概率就大；反之，当一条路径上其它蚂蚁的信息量越多，则潜意识中蚂蚁k对该路径就越排斥，该路径被选择的概率就小。这种机制有效地防止了蚂蚁一味相信他者而造成的盲从现象，大大的降低了大量蚂蚁聚集于少数局部较优路径上造成早熟、停滞现象的可能性。当信息量变化较大时，蚂蚁在显意识作用下受整体信息量的影响而选路，遵循路径上走过的蚂蚁越多选择该路径的概率越大的原则，趋向于选优势较大的路径（这里的优势主要指其信息量较大和长度较短），保证了所选路径的优越性而且加快了收敛速度。
化量都能引起感觉[18]。例如，在100克的重量上如果只增加1克的重量，我们感受不到两者的差异。由于经验和潜意识的作用，当刺激条件的改变幅度仅局限于一定的范围内时，包括特定感觉的知觉的映象仍然保持相对不变，这就是知觉的“恒常性”。只有当刺激变化到一定量时才能使我们感觉到差别，能引起差别感觉的刺激物的最小变化量，称为差别感觉阈限（Contrast Sensor Threshold），记作CST。早在19世纪前半期，德国心理学家韦伯在研究差别感觉阈限时发现，差别感觉阈限随原来刺激量的变化而变化，而且表现为一定的规律性。在一定的范围内差别感觉阈限与原来的量的比值是一个常数。如果将它用公式来表示，设I表示原来刺激物的强度，△I表示差别感觉阈限，那么在I小于某个特定的限度IT（intensity-threshold）时，就有
∆=K
2.3 蚂蚁搜索的结束阶段
由于韦伯定律只能在刺激物的强度I小于某个特定的限度IT时才能适用，在超过IT时并不适用，故当路径上信息量达到相当大的程度时，我们应改变蚂蚁的选路策略。为了确定IT的值，我们首先估计各个路径上可能的最大信息量τmax 。由于一条路径上的信息量取得最大只能是在所有蚂蚁每次迭代都走该路径的情况下，若预定蚂蚁搜索的最大遍历次数为NC，蚂蚁总数为m，则此时的最大信息量可以表示为
τmax=NC×m×适应度的数量级
此处K是一个常数，称为韦伯系数。这就是著名的韦伯定律（Weber’s Law），重量感觉的韦伯系数为1/30，听觉为1/10，视觉为1/100。
由于各条路径上的信息量也是在不断变化的，我们将上述定律应用到蚁群算法的搜索过程中。我们改变传统蚁群算法中信息量一旦变化就直接影响蚁群选路的做法，认为蚁群在一定刺激强度范围内也存在一个差别感觉阈限。当路径上信息量的增加或减少的量在差别感觉阈限CST之下时，蚂蚁遵循知觉的恒常性规律，感受不到该路径上信息量的变化，该条路径被选择的概率主要依据于以前迭代中蚂蚁选路经验形成的潜意识作用；反之，蚂蚁受其显意识控制，按照路径上所有蚂蚁信息量高低决定选路概率的大小。根据韦伯定律，在具体实现此过程时，我们取
CST=τij(t)×K
这里，K为蚂蚁对信息量感觉的韦伯系数，本文取值为1/50。若记
k
αijθijk=βijk
τ(t)η
ijij
从AST的定义可知，此处适应度的数量级应该和AST相当，所以我们取
IT = h·τmax = h×NC×m×AST
这里h为一常数，可取1/2、2/3或3/4等。应该看到，某路径上信息量强度较大，可能是因为进入了局部最优的状态，或者是因为整个蚂蚁的群体遍历行为已经接近尾声。但由于上述的搜索的中间阶段的选路策略已经有效地避免了停滞现象的产生，所以此时不大可能是因为陷入局部最优，而是因为这些路径占有绝对优势。为加快收敛，此时我们引用Ant-Q中的选路策略[8,9]来选择下一城市j：
∆τij≤CST否则
τij(t)−τk(t)ij
h∈allowedk
其中：α=
k
k
ij
kτij(t)h∈allowedk
∑
τihtk
β=k
ij
∑
τt−τtih
kij
argmax{τtj∈allowed}
ijk
j=
蚂蚁k以公式(7)的概率选择城市j
()
q≤q0否则
(6)
τij(t)表示至t时刻蚂蚁k在路径(i, j)上历次遗留的总信
息量，ηij＝1/dij 。这里，我们用αij表示蚂蚁k的潜意识作用下路径(i, j)对它的吸引程度，βij 表示该路径对其他蚂蚁的吸引作用。实际上，当蚂蚁k按照其潜意识选择路径时，βij包含了所有其它蚂蚁所留信息量的作用，干扰了蚂蚁k的潜意识，构成了潜意识作用下蚂蚁k对路径(i, j)的排斥作用。蚂蚁k选择路径(i, j)的概率为：
k
θijkk
pij=∑θih
h∈allowedk0
τij(t)ηij(t)
pij(t)=∑r∈alloedτir(t)ηir(t)
k
0
k
j∈allowedk
否则
(7)
其中ηij(t)=1/dij，q为产生的随机数，q0为一常数。通过大量的实验，我们选取q0的值在0.7左右。
2.4 算法框架
综上所述，算法的框架可以描述如下：
main( ) {
j∈allowedk
否则
(5)
(a). 初始化
随机产生m个初始解，计算这m个初始解的适应度，即m只蚂蚁遍历完成的路径长度的倒数，记其最大适应度为
当路径(i, j)上的信息量变化Δτij小于CST时，蚂蚁则
Vol. 15 No. 10
October 2003 陈 崚, 等：具有感觉和知觉特征的蚁群算法
fmax 。取AST=C*fmax ，这里C为常数，我们取其值为5。设经过路径（i,j）的初始解有s个，它们的总长度分别为L1, L2, …, Ls , 则路径（i,j）上的初始信息量为
・1421・
同一路径后，信息量增加的幅度太大就容易使多只蚂蚁集中到该路径，所以我们取1/di为增加的信息量；若选择该路径的蚂蚁达到m/2，或有m/4的蚂蚁选择该路径后因当前距离超过上一次的最优路径长度而终止遍历，则减少5/dij的信息量，以使其趋于各条路径信息量的平均值，从而使蚂蚁选择其它路径的可能性增加，让搜索得到的解趋于多样化。
上述算法的1.2和3.1行分别按（9）和（10）式整体更新信息量:
τ
ij
(0)=∑1
Lkk=1
s
(b). 迭代过程
while not 结束条件 do
for i=1 to n do (对n个城市循环) {
for k=1 to m do (对m个蚂蚁循环)
if (以城市i为起点的各条路径的平均信息量未达到AST) then {
1.1蚂蚁在当前城市随机产生下一次访问的城市序号; 1.2按(9)式更新蚂蚁 k的信息量; } else {
2.1.if ( 以城市i为起点的各条路径上的平均信息量小
于IT ) then
根据概率选择公式（5）选择下一城市j else 根据公式（6）选择下一城市j； 2.2根据(8)式局部更新 (i,j)上的信息量； }
end for k
m只蚂蚁中若有当前已遍历的路径长度已经超过上一次迭代得到的最优路径长度的，则停止该蚂蚁对下一城市的遍历； }
end for i
3.1按公式(10)对所有蚂蚁的路径整体更新其信息量；
end while }
τk(t+1)=(1−ρ)×τijk(t)+ψk∗∆τkij(t) (9) ij
k
τij(t+1)=(1−ρ)×τij(t)+∑ψk∆τij(t) (10)
k=1m
其中,Δτijk为蚂蚁k在本次循环中在路径(i,j)留下的信息量,由(4)式定义.L k (t)为本次迭代中第k只蚂蚁遍历的路径全长.ψk为第k只蚂蚁所对应的解对该路径上信息量更新的影响程度。ψk 的计算方法如下：设对经过路径(i,j)的总数为s的蚂蚁在本次迭代中遍历的路径全长由小到大进行排序，所得序号存于数组rank中, rank[s]表示第s只蚂蚁对应的序号，取：
ψk =s/2-rank[k]+1
上式中，若rank[k]值比较大, 即第k只蚂蚁遍历时路径总长度较长，超过了其它一半以上蚂蚁的路径长度，那么ψk 就为负值，整体更新时该蚂蚁则减小相应路径上的信息量强度，而且rank[k] 越大，即长度越长, 路径上信息量减小的程度越大，从而使得越差路径上的信息量保留得越少，有利于保持较好路径上信息；反之，若rank[k]值较小，ψk 就为正值，则蚂蚁在（i,j）上增强信息量，且rank[k] 越小，即路径越短，则ψk 越大，信息量增加的强度就越大，有效地强化了短路径上的信息。这种自适应的信息量更新机制可以动态地调整信息量，有效地实现蚂蚁的搜索速度和解的多样性之间的平衡。
3 自适应的信息量更新策略
本文引言中所涉及的一些典型算法在更新信息量时，要么采取只要蚂蚁遍历时经过该条路径就增加其信息量的方法[1,2]；要么只让最优适应度的路径上的信息量得以增加，其余路径上的信息量被削减；要么就是基于等级的算法，让适应度相对较好的固定若干条路径根据其解的优劣程度决定信息量的增加幅度[19]。这些做法都采用了固定的信息量增减的比例，忽视了解的分布情况。为此，我们提出自适应的更新策略，根据信息量的分布情况进行信息量的更新，以动态地调整各路径上的信息量的分布，使之不至于过分集中或者分散，以在加速收敛的同时避免早熟。上述算法的2.2行的信息量的局部更新可根据以下策略：
()
τijt−5/dij
τij(t+1)=
τij(t)+1/dij
如果在此之前已经有m/2只
蚂蚁选择了同一城市j或有m/4只蚂蚁选择该城市后终止本次遍历
否则
[10]
4 实验结果及分析
我们对各种规模的对称和不对称TSP问题[20]用上述算法和传统蚁群算法在PC机上用C语言编程进行了测试。我们取蚂蚁的个数等于城市数目，C=5，K=1/50，h=0.7（具体分析见后），运行二十五次，每次运行迭代1500次，所测试的结果如表1、表2和表3所示。在表中“传统算法”指MMAS算法，“平均时间”指一次运行中找到最好解的平均时间，“允许时间”指每次运行所允许执行的最长时间。各问题名称中的数字即为所包含的城市数（kro124p为100个
(8)
城市）。
图1和图2分别给出了各个对称和不对称TSP问题逐代最优解进化曲线。为方便引用,在这里记传统算法为TA(Traditional Algorithm), 本文算法为SCA (Sensational and Consciousness Algorithm)，从图中不难看出，我们的算法不但收敛速度较快而且具有较高的稳定性，比较适合求解较大
我们认为一次迭代中蚂蚁在一个城市选择下一城市时间间隔内信息量尚未被蒸发，所以局部更新时不考虑蒸发因子。由于蚂蚁常常选择信息量较大的路径，当多只蚂蚁选中
15000
30000
[**************]
20000
・1422・
140050
550
1050
1550
2050
2550
3050
3550
40503550
4050
[1**********]0
1550
2050
105055050
2000ry48p(TA)
ry48p(SCA)
d198(TA)
d198(SCA)
[***********]10
[***********][1**********]250
50000
10
[***********][1**********]250
500038000
50
150550
1050
1550
2050
2550
3050
3550
4050
50000
50
50
250
350
450
550
650
750
850
950
1050
[1**********]00
ft70(TA)
50
550
1050
1550
2050
2550
3050
3550
4050
150
250
350
ft70(SCA)
450
550
650
lin318(TA)
lin318(SCA)
750
850
950
图1 对称TSP问题的最优解进化曲线
图2 不对称TSP问题的最优解进化曲线
50
550
1050
1550
2050
2550
3050
3550
4050
1050
50000
60000
60000
35000
kro124p (TA) kro124p(SCA)
50
[***********][***********]250
50
550
1050
1550
2050
2550
3050
3550
4050
50150
250350
450550650
pcb442(TA)
pcb442(SCA)
750850
Vol. 15 No. 10
系 统 仿 真 学 报 October 2003
9501050
Vol. 15 No. 10
October 2003 陈 崚, 等：具有感觉和知觉特征的蚁群算法
表1 对称TSP问题测试结果
问题 d198 lin318 pcb442 att532
算法 传统 本文 传统 本文 传统 本文 传统 本文
最优 15780 15780 42029 42029 50778
平均 15780.9 15780.3 42029.2 42029.0 50778.5
最差 15786 15783 42034 42029 50782 50781 27688 27689
命中最优次数 平均时间/s
19 22 24 25 19 24 22 23
113.5 109.7 198.6 151.2 584.1 376.8 537.0 469.2
・1423・
韦伯系数K (0
参数h在各种取值下对问题d198和ry48p所得到的不同最优解的比较如表6所示，(取C=5 、K=5，且0.5≤h
由上述各表及最优解进化过程图可见，本文算法找到最优解的平均时间较短，同时命中最优的次数也相对较高，从而证明了本文算法具有较好的收敛性和稳定性。我们让蚂蚁的搜索不完全依赖于信息量，而是由依赖自身经验积累，逐步过渡到依赖于信息量；在对路径的选择中，不是依赖路径上的信息量的绝对值，而是与路径上的信息量的变化程度有关。
由于在蚂蚁搜索的过程中，各个路径上信息量的变化不仅是在增加，有时候会在减少。这样，在任何时刻（不仅是在搜索的初期），一旦以某城市为起点的各条路径上的平均信息量低于AST ，蚂蚁的选路就会不受信息量的影响，而是随机选择下一次访问的城市，以增加解的多样性。同样，在任何时刻，一旦以某城市为起点的各条路径上平均信息量超过AST，蚂蚁就会按（5）式，根据信息量变化Δτij是否小于差别感觉阀限CST来决定选择概率。在任何时刻，如果以某城市为起点的各条路径上的平均信息量大于IT, 则按（6）式决定选择概率，强化对较优路径的选择。
这样，实际上就形成了一种自适应的机制，让蚂蚁根据路径上的信息量变化情况来不断改变路径选择策略，以调整所选路径的集中程度，在收敛速度和防止早熟之间取得了动态的平衡。又由于在信息量的更新中，采用基于蚂蚁分布情况的自适应的信息量更新，从而使得解具有较好的多样性﹑全局性，避免了早熟现象。因此本文的算法具有很强的发现最优解的能力、更快的进化速度，对于求解规模较大的优化问题十分有利。
64.2 42.3 78.4 58.7 103.5 67.8 109.9 87.6
50778 50778.1
27686 27686.2 27686
27686.2
表2 不对称TSP问题测试结果
问题 ry48p
算法 最优
平均
最差 命中最优次数 平均时间/s
18 24 22 24 21 23 25 25
传统 14422 14424.1 14431 本文 14422 14422.3 14430 传统 38673 38676.7 38702 本文 38673 38673.8 38779 传统 36230 36231.5 36244 本文 36230 36230.4 36237 传统 2755 本文 2755
2755.0 2755.0
2755 2755
ft70
kro124p
ftv170
表3 几个TSP问题达到最优解所需的平均迭代次数 问题 d198 lin318 pcb442 ry48p ft70 kro124p
传统算法 1659 2699 4023 201 737 1018
本文算法 1120 1833 2976 175 524 712
规模的TSP问题。
由于参数C、K和h决定了AST、CST和IT的取值，从而决定了蚂蚁的搜索何时从初始阶段进入中间阶段、何时在潜意识的影响下选择路径以及何时进入选路的结束阶段, 它们直接地影响了蚂蚁搜索的速度及所得到解的质量。为了分析这些参数对算法性能的影响，我们在对称和不对称TSP问题中各取一个实例在等同条件下运行10次，并在表4、表5和表6中用d198和ry48p两个实例对这三个参数作了详细的实验分析。
我们对参数C取介于0到10之间的不同值进行测试，其结果如表4所示。由表4可见，C取常数1时,虽然对实例d198运行算法消耗的时间较短, 但蚂蚁所搜寻得到的解的稳定性较差。显然，这是因为C值太小导致蚂蚁过早进入中间阶段，而造成了解的局部收敛。而当C值取9时, 算法收敛所需代数较多、时间较长，这是因为蚂蚁用于随机搜索的时间加长的缘故。从表中可以看出，当C=5时, 算法在解的稳定性和求解速度之间取得了较好的平衡，蚂蚁不会因AST取值较小而过早进入中间阶段，造成解的局部性; 也不会因AST取值太大，使蚂蚁徘徊于选路的初始阶段从而大大降低收敛速度。
5 结论
本文提出了一种具有感觉和知觉特征的蚁群算法，该方法模拟蚂蚁的感觉和知觉规律进行选路，并根据路径上信息
・1424・
Vol. 15 No. 10
系 统 仿 真 学 报 October 2003
还自适应地更新各条路径上的信息量，可以在取得更快的速度的同时使得解更具有多样性、全局性。我们以各种规模的TSP问题为例进行的实验结果表明，该方法尤其适用于规模比较大的优化问题。
平均时间(s)
156.3 195.6 166.9 201.5 293.9 123.5 117.2 72.6 128.3 139.0
平均迭代次数
1698 1872 1744 2143 2967 509 475 281 517 546
量的情况动态地、自适应地决定路径选择策略，成功地避免了完全受信息量影响的“道听途说”而造成的干扰和盲目选路，有效地缓解基本蚁群算法容易早熟、停滞和收敛速度之间的矛盾，使得蚁群算法具有更好的收敛性、稳定性。算法
问题
C 1 3
d198
5 7 9 1 3
ry48p
5 7 9
15780
15780 15862 15780 15794 15780 15780 15834 15932 15780 14532 14422 14542 14422 14422 14422 14422 14426 14428 14530
表4 在C的各种取值下d198和ry48p所得到的不同最优解 10次运行分别得到的最优解 方差 15794 15832 15910 15780
98.108
15780 15784 15780 16102 15780 15962 15780 15780
56.605
15782 15780 15780 15802 15882 15832 15780 15852
34.505
15822 15780 15780 15788 15882 15782 15780 15782
64.510
15988 15780 15780 15812 15782 15868 15780 15986
71.252
15798 15840 15794 15920 14422 14462 14428 14462
51.589
14422 14312 14422 14432 14422 14438 14464 14430
37.500
14422 14486 14422 14428 14508 14422 14484 14422
37.585
14516 14422 14422 14424 14422 14648 14422 14422
67.344
14464 14422 14422 14424 14422 14466
14426 14574
14422 14422
14552 14422
58.260
表5 在K的各种取值下d198和ry48p所得到的不同最优解
问题
K 1/20 1/30 1/40 1/50
d198
1/60 1/70 1/80 1/90 1/20 1/30 1/40 1/50
ry48p
1/60 1/70 1/80 1/90
15783
15825 15832 15780 15780 15834 15780 15805 15782 15780 15780 15794 15796 15780 15863 15825 14428 14422 14422 14704 14422 14424 14422 14422 14470 14422 14422 14486 14474 14428 14620 14422
10次运行分别得到的最优解 15910 15780 15780 15780 15780 15798 15782 15780 15780 15794 15816 15780 15902 15780 15780 15788 14486 14424 14422 14426 14422 14492 14432 14424 14422 14422 14432 14454 14422 14422 14422 14466
15782 15788 15796 15782 15784 15780 15780 15792 15780 15780 15780 15780 15780 15780 15982 15780 14472 14422 14422 14452 14422 14422 14422 14484 14422 14504 14538 14422 14482 14422 14516 14422
15780 15782 15812 15780 15798 15780 15780 15780 15780 15780 15780 15896 15786 15780 15780 15784 14422 14424 14488 14422 14428 14454 14422 14422 14436 14422 14422 14422 14524 14422 14422 14428
15780 15791 15780 15780 15780 15782 15787 15804 15780 15842 15780 15780 15780 15792 15814 15780 14512 14422 14422 14422 14422 14422 14422 14422 14422 14422 14428 14422 14422 14482 14422 14422
方差 38.842 17.169 16.317 9.529 18.535 34.917 35.898 60.676 31.875 83.788 21.804 18.440 26.740 36.761 35.361 61.900
平均时间(s) 197.2 168.3 152.1 126.9 129.4 127.2 149.0 142.2 69.1 70.6 62.4 56.0 61.5 65.3 59.4 58.8
平均迭代次数
2587 2149 1975 1572 1604 1583 1885 1799 286 307 252 205 241 263 230 212
Vol. 15 No. 10
October 2003 陈 崚, 等：具有感觉和知觉特征的蚁群算法
表6 在h的各种取值下d198和ry48p所得到的不同最优解
问题
h 0.5 0.6
d198
0.7 0.8 0.9 0.5 0.6
ry48p
0.7 0.8 0.9
15812 15788 15788 15792 15783 15780 15784 15780 15792 15786 14422 14422 14422 14442 14422 14422 14432 14422 14440 14422
10次运行分别得到的最优解 15780 15782 15780 15780 15788 15794 15780 15782 15784 15780 15780 15782 15780 15782 15780 15780 15780 15782 15782 15780 15780 15790 15780 15780 15780 15780 15804 15782 15780 15780 14512 14422 14454 14448 14432 14424 14436 14422 14422 14424 14434 14424 14434 14424 14424 14422 14422 14428 14442 14422 14424 14424 14422 14422 14424 14422 14422 14424 14422 14424
方差
15782
15780 15780 15788 15780 15781 15784 15798 15788 15780 14424 14422 14422 14422 14422 14422 14432 14422 14422 14422 656-665.
9.594 4.079 1.077 5.618 7.440 26.988 7.057 3.555 6.437 5.276
平均时间(S)
125.2 127.4 110.3 148.6 172.1 59.7 57.3 42.8 62.4 77.2
・1425・
平均迭代次数
1239 1273 1122 1495 1835 267 232 180 258 304
参考文献:
[1]
Dorigo M., Maniezzo V., Colorni A. Ant system: Optimization by a colony of coorperating agents [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 1996, 26(1): 29-41. [2] [3] [4]
Dorigo M., Gambardella L. M.Ant colonies for the traveling salesman problem [J]. BioSystems, 1997, 43(2): 73-81.
Gutjahr J.W. A Graph-based Ant System and its convergence [J]. Future Generation Computer Systems, 2000, 16(8): 873-888.
Talbi E.G., Roux O., Fonlupt C., Robillard D. Parallel Ant Colonies for the quadratic assignment problem [J]. Future Generation Computer Systems, 2001, 17(4): 441-449. [5]
Maniezzo V., Carbonaro A. An ANTS heuristic for the frequency assignment problem [J]. Future Generation Computer Systems, 2000, 16(8): 927-935. [6]
Chang C.S., Tian L., Wen F.S. A new approach to fault section in power systems using Ant System [J]. Electric Power Systems Research, 1999, 49(1): 63-70. [7] [8]
吴庆洪, 张纪会, 徐心和. 具有变异特征的蚁群算法[J]. 计算机研究与发展, 1999, 36(10): 1240-1245.
Dorigo M., Luca M. The Ant-Q algorithm applied to the nuclear reload problem [J]. Annals of Nuclear Energy, 2002, 29(12): 1455-1470. [9]
Dorigo M.,Gambardella L.M. A study of some properties of Ant-Q [A]. In:Voigt H.-M, Ebeling W., Rechenberg I., Schwefel H.-S(Eds.). Proceedings of PPSN IV-Fourth International Conference on Parallet Problem Solving From Nature [C]. Berlin:Springer-Verlag, 1996,
[10] Stützle T., Hoos H.H. MAX-MIN Ant System [J]. Future Generation
Computer Systems Journal. 2000, 16(8): 889-914.
[11] Gambardella L.M, Dorigo M. An Ant Colony System Hybridized
with a New Local Search for the Sequential Ordering Problem [J]. INFORMS Journal on Computing, 2000, 12(3): 237-255.
[12] Botee H.M, Bonabeau E. Evolving ant colony optimization [J].
Complex Systems, 1998, 1(2): 149-159.
[13] Bilchev G., Parmee I.C. Adaptive search strategies for heavily
constrained design spaces [A]. Proceedings of 22nd International Conference on Computer Aided Design ’95 Yelta [C]: Ukraine, 1995, 230-235.
[14] 陈崚, 沉洁, 秦玲. 蚁群算法求解连续型优化问题的一种新方法
[J]. 软件学报, 2002, 13(12): 2317-2322.
[15] 吴斌, 史忠植. 一种基于蚁群算法的TSP问题分段求解算法[J].
计算机学报, 2001, 24(12): 1328-1333.
[16] 张纪会, 高齐圣, 徐心和. 自适应蚁群算法[J]. 控制理论与应用,
2000, 17(1): 1-3.
[17] 陈录生, 马剑侠. 新编心理学 [M]. 北京: 北京师范大学出版社,
1996, 3: 53-61.
[18] 叶奕干, 祝蓓里. 心理学[M]. 华东师范大学出版社, 1996, 3: 84-85. [19] Bullnheimer B., Hartl R.F., Strauss C. A New Rank Based Version of
the Ant System-A Computational Study [J]. Central European Journal for Operations Research and Economics, 1999, 7(1): 25-38. http://citeseer.nj.nec.com/bullnheimer97new.html
[20] www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95
[EB/OL].
《第三届全国虚拟现实与可视化学术会议文集》征订启事
主要栏目有：(1)综述；(2)图形图象与可视化；(3)虚拟人、人机交互与界面；(4)网络与分布式虚拟现实；(5)建模与仿真技术；(6)虚拟博物馆与地理信息系统；(7)虚拟设计与虚拟制造；(8)虚拟现实系统、应用及其它。
共刊登172篇优秀论文。全册150元（含邮费）。请将汇款寄至编辑部。 地址：北京142信箱13分箱 邮编：100854 电话：010-68388709