TSP算法

TSP算法（精选九篇）

TSP算法 篇1

随着城市化、工业化进程的加快,工业的不断发展,环境问题日益凸显,其中温室效应、全球气候变暖已经成为世界性的环境问题,产生的各种负面影响已经严重威胁到了人类赖以生存的地球以及人类自身的健康,为了应对该问题,世界各国达成高度一致,一起努力控制碳排放量以减少地球的温室效应。哥本哈根气候变化峰会试图建立一个温室气体排放的全球框架。中国作为能源消耗大国、温室气体排放大国,受到越来越多来自国际社会的压力,中国在哥本哈根会议上已做出了2020年单位GDP碳排放比2005年下降40%~45%的承诺。据调查,交通中的碳排放量占据着很大的比例,因此,如何优化车辆路径这一问题,不仅仅是最短路径、最小成本的问题,同时是一个低碳经济的问题。很多人对车辆路径问题做过研究,如精确算法有Laporte[1]等提出的分支定界法,Christofidest[2]等提出的k度中心树算法,Eilon[3]等提出的动态规划法,Balinski[4]等提出的集分割和列生成,人工智能算法有Clarke和Wright[5]提出的Clarke-Wright算法、Gillett等提出的Sweep算法、Gendreau等提出的禁忌搜索[6]、J.Lawrence提出的遗传算法[7]等等。

本文研究低碳TSP问题,在引入碳排放量这个因素后使问题具有更符合当下的现实意义,当节点比较少时,可以采用动态规划,但一般情况下,物流TSP问题的节点都比较多,这时群体智能算法能很好的解决问题。本文采用改进的蛙跳算法来解决该问题,并取得了很好的结果,证明了算法的有效性和实用性,从而也扩大蛙跳算法的研究领域。

2 低碳TSP问题的描述及建模

2.1 TSP问题[8]

旅行商问题描述如下:给定n个城市及两两城市之间的距离,求一条经过各城市一次且仅一次的最短路线。其图论描述为:给定图G=(V,A),其中V为顶点集,A为各顶点相互连接组成的弧集。已知各顶点间连接距离,要求确定一条长度最短的Hamilton回路。即遍历所有顶点一次且仅一次的最短回路。设dij为城市i与j之间的距离,即弧(i,j)的长度。引入决策变量

则TSP的目标函数为

2.2 低碳TSP问题

由于在货车送货服务过程中,载重随行驶距离不断增加而呈现线性较少,从而每一段路径的碳排放量不同,我们的目标是寻找到一条最优路径,使得总的碳排放量最低,油耗最少。(假设货车在运输过程中以匀速运动且燃烧效率不变)建立模型如下:

模型中,式(1)表示一次运货所求的最小碳排量,其中dij为节点i与j之间的距离,ε(Qij)表示货车从节点i与j之间的与载重相关的碳排放系数,本文采用的是二次函数ε(Qij)= (-2/105)Q2ij+0.0127Qij+0.7725[9]。Qij为节点i与j之间的载重;式(2)、式(3)是为了保证货车能经过所有节点;式(4)是为了限定每个节点只能被服务一次;式(5)是为了保证不出现孤岛解;式(6)保证了货物量不超过货车的最大载重量。

3 本文算法

3.1 蛙跳算法[10,11]

(1)基本混合蛙跳算法

混合蛙跳算法(SFLA)是受湿地里的青蛙的启发而产生的一种仿生物的群体智能算法。首先将整个湿地看作一个系统,将整个青蛙群体分成若干个子群体,每只青蛙通过不同的石头进行跳跃来搜寻食物较多的地方,每个子群体进行着局部搜索,而且每个子群体之间也存在着交流,即模因信息的传递,然后再根据一定的条件重新划分子群体,重复子群体的局部搜索和子群体间的信息交流。这样,每个子群体的局部搜索影响了整个青蛙种群的发展,从而搜索到食物最多的地方。由上可以看出,蛙跳算法其实主要由子群体的局部搜索和子群体之间的信息交换两部分组成。

蛙跳算法基本模型介绍如下:

目标空间假设为D维的,每一只青蛙代表一个初始解,如第i只青蛙代表的解为Xi=(xi1,xi2,…,xiD),共P只青蛙,设置一个适应度函数,根据适应度值将全部青蛙按降序排列,依次划分到M个子群体中(第1只青蛙分到第1子群体,第2只的青蛙分到第2子群体,第M只青蛙分到第M子群体,而第M+1只青蛙则分入第1子群体,第M+2只青蛙分入第2子群体),直到划分完毕。在子群体的每一次局部寻优过程中,都要记录子群体的最差个体Xw、最好个体Xb和全局最好个体Xg.并且只对最差个体Xw进行更新操作。更新策略如下:

蛙跳步长的更新公式:

青蛙个体的位置更新公式

其中,rand()表示随机产生在[0,1]之间的数;Ωi表示每只青蛙的更新步长,i=1,2,…,N;‖Ωmin‖,‖Ωmax‖分别表示所能更新的最大和最小蛙跳步长。当执行完(8)、(9)两步后,如果新产生的newXw的适应度值比原来的Xw更好,那么就用newXw代替原来的Xw.否则,就用全局最优Xg代替子群体最优Xb进行上述更新,只是若这样更新完以后,适应度值仍旧没有改进,那么则会随机产生一个newXw取代原来的Xw,从而完成一次局部搜索。当全部子群体局部搜索结束后,将整个蛙群混合,然后再把这个新的青蛙种群进行排序,分组,各个子群体再次进行局部搜索,重复上述过程,直到迭代次数结束。

(2)本文改进的蛙跳算法[12]

在本文低碳TSP问题中,各个术语代表如下:

青蛙:算法中的一个解,在TSP问题中则是代表一条路径。

青蛙群体:TSP问题中的所有青蛙的路径。

模因分组:青蛙群体分为若干个子群体。

食物源:在算法中代表最优解,在TSP问题中则为最优路径。

适应度:青蛙对环境的适应程度,在算法中表现为青蛙距离目标的远近,在TSP问题中表示一次运货的油耗量。

分组算子:SFLA采用一定的分组规则,基本蛙跳算法是按适应度降序进行排列分组(如上所提)。

本文对于SFLA的改进主要有两点:

其一是在随机分组策略上。蛙跳算法本身是根据适应度值将全部青蛙按降序排列,依次划分到m个子群体中,而本文算法则是在每一次迭代过程中,将每一次混合后的第1至m只青蛙随机划分到m个子群体中,由于每个青蛙只能划分到一个子群体,故第m+1到F只青蛙则仍还是按适应度值依次划分到各个子群体中。这是提升了跳出局部最优解的能力,因为全局最优解所在分组更新得到全局最优解的次数最多,寻优能力强于其他分组,一旦陷于局部最优,则整个种群很难跳出。而随机分组可以保证每个组更新的全局最优次数相当,很好的增强了各个组的寻优能力,同时也保证了个体多样性,加快了迭代速度。

其二是将交叉算子引入全局信息交换阶段,从而改进更新策略。引入交叉算子是为了增加种群多样性,避免在迭代后期陷入局部最优解,从而加快迭代速度。本文改进的更新策略就是用随机截取的最优个体的一段序列来替换最差个体相同位置的序列,从而实现青蛙个体的位置更新,具体更新策略如下:

①截取路径序列:任意截取Xb中的一段路径序列(≥2);

②替换路径序列:用Xb与之相应的路径序列替换Xw中的序列,并放在前面,其余依次排列在后面,比如说Xb为,Xw为2476351,则变换成5724631,这样的交叉能很好的保证种群多样性;

③更新:产生新的可行解Xq,若Xq优于Xw,则更新;否则,用全局最优Xg代替Xb进行第②步操作;

④若新的可行解Xq′优于Xw,则更新替换;否则,随机产生一个新的可行解,更新Xw.

4 算法流程

本文改进的蛙跳算法流程如下:

①参数初始化;

②初始化种群,随机产生F个初始可行解;

③计算青蛙个体的适应度,适应度函数为;

④全部青蛙个体按本文改进的随机分组策略划分到m个族群中,构造子族群;

⑤对每个子群体重复执行以下步骤iter次,确定当前迭代中子群体的最差个体的位置Xw,根据本文的更新策略对其进行更新;

⑥当更新完所有子群体后,只要没达到最大迭代次数,就重新混合全部的青蛙个体,转至第③步开始重新计算,直至满足最大迭代次数iter,则结束进化过程,得到全局最优值;

⑦找出所有划分块中的最优适应度,其路径即为所求;

⑧把最优路径做2-opt,如果更优,则改进,否则保持原最优路径。

5 实例仿真分析

某一大型物流公司负责该地区的货物运输,初始时车辆负载总重为300 吨(包括货物重量),迭代次数为100,种群数目为100,分成10组。该顾客点坐标及需求(其中坐标,需求均随机产生),其中第一个坐标点为仓库,数据如表1。

用java编程在win7下实现本文改进算法(其中迭代次数为100,青蛙规模为100只,分10组,每组10只青蛙)得到低碳TSP问题的最优路径为:0-1-9-4-7-5-6-2-8-3-0,路径长为164km,总的CO2为593kg.

经典TSP得到最优路径为:0-3-8-2-6-5-7-4-9-1-0,路径长为164km.接着,在这个基础上考虑载重对碳排放的影响。计算结果为CO2为636kg.

其中假设货车用的是柴油,柴油的分子式为C13H28,燃烧发生的化学反应为C13H28+20O2→13CO2+14H2O,其中柴油(C13H28)的分子量为184,CO2的分子量为44,计算可得,每kg柴油燃烧产生13×44/184=3.11kg CO2.已知柴油的密度为0.84kg/l,可知每升柴油对应3.11×0.84=2.61kg的CO2,即2.61kg CO2/l柴油。

计算结果比较如下:

从表2可以看出,低碳TSP的最有路径长度和经典TSP一样,只是改变了一下运行线路,碳排放量就可以减少43kg,相当于少耗费了16.5 升柴油,这对经济和环保都有十分重要的意义。

为了保证本文算法的可靠性,又对TSP数据库中的大部分数据进随机载重后进行测试,下表列出了部分数据结果:

其中,()中为经典TSP问题的已知最优解。

从表中数据可以发现,本文算法在求解经典TSP问题是有效的,结果几货都优于已知最优解。尤为重要的是,本文算法求出的两个目标函数距离相差并不大,却可以减少较多碳排放量,其中Eil101运输路程差别不大,但却可以减少4倍的碳排放量,而Busma14在运输路程相同的情况下,还能减少碳排放量。故本文确实提出了一种有效和实用的算法,既有助于解决当下重要的环保问题,又拓宽了算法的应用领域。

6 结论

当前节能减排和低碳环保已成为一个迫在眉睫的问题,本文在研究TSP问题时,考虑了碳排放,建立了一个低碳的TSP模型,与经典的TSP问题相比,虽然运输距离可能有所增加,但减少了油耗,节约了成本,降低了总的碳排放量,符合当前经济发展转型的需要。

摘要：为了响应低碳经济这一环保理念,在研究车辆路径问题时引入碳排放因素,建立了一个最小碳排放的TSP模型,模型重点考虑了载重对碳排放的影响。最后用改进的蛙跳算法求解了一系列TSP的benchmark问题,并将结果与已知最优解相比较,证实了本文算法的有效性和实用性,也拓宽了蜂群算法的应用范围。

TSP算法 篇2

混合免疫算法求解对称TSP的仿真分析

针对对称TSP,将局部搜索方法与免疫算法相结合,构造了混合免疫算法.数值实验结果表明,混合免疫算法求解对称TSP是可行的.;新的算法既具有局部搜索方法较快的收敛速度和较强的局部寻优能力,又具有免疫算法的全局收敛特性.

作 者：张全兴 王海莉 Zhang Quanxing Wang Haili 作者单位：长安大学,理学院,陕西,西安,710064刊 名：宁夏大学学报(自然科学版) ISTIC PKU英文刊名：JOURNAL OF NINGXIA UNIVERSITY(NATURAL SCIENCE EDITION)年，卷(期)：29(3)分类号：O224关键词：免疫算法 混合免疫算法 局部搜索方法 对称TSP

TSP算法 篇3

【关键词】TSP问题；蚁群算法；遗传算法；仿真分析

目前，关于蚁群算法在TSP问题中的应用及改进已经相对成熟，文献[1]通过引入模糊集合的概念提出改进路径更新效果的蚁群算法（FACO），该方法通过模糊评价充分合理利用信息素，能有效提高求得最优解的几率，是一种有效的改进算法。文献[2]通过在最大最小蚁群算法基础上，通过遗传算法特点对蚁群算法参数设置进行优化，有效提高算法求解信息素的速度。文献[3]通过提出相遇策略以及分组并列运行方式改进蚁群算法以及在二维和三维环境进行建模仿真，验证了蚁群改进算法的可靠和有效性。文献[4]通过提出扩大局部搜索空间策略和信息素更新机制提出蚁群自适应优化算法求解TSP问题的方法，提高算法收敛速度和精度。同时探讨了将混沌扰动引入信息素更新的求解过程，可以用更优解取代当前最优值。

1、基本蚁群算法TSP仿真分析及改进

基本蚁群算法求解TSP问题的实质在于引入蚂蚁行走的思想求解最优路径问题，蚂蚁随机挑选路径并产生信息素，信息素越大代表路径长度越短从而反馈引导蚂蚁选择路径最短的路线，蚁群算法有比较好的自组织性，通过整体反馈寻优可以应用于很多实际组合优化问题。

对于蚁群算法的流程，首先应该明确蚁群算法公式及符号定义

在蚁群算法描述之前，引入如下变量记号：m：蚁群中的蚂蚁数量；

β：启发信息影响程度的表达因子，相当于能见度；

ρ：信息素挥发系数，ρ<1；

dij：边（i，j）代表城市距离；

ηij：边（i，j）的启发因子，取ηij=I/dij，这个值固定，一般不随蚂蚁系统而改变；

τij：边（i，j）的信息素值表示；

Pkij（t）：在t时刻蚂蚁k从城市i转移到城市j的概率，i为当前蚂蚁所在的城市，j为蚂蚁尚未访问过的城市；

其中，蚂蚁系统使用随机比例规则进行状态转移，用公式（1-1）表示：

（1-1）

allowedK：在本次循环中蚂蚁k未曾访问的城市集合；

tabuK：蚂蚁k的禁忌表，记录蚂蚁己经访问的城市而禁止再走这些城市。

城市i和城市j之间路径的信息素量，经过n个时刻，信息素调整如公式（1-2）所示：

（1-2）

其中信息素调整原则我们采用蚁周（ant-cycle system）模型，利用的是蚂蚁的全局信息素调整方式，效果最为优越，蚁周模型中：

其中Q：表示蚂蚁释放在所经过路径上（一个过程或一次迭代）的信息素总量，为正常数；

Lk：表示第k只蚂蚁在当前迭代中所经过的路径长度；

△τijk：表示蚂蚁k释放在路径（i，j）上的信息素；△τij：表示所有蚂蚁释放在路径（i，j）上的信息素总和。

本文进行如下蚁群算法TSP仿真实现，选取参数信息素启发因子 a=1，路径启发因子β=2，局部信息素挥发系数ρ1=0.2，全局信息素挥发系数ρ2=0.1，蚂蚁数量为m=100，最大迭代次数NCmax=500实际仿真结果如下：

同时我们输出蚁群个体适应度最优随着迭代次数的变化曲线，在迭代50次以后适应度值达到相对稳定状态，表示路径选择基本稳定在小范围波动，从而达到输出路径的效果[5]。验证了蚁群算法的有效性。

同时可以对基本蚁群算法作出改进，即采用最大最小蚂蚁系统对将信息素在每条路径上的值限定于[τmin，τmax]范围内，如若超出范围则被强制置为上限或下限。这样可以有效控制路径上的信息素差值多大导致的算法过早收敛，同时有利于蚁群的集中搜索[6]。仿真结果如图3：

2、结论

利用蚁群算法对TSP问题的求解，验证了蚁群算法在路径规划问题中的有效性，同时对蚁群算法的参数设置对仿真结果的影响进行探讨，蚁群算法的参数较多，如何设置需要根据对算法具体要求合理配置。综上分析，蚁群算法在求解TSP问题时具有比较强的速度优势，而遗传算法具有比较高的可靠性和独立性，因此我们通过以上仿真分析的结论，可以为进一步的融合算法深入研究打好基础。

参考文献

[1]江迎春.改进的蚁群算法在TSP问题上的应用[D].中南民族大学，2009.

[2]冯月华.基于遗传算法的蚁群算法参数优化研究[J].贵阳学院学报：自然科学版，2014，（1）.

[3]马金财.基于蚁群算法的机器人路径规划问题研究[D].昆明理工大学，2014.

[4]王胜训.蚁群算法的改进及TSP仿真研究[D].西安电子科技大学，2014.

遗传算法求解TSP的研究 篇4

文章提出用遗传算法求解TSP这个古老而有挑战性的NP问题, 利用遗传算法的原理对个城市进行编码, 从一组随机产生的初始解开始搜索, 种群中的每个染色体是问题的一个解的编码串, 这些染色体在后续迭代中不断进化, 运算过程中计算每个个体的适应度来衡量染色体的好坏。遗传和变异过程中, 根据选择规则选择部分后代, 同时淘汰部分后代, 最后算法收敛于最好的染色体, 可能是TSP的最优解。

2 国内外研究现状

目前对遗传算法的研究大部分是从算子出发, 提出各种杂交算子, 但这些算子一般在实际使用中需要花费较大的工作量, 比如已有的OX, PMX, SSX, ERX, CSEX和DPX等。还有其他一种变异算子, 这种变异算子以颠倒作为基石, 它的工作效率比较高, 但也有自身的缺点, 就是具有一定的随机性, 从而实现不了对团体中的个别的消息进行再次构建。所以, 由Michalewicz和郭涛根据以上两类算子的优缺点进行了结合, 得到了一种比较适合的算子, 这种算子叫做Inver-Over, 这种算子能够容易获取, 查找领域宽, 它的基本思路是:旅行商问题的核心参数是城市之间的边, 却不是这些城市的具地理位置。

另外一些研究者为了提高群体的质量, 发明了疫苗, 通常称之为疫苗算法, 而这种是一种基因库的观念, 这种观念是录制好基因的集合, 通过路径抓举、灌输疫苗来实现的。量子遗传算法 (Q GA) 在求解数值和组合优化问题时效率明显优于传统进化算法, 但目前较多被用于求解组合优化的背包问题, 为了充分发挥Q GA的优点, 文中用其求解TSP这一经典的NP难问题。首先, 文中设计了一种利用几率幅值编码的新的编码方式, 即利用几率幅值编码的量子个体与一组向量对应, 而此向量又与一条可行路径一一对应。这样的编码方式不仅缩小了种群规模, 占用较少内存, 所得的解均可行, 而且有效地增强了种群的多样性;其次, 为了继承比较优秀的基因集, 通过对量子进行杂交, 并且是在量子的个体上的操作来实现的;最后, 通过加上两步的查找, 并且是局部查找, 从而降低了算法的收敛时间, 第一阶段主要针对实例中排列稀疏处的城市进行优化, 第二阶段在第一阶段的基础上着重对排列密集处的城市优化。据此, 设计了解TSP的一个新的高效的QGA, 并证明了其以概率1收敛到全局最优解;测定算法性能的数值。

3 算法理论分析

达尔文著名的自然选择学说, 是遗传算法的来源理论, 该算法是一种迭代搜索算法。达尔文的自然选择学说认为:生物的变异一般不是定向的, 而自然选择是定向的, 只有那些能适应环境的变异类型才能生存下来, 产生后代, 而那些与环境不相适应的变异类型将可能被淘汰。在自然环境中, 每种生物都有自己的适应能力, 适应能力的不同揭示了不同生物的繁衍能力。

最原始的遗传算法中, 仅仅包含三种最基本的遗传算子, 也就是选择算子、交叉算子和变异算子, 这种最原始的遗传算法工作的过程是非常简单的, 并且较为人们学习, 它也是其他的后来发展的遗传算法的祖辈。

⑴最原始的遗传算法的组成部分。遗传算法中最基本的就是染色体了, 它是利用二进制编码的0和1组成的符号串来表示的, 也就是说它的等位基因是由零和一构成的。而最初的状态下, 0和1的符号串是可以随机的来生成染色体的。

⑵群体中的个体对环境的适应性的得分。决定是否遗传的概率的大小, 这个值是由个体的自适应性的大小决定的, 可以说, 自适应行越高, 那么遗传的概率也就越高。这里, 要得到这个遗传的概率, 那么初始状态下, 必须让每个个体的适应性的得分为0或者是大于0的数。所以, 我们必须确定自适应性与遗传的概率的之间的正确规则。

⑶遗传算子:这里我们只谈到了三个最基本的遗传算子:使用比例选择算子的是选择算子;使用单点交叉算子的是交叉算子;使用基本位变异算子或均匀位变异算子是变异算子。

⑷每一种算法都有自己的参数, 那么遗传算法的参数包括以下:M:群体中的个体的总数是多少, 也就是说, 群体的多少问题;S:作为遗传算法, 它在进化过程中, 什么时候停止的问题;Pc:这是指交叉的概率;Pm:这是指变异的概率。

4 算法的技术路线

(1) 编写代码, 用代码来回答问题。 (2) 模拟一个原始的群体, 这个群体的规模是固定的。 (3) 这一步需要计算每个个体的适应性程度, 前面已经讲到了, 适应度大, 那么个体就好, 适应度小, 那么个体就差。 (4) 若终止条件T (a:最优个体保持20代不变;b:t>500;c:平均适应度与最优个体适应度之差小于e, e是任意小的正实数;只要满足其中一条就终止) 满足, 则算法终止;否则, 计算概率

并以概率pi从P (t) 中随机选取一些个体构成一个种群RP (t) 。 (5) 为了得到一个新的交叉后的种群, 应该由交叉概率获取。最后再以概率pm, 再进行变异, 从而生成一个新的种群P (t+1) 。 (6) t=t+1, 如不满足终止条件转 (3) 。

5 数据实验及结果

本实验的硬件环境:Intel (R) Core (TM) 2 Duo CPU T5800@2。00GHz 1。99GHz, 2。00GB的内存。本实验的软件环境:Dev-C++编译器对程序进行编译执行。实验对标准的TSPLIB 20个城市进行了计算, 程序输入的初值为20个城市的坐标 (城市数, 城市的横坐标, 城市的纵坐标) 。通过读取文件input。txt中的20个城市的坐标进行计算, 计算结果保存在文件out。txt中。程序运行时需在相同目录下新建文件input。txt和out。txt, 将20个城市的坐标放在input。txt中。程序经过10次运算, 计算结果最优值为:25。800371507, 具体的路径为:8 4 2 176 20 13 5 16 18 7 19 10 15 9 12 3 114 11。

6 结语

该算法对求解大型的TSP性能不优, 后续工作主要是研究优化的遗传算法求解大型的TSP。遗传算法具备自身很多的优点, 尤其是同传统的一些优化方法进行比较的时候, 因为遗传算法具有非常优秀的收敛性, 并且工作的时间上花费较少, 在工作的精准度上也比较优秀。具体的优点在实践中的应用可以看出来, 特别是在文章中的旅行商问题的解决上可以看出来。但就像前述讲过的, 在解决大规模的问题上, 可能遗传算法就会逊色很多了。

实验过程中对于如何确定GA有关参数最佳范围是一个难题, 如迭代次数的选择和运行时间两方面的权衡问题, 以及遗传概率和变异概率的选择等。后续的工作是寻求优化的遗传算法对TSP进行求解。

参考文献

[1]Grover L K.A fast quant um mechanical algorithm for database search//Proceedings of the 28th ACM Sympium Theory Computing.Philadelphia, Pennsylvania, USA, 1996:212-219.

[2]Deut sch D, Jozsa R.Rapid solution of problems by quantum computation//Proceedings of t he Royal Society London A.London, UK, 1992, 439:553-558.

[3]吴斌, 史忠植.一种基于蚁群算法的TSP问题分段求解算法.计算机学报[J].2001, 24 (12) :1329-1333.

[4]杨辉, 康立山, 陈毓屏.一种基于构建基因库求解TSP问题的遗传算法[J].计算机学报, 2003, 26 (12) :1753-1758.

[5]周智, 万颖瑜, 陈国良, 等.基于局部最优解的归约算法:一般方法和在TSP问题上的应用[R].合肥:国家高性能计算中心, 1999.

[6]康立山, 谢云, 尤矢勇, 等.非数值并行算法 (第一册) :模拟退火算法[M].北京:科学出版社, 1997.

[7]赵春英, 张铃.求解货郎担问题 (TSP) 的佳点集遗传算法[J].计算机工程与应用, 2001, 37 (3) :83-84.

[8]朱文兴, 傅清祥.一个基于填充函数变换的对称TSP问题的局部搜索算法[J].计算机学报, 2002, 25 (7) :701-707.

求解TSP的改进QPSO算法 篇5

量子粒子群算法QPSO算法虽然成功地应用于连续优化问题中,但在组合优化问题中的研究和应用还很少。本文通过引入交换子和交换序[1],对基本QPSO[2]算法进行改造,成功地将QPSO应用于求解TSP中。同时引入遗传算法中变异算子的概念,克服传统PSO算法中粒子在落入局部最优解时导致搜索能力下降的缺点。传统PSO算法应用在TSP中时[1,2,3],粒子是在一个有限的范围内搜索,以确保粒子的聚集性,从而使算法收敛于全局最优点或局部最优点。而在QPSO算法中,粒子可以以某一确定的概率出现在整个可行的搜索空间中的任何一个位置,而此位置可能比当前群体中的pBest具有更好的适应度值。实验表明本文算法在解决TSP时与常用的一些PSO算法相比具有更强的搜索能力,收敛速度更快。

1 TSP描述

旅行商问题TSP是运筹学、图论和组合优化中的NP难题,描述如下:给定n个城市及两两城市之间的距离,求一条经过各城市一次且仅一次的最短路线。其图论描述为:给定图G= (V ,A ),其中V 为顶点集,A为各顶点相互连接组成的弧集,已知各顶点间连接距离,要求确定一条长度最短的Hamilton 回路,即遍历所有顶点一次且仅一次的最短回路。设dij为城市i与j之间的距离,即弧(i,j)的长度。引入决策变量:

$x{}_{ij}=\{\begin{array}{l}1\text{若}\text{旅}\text{行}\text{商}\text{访}\text{问}\text{城}\text{市}i\text{后}\text{访}\text{问}j\\ 0\text{否}\text{则}\end{array}$

则TSP 的目标函数为:

$\text{Μ}\text{i}\text{n}\left\{{\rm Z}={\displaystyle \sum _{i,j=1}^{n}x}{}_{ij}d{}_{ij}\right\}(1)$

2 求解TSP的量子粒子群算法

2.1 QPSO算法

量子粒子群优化(QPSO)算法[2]是在经典的微粒群算法的基础上所提出的一种有较高收敛性和稳定性的进化算法。在QPSO算法中,粒子群按照下面的三个公式移动:

$m{}_{best}=\frac{1}{{\rm M}}{\displaystyle \sum _{i=1}^{{\rm M}}{\rm P}}{}_i=(\frac{1}{{\rm M}}{\displaystyle \sum _{i=1}^{{\rm M}}p}{}_{i1},\cdots ‚\frac{1}{{\rm M}}{\displaystyle \sum _{i=1}^{{\rm M}}p}{}_{ij})(2)$

ppij=f×pij+ (1-f)pgjf=rand (3)

xij=ppij±a×(mbest-xij)×ln(1/u) u=rand (4)

这里mbest是粒子群pbest的中间位置,ppij为pij (局部最优)和pgj(全局最优) 之间的随机点。a为QPSO的收缩扩张系数,它是QPSO收敛的一个重要的参数, 第T次迭代时一般可取a=0.5+0.5×(Maxtime-T)/Maxtime(具体a取值视情况而定),其中Maxtime是迭代的最大次数。QPSO算法流程如下:

输入:粒子的维数(参数组个数),粒子个数(参数个数)。

输出:迭代后粒子群的最佳目标函数值,最优的隶属度函数参数组和适应度函数值。

(1) 初始化for T=1:Maxtime;

(2) 根据公式计算粒子的目标函数值;

(3) 更新每个粒子的新局部最优位置pij;

(4) 更新全局最优位置pgj;

(5) 根据公式(1)计算mbest;

(6) 根据公式(2)计算每个粒子随机点ppij;

(7) 根据公式(3)( 以一定的概率取加或减)更新每个粒子的新位置;

(8) End。

重复计算(2) 至(7) 步, 直到满足迭代的次数。

2.2 定义概念交换子和交换序

定义1 设n个节点的TSP的解序列为S=(ai);i=1,…,n。表示该问题的行走路径。 定义交换子SO(i1,i2)为交换子,表示对解序列的一种操作。设S中的点ai1和ai2,则S′= S+SO(i1,i2)为解S经交换算子SO(i1,i2)操作后的新解序列,这里为符号“+”赋予了新的含义。在后面文章中的运算符“+”号均表示该操作。

定义2 一个或多个交换子的有序队列就是交换序, 记作ss。

ss = (so1,so2,…,son),其中so1,so2,…,son是交换子,它们之间的顺序是有意义的。交换序作用在一个TSP解上意味着这个交换序中的所有交换子依次作用于该解上。

定义3 不同的交换序作用在同一解上可能产生相同的新解,所以有相同效果的交换序的集合称为交换序的等价集。

定义4 若干个交换序可以合并成一个新的交换序,定义⊕为两个交换序的合并算子。

定义5 在交换序等价集中, 拥有最少交换子的交换序被称为该等价集的基本交换序。可按如下的方法构造一个基本交换序。设给定两个解路径A和B,需要构造一个基本交换序ss, 使得B+ss=A。

A:(1 2 3 4 5) ; B:(2 3 1 5 4)。

可以看出A(1)=B(3)=1,所以第一个交换子是SO(1,3),B1=B+SO(1,3),得到B1:(1 3 2 5 4),A(2)=B1(3)=1,所以第二个交换子是SO(2,3),B2=B1+SO(2,3),得到B2:(1 2 3 5 4)。

同理,第三个交换子是SO(4,5),B3=B2+SO(4,5)=A。这样,就得到一个基本交换序:

ss=A-B=(SO(1,3),SO(2,3),SO(4,5))。

定义6 小数与交换序列的乘积定义

设有数η∈(0,1)与交换序列Q,且Q 中有n个交换,若有$\frac{m}{n}$≤η<$\frac{m+1}{n}$,其中m为0至n-1间的整数则,η×Q即为Q的前m个交换所构成的解序列。如果η大于或者等于1则保持交换序列Q不变。

2.3 求解TSP 的改进QPSO 算法

利用2.2节中定义的概念重新构造QPSO公式。

定义目标函数f(xij),表示每个粒子代表路径的长度。

mbest:取f(pi)的平均值,选取f(pi)中最接近该平均值的pi赋值给mbest。粒子pi数目为M。

ppij随机选取ppj或pgj的值。ppj为粒子本身找到的最优解pbest,pgj为整个种群目前找到的最优解gbest。

为克服粒子在落入局部最优解时导致搜索能力下降的缺点,同时增强粒子的局部搜索能力,引入了算法中的变异以及其运算规则:

定义7 变异算子与交换序列乘积定义

引入遗传算法中的变异算子概念,定义变异算子G=(x,y),其中x,y是所作用序列Q中随机选取的两个位置。Q×G定义为x,y位置的交换子互换。当x=y时,Q保持不变。

定义8 贪婪倒位变异

对于一个粒子,首先随机选择一个城市C,然后选取除C,Cleft,Cright 外距离C最短距离的点C′。如果C′在C右边,则对Cright到C′之间的城市进行倒置产生新的个体。C′在C左边同理。如个体(1 5 3 6 2 4),若随机选取城市5,离5最近的城市是4,产生新个体为(1 5 4 2 6 3)。

对2.1节中的式(4)改造如下:

xij=ppij +[a×(mbest-xij)]×G; (5)

因为公式(4)中ln(1/u)在解决TSP过程中作用不大,故引入定义7中的变异算子,以一定的概率让粒子跳出有限的搜索范围,抑制算法过早地陷入局部最优解。

获得变异算子G的流程:

(1) 在所作用交换序中随机选取一个位置x;

(2) 选取变异概率:

P=α×$\frac{\text{Μ}\text{a}\text{x}\text{t}\text{i}\text{m}\text{e}-{\rm T}}{\text{Μ}\text{a}\text{x}\text{t}\text{i}\text{m}\text{e}}$α∈(0,1) (6)

(3) 以概率P在交换序中随机选取不同于位置x的位置y,得到变异算子G=(x,y),(1-p)的概率y=x。α值的选取视情况而定,本文实验中选取α=0.2。

计算mbest和xij之间的差A,A = mbest-xij,其中A 是一个基本交换序,表示A作用于mbest得到xij;A 经过a作用后得到一个新的交换序列,该序列经过变异算子G变换后作用于ppij得到新的xij。

该算法的流程如下:

(1) 初始化粒子群,即给群体中的每个粒子赋一个随机的初始解;

(2) 计算出每个粒子的目标函数值f(xij),即每个粒子代表路径的长度;

(3) 计算f(xij)平均值,选取最接近该平均值的f(xij)粒子,赋予mbest;

(4) 计算出随机点ppij,ppij随机选取ppj或pgj的值;

(5) 根据公式(5)更新粒子xij;

(6) 更新每个粒子的新局部最优位置ppj,根据定义8中贪婪倒位变异对ppj进行变异,如果优于原ppj则替换,否则保持不变化;

(7) 更新全局最优位置pgj;

(8) t=t+1返回到(2),直到终止条件;

(9) end。

3 算法的测试与分析

为了验证本文算法在求解TSP时的有效性,针对TSPLIB库[11]中的四组TSPBurma14 、Oliver30、att48和EIL51进行仿真实验,并与文献[9]中的实验结果进行比较。实验环境为PC(Pentium IV 2.4GHz CPU,1G RAM,WinXP,VC++6.0)。粒子群种群数目为100,迭代次数100,每组数据进行100次实验。实验结果如表1所示。

表1中的结果表明本文算法良好地解决了实验中的四组TSP,均求得了TSPLIB中的已知最优解,并且四组实验求得的最优解均优于Chaotic Particle Swarm Optimization[9]的实验结果。

实验中发现,在解决Burma14问题时,本文算法92次寻得已知最优解30.8785,收敛到最优解的平均迭代次数为23,表现出很强的搜索能力。

但算法在TSP规模增大过程中求得最优解的次数在下降,表现出寻求最优解的能力的减弱。在实验中还发现2.3节中参数a和α值的正确选取可以提高算法的寻优能力。

4 结 语

本文针对TSP对QPSO基本算法进行改进,同时引入了遗传算法中的变异的概念。该算法保持了量子粒子群算法计算简便、参数较少的优点,同时使群体粒子具有了多样性。粒子可以以某一确定的概率出现在整个可行的搜索空间中的任何一个位置,克服了容易陷入局部最优的缺陷,使粒子群具有跳出局部最优解的能力。

实验表明本文算法相比文献[9]中的PSO算法在寻优性能上有了很大的提高;同时也能很好的解决较大规模的TSP。但是在TSP规模和复杂度提高后算法性能会下降,这有待以后进一步研究。

摘要：旅行商问题(TSP)是运筹学、图论和组合优化中的NP难题。量子粒子群算法(QPSO)参数个数少、随机性强,并且能覆盖所有解空间,保证算法的全局收敛。针对TSP的特点,通过建立交换子、交换序的运算法则,对基本QPSO算法进行了改造,同时引入了遗传算法中的变异,提出一种求解TSP的改进QPSO算法。实验结果表明了该算法在解决TSP时的有效性,同时算法在稳定性、收敛性以及寻优能力上较其他的一些PSO算法有了很大的提高。

关键词：旅行商问题,量子粒子群优化算法,遗传变异算子,交换子,交换序

参考文献

[1]Clerc M.Discrete Particle Swarm Optimization Illustrated by the Trave-ling Salesman Problem,http://www.mauriceclerc.net,2000.

[2]Sun J,Feng B,Xu WB.Particle SwarmOptimization with particles Hav-ing Quantum Behavior[C]//Proceedings of 2004 Congress onEvolution-ary Computation.2004:325-331.

[3]Kang-Ping Wang,Lanhuang,Chun-Guang Zhou,et al.Particle Swarn Opti-mizatiln for TravelingSalesan Problem[C]//Proceedings of the Second In-ternational Conference on Machine Learningand Cyberntics,Xi an,2003,41(11):477-480.

[4] Parsopulos K E,Vrahat M N.Recent approaches to global optimization problems through particle swarm optimization[J].Vature Computing.Kluwer Academic Publishers,2002(1):235-306.

[5]Lovbjer M,Rasmussen T K,Krink T.Hybrid Particle Swarm optimiza-tion With Breeding and Subpopulations[C]//Proc Of the third Geneticand Evolutionary Computation Conference Tulv.2001.

[6]Van den Bergh F,Engelbrecht A P.Effect Of Swarm Size on Coopera-tive Particle Swarm Optimization[G].Pine of the GEOOC,San Fran-cisco.USA,2001.

[7] Bergh F V D.An Analysis of Particle Swarm Optimizers[D].Pretoria:University of Pretoria,2001.

[8]Kennedy J,Eberhart R C.Particle swarm optimization[C]//Proceed-ings of the IEEE International Conference on Neural Networks,Perth,Australia,IEEE Services Center,Piscataway,NJ,1995,4:1942-1948.

[9]Yuan Zhenglei,Yang Liliang,Wu Yaohua,et al.Chaotic Particle SwarmOptimization Algorithm for Traveling Salesman Problem[C]//Proceed-ings of the IEEE International Conference on Automation and Logistics,August,2007:18-21.

[10] Shi X H,et al.Particle swarm optimization-based algorithms for TSP and generalized TSP.Information Processing Letters (2007),doi:10.1016/j.ipl.2007.03.010.

TSP问题的算法与应用的研究 篇6

旅行商问题TSP(Traveling Salesman Problem)就是为人们所广泛研究的典型组合优化问题[1],问题要求求得一条遍历所有城市的最短路径,是一个易于描述却难以处理的NP-HARD问题。由于TSP问题在交通运输、计算机网络、电路板设计以及物流配送等领域内有着广泛的应用,国内外学者对其进行了大量的研究。目前,常用的算法主要有遗传算法和蚁群算法,另外还有模拟退火算法、禁忌搜索算法、贪婪算法和神经网络方法等诸多算法。

对于求解N个城市的TSP问题存在( N-1)! 条闭合路径的排列方案,对于这类问题很难用全局搜索法精确地求出其最优解,因此研究相应的有效算法,寻找其最优或近似最优解是非常必要的。本文通过对遗传算法和蚁群算法的研究、实现和比较,以及TSPLIB经典数据的验证,给出了能较好地平衡算法执行次数和运算结果最优化的蚁群算法的实现方法。

1 TSP问题的算法研究

1.1 TSP问题

旅行商问题可以描述为:一名商人欲到n个城市推销商品,每两个城市i和j之间的距离为dij (i,j=1,2,…,n),如何选择一条路径,使得商人从一个城市出发,经过所有城市一次且仅一次后回到出发点,所行走的总行程最短。

1.2 遗传算法研究

遗传算法的思想来自达尔文的进化论和Mendel的遗传学说,该算法是一种模拟生物在自然环境中遗传和进化过程而形成的自适应全局化概率搜索算法。该算法由密执安大学教授Holland及其学生于1975年创建。研究发现,生物进化是一个不断循环的过程,在这一过程中,生物群体不断完善和发展。所以生物进化过程本质上是一种优化过程,这种认识启发着遗传算法的研究者将其应用到优化计算领域,创立新的优化计算方法,并将这些方法应用到复杂的工程计算领域之中。

遗传算法的基本原理是:遗传算法从一组随机产生的初始解(称为群体)开始搜索过程。群体中的每个个体是问题的一个解,称为染色体。这些染色体在后续迭代中不断进化,称为遗传。遗传算法主要通过选择、交叉、变异运算实现。交叉和变异运算产生下一代染色体,称为后代。染色体的好坏用适应度来衡量。根据适应度的大小从上一代和后代中选择一定数量的个体,作为下一代群体,再继续进化。这样经过若干代后,算法收敛于最好的染色体。它很可能就是问题的最优解或次优解。遗传算法中使用适应度的概念来衡量群体中的各个个体在优化计算中有可能到达最优解的优良程度。度量个体适应度的函数称为适应度函数,适应度函数的定义与具体求解问题有关。

从图1中的优化框架中可以看出,遗传算法的运行过程是一个非常典型的迭代过程,其基本流程包括:

(1) 选择编码策略,把参数集合s转换为位串的结构空间x;

(2) 定义适应度函数f(x);

(3) 确定遗传策略,包括选择群体大小,选择、交叉、变异方法,以及确定交叉概率、变异概率等遗传参数[2];

(4) 随机初始化生成群体;

(5) 计算群体中个体位串解码后的适应度函数值;

(6) 按照遗传策略,运用选择、交叉和变异等遗传算子作用于群体,形成下一代群体;

(7) 判断群体性能是否符合终止条件,或者已达到预定迭代次数,若满足设定的条件,则结束运行;若不满足则返回步骤(6),或者修改遗传策略再返回步骤(6)。

1.3 蚁群算法研究

基本蚁群算法在TSP问题中的实现过程如下:假设将m只蚂蚁放到n个随机选择的城市中,每只蚂蚁根据一定的概率选择下一个它还没有访问过的城市。蚂蚁选择下一个目标城市的主要依据有以下两点:①τij(t)为t时刻连接城市i和j的路径上的信息素浓度。初始时刻,各条路径上的信息量相等;②ηij为由城市i转移到j的可见度,亦称启发信息,该启发信息是由所要解决的问题给出和一定的算法实现的。在TSP问题中,一般取ηij=1/dij,dij表示城市i、j之间的距离。t时刻位于城市i的蚂蚁k选择城市j为目标城市的概率为:

${\rm P}{}_{ij}^k(t)=\{\begin{array}{l}[\tau {}_{ij}(t)]{}^{\alpha }\cdot [\eta {}_{ij}]{}^{\beta }/{\displaystyle \sum _{j\in \text{a}\text{l}\text{l}\text{o}\text{w}\text{e}\text{d}}[}\tau {}_{ij}(t)]{}^{\alpha }\cdot [\eta {}_{ij}]{}^{\beta }j\in \text{a}\text{l}\text{l}\text{o}\text{w}\text{e}\text{d}\\ 0j\notin \text{a}\text{l}\text{l}\text{o}\text{w}\text{e}\text{d}\end{array}(1)$

其中,allowed是待访问城市的集合。蚂蚁k选中某个城市的可能性是问题本身所提供的启发信息与蚂蚁目前所在城市到目标城市路径上残留的信息素的函数。

为了避免对同一个城市的重复访问,每一只蚂蚁都保存一个列表Tabu(k),用于记录到目前为止蚂蚁已经访问过的城市集合。Tabu(k)随着蚂蚁寻优过程作动态调整。为了避免残留信息素过多引起残留信息淹没启发信息,在每一只蚂蚁走完一步或完成对所有n个城市的访问后(即一次循环结束),对残留信息进行更新处理。

这样,得到(t+n)时刻在ij路径上的信息素浓度为:

τij(t+n)=ρτij(t)+Δτij(t+n) (2)

其中,ρ表示信息素的保留率,则1-ρ表示信息素的挥发率。为了防止信息素的无限积累,ρ的取值范围限定在0～1;Δτij表示蚂蚁k在时间段t到(t+n)的过程中,在i到j的路径上的残留信息浓度。本算法采用ant-cycle模型更新信息素。

根据信息素更新策略的不同,有三种不同的蚁群算法模型。ant-quantity模型、ant-density模型和ant-cycle模型。本算法采用ant-cycle模型更新信息素。

ant-cycle模型:

$\Delta \tau {}_{ij}^k(t,t+1)=\{\begin{array}{l}Q{}_3/L{}^k\text{如}\text{果}\text{蚂}\text{蚁}k\text{在}\text{巡}\text{回}\text{中}\text{经}\text{过}ij\\ 0\text{如}\text{果}\text{蚂}\text{蚁}k\text{在}\text{巡}\text{回}\text{中}\text{不}\text{经}\text{过}ij\end{array}(3)$

其中,Q3是常量,Lk表示第k只蚂蚁的循环路线,即如果蚂蚁经过ij,则信息素增量为一个常量除以蚂蚁k的巡回路线长。这里,信息素增量只与蚂蚁的巡回路线和Q3有关系,而和具体的dij无关。

前两种模型利用的是局部信息,蚂蚁在完成一步(从一个城市到达另外一个城市)后更新所有路径上的信息素,而最后一种模型利用的是整体信息,蚂蚁在一个循环(对所有n个城市的访问)以后,更新所有路径上的信息素。因此,在求解TSP问题时,ant-cycle模型性能比前面两种模型好。

1.4 算法实验结果比较

遗传算法和蚁群算法实验结果比较如表1所示:

实验中,遗传算法实现选取k(选择系数)为25,蚁群算法实现选取Alpha(信息素重要程度参数)为1,选取Beta(启发信息重要程度参数)为4,选取Gamma(信息素蒸发参数)为0.7,分别运行了20次。

从表1中可以发现,蚁群算法在最优解、收敛速度和运算结果稳定性上均优于遗传算法,其通过对信息素强度的控制,使得可行解范围扩大,又保证了一定的正反馈作用,在加速算法收敛与防止算法过早停滞之间取得了较好的平衡。

蚁群算法实验结果与TSPLIB的比较:

由表2可以看出,本文的蚁群算法实现最优解与TSPLIB中给出的最优解已经很接近了,在st70和ch150中,两者的差值分别仅占TSPLIB最优解的2.96%和1.93%;算法的稳定性进一步得到认证,优差解差值分别仅占算法最优解的3.02%和2.64%;获得极值的运行次数分别只有10次和59次,在算法执行次数上和运算结果最优化之间有良好的平衡。

从实验结果可以得出结论,该蚁群算法实现符合本文预期的设计要求,将作为一个数据执行模块运用到ERP物流配送路径系统中。

2 TSP算法应用的研究与实现

2.1 实际问题的TSP模型化

前面给出了一个较优的解决TSP问题的蚁群算法的实现。TSP问题一直是学术界和工程界共同关注的问题,许多实际问题经过转化都可以变为求解相应的TSP问题。 比如连锁店货物配送、航班着陆排序[3]、计算机网络、电路板钻孔路线等许多实际问题经过简单的转化,都可以转化为对TSP问题的求解问题。

2.2 设计目标

为了使广大的用户使用到该算法、分享该算法,本文设计了基于网络浏览器运行的应用实现策略。该实现策略为Brower/Server三层架构,客户端以浏览器的形式供用户操作和使用。其优良性能如下:

(1) 浏览器是每个计算机操作系统必备的应用软件之一,因此不要求每个用户均在自己的计算机上安装Matlab软件,减少了客户端安装的不便;

(2) 利用Web开发技术设计友好的用户界面,使广大用户方便地操作;

(3) 待运算的点阵数据以Excel文件的形式提交,运算结果连同该数据文件一同存储在数据库中,去除了用户输入数据时的繁琐,也方便了对点阵数据的管理;

(4) 通过研究相关技术,使TSP应用服务器能与Matlab引擎进行良好通信。TSP应用服务器作为提供数据和获取结果的一方,Matlab引擎作为数据运算和结果提供的一方,充分利用Matlab在科学计算方面的优势,弥补其在网络应用方面的不足;

(5) 只要保持Matlab中算法的接口不变,对算法的修改不会影响系统的运行,大大方便了服务器端的维护和升级工作;

(6) 由于网络的存在使其应用范围得到了很大的扩展,每一个用户只要在该系统注册成功,均可以使用该系统。

2.3 实现框架

本文实现基于Brower/Server的Web页面、TSP应用服务器、应用项目数据库三层结构。TSP应用的实现框架如图2所示。

用户管理模块对系统用户进行管理,每个用户仅能对自己建立的项目进行操作,而他人的项目是没有权限访问的。另外需要对用户进行登录和退出处理,确保每个用户在同一时间内,只能在一个浏览器上登录系统。

用户登录或注册成功,将显示当前该用户已经执行的项目列表。1)如果用户需要运行新的项目,则进入数据获取模块,在这里,系统将得到用户输入的路径点阵和算法参数等数据,并进入数据执行模块,将数据传输到Matlab引擎并得到运行结果,进而通过数据存取模块存储到应用项目数据库中;2)如果用户需要对当前的多余项目列表进行删除操作,可通过数据删除模块操作应用项目数据库,将相关的项目信息删除。

3 ERP物流配送路径决策支持

ERP,即企业资源规划,能够对企业整个资源进行整合,并为达到一定的目标作企业资源的最优化配置。物流资源管理是ERP的重要组成部分。

在该系统中,用户只需将待运行的Excel数据文件上传,就可快捷地得到期望的运行结果,为企业物流配送路线提供科学合理的建议;用户不需要再次上传数据,就可以对某一物流配送路线原始数据通过修改运行参数等方式执行多次;用户也可以对运行过的陈旧结果进行删除;为了数据安全考虑,系统不允许某一用户查看和操作不属于该用户的数据,也不允许某一用户同时在异地登录。

本系统服务器端运行在Windows 2003 Server上,数据库使用SQLServer 2000,Java版本使用SUN J2SE5.0,Web服务器使用Apache Tomcat5.0,数据执行使用数值计算软件Matlab7.1,客户端可以是MS IE5.0或更高版本。

4 结束语

本文通过对遗传算法和蚁群算法原理的分析,针对两种算法涉及的关键因素进行了细致的研究。通过对遗传算法和蚁群算法实验结果的比较和蚁群算法实验结果与TSPLIB经典数据的比较,给出了在算法执行次数和运算结果最优化之间有良好平衡的蚁群算法的实现方法。在算法应用的实现方式方面,采用了性能优良的网络浏览器运行的实现方式。作为TSP应用实例,给出了ERP系统中的物流配送路径的优化问题,运用本文研究的算法和实现的技术,实现了该系统的原型。文中给出的蚁群算法对求解一般意义上的TSP问题,能够在较短的运算次数内给出优良的解,但当群体规模很大时,要找到一条较好的路径仍需要比较多的运算次数,这一点还有待进一步的改进。

摘要：TSP问题是一个典型的组合优化问题。针对TSP问题的两种主要算法:遗传算法和蚁群算法,进行了分析和研究。并且提出了网络浏览器运行的实现方法,给出了系统实现的B/S三层架构。最后,运用本算法和实现的技术,作为应用实例实现了ERP物流配送路径决策支持系统的原型。

关键词：TSP,遗传算法,蚁群算法,TSPLIB

参考文献

[1]Garey M R,Johnson D S.A guide to the Theory of NP-Completeness[J].Computers and Intractability,1979,3(5):23-26.

[2]蔡之华,彭锦国,高伟,等.一种改进的求解TSP问题的演化算法[J].计算机学报,2005,28(5):823-828.

[3]Vranas P,Bertsimas D,Odomi A R.The multi-airport ground-holdingproblem in air traffic control[J].Operation Research,1994,42(2):249-261.

[4]陈文兰,戴树贵.旅行商问题算法研究综述[J].滁州学院学报,2006,8(3):1-6.

[5]Dantzig G B.Solution of a Large Scale Traveling Salesman Problem[J].Operation Research,1954,2(9):77-82.

用并行回溯搜索算法求解TSP问题 篇7

旅行商问题 (Traveling Salesman Problem, 简称TSP) 是一个典型的NP完全难题。给定n个城市和两两城市之间的距离, 要求确定一条经过各城市当且仅当一次的最短路线。其图论描述为:给定图G= (V, E) , 其中V为顶点集, E为各顶点相互连接组成的边集, 设D= (dij) 是由顶点i和顶点j之间的距离所组成的距离矩阵, 要求确定一条长度最短的Hamilton回路, 即遍历所有顶点当且仅当一次的最短距离。

旅行商问题可分为如下两类:

1) 对称旅行商问题 (dij=dji, i, j=1, 2, 3, …, n)

2) 非对称旅行商问题 (dij≠dji, i, j=1, 2, 3, …, n)

这里我们主要探讨对称旅行商问题的求解。

2 并行回溯搜索算法设计

2.1 深度优先搜索策略和剪枝函数。

在回溯搜索算法中, 为了遍历n个点所形成的全部回路, 采用了深度优先搜索策略, 即从这n个点中任选一个点作为根节点, 其余节点作为它的孩子节点, 按此方式生成n个点的一棵完整的搜索树。例如, 要找出abcd四个点所能形成的全部回路, 则使用深度优先搜索策略可以生成图1所示的搜索树。

在深度优先搜索的过程中, 为了加快搜索速度, 可以使用剪枝函数来避免不必要的搜索。具体算法是:当搜索到达一个节点时, 首先判断到此节点时的路径长度是否大于前面已经搜索出的最短回路值。是则不必再往此节点的下层进行搜索, 而直接回溯到上一级中, 这样的剪枝函数可以加快搜索速度, 实现起来也较为容易。另外, 若搜索到达叶节点, 则先闭合回路, 计算出此回路的长度值再和前面已经搜索出的最短回路值比较, 取较小者作为新的最短回路值即可。

2.2 域分解方法。

假设有n个处理器并行求解P (P>>n) 个点的TSP问题, 则可将这P个点生成的搜索树划分成n份分配给n个处理器。划分的方法是对这棵搜索树的第2层节点按如下方式分割:设n个处理器的编号从0至n-1, P个点的编号从0至P-1, 令d=[ (P-1) /n], r= (p-1) %n, 则在第i号处理器所分配子树的第2层上, 最左节点编号为Si=i×d+min (i, r) +1, 最右节点编号为Ei= (i+1) ×d+min (i+1, r) 。这样, 每个处理器都从搜索树上划分出一棵子树进行局部搜索。例如, 图1的搜索树若由2个处理器来分割, 分割方法如图2所示;若由3个处理器来分割, 分割方法如图3所示。

2.3 主从通信模式 (Master-Slave Communication) 。

在进行并行计算时, 多个处理器需要相互协作才能完成整个计算过程。这里采用了主从通信模式, 即从n个处理器中, 选定1个作为主处理器, 其余n-1个作为从处理器。n个处理器之间的通信协作过程如下:1) 主处理器首先将整棵搜索树按2.2节的方法划分成n棵搜索子树并发送给各个从处理器, 同时主处理器也给自己分配了一棵搜索子树。2) 然后主、从处理器并行进行回溯搜索, 直到得到自己所分搜索子树中的最短回路。3) 接着各从处理器将得到的局部最短回路送回主处理器。4) 主处理器对全部结果进行汇总, 从中选出最优解。

2.4 并行回溯搜索算法描述。

定义:

1) 城市总数目P (P≥3) , 每个城市编号从0至P-1。

2) 并行处理器总个数N (N≥1) 。每个处理器编号从0至N-1。

3) 距离矩阵D, Di, j表示城市i与城市j之间的距离 (P-1≥i≥0, P-1≥j≥0) 。

4) 全部城市的一个排列T, T[i]表示T中第i (P-1≥i≥0) 个位置上的城市编号, T (i) 表示T中从T[0]到T[i]走过的路径总长度, 即 , 并补充规定T (0) =0。

5) 一个排列T对应的回路长度CT=T (P-1) +DT[0], T[P-1]。

主算法——并行化:

前提:设0号处理器为主处理器, 其余处理器为从处理器。

输入:P, N, D, 当前处理器编号Id。

输出:最短回路Tbest。

1) 令T为一个初始排列, T[i]=i, (i=0, 1, …P-1) 。又令T1=T。

2) 若Id≠0, 则转到9) 。

4) 计算每个处理器所分割子树根节点的最左孩子位置:Si=i×d+min (i, r) +1, (i=0, 1…N-1) 和最右孩子位置:Ei= (i+1) ×d+min (i+1, r) , (i=0, 1…N-1)

5) 将Si和Ei发送给从处理器i:Send (Si, Ei) , i=1, 2, ..N-1。

6) 主处理器进行局部回溯搜索:Search (T, T1, 0, S0, E0) , 得到一个局部最短回路Tbest。

7) 主处理器接收每个从处理器发回的局部最短回路Ti, (i=1, 2, …N-1) , 若CTi

8) 主处理器输出最优解Tbest, 算法结束。

9) 从处理器Id接收SId和EId:Recv (SId, EId) 。

10) 从处理器Id进行局部回溯搜索:Search (T, T1, 0, SId, EId) , 得到一个局部最短回路TId。

11) 从处理器Id发送TId给主处理器:Send (TId)

12) 从处理器Id结束运行。

子算法——局部回溯搜索递归算法:Searc (T, T1, Pos, Start, End)

输入参数:T为正在进行搜索的一个排列, T1为已搜索到的一个最短回路, Pos为正在搜索的子树根节点在T中的位置, Start为正在搜索的子树根的最左孩子位置, End为正在搜索的子树根的最右孩子位置。输出:局部最短回路T1。

1) 若T (Pos) ≥CT1, 则直接返回上一层。

2) 若Pos≠P-1, 则转到5) 。

3) 若CT

4) 返回上一层。

5) 若Pos+1≠1, 则令Start=Pos+1, End=P-1。

6) 对于i=Start, Start+1, …End:

a.交换T[i]和T[Pos+1]。

b.递归向下搜索:Search (T, T1, Pos+1, Start, End) 。

c.交换T[i]和T[Pos+1]。

7) 返回上一层。

3 实验结果分析

本文利用MPICH1.25软件包构建了并行计算环境, 用C++语言实现了2.4节的并行算法。对15个城市的TSP问题进行实验, 得到图4所示的最优解。并且, 从图5可以看到, 增加并行计算时所用处理器的数量, 能够有效减少计算所耗费的时间, 故本算法具有一定的性能优势。但是, 随着问题规模的增加, 本算法的计算复杂度会呈指数级增长。因此, 本并行算法较适合解决小规模的TSP问题。

参考文献

[1]陈国良, 吴俊敏.并行计算机体系结构[M].北京:高等教育出版社, 2002.

[2]都志辉.MPI并行程序设计[M].北京:清华大学出版社, 2002.

[3]田贵超.旅行商问题的几种求解方法[J].计算机仿真, 2006, 8:153-156.

基于遗传算法的动态TSP问题求解 篇8

关键词：动态TSP,遗传算法,2-OPT,弹性松弛算法

TSP (Traveling Salesman Problem, TSP) 问题是组合优化问题中最典型的问题之一, 并且是一个NP-Hard问题, 吸引了包括数学、运筹学、物理、生物和人工智能等不同领域的研究者。很多实际问题可以转化为动态TSP问题, 动态TSP问题已广泛应用于通信、路由选择、机器人控制、车辆选路、移动计算等领域。解决动态TSP问题有很重要的理论和实际意义。

1 动态TSP问题

TSP (Traveling Salesman Problem) 的简单描述是:给出一条遍历所有城市一次且仅一次的最短路径。数学语言描述为:设有N个城市C={C1, C2, C3…..Cn}, 其中任意两个城市的距离记为d (Ci, Cj) , 求一条经过C中所有城市一次的一条路径 (Cn (1) , Cn (2) , Cn (3) , …..Cn (N) ) , 使得闭合路径为最小。

2 求解动态TSP问题算法设计

一个求解动态TSP问题的好的算法不但要求有高质量的解, 而且要求较高的效率和快速的响应。本文在遗传算法的变异阶段后引入2-OPT算法。由于在解的输出前引入2-OPT算法, 这样将2-OPT算法与遗传算法结合起来, 前者可提高算法的响应速度, 后者可提高算法的解的质量, 因此与传统的遗传算法相比可选择出更优的个体。在选出最优的个体后, 本文结合弹性松弛算法的思想找出最佳D-TSP路径, 从而更好地解决了动态TSP问题。

2.1 编码方案

对于城市数为n的TSP问题, 采用一个具有n个元素的数组来表示一条染色体, 数组中元素对应于实际路径中的城市标号, 也就是说这n个城市的任何一种排列都可以表示为一条染色体, 如 (C1, C2, …Cn) 。在这里, 一条染色体表示了旅行商一次旅行所走的实际路线。

2.2 适应值函数的定义

本文解决TSP问题算法的适应度采用路径长度的倒数表示, 适应度越大, 则路径越短, 个体越优。本文计算适应度的评价函数定义为:

2.3 遗传算法的算子设计

(1) 选择算子。

采用比例选择方法, 根据个体的适应度, 采用概率选择即轮盘赌策略, 并保留当前最优解, 使适应较大的个体能以较大的概率生存下来。

例如:有五个个体1, 2, 3, 4, 5, 它们的选择概率分别为0.1, 0.15, 0.2, 0.25, 0.3。

假设随机数序列为:0.33, 0.64, 0.78, 0.83, 0.56, 则被选中个体序列为:3, 4, 5, 5, 4。

(2) 交叉算子。

本文使用部分映射的双点交叉。基本算法如下:

根据选择概率选择出两个染色体A, B。产生随机数i、j, 且i、j<染色体最大长度, i

假设A:1, 2, 3, 4, 5, 6, 7, 8, 9。

假设B:9, 8, 7, 6, 5, 4, 3, 2, 1。

再假设i=3, j=6。设置临时数组temp A、temp B, 把A、B中i、j之间的染色体放到临时数组的前面, 余下的按照部分映射分别由另一个染色体补充。得到交叉后的染色体为:

temp A:3, 4, 5, 6, 9, 8, 7, 2, 1。

temp B:7, 6, 5, 4, 1, 2, 3, 8, 9。

最后, 将两个临时数组中的数据写回到A、B中, 交叉操作完毕。

(3) 变异算子。

为了实现变异运算, 本文使用的变异算子如下, 即在个体编码串中随机选择两个城市, 是第一个城市的右城市与第二个城市之间的编码倒序排列, 从而产生一个新个体。

若染色体A为:1, 2, 3, 4, 5, 6, 7, 8, 9。

随机选择两个城市, 若选中的为3, 7。那么变异后, 染色体A变为:1, 2, 3, 7, 6, 5, 4, 8, 9。

3 结语

本文的创新之处在于将2-OPT算法、弹性松弛算法和遗传算法相结合解决动态TSP问题, 通过仿真实验证明了与传统的求解动态TSP问题的遗传算法相比, 不仅提高了解的质量, 并且克服解的退化现象, 有很快的响应速度和很高的效率。

本文只是给出了一种实现动态TSP问题的方法, 其它一些策略也可以提高动态TSP问题的搜索速度。比如, 把搜索空间分割成子空间;运用更快的启发式搜索算子等等。在这些策略上进行实验也是一个研究方向。

参考文献

[1]王小平, 曹立明.遗传算法理论、应用与软件实现[M].西安:西安交通大学出版社, 2002

[2]玄光男, 程润伟.汪定伟, 译.遗传算法与工程设计[M].北京:科学出版社, 2000

[3]康立山, 刘钊, 蒋良孝.-OPT算法和遗传算法相结合解决动态TSP问题.中国地质大学 (武汉) 信息工程学院

TSP算法 篇9

关键词：遗传算法,单纯形,旅行商问题

旅行商问题 (TSP问题) 可描述为:一个商人欲从自己所在城市出发, 到若干城市推销商品, 最后回到自己所在的城市, 要求经过每个城市一次且仅一次, 求一条最短的周游路径。

由于TSP问题的可行解数目与城市数目n是成指数型增长的, 因而一般只能近似求解, 遗传算法 (GA) 是求解该问题较为有效的方法之一, 目前应用遗传算法解决TSP问题, 限于遗传算法自身的缺点, 本文讨论遗传算法和单纯形法的函数优化混合算法。

1 遗传算法和单纯形算法的描述

遗传算法是一种概率搜索算法, 它是利用某种编码技术作用于称为染色体的二进制数串, 其基本思想是模拟由这些串组成的进化过程[1～3]。遗传算法通过有组织但随机地信息交换来重新结合那些适应性好的串, 在每一代中, 利用上一代串结构中适应性好的位和段来生成一个新的串的群体;偶尔要在串结构中尝试用新的位和段来代替原来的部分。遗传算法是一类随机算法, 但它不是简单的随机走动, 它可以有效利用已有的信息来搜寻那些有希望改善质量的串。与自然界相似, 遗传算法对求解问题的本身一无所知, 它需要的仅是对算法所产生的每个染色体进行评价, 并基于适应值来选择染色体, 使适应性好的染色体比适应性差的染色体有更多繁殖机会。

遗传算法利用简单的编码技术和繁殖机制来表现复杂的现象, 从而解决非常困难的问题。特别是由于它不受搜索空间的限制性假设的约束, 不要求诸如连续性、导数存在和单峰等假设。算法的基本步骤如下:

1.1 在一定编码方案下, 随机产生一个初始种群;

1.2 用相应的解码方法, 将编码后的个体转换成问题空间的决策变量, 并求得个体的适应值;

1.3 按照个体适应值的大小, 从选出适应值较大的一些个体进入交配池;

1.4 由交叉和变异这两个遗传算子对交配池中的个体进行操作, 并形成新一代的种群;

1.5 反复执行步骤1.2～1.4, 直至满足收敛判据为止。

单纯形算法是一种稳健的算法, 不需要求导数, 因而相对其它算法随参数的增加收敛速度慢。算法是由Nelder-Mead于1965年提出的, 它可求解有多个变量的函数的局部极小值, 该方法也称为“amoeba”方法[4]。单纯形算法的优点是不用求函数的一次导数矩阵, 不用进行复杂的矩阵运算;可以代替最小二乘法用于数据处理中, 对于大型和复杂方程式 (如指数曲线) 的回归, 其优点是遗传算法所不能比拟的。但是单纯形算法也有很多缺点, 如单纯形算法的迭代次数太多, 收敛速度缓慢, 在迭代过程中, 有时会出现单纯形最大边长较长, 而单纯形体积却己接近于零这一病态现象而导致的退化现象和搜索失败等, 这些缺点严重影响了单纯形算法的使用。

单纯形算法的基本思想:在n维空间中取n+1个点构成初始单纯形, 比较n+1各点处目标函数值得大小, 丢弃最坏的点 (函数最值点, 如最大值) , 代之以新的点, 构成新的单纯形, 反复迭代, 使其顶点处的函数值逐步下降, 顶点逐步逼近目标函数最小值。

针对上述遗传算法和单纯形法的不足, 综合两种方法的优势, 解决TSP问题, 现在说明算法结合的基本思想[5]。

对于多极点函数f (x) , 如f (x) =cos (5x) -2sin (3x) , x∈[-2, 6]。如图1所示,

存在A、B、C、D四个极小值点, 其中B为最小值点。

混合算法的步骤是先用遗传算法搜索到某一个点E点, 转用单纯形法快速搜索到极小值点C, 然后转用遗传算法。一旦用遗传算法搜索到比点C的函数值稍低的点, 立即用单纯形法寻找附近的谷底。如此交替进行, 直至找到最小值点B。

2 实验过程及结果

在计算机上用MATLAB程序进行仿真, 随机产生20个城市, 它们位置分布如表1所示。选择参数为:种群数目为20, 交叉概率为0.8, 变异概率为0.01, 选择三角形单纯形进行仿真。图2给出了采用算法所取得经过路径距离, 可以看出, 混合算法比遗传算法大大加快了收敛速度, 从而证明了算法的有效性。路径结果如图3所示。

参考文献

[1]贾金锁, 高梅国.遗传算法在海杂波产生中的应用[J].北京理工大学学报, 2004, 24 (5) :446-449.

[2]彭新竹.遗传算法的改进策略及其应用[J].华东船舶工业学院学报, 2002 (16) :53-58.

[3]S.C.Ng, S.H.Leung, C.Y.Chung.The Genetic Search Approach:A New Learning Al-gorithm for Adaptive IIR Filtering.IEEE Sig-nal Processing Magazine.1996, 13 (6) :38-46

[4]H.John, Mathews.Numerical Methods Using Matlab.电子工业出版社, 2003:301-302