图2为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。
假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而 ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2：1。
寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3：1。
若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。
若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。这就是正反馈效应。
人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。在TSP问题中，可以预先知道当前城市到下一个目的地的距离。
TSP问题表示为一个N个城市的有向图G=（N，A），其中
N?{1,2,...,n} ，A?{(i ,j)| i,j?N} (1)
城市之间的距离目标函数为：(dij)n?n
其中
f(w)??dil?1il (2)
l?1n为城市1，2···n的一个排列。w?(i1,i2,?,in),in?1?i1。
假设m只蚂蚁在图的相邻节点间移动，从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定：一，信息素值，也称信息素痕迹。二，可见度，即先验值。
信息素的更新方式有2种，一是挥发，也就是所有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程；二是增强，给评价值“好”(有蚂
6
蚁走过)的边增加信息素。
蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越接近最优解。
蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。
算法步骤如下：
步骤1： 对n个城市的TSP问题，N?{1,2,...,n} A?{(i ,j)| i,j?N}，城市间的距离矩阵为(dij)n?n，给TSP图中的每一条弧(i,j)赋信息初始值
?ij(0)?1 (3) |A|假设m只蚂蚁在工作，所有蚂蚁都从同一城市出发。当前最好解是w?(1,2,?,n)。 步骤2：（外循环）如果满足算法的停止规则，则停止计算并输出计算得到的最好解。否则使蚂蚁s从起点i0出发，用L(s)表示蚂蚁s行走的城市集合，初始L(s)为空集，
1?s?m。
步骤3（内循环）按蚂蚁1?s?m的顺序分别计算。当蚂蚁在城市i，若
L(s)?N或?l|(i,l)?A，l?L(s)??? (4)
完成第s只蚂蚁的计算。否则，若
L(s)?N且T??l|(i,l)?A,l?L(s)???i0??? (5)
则以概率
pij?到达j，
?ij(k?1),j?T，pij?0,j?T (6)
??ij(k?1)l?TL(s)?L(s)??j?,i?j (7)
若
L(s)?N且T??l|(i,j)?L(s)???i0??? (8)
7
则到达i0，
L(s)?L(s)??i0?,i?i0 (9)
重复步骤3。
步骤4：对1?s?m，若L(s)?N，按L(s)中城市的计算路径程度；若L(s)?N，路径长度置为一个无穷大值（即不可到达）。比较m只蚂蚁中的路径长度，记走最短路径的蚂蚁为t。若f(L(t))?f(L(W))，则W?L(t)。用如下公式对W路径上的信息素痕迹加强，对其他路径上的信息素进行挥发。
?????ij(k)?(1??k?1)?ij(k?1)?k?1??(i,j)为W上的一条弧?|W|?? (10)
??(k)?(1??)?(k?1)?????(i,j)不是W上的一条弧?k?1ij?ij?得到新的?ij(k),k?k?1，重复步骤2。
在步骤4中，挥发因子?k对于一个固定的K?1，满足
?k?1??lnkln(k?1)，k?K (11)
并且??k??，经过k次挥发，非最优路径的信息素逐渐减少至消失。
k?1最总停止计算，输出本次运行的最优路径。 3.1.2 模型的求解
在求解时利用各个城市的经纬度作为决策变量，运行MATLAB-M文件[5]（详见附录-MATLAB程序1），将34城市的经纬度
?126125123116117??113108103114113?W??? 4644424039??2823252222??调入程序。
运行多次后，出现多个运行结果。
在此，要对多个运行结果进行筛选，即求出多个运行结果中的最优解与次优解。首先需要知道路径中城市与城市之间的距离dij。
将所有城市编号得：
8
城市 编号 哈尔滨 1 长春 2 沈阳 3 ··· ··· 昆明 32 香港 33 澳门 34 利用城市经纬度
?126125123116117??113108103114113?W??? 4644424039??2823252222??用MATLAB（详见附录-MATLAB程序2）求出：
?0?230??510??dij??????3145?2856??2878?2310282??2934262526475112820??2663????3145??2934??2663??0285626252346??12000622878?2647??2367???? ???1141?62??0??2346??12002367??1141根据得出的数据能够直接得到城市i到j距离，进而利用MATLAB求出了最短路径最优解（图1）S1?15869.54km与次优解（图2）S2?15966.19km：
哈尔滨
哈尔滨
图3 图4
假设旅行线路的方向如图3、图4所示，对路径上的城市旅游的先后顺序进行编号。 路径最优解：
9
哈尔滨（1）?长春（2）?沈阳（3）?天津（4）?北京（5）?呼和浩特（6）?太原（7）?石家庄（8）?济南（9）?郑州（10）?西安（11）?银川（12）?兰州（13）?西宁（14）?乌鲁木齐（15）?拉萨（16）?昆明（17）?成都（18）
?重庆（19）?贵阳（20）?南宁（21）?海口（22）?广州（23）?澳门（24）?香港（25）?台北（26）?福州（27）?南昌（28）?长沙（29）?武汉（30）?合肥（31）?南京（32）?杭州（33）?上海（34）?哈尔滨（1）路径次优解：
哈尔滨（1）?长春（2）?沈阳（3）?天津（4）?北京（5）?呼和浩特（6）?太原（7）?石家庄（8）?济南（9）?郑州（10）?西安（11）?银川（12）?兰州（13）?西宁（14）?乌鲁木齐（15）?拉萨（16）?昆明（17）?成都（18）
?重庆（19）?贵阳（20）?南宁（21）?海口（22）?香港（23）?澳门（24）?广州（25）?长沙（26）?武汉（27）?南昌（28）?台北（29）?福州（30）?杭州（31）?合肥（32）?南京（33）?上海（34）?哈尔滨（1）3.2 问题（2）（3）模型的建立及求解 3.2.1 模型的建立
针对在问题（1）中求出的最短路径最优解（最短路径次优解的解法与此相同）在互联网上分别查到城市Ci?Ci?1`的旅行方式m（动车m1、快车卧铺m2、航空m3）的车次或航班N，以及每个车次或航班的出发时间t，到达时间tt，总共花掉的时间
T?t?tt，里程S，及价格P。
基于要从互联网上选择最好的车次或航班，每个车次或航班具有不同的参考因素值（旅行方式，出发时间，到达时间，总共时间，里程，票价），因此，把决定车次或航班的问题归为多属性决策问题[3]。这几个属性都属于主观评价的范围，最终结果取决于决策者的主观意见。为了反映决策者的主观意见，这里引入重要性程度G与满意度H，即对于选择每个车次或航班的每一个参考因素的满意程度。
定义：（1）重要性程度G为所有参考因素（旅行方式，出发时间，到达时间，总共时间，
里程，票价）中每个参考因素占整个参考因素的百分比。
（2）满意度H为决策者对于每个参考因素的值的满意程度，这里用分值度量。 下面是决定车次或航班的决策树：
10