基于TSP的禁忌搜索算法.docx

基于TSP的禁忌搜索算法.docx:..基于TSP的禁忌搜索算法禁忌搜索最先由Glover提出,其主要思想是在搜索过程屮可以接受劣解,使得在搜索过程屮能够跳出局部最优解,进而转向其他区域进行搜索,并通过藐视准则来赦免一些被禁忌的优良状态,从而提髙优化效率,、邻域、禁忌表、禁忌长度、候选解、藐视准则等概念,•它的集中策略体现在局部搜索,即从—•点出发,在这点的领域内寻求更好的解,以达到局部最优解而结束•为了跳出局部最优解,扩散策略通过禁忌表的功能来实现•禁忌表屮记录卜已经到达某些点的信息,算法通过对禁忌表屮点的禁忌,而达到一些没有搜索的点,从而实现更人区域的搜索.—:TSPTSP也称为旅行商问题(travelingsalesmanproblem,TSP)一个商人欲到n个城山•推销商品,每两个城Mi和j之间的距离为也,如何选择一条道路使得商人每个城M走一遍后冋到起点且所走路径最短?TSP还可以细分为対称和非对称距离两大类问题•当妒心,时,称为对称距离TSP,,—种数学模型描述为:min工给列详j乩/工列=1,j=1,2,…昇27=1工®iJ=l,2,•••,///=!工兀了5忖一1,2<|5|</?-2,su{l,2,…/}©w{0,l}, =1,2,J以上是基于图论的数学模型,其屮式列丘{0,1},= 丿屮的决策变量xy.=1表示商人行走的路线包含从城市i到城市j的路径,©=,使得共有Mx(n-l)=l,2,要求商人从城市i恰好出来一•次,式$>“=1j=i /=ij=1,2,…/要求商人恰好走入城市j一次•两式合起来表示每个城市恰好经过一•,因此式工忖一1,2勻$u{l,2,・:/?}约ijes束旅行商在任何一个城市真子集屮不形成冋路,:D={S=(A,L,…人)仏仏,…人是12…必的排列}•如四个城市的TSP实例,当5=(1,2,3,4)时,N(S)={(1,2,3,4),(2,1,3,4),(3,2,1,4),(4,2,3,1),(1,3,2,4),(1,4,3,2),(1,2,4,3)}・-:局部搜索禁忌搜索是一种人工智能的算法,是局部搜索算法的扩展•它的一个重要思想是标记已得到的局部最优解惑求解的过程,并在进一步的迭代中避开这些局部最优解或过程•因为禁忌搜索算法屮川到局部搜索算法,首先介绍局部搜索算法:STEP1选定一个初始可行解:x°;记录当前最优解:xbest:= ,T=NfSTEP2当八{兀曲}=0吋,或满足其他停止运算准则时,输出计算结果,停止运算;否则,从T中选一集合S,得到S中的最好解兀"曲;若f(xnow)<W),则尸:=严",T=N(xbest);否则,T=T\S;,STEP1的初始可行解可用随机的方法选择,也可用一-