基于蚁群算法的旅行商路径搜索.doc

基于蚁群算法的旅行商路径搜索xxxx（上海大学 机械制造及其自动化学院，上海200072）摘要：蚁群算法(Ant Colony Algorithm,简称ACA)是由意大利学者DorigoM等人首先提出来的一种新型的模拟进化算法。其主要特点就是:通过正反馈、分布式协作来寻找最优路径。这是一种基于种群寻优的启发式搜索算法。它充分利用了生物蚁群能通过个体间简单的信息传递,搜索从蚁穴至食物间最短路径的集体寻优特征,以及该过程与旅行商问题求解之间的相似性,得到了具有NP非确定型(Nondeterministic Polynomial)难度的旅行商问题的最优解答。关键词：蚁群算法；旅行商问题；智能控制；信息素Based on Ant Algorithm for Traveling Salesman Path Searchingxxxx(Institute of Mechanical Manufacturing and Automation, Shanghai University, Shanghai 200072, China)Abstract: Ant colony algorithm (Ant Colony Algorithm, abbreviated as ACA) by the Italian scholars Dorigo M, who first proposed a new type of simulated evolutionary algorithm. Its main characteristic is: Through positive feedback, distributed collaboration to find the optimal path. This is a population-based optimization heuristic search algorithm. It takes full advantage of biological ant colony through the simple transmission of information between individuals, the search of food from the colony to the shortest path between the collective optimization features, as well as the traveling salesman problem-solving process and the similarity between the obtained with the non-NP deterministic (Nondeterministic Polynomial) the optimal degree of difficulty of the traveling salesman problem solution. Key words: Ant colony algorithm; TSP; Intelligent Control; Pheromone1 旅行商问题1.1旅行商问题简介旅行商问题( Traveling Salesman Problem) ,又称旅行推销员问题,是指给定n个城市,任何两城市之间皆有路连通,其距离为已知,某旅行商从其中某城市出发,要经过每城市一次,且只能一次,最后又必须返回出发城市,要求找出最短的巡回路径. TSP 可分为对称TSP ( symmetric traveling salesman problem)和非对称TSP ( asymmetric traveling salesman problem) 两大类, 若两城市往返的距离相同, 则为对称TSP,否则为非对称TSP1。本文研究的是对称TSP。TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。TSP由美国RAND公司于1948年引入，该公司的声誉以及线形规划这一新方法的出现使得TSP成为一个知名且流行的问题2。同样的问题，在中国还有另一个描述方法：一个邮递员从邮局出发，到所辖街道投邮件，最后返回邮局，如果他必须走遍所辖的每条街道至少一次，那么他应该如何选择投递路线，使所走的路程最短？这个描述之所以称为中国邮递员问题（Chinese Postman Problem CPP）因为是我国学者管梅古教授于1962年提出的这个问题并且给出了一个解法。1.2 传统方法解决TSP基于TSP的问题特性,构造型算法成为最先开发的求解算法,如最近邻点、最近合并、最近插入、最远插入、最近添加、贪婪插入等。但是,由于构造型算法优化质量较差,迄今为止已开发了许多性能较好的改进型搜索算法3 ,主要有:1) 模拟退火算法模拟退火算法( simulated annealing, SA) 是基于MonteCarlo迭代求解策略的一种随机寻优算法,其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。SA算法由某一较高初温开始,结合具有概率突跳特性的Metropolis抽样策略在解空间中随机寻找目标函数的全局最优解,伴随温度参数的不断下降重复抽样过程,最终得到问题的全局最优解4。从算法结构知,新状态产生函数、新状态接受函数、退温函数、抽样稳定准则和退火结束准则(简称三函数两准则)以及初始温度是直接影响算法优化结果的主要环节。2) 禁忌搜索算法禁忌搜索( Tabu Search或Taboo Search,简称TS) 是一种亚启发式搜索技术,由Glover在1986年首次提出,进而形成一套完整算法。它是对局部邻域搜索的一种扩展,是一种全局逐步寻优算法,是对人类智力过程的一种模拟。TS算法通过引入一种灵活的存储结构和相应的禁忌准则来避免迂回搜索,并通过藐视准则来赦免一些被禁忌的优良状态,进而保证多样化的有效探索以最终实现全局优化。简单TS算法的基本思想是:给定一个当前解(初始解)和一种邻域,然后在当前解的邻域中确定若干候选解;若最佳候选解对应的目标值优于“best so far”状态,则忽视其禁忌特性,用其替代当前解和“best so far”状态,并将相应的对象加入禁忌表,同时修改禁忌表中各对象的任期;若不存在上述候选解,则选择在候选解中选择非禁忌的最佳状态为新的当前解,而无视它与当前解的优劣,同时将相应的对象加入禁忌表,并修改禁忌表中各对象的任期;如此反复上述迭代搜索过程,直至满足停止准则。邻域函数、禁忌对象、禁忌表和藐视准则,构成了禁忌搜索算法的关键5。3) Hopfield神经网络优化算法 神经网络优化算法就是利用神经网络中神经元的协同并行计算能力来构造的优化算法,它将实际问题的优化解与神经网络的稳定状态相对应,把实际问题的优化过程映射为神经网络系统的演化过程。Hopfield网络是典型的全连接网络,通过在网络中引入能量函数以构造动力学系统,并使网络的平衡态与能量函数的极小解相对应,从而将求解能量函数极小解的过程转化为网络向平衡态的演化过程6。2 基于蚁群算法的旅行商路径搜索2.1 蚁群算法蚁群算法(Ant Colony Algorithm,简称ACA)是由意大利学者DorigoM等人首先提出来的一种新型的模拟进化算法。其主要特点就是:通过正反馈、分布式协作来寻找最优路径。这是一种基于种群寻优的启发式搜索算法。它充分利用了生物蚁群能通过个体间简单的信息传递,搜索从蚁穴至食物间最短路径的集体寻优特征,以及该过程与旅行商问题求解之间的相似性,得到了具有NP非确定型(Nondeterministic Polynomial)难度的旅行商问题的最优解答。同时,该算法还被用于求解Job - Shop调度问题、二次指派问题以及背包问题等,显示了其适用于组合优化类问题求解的优越特征7.2.3 蚁群系统的基本原理在蚂蚁群找到食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素（pheromone）。当它们碰到一个还没有走过的路口时，就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激素浓度越低。当后来的蚂蚁再次碰到这个路口的时候，选择激素浓度较高路径概率就会相对较大。这样形成了一个正反馈。最优路径上的激素浓度越来越大，而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。在整个寻径过程中，虽然单个蚂蚁的选择能力有限，但是通过激素的作用，整个蚁群之间交换着路径信息，最终找出最优路径8。2.4 基本蚁群算法解决旅行商问题的数学模型在TSP求解中,参与路径搜寻的每只蚂蚁都具有下列特征:1)其选择城市的概率是城市之间的距离和连接支路上所包含的当前信息素余量的函数; 2)为了强制蚂蚁进行合法的周游,直到一次周游完成时,才允许蚂蚁游走已访问的城市;3)当完成一次周游,每只蚂蚁在每条访问过的支路上留下信息素。我们以求解平面上n个城市的TSP问题( 1,2, , n表示城市序号)为例说明ACA的模型。n个城市的TSP问题就是寻找通过n个城市各一次且最后回到出发点的最短路径。为模拟实际蚂蚁的行为, 首先引入如下记号:设bi(t)表示t时刻i城市的蚂蚁数目,m=b1(t)+b2(t)+bi-1(t)+ bn(t),为蚁群中蚂蚁的总数目。令ij(t)为t时刻路径(i,j)上的信息素强度。在初始时刻各条路径上的信息量相等,设ij ( 0) =c。 蚂蚁k(k =1,2,m)在运动过程中,根据各条路径上的信息量决定其转移方向,这里用禁忌表tabuk(k =1,2，,m)来记录蚂蚁k当前所走过的城市。在搜索过程中,蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。pkij(t)表示在t时刻蚂蚁k由城市i转移到城市j的状态转移概率:公式1状态转移概率其中,allowedk =C -tabuk表示蚂蚁k下一步允许选择的城市;为信息启发式因子，表征信息素重要程度的参数;为期望启发式因子,表征启发式因子重要程度的参数(可视度);ij(t)为启发函数。公式2启发函数其中:dij表示相邻两个城市之间的距离。当m只蚂蚁都走完一个完整路径后, 对所有经过的路段进行信息素更新：公式3信息素更新其中:表示了t时刻和t + n时刻之间信息素的挥发程度,ij(t)表示本次循环中路径(i,j)上的信息素的变化量,kij(t)表示第k只蚂蚁在本次循环中留在路径(i,j)上的信息量。2.5 基于Matlab的蚁群算法求解旅行商问题的流程求解旅行商路径(TSP)问题的蚂蚁算法中，每只蚂蚁是一个独立的用于构造路线的过程，若干蚂蚁过程之间通过自适应的信息素值来交换信息，合作求解，并不断优化，这里信息素值分布式地存储在图中，与各弧相关联。(1)首先初始化，设最大迭代次数为NC_max。NC_max=30;m=30;Alpha=0.9;Beta=0.1;Rho=1.5;Q=2;(2)将m个蚂蚁置于n个顶点上。Randpos=;for i=1:(ceil(m/n) Randpos=Randpos,randperm(n);endTabu(:,1)=(Randpos(1,1:m);(3)构造解。每个蚂蚁按照状态变化规则逐步地构造一个解，即生成一条路线。蚂蚁任务是以概率大小选择路径访问所有的城市后回到起点，生成一条回路。%计算待选城市概率分布 for k=1:length(J) P(k)=(Tau(visited(end),J(k)Alpha)*(Eta(visited(end),J(k)Beta); endP=P/(sum(P);%按概率原则选取下一个城市Pcum=cumsum(P);Select=find(Pcum=rand);to_visit=J(Select(1);Tabu(i,j)=to_visit; endendif NC=2 Tabu(1,:)=R_best(NC-1,:);End(4)局部更新信息素值。应用局部信息素更新规则来改变信息素值。使得下次的路径按照新的信息素信息来规划，进一步地逼近最优解。%信息素更新Delta_Tau=zeros(n,n);for i=1:m for j=1:(n-1) Delta_Tau(Tabu(i,j),Tabu(i,j+1)=Delta_Tau(Tabu(i,j),Tabu(i,j+1)+Q/L(i); end Delta_Tau(Tabu(i,n),Tabu(i,1)=Delta_Tau(Tabu(i,n),Tabu(i,1)+Q/L(i);endTau=(1-Rho).*Tau+Delta_Tau;(5)若所有的m个蚂蚁都构造完解，则转(6)；否则转(3)。(6)全局更新信息素值。应用全局信息素更新规则来改变信息素值。当所有m个蚂蚁生成了m个解时，其中有一条最短路径是本代最优解。(7)终止。若终止条件满足，则结束；否则NC=NC+1，转(2)进行下一代进化。3 Matlab仿真结果为说明蚁群算法的优点,本文以n=6的城市模型为例给出该算法求解TSP实验结果,其中Alpha=0.9;Beta=0.1;Rho=1.5;Q=2。图1最佳路径结果图2旅行商问题优化结果图3平均距离和最短距离可见基于蚁群算法的旅行商路径搜索能够准确地找到最优解。图1和图2显示了最优路径是3(4,6)至6(7,4)至5(6,2)至4(5,1)至2(3,0)至1(0,3);其实由于m只蚂蚁在初始状态是分布在n个城市的，所以最优解的结构跟出发点是无关的，只要6个点联合顺序一样的话都能构成shorttest Length为18.7345的最优路径。图3显示了平均距离和最短距离，从图中可以看出，平均距离整体呈现递减的趋势，但是在某几次循环中会出现激变的，这跟蚁群算法基于状态转移概率来求解最优解有关，但是从最短距离曲线上就可以很好地证明了蚁群算法的优点，每次更新完信息素，都能够有效地优化路径，一步一步准确地逼近最优解。4 结束语蚁群算法是一种新型的模拟进化算法,尽管人们对蚁群算法的研究时间不长,在这一领域还有一些问题需要进一步研究和解决,但是理论研究和实际应用表明它是一种很有前途的仿生优化算法。通过对国内外的研究回顾,不难发现蚁群算法的主要优点在于:它是一种自适应、自组织、本质上并行的方法,而且是一种正向反馈的方法,可以促使整个系统向最优解进化,具有较强的鲁棒性,对蚁群算法模型稍加修改,就可以应用于其他问题,同时它可以与多种启发式算法结合,以改善算法的性能.但是该算法也具有收敛速度慢、易陷入局部最优等缺点. 此外,算法中的参数设定目前尚无理论的依据,要靠实验来调整和确定。因此关于蚁群算法理论及其应用的研究必将是一个长期的研究课题。相信随着人们对仿生智能系统理论及应用研究的不断深入,蚁群算法这一新型的仿生优化算法必将展现出更加广阔的发展前景。致谢 感谢徐昱琳教授在本次研究中的帮助，感谢吴勇昊，杨晓，王昆同学在实验中提出的宝贵意见！参考文献：1 李虹，孙志毅. 基于 MATLAB 的改进型基本蚁群算法J.太原重型机械学院学报，2003（9）:201 204.2SeungGwanLee，TaeUngJung, TaechoongChung.Aneffective dynamic