改进的蚁群算法在TSP问题上的应用

改进的蚁群算法在TSP问题上的应用

摘要：旅行商问题（Traveling Salesman Problem，TSP）是近代组合优化领域的一个典型难题。现实生活中的很多问题都可以转化为TSP问题，如邮路问题、通讯网络设计、大规模集成电路的综合布线设计等。因此，对TSP问题的研究具有重要的理论意义和实际应用价值。然而关于TSP问题的完全有效的算法目前尚未找到，这促使人们长期以来不断地探索并积累了大量的算法。本文所用到的蚁群算法也在其中。

蚁群算法是受大自然中蚂蚁觅食启发而提出的一种智能仿生算法，具有较强的鲁棒性、分布式计算、易于与其它方法结合等优点。本文提出一种基于模糊集合的改进蚁群算法，该算法根据隶属度对种群进行评价，并依此进行信息素的更新，在求解速度和解的质量上取得一个较好的平衡。通过对改进算法的仿真实验，验证了该算法的可行性及有效性。本文主要的研究工作如下:

1．阐述了论文研究的背景及意义，总结了迄今为止出现的求解TSP问题的各种方法，并对常见的求解方法的优缺点进行了详细的分析，最后，分析了蚁群算法国内外研究现状。

2．给出了蚁群算法的基本原理、算法模型以及特点。

3．提出一种改进的蚁群算法。该算法引入模糊集合的概念，利用隶属度对蚁群寻找到的路径进行模糊评价，并根据模糊评价结果对路径上的信息素进行更新，从而加快了算法收敛速度，提高了算法的性能。 关键词：TSP问题；蚁群算法；组合优化；模糊集合

1

一、绪论

1.1论文选题背景与意义

组合优化问题是运筹学中的一个经典且重要的分支,而在组合优化问题中，旅行商问题（Traveling Salesman Problem，TSP）是近代组合优化领域的一个典型难题。由于TSP问题形式简单、易于描述、且属于典型的NP难问题，因此其作为算法研究与验证的平台而被广泛研究。在TSP问题上取得的理论或者实验成果，可以应用于其他的NP难解问题。事实上，求解NP难问题的许多方法都源自于TSP问题的研究。

TSP问题不但具有很大的理论价值，而且在科学、工程及经济的各方面具有广泛的应用，是诸多领域内出现的多种复杂问题的集中概括和简化形式。如：网络通讯、电路板钻孔、管道铺设、货物配送、交通调度、电网规划等，这些问题或者直接就是TSP问题的原型，或者可以转化为TSP问题。因此，快速、有效地解决TSP问题有着极高的实际应用价值。然而关于TSP问题的完全有效的算法目前尚未找到，这促使人们长期以来不断地探索并积累了大量的算法，如遗传算法、禁忌搜索算法、模拟退火算法、蚁群算法等。本文重点研究的是改进的蚁群算法在TSP问题中的应用。

蚁群算法(Ant Colony Optimization,ACO)是一种模仿蚂蚁群体行为的新的智能优化算法。1991年，意大利学者Dorigo M等人首次提出蚁群算法，开始并没受到国际学术界的广泛关注，直到1996年，Dorigo M等人在《IEEE Transactions onSystems,Man,and Cybernetics-Part B》上发表了”Ant system:optimization bya colony of cooperating agents”一文,奠定了蚁群算法的基础。从此之后，蚁群算法逐渐引起了国际学术界的广泛关注。1998年，Dorigo M组织在比利时布鲁塞尔召开了第一届蚂蚁优化国际研讨会，以后每两年召开一次。2000年，GutjahrW J发表了题为“A graph-based ant system and its convergence”的学术论文，对蚁群算法的收敛性进行了证明。同年，Dorigo M和Bonabeau E等在国际顶级学术杂志《Nature》上发表了蚁群算法研究综述，将这一研究推向国际学术界的前沿。

和遗传算法、禁忌搜索算法等智能优化算法相比，蚁群算法具有正反馈性、并发性、易与其它算法相结合等主要特点。这些特点使得蚁群算法的应用非常广泛。如：英国电信公司的电信网络管理试验是基于电子蚂蚁的；英国联合利华公司的生产计划管理软件、美国太平洋西南航空公司的运输管理软件都是基于蚁群算法的。实际上，蚁群算法在诸多的领域都有不俗的表现，如电子系统、控制参数优化、聚类分析、网络路由问题、布局优化等。

总之，蚁群算法已经渗透到多个应用领域，从一维静态优化问题到多维动态优化问题，从离散问题到连续问题。蚁群算法都展现出优异的性能和广阔的发展前景。

1.2 TSP问题简介

TSP问题也称货郎担问题，是一个较古老的问题。最早的记录来自于1759年欧拉研究的骑士周游问题，即对于象棋盘中的64个方格，走访每个方格一次且仅一次。1948年，由于美国兰德公司的推动，TSP问题成为一个知名且流行的问题。它已经被证明属于NP难题。 1.2.1 TSP问题的定义

TSP问题可以简单描述为：给定n个城市(记为：r1，r2，...，rn)和它们

2

两两之间的直达距离(记为：d(ri，rj))，寻找一条闭合的旅程，使得每个城市刚好经过一次且总的旅行距离最短。即寻找一条巡回路径R?(r1，...，r2，rn)，使得公式(1.1)所示的目标函数最小。

用图论的语言描述为：在一个赋权完全图中，找出一个最小权的哈密顿圈。记G=(V,E)为赋权图，V={1,2,L,n}为顶点集，各顶点间距离

（dij?0，，并设 dij???，i，j?V）dij已知

则TSP的数学模型可写成如下的线性规划形式：

上式中，S为集合S中所含图G的顶点个数。前两个约束意味着对每个顶点而言，仅有一条入边和一条出边，后一约束则保证了没有任何子回路解的产生。满足上述约束的解构成了一条哈密顿回路。

当dij?dji（i,j=1,2,3,L,n)时，称为对称TSP问题。

当dij?dji (i,j=1,2,3,L,n)时，称为非对称TSP问题，或有向TSP问题。 本文探讨的是对称TSP问题的求解。 1.2.2求解TSP问题的智能优化算法

关于求解TSP问题的完全有效的算法目前尚未找到，这促使人们长期以来不断地探索并积累了大量的算法。归纳起来，主要分为三类：精确算法、近似算法以及智能优化算法。常见的精确算法有：整数规划方法、动态规划方法、分支定界算法等。这类算法虽可得到精确解，但计算时间长，实际应用中极少采用。常

3

见的近似算法有：插入算法、r-opt算法和最近邻算法等。这类算法虽然可以较快地求得接近最优解的可行解，但其接近最优解的程度不能令人满意。智能优化方法是近年来发展起来的一个非常活跃的研究领域，主要包括：遗传算法、禁忌搜索算法、模拟退火算法、蚁群算法和粒子群算法等。这类算法虽然不能保证在有限的时间内获得最优解，但选择充分多个解验证后，错误概率可降到可以接受的程度。

1.3蚁群算法研究现状

蚁群算法是一种新型启发式优化算法，在求解节点数为5到100的组合优化问题上，选用合适的参数，其优化结果普遍好于遗传算法和模拟退火算法。因此，目前国内外有许多学者开展了对蚁群算法的研究工作。如：国外学者Stuzle和Hoss提出了最大—最小蚂蚁算法，该算法只对最佳路径增加信息素浓度，并且为信息素设置上下限来避免算法过早出现停滞现象。Cordon O等提出最优—最差蚂蚁算法，该算法对最优解进行更大限度的增强，而对最差解进行削弱，使得最优解与最差解之间的信息素差异增大，从而使蚂蚁的行为更集中于最优解附近。

国内对蚁群算法的研究始于上世纪末，从公开发表的论文看，最先研究蚁群算法的是东北大学的张纪会博士和徐心教授。为了克服蚁群算法计算时间长这一缺点，吴庆洪等于1999年提出了具有变异特征的蚁群算法，该算法采用逆转变异的方式，随机地进行变异，以增大进化时所需的信息量。这种变异机制充分利用了2交换法简洁高效的特点，因此具有较快的收敛速度。吴斌等于2001年提出了一种相遇算法，该算法将相遇算法与采用并行策略的分段算法相结合，用两

只蚂蚁共同完成对一条路径的搜索，以提高搜索速度。徐精明等于2005年提出一种多态蚁群算法，该算法通过引入侦察蚁、搜索蚁和工蚁三种不同种类的蚁群，将局部搜索与全局搜索相结合，使收敛速度大幅提高。针对蚁群算法易限于局部最小点的缺陷，王颖等于2002年提出一种自适应的蚁群算法，该算法通过自适应地改变算法信息素的挥发度系数，在保证收敛速度的条件下提高了解的全局性。刘立东等于2008年提出了一类融入遗传算法的混合蚁群算法，该算法在每代进化中保留最优解和次优解的公共解集后引入遗传操中的交叉算子和变异算子进行运算，加快了算法收敛速度，提高了解的全局性。陈星宇等人于2008年提出一种融入LK算法的混合蚁群算法，该算法将改进的LK算法优化蚂蚁生成解阶段，并在不同阶段灵活运用局部优化算法，此外还将Metropolis概率接受准则融入进来，有效地避免陷入局部最优。

以上改进算法与基本蚁群算法相比，有的算法虽然提高了搜索速度，但不能有效的防止算法陷入局部最优解；有的算法虽然有效的防止算法得到局部最优解，但是在防止陷入局部优化的同时，消耗了大量的计算时间。因此，如何在加快收敛速度和防止陷入局部最优之间取得一个平衡是目前研究的难点之一。

4

二、蚁群算法

蚁群算法不同于其他智能优化算法最为显著的特点是：采用了正反馈机制或称是一种增强学习系统，通过不断更新信息素达到最终收敛于最优解的目的。本章将对蚁群算法的基本原理、算法模型以及优缺点进行详细的分析。 2.1蚁群算法的原理 2.1.1蚁群觅食的特性

觅食行为是蚁群一个重要而有趣的行为。据昆虫学家的观察和研究发现，蚂蚁有能力在没有任何可见提示下找出从蚁穴到食物源的最短路径，并且能随环境的变化而自主地搜索新的路径，产生新的选择。这是因为在从蚁穴到食物源并返回的过程中，蚂蚁能在其走过的路径上分泌一种化学物质——信息素，通过这种方式形成信息素轨迹。蚂蚁在运动过程中能够感知这种物质的存在及其浓度，并以此指导自己的运动方向，使蚂蚁倾向于朝着该物质浓度高的方向移动。信息素轨迹可以使蚂蚁找到它们返回食物源(或蚁穴)的路径，其他蚂蚁也可以利用该轨迹找到由同伴发现的食物源的位置。

如图2.1(a)所示，A为蚁巢，D为食物源，蚂蚁总是会选择最短的直线路径AD来搬运食物。如果搬运路线上突然出现障碍物，不管路径长短，蚂蚁按相同的概率选择在图中B点和C点绕过障碍物，如图2.1(b)所示。由于路径ABD的长度小于路径ACD的长度，单位时间内通过路径ABD的蚂蚁数量大于通过路径ACD的蚂蚁数量，则在路径ABD上面遗留的信息素浓度比较高，所以选择路径ABD的蚂蚁随之增多，如图2.1(c)所示。于是，蚁群的集体行为表现出一种信息正反馈现象，即最短路径上走过的蚂蚁越多，则后来的蚂蚁选择该路径的概率就越大，蚂蚁个体之间就是通过这种信息的交流找到寻找食物和蚁穴之间最短路径的目的，如图2.1(d)所示。

图2.1 蚁群寻找食物过程

2.1.2蚁群算法的基本思想

受到自然界中真实蚁群集体行为的启发，意大利学者Dorigo于1991年首次提出了一种基于蚂蚁种群的新型优化算法——蚁群算法。为了和真实的蚂蚁相区别，我们称蚁群算法中的蚂蚁为人工蚂蚁。人工蚂蚁具有双重特性：一方面，它们是真实蚂蚁的抽象，具有真实蚂蚁的一些特性，如个体相互交流的通信机制、

5

相同的任务、随机选择策略；另一方面，它们还具有以下三种特性： (1)人工蚂蚁具有记忆能力。

(2)人工蚂蚁生活在离散时间的环境中。

(3)人工蚂蚁选择路径时并不是完全盲目的，受到问题空间特征的启发，按一定算法规律有意识地寻找最短路径。

基本蚁群算法是采用人工蚂蚁的行走路线来表示待求解问题可行解的一种方法。每只人工蚂蚁在解空间中独立地搜索可行解，当它们碰到一个还没走过的路口时，就随机挑选一条路径前行，同时释放出与路径长度有关的信息素。路径长度越短信息素的浓度就越大。当后继的人工蚂蚁再次碰到这个路口的时候，以相对较大的概率选择信息素浓度较高的路径，并在“行走路线”上留下更多的信息素，影响后来的蚂蚁，形成正反馈机制。随着算法的推进，代表最优解路线上的信息素逐渐增多，选择它的蚂蚁也逐渐增多，其他路径上的信息素却会随着时间的流逝而逐渐消减，最终整个蚁群在正反馈的作用下集中到代表最优解的路线上，也就找到了最优解。在整个寻优过程中，单只蚂蚁的选择能力有限，但蚁群具有高度的自组织性，通过信息素交换路径信息，形成集体自催化行为，找到最优路径。

2.2蚁群算法的模型

为了更好的理解蚁群算法的模型和实现过程，我们以求解平面上n个城市(1,2,L,n为城市编号)的TSP问题为例，说明蚁群算法模型。首先引入如下记号： m——蚁群中蚂蚁的总数。

nij（i，j）——路径的能见度,用某种启发式算法算出，在TSP问题中，一般取

nij?1d，dij表示城市i与城市j之间的距离，i,j∈{1,2,L,n}。

ij?ij(t)——在t时刻路径（i，j）上残留的信息素。

??ij——一次循环中路径（i，j）上的信息素增量。

（i，j）上的信息素 ??ij——第k只蚂蚁在一次循环中留在路径

(k)pij(k)(t)——在t时刻蚂蚁k由位置i转移到位置j的概率。

?——启发因子，轨迹的相对重要性，亦即蚁群在运动过程中所残留的信息素的

相对重要程度。

?——期望启发因子，能见度的相对重要性。

?——信息素挥发度(0≤ρ<1),1?ρ可理解为信息素的残留系数。

Q——蚂蚁循环一次在经过的路径上所释放的信息素总量。

TSP求解中，蚁群算法中的每只人工蚂蚁具有以下特征：

(1)根据以城市距离和连接边上信息素的数量为变量的概率函数选择下一个城市。

(2)规定蚂蚁走合法路线，除非周游完成，不允许转到已访问城市，由禁忌表控

6

制。

(3)完成周游后，蚂蚁在它每一条访问的边上留下信息素。

于是，基本蚁群算法可以理解为：初始时刻，各条路径上的信息素相等，设

?ij(0)=常数。蚂蚁k(k=1,2,L,m)在运动过程中根据各条路径上信息素决定转移方

向。在t时刻，蚂蚁k在城市i选择城市j的转移概率为如下：

pij(k)(t)，其计算公式

其中，allowedk?{1,2，L,n}?tabuk表示蚂蚁k下一步允许选择的城市，

tabu用以记录蚂蚁k当前所走过的城市，tabu集合随着进化过程做动态调

kk(t)与?ij??ij成正比，蚂蚁在选择路径时会尽量选择离自己距离较近且信息素浓度较大的方向。为了避免残留信息素过多而淹没启发信息，在每只蚂蚁走完一步或者完成对所有n个城市的遍历后，要对残留信息素进行更新处理。(t+n)时刻，所有的蚂蚁完成了周游,路径(i,j)上信息素可根据以下公式做调整： 整。上式表明：转移概率

pij(k)??

根据信息素更新策略的不同，Dorigo M提出了三种基本蚁群算法模型，分别称之为蚁周模型(Ant-Cycle Model)，蚁量模型(Ant-Quantity Model)及蚁密模型(Ant-Density Model)。 蚁周模型：

L

k表示第k只蚂蚁在本次循环中所走路径的总长度。

蚁量模型：

7

蚁密模型：

上述三种模型的区别在于：蚁周模型利用的是蚁群的整体信息，即走完一个循环后才进行残留信息素的全局调整；而在蚁量、蚁密这两种模型中，蚂蚁每走一步都要更新残留的信息素，利用的是局部信息。本文的研究都是基于蚁周模型基础之上。

解TSP的蚁群算法的基本步骤如下：

第1步：初始化参数m、α、β、ρ、Q。令t=0,循环次数nc=0,设置最大循环次数NC,路径(i,j)的初化信息量?ij(0)=常数，初始时刻??ij(0)?0。

第2步：将各蚂蚁的初始出发点置于当解集中；对每只蚂蚁k(k=1,2,3,L,m),按概率

pijk（公式2.1）移至下一顶点j；将顶点j置于当前解集。

第3步：计算各蚂蚁搜索的路径长度Lk(k=1,2,L,m)；记录当前的最好解。 第4步：按更新方程(2.2)、（2.3）修改路径上的信息素。 第5步：对各条路径(i,j)，置??ij?0；nc?nc?1。 第6步：若nc

算法流程如图2.2所示。

8

图2.2 基本蚁群算法流程图

2.3蚁群算法的参数分析

从蚁群算法的模型中可以看出，蚁群算法的参数空间庞大。合适的参数组合能够有全局搜索能力和较快的收敛速度，不合适的参数组合则会使得算法收敛较慢或达到局部最优解。然而，目前对各参数该如何选择也没有严格的理论依据，只是根据经验和试验来选取合适的参数值。基于此，国内外许多研究人员在蚁群算法的参数分析和优化组合方面做了大量工作。Dorigo M等最早对α、β、ρ、m等参数的选择进行了初步研究；国内的段海滨、叶志伟、蒋玲艳、涂亚平等也对参数的选择进行了研究。研究表明：对于TSP问题，基本蚁群算法的初始参数的选择也有一般规律。 (1)蚂蚁数量m

蚁群算法是通过多个候选解组成的群体进化过程来搜索最优解，所以蚂蚁的数目m对蚁群算法有一定的影响。m大(相对处理问题的规模)，会提高蚁群算法

9

的全局搜索能力和稳定性，但数量过大会导致大量曾被搜索过的路径上的信息素变化趋于平均，信息正反馈作用减弱，随机性增强，收敛速度减慢。反之，m小，会使从来未被搜索到的解上的信息素减小到接近于0，全局搜索的随机性减弱，虽然收敛速度加快，但是会使算法的全局性能降低，稳定性变差，出现过早停滞现象。经大量的仿真试验获得：当m∈[0.6 n,0.9 n]时（n为城市规模），蚁群算法的全局收敛性和收敛速度都比较好。 (2)启发因子α

启发因子α是表示蚂蚁在运动过程中所积累的信息素在指导蚁群搜索中的相对重要程度，其大小反映了蚂蚁在路径搜索过程中随机因素作用的强弱。α越大，蚂蚁选择以前走过路径可能性就越大，实现自催化过程，但搜索的随机性减弱；α越小，易使蚁群算法过早陷入局部最优。文献研究表明：对于小规模的TSP问题，在蚁群算法的三种模型中，α=1时，解的质量和稳定性都是最好的。 (3)期望启发因子β

期望启发因子β是表示能见度相对重要程度的参数。β的大小反映了蚂蚁在路径搜索过程中确定性因素作用的强弱。文献研究表明：β过小，将导致蚂蚁群体陷入纯粹的随机搜索，在此情况下很难找到最优解；β过大，蚂蚁在局部点上选择局部最短路径的可能性越大，虽然加快了收敛速度，但减弱了随机性，易陷入局部最优。对于TSP问题，不同城市规模，β的具体取值各有不同。对于Oliver 30TSP来说：β∈[2,8.5]时，算法的综合性能比较好。 (4)信息素挥发度ρ

在蚁群算法中，人工蚂蚁是具有人类记忆功能的，随着时间的推移，以前留下的信息将要逐渐消逝。如前所述，在算法模型中，参数ρ表示信息素挥发度，其大小直接关系到蚁群算法的全局搜索能力及其收敛速度；1?ρ信息素残留因子，反映了蚂蚁个体之间相互影响的强弱。研究表明：在其它参数相同的情况下，信息素挥发度ρ的大小对蚁群算法的收敛性影响非常大，ρ与循环次数近似成反比关系。当ρ极小时，路径上残留信息占主导地位，信息正反馈作用相对较弱，搜索的随机性增强，因而蚁群算法的收敛速度很慢。若ρ较大时，正反馈作用占主导地位，搜索的随机性减弱，导致收敛速度快，但易陷入局部最优状态。对于TSP问题，不同的问题规模，ρ的取值也不尽相同。对于Oliver 30TSP来说：ρ∈[0.1,0.5]时，算法的性能较好。 (5)总信息量Q

总信息量Q为蚂蚁循环一周时释放在所经路径上的信息素总量，在基本蚁群算法中它为一常量。一般的理解是：总信息量Q越大，则在蚂蚁已经走过的路径上信息素的累积越快，可以加强蚁群搜索时的正反馈性能，有助于算法的快速收敛。Q值过小，则信息素浓度增长太慢，正反馈信息太少，使算法难以收敛。研究表明：在蚁周模型中，由于TSP的规模不同，路径长度各不相同，如果对不同的TSP使用相同的Q值，则信息素总量更新尺度是不同的，最终修改信息素的程度存在很大不稳定性。Q的取值应与所处理的TSP的规模相对应，确保信息素总量更新在可控制范围内。在小规模TSP问题中，Q=100是大多数论文所公认的较好的值。 2.4蚁群算法的优缺点 2.4.1蚁群算法的优点

蚁群算法的成功运用激起了人们的极大兴趣，并吸引了一批研究人员从事蚁群算法的研究。研究表明，蚁群算法是一种有效的随机搜索算法，具有如下优点：

10

（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

四、MATLAB程序实现

按照枚举法，我国31个直辖市、省会和自治区的巡回路径应该有约

1.326?10种，利用蚁群算法寻找一条最佳或者较佳的路径。利用MATLAB中提

32供的函数，可以方便地在MATLAB环境下实现。 4.1 清空环境变量

程序运行之前，清除工作空间Workspace中的变量及Command Window中的命令。具体程序如下： %% 清空环境变量 clear all clc

4.2 导入数据

31个城市的位置坐标保存在citys_data.mat文件中，变量citys为31行2列的数据，第1列表示各个城市的横坐标，第2列表示各个城市的纵坐标。具体城市如下： %% 导入数据

load citys_data.mat

4.3 计算城市间相互距离

利用城市的横、纵坐标，可以方便地计算出城市间的相互距离。具体程序如下：

%% 计算城市间相互距离 n = size(citys,1); D = zeros(n,n); for i = 1:n for j = 1:n if i ~= j

D(i,j) = sqrt(sum((citys(i,:) - citys(j,:)).^2)); else

D(i,j) = 1e-4; end end

end

4.4 初始化参数

在计算之前，需要对参数进行初始化。同时，为了加快程序的执行速度，对于程序中涉及的一些过程变量，需要预分配其存储容量。具体程序如下： %% 初始化参数

m = 50; % 蚂蚁数量

alpha = 1; % 信息素重要程度因子 beta = 5; % 启发函数重要程度因子 rho = 0.1; % 信息素挥发因子 Q = 1; % 常系数 Eta = 1./D; % 启发函数 Tau = ones(n,n); % 信息素矩阵 Table = zeros(m,n); % 路径记录表

16

iter = 1; % 迭代次数初值 iter_max = 200; % 最大迭代次数 Route_best = zeros(iter_max,n); % 各代最佳路径 Length_best = zeros(iter_max,1); % 各代最佳路径的长度 Length_ave = zeros(iter_max,1); % 各代路径的平均长度

4.5 迭代寻找最佳路径

迭代寻找最佳路径为整个算法的核心，首先逐个蚂蚁逐个城市访问，直至遍历所有的城市，以构建问题的解空间，然后计算各个蚂蚁经过路径的长度，记录下当前迭代次数中的最佳路径，并实时对各个城市间连续路径上的信息素浓度进行更新，最终经过多次迭代，寻找到最佳路径。具体程序如下： %% 迭代寻找最佳路径

while iter <= iter_max

% 随机产生各个蚂蚁的起点城市 start = zeros(m,1); for i = 1:m

temp = randperm(n); start(i) = temp(1); end

Table(:,1) = start; % 构建解空间

citys_index = 1:n; % 逐个蚂蚁路径选择 for i = 1:m

% 逐个城市路径选择 for j = 2:n

tabu = Table(i,1:(j - 1)); % 已访问的城市集合(禁忌表) allow_index = ~ismember(citys_index,tabu);

allow = citys_index(allow_index); % 待访问的城市集合 P = allow;

% 计算城市间转移概率

for k = 1:length(allow)

P(k) = Tau(tabu(end),allow(k))^alpha * Eta(tabu(end),allow(k))^beta; end

P = P/sum(P);

% 轮盘赌法选择下一个访问城市 Pc = cumsum(P);

target_index = find(Pc >= rand); target = allow(target_index(1)); Table(i,j) = target; end end

% 计算各个蚂蚁的路径距离 Length = zeros(m,1);

17

for i = 1:m

Route = Table(i,:); for j = 1:(n - 1)

Length(i) = Length(i) + D(Route(j),Route(j + 1)); end

Length(i) = Length(i) + D(Route(n),Route(1)); end

% 计算最短路径距离及平均距离 if iter == 1

[min_Length,min_index] = min(Length); Length_best(iter) = min_Length; Length_ave(iter) = mean(Length); Route_best(iter,:) = Table(min_index,:); else

[min_Length,min_index] = min(Length);

Length_best(iter) = min(Length_best(iter - 1),min_Length); Length_ave(iter) = mean(Length); if Length_best(iter) == min_Length

Route_best(iter,:) = Table(min_index,:); else

Route_best(iter,:) = Route_best((iter-1),:); end end

% 更新信息素

Delta_Tau = zeros(n,n); % 逐个蚂蚁计算 for i = 1:m

% 逐个城市计算

for j = 1:(n - 1)

Delta_Tau(Table(i,j),Table(i,j+1)) = Delta_Tau(Table(i,j),Table(i,j+1)) + Q/Length(i); end

Delta_Tau(Table(i,n),Table(i,1)) = Delta_Tau(Table(i,n),Table(i,1)) + Q/Length(i); end

Tau = (1-rho) * Tau + Delta_Tau; % 迭代次数加1，清空路径记录表 iter = iter + 1; Table = zeros(m,n); end

4.6 结果显示

为了更为直观地对结果进行观察和分析，将寻找到的最佳路径及其长度显示在Command Window中。具体程序如下： %% 结果显示

18

[Shortest_Length,index] = min(Length_best); Shortest_Route = Route_best(index,:); disp(['最短距离:' num2str(Shortest_Length)]);

disp(['最短路径:' num2str([Shortest_Route Shortest_Route(1)])]);

由于各个蚂蚁的起始城市是随机设定的，因此每次运行的结果都会不同。某次运行的结果如下： 最短距离:15828.7082

最短路径:15 14 12 13 11 23 16 4 2 5 6 7 8 9 10 3 18 17 19 24 4.7 绘图

为了更为直观地对结果进行观察和分析，以图形的形式将结果显示出来。具体程序如下： %% 绘图 figure(1)

plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],... [citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'o-'); grid on

for i = 1:size(citys,1)

text(citys(i,1),citys(i,2),[' ' num2str(i)]); end

text(citys(Shortest_Route(1),1),citys(Shortest_Route(1),2),' 起点');

text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2),' 终点');

xlabel('城市位置横坐标') ylabel('城市位置纵坐标')

title(['蚁群算法优化路径(最短距离:' num2str(Shortest_Length) ')']) figure(2)

plot(1:iter_max,Length_best,'b',1:iter_max,Length_ave,'r:') legend('最短距离','平均距离') xlabel('迭代次数') ylabel('距离')

title('各代最短距离与平均距离对比')

与运行结果对应的路径如图4-1所示。从图中可以清晰地看到，自起点出发，每个城市访问一次，遍历所有城市后，返回起点。寻找到的最短路15828.7082km。

各代的最短距离与平均距离如图4-2所示，从图中不难发现，随着迭代次数的增加，最短距离与平均距离均呈现不断下降的趋势。当迭代次数大于121时，最短距离已不再变化，表示已经寻找到最佳路径。

19

图4-1 蚁群算法优化路径

图4-2 各代的最短距离与平均距离对比

20

参考文献:

[1]Dorigo M,Maniezzo V,Colorni A.The ant system:optimization by a colonyof cooperating agents[J].IEEE Transaction on Systems,1996,26(1):1-26

[2]Gutjahr W J.A graph-based ant system and its convergence[J].FutureGeneration Computer Systems,2000,16(8):873-888

[3]Bonabeau E,Dorigo M,Theraulaz G.Inspiration for optimization fromsocial insect behavior[J].Nature,2000,406(6):39-42

[4]马良，朱刚，宁爱兵．蚁群优化算法[M]．北京：科学出版社，2008

[5]周康，强小利，同小军等.求解TSP算法[J].计算机工程与应用,2007,43(29):43-47 [6]Holland J H.Genetic algorithms and the optimal allocation of trials[J].SIAM Journal of Computing,1973,2(2)：89-104

[7]胡纯德,祝延军,高随祥.一种求解旅行商问题的单亲遗传算法[J].计算机工程与应用,2004,40(35)：37-40

[8]刘烨,倪志伟,刘慧婷.求解旅行商问题的一个改进的遗传算法[J].计算机工程与应用,2007,40(6)：65-68

[9]莫海芳,康立山.求解TSP问题的混合遗传算法[J].计算机工程与应用,2007,43(18)：40-41

[10]Glover F.Future Paths for Interger Programming and Links to ArtificalIntelligence[J].Computers and Operations Research,1986,13(5):533-549 [11]方永慧,刘光远,贺一等.一种基于插入法的禁忌搜索算法[J].西南师范大学学报(自然科学版),2002,27(3):341-345

[12]杨宁，田蔚风，金志华.一种求解旅行商问题的交叉禁忌搜索[J].系统仿真学报，2006，18(4)：897-900

21

参考文献:

[1]Dorigo M,Maniezzo V,Colorni A.The ant system:optimization by a colonyof cooperating agents[J].IEEE Transaction on Systems,1996,26(1):1-26

[2]Gutjahr W J.A graph-based ant system and its convergence[J].FutureGeneration Computer Systems,2000,16(8):873-888

[3]Bonabeau E,Dorigo M,Theraulaz G.Inspiration for optimization fromsocial insect behavior[J].Nature,2000,406(6):39-42

[4]马良，朱刚，宁爱兵．蚁群优化算法[M]．北京：科学出版社，2008

[5]周康，强小利，同小军等.求解TSP算法[J].计算机工程与应用,2007,43(29):43-47 [6]Holland J H.Genetic algorithms and the optimal allocation of trials[J].SIAM Journal of Computing,1973,2(2)：89-104

[7]胡纯德,祝延军,高随祥.一种求解旅行商问题的单亲遗传算法[J].计算机工程与应用,2004,40(35)：37-40

[8]刘烨,倪志伟,刘慧婷.求解旅行商问题的一个改进的遗传算法[J].计算机工程与应用,2007,40(6)：65-68

[9]莫海芳,康立山.求解TSP问题的混合遗传算法[J].计算机工程与应用,2007,43(18)：40-41

[10]Glover F.Future Paths for Interger Programming and Links to ArtificalIntelligence[J].Computers and Operations Research,1986,13(5):533-549 [11]方永慧,刘光远,贺一等.一种基于插入法的禁忌搜索算法[J].西南师范大学学报(自然科学版),2002,27(3):341-345

[12]杨宁，田蔚风，金志华.一种求解旅行商问题的交叉禁忌搜索[J].系统仿真学报，2006，18(4)：897-900

21

本文来源：https://www.bwwdw.com/article/4yq6.html