（1）自组织性：算法初期，单个的人工蚂蚁无序地寻找解，经过一段时间的演化，蚂蚁间通过信息素的作用，自发地越来越趋向于寻找到接近最优解的一些解，是个从无序到有序的过程；
（2）较强的鲁棒性：无中心控制，不会由于某一个或者某几个个体的故障而影响整个问题的求解；
（3）本质并行性：蚁群在问题空间的多点同时开始进行独立的解搜索，增强了算法的全局搜索能力；
（4）正反馈性：蚁群能能够最终找到最短路径，直接依赖于最短路径上信息素的堆积，而信息素的堆积就是一个正反馈的过程；
（5）易于与其它方法相结合：蚁群算法很容易与多种启发式算法结合，以改善算法的性能。
2.4.2蚁群算法的缺点
虽然蚁群算法有上述这些优点，但与已经发展成熟的一些启发式算法比较起来，还存在计算量比较大、搜索时间比较长、易出现停滞现象等缺点。并且，在人工蚁群算法中经常出现信息素浓度最强的路径不是所需要的最优路径的情况。
这是由于人工蚁群算法中，路径上的初始信息素浓度是相同的，蚁群创建的第一条路径所获得的信息主要是城市之间的距离信息。这时，蚁群算法等价于贪婪算法。第一次循环中蚁群在所经过的路径上留下的信息不一定能反映出最优路径的方向。正反馈的作用会使得这条不是最优解的路径上的信息得到不应有的增强，阻碍以后的蚂蚁发现更好的全局最优解。事实上，不仅是第一次循环所建立的路径可能对蚁群产生误导，任何一次循环所利用的信息较平均地分布在各个方向上，这次循环所释放的信息素就可能会对以后蚁群的决策产生误导。并且，基本的蚁群算法对所有蚂蚁搜索的路径都进行了信息素的更新，降低了搜索最优路径的效率，使得蚂蚁的搜索行为不能很快集中在最优路径的邻域内。
因此，合理的利用和开发信息素是提高蚁群算法性能的关键。
11
三、一种改进的蚁群算法
针对基本蚁群算法的不足，本章将提出一种基于模糊集合的改进的蚁群算法(Fuzzy Ant Colony Optimization，简称FACO)。该算法引入模糊集合的概念，利用隶属度对蚁群寻找到的路径进行模糊评价，并根据模糊评价结果对部分蚂蚁搜索出来的路径进行信息素的更新，从而加快算法收敛速度，提高算法的性能。 3.1改进的蚁群算法FACO的思想
由上一章的分析可知：合理的利用和开发信息素是提高蚁群算法性能的关键。在基本蚁群算法中，所有蚂蚁搜索的路径都进行信息素的更新。当蚂蚁数目很大时，如果不对所有蚂蚁搜索的路径都进行信息素的更新，肯定会提高算法的效率。选择怎样的蚂蚁进行更新既能提高算法的效率又能保证解的质量？从最大－最小蚂蚁系统中得到启示：更新一些较优的解(搜索路径较短的解)，可以使蚂蚁的搜索行为集中在最优路径的附近，从而改进算法的性能。
然而“较短”是一个模糊概念，对于不同的人有不同的理解，它属于不确定性问题。解决模糊不确定性问题的工具是由美国控制论专家Zadeh创立的模糊数学，它包括模糊集合理论、模糊逻辑、模糊推理和模糊控制等方面的内容。其中模糊集合研究中处理的是模糊现象，它是由于概念外延的模糊而难以确定，一个对象是否符合这个概念而呈现出不确定性(即模糊性)，其说明事物与概念间没有决定的排中(是与否)关系，这是排中律——隶属规律——事件隶属度的客观含义，它反映了事件与模糊概念间的联系与制约。可见，隶属度也不能主观的任意捏造，它仍然具有客观的规律性。因此，引入隶属度对蚁群中的路径进行评价是合理并且可行的。
模糊子集与隶属度的定义如下：
定义3.1 设给定论域U，所谓U上的一个模糊子集A是指对于任意的x∈U，
1]，用这个数表示x属于A的程度。映射 都能确定一个数?A(x)?[0，
x）称为A的隶属函数，常数?（叫做U中的元素对模糊子集A的隶属度。 Ax）x）隶属度?（表示x属于A的程度，?（越接近于0，表示x隶属于AAAx）x）的程度越小；?（越接近于1，表示x隶属于A的程度越大；若?（越接AA近于0.5，则表示x隶属于模糊集合A的程度越模糊。隶属函数的确定方法常见
的有：模糊统计法、借助于概率论的方法、德尔菲法、借助已知的模糊分布。 3.2改进的策略
在FACO算法中，针对不同的问题，可以定义不同的模糊集合以及选择不同类型的隶属函数。如：对TSP问题，我们定义模糊子集为A=“较短”，论域U=[min L,max L]，其中min L表示到目前为止蚁群搜索出来的最短的路径长度，max L表示到目前为止蚁群搜索出来的最长的路径长度，选择偏小型隶属函数对每只蚂蚁搜索出来的路径进行评价。然后，采用新的信息素的计算方法以及部分更新规则对各条路径上的信息素进行更新。 3.2.1更新规则
12
经过n个城市的搜索，蚂蚁完成一次循环，计算每个蚂蚁搜索得到的路径对于模糊子集A=“较短”的隶属度。对隶属度大于一个给定的数λ(λ∈[0,1])的路径进行信息素更新，其它的路径则不进行信息素的更新。由于挥发机制的存在，其它路径上的信息量会逐渐减少，这就增大了较好路径与较差路径在信息素上的差异，使得蚂蚁更倾向于选择较优路径中的边，从而使其搜索行为能够很快的集中到最优路径附近。 3.2.2信息素的更新
对隶属度大于λ的路径赋予一个与隶属度相对应的权重进行信息素的更新。即蚂蚁k在每次循环中在城市i和城市j之间的路径上留下的信息素变为：
其中，lsd(k)是蚂蚁k的对于模糊子集A=“较短”的隶属度。这样就增大了较短路径之间信息素的差异，更合理的利用了信息素。 3.3 FACO算法求解TSP问题 3.3.1 FACO算法框架
求解TSP问题的FACO算法框架如下：
设置参数m、α、β、ρ、Q、λ，初始化信息素 While(不满足停止条件时)do 构造解；
选择合适的隶属函数对解进行评价； 根据评价结果修改各路径的信息素； End
3.3.2初始信息素的设置
在基本蚁群算法中，各条路径上的初始信息素设置为相同的常数。这就导致在算法初期各条路径上的信息素分配差异不明显，算法要经过较长的一段时间才能使较好路径上的信息素优势显现出来，可见算法初期浪费了较长时间。因此，在FACO算法中设各条路径上的初始信息素的大小为各条路径长度的倒数。这样可以加强算法初期信息素的作用。 3.3.3确定模糊子集及隶属函数
对于TSP问题，我们希望蚂蚁寻找到的路径越短越好，所以我们取模糊子集为A=“较短”。根据我们研究的问题，本文借助已知的模糊分布，选择matlab模糊工具箱中的Z型函数作为隶属函数：
Z型函数是基于样条插值的函数，两个参数a、b分别定义了样条插值的起点和终点。当a 13 (k)在t时刻，蚂蚁k从城市i转移到城市j的概率不意味着蚂蚁k到达城市i后，一定从这些 pij并(t)由公式(2.1)计算， pij(k)(t)中找出最大者，以其对应的 城市作下一目标城市。否则算法就失去了随机性，就可能丢失某些较好解，以致最终找不到真正最优解。这里我们采用徐精明等提出的轮盘赌方法来实现蚂蚁选择下一城市的随机性。即先按(2.1)计算 pij(k)(t)，将这些选择概率作累积概率统 计，然后产生一个随机数，该随机数落入哪一个累积概率中，该累积概率对应的城市就作为下一个被选城市。 3.3.5初始参数的设置 对于给定的参数λ，当λ=0时，因为大多数路径的隶属度都是大于零的，所以，此时几乎对所有蚂蚁搜索的路径都要进行信息素的更新，改进的算法同基本的蚁群算法性能相同。当λ=1时，则只有少数的几条路径才进行更新，改进的算法很容易陷入局部最优。因此，取λ∈(0,1)。 由上一章的分析可知：蚁群算法初始参数的选取对算法性能有很大的影响。而蚁群算法各参数之间是相互耦合的，具有复杂的关系，所以参数的选取应当综合考虑。为了使得试验的组合数目较少而又能够获得算法运行的最佳参数组合，本文采用黄永青等提出的均匀设计方法编制试验方案，选择合适的初始参数组合。均匀设计是一种非常有效的部分因子试验方法，可以用较少的试验获得期望的结果。关于均匀设计的原理可以参看文献，用均匀设计方法设定FACO算法参数的步骤如下： ①对s=6个参数分别确定取值范围； ②对每个参数取n个水平，找出均匀设计表Un(n)，根据推荐表使用n?1列中的s列，得到Un(n)； ③根据挑出来的均匀表编制试验方案，即找出对应的参数组合，对每组进行多次试验，统计其数据，找出最优的组合。 3.3.6 FACO算法的实现 FACO算法对TSP问题求解的实现过程可以用伪代码表示如下： (1)初始化过程 设nc=0； {nc循环次数计数器} sn?1?ij(t)?1/dij； {设每路径长度的倒数为其路径上信息素浓度的初始值} ??ij?0； {信息素的增量的初值设为0} ?ij?1/dij； {路径(i,j)的能见度设为各路径长度的倒数} ktabu??； {在初始阶段，禁忌表为空} 将m只蚂蚁随机地置于n个节点上： 设置s:=1 {s为禁忌表索引，将各蚂蚁的初始城市置于当前禁忌表中} For i:=1 to n do 14 For k:=1 to kb(t) do {b(t)为t时刻位于城市i的蚂蚁数} ii(s)?i tabu(2)重复直到禁忌表满为止 {这一步要重复(n?1)次} 设置s:=s+1 for i:=1 to n do For k:=1 to b(t) do i 按公式(2.1)计算 pij(k)(t)，用轮盘赌方法选择下一个城市j； 将蚂蚁k移到j； 将刚刚选择的城市j加到tabuk中； (3)for k:=1 to m do 根据禁忌表的记录计算Lk； 按公式(3.4)计算Lk的隶属度； if lsd(k)>λ do for s:=1 to n?1 do {搜索蚂蚁k的禁忌表} (h,l):?(tabuk(s),tabuk(s?1)){(h,l)是在蚂蚁k的禁忌表中连接城 市(s,s+1)的路径} (4)对于符合条件的路径(i,j)，根据公式(2.2)、（2.3）计算?ij(t?n) (5)记录到目前为止的最短路径 If nc do清空所有的禁忌表 设置s:=1 For i:=1 to n do for k：=1 to kb(t) do itabu(s)?i {一次循环后蚂蚁又重新回到初始位置} 对于每一条路径(i,j)，设置??ij?0 返回步骤(2); else 输出最短路径； 15