计算智能课程设计粒子群优化算法求解旅行商问题Matlab实现.doc

该【计算智能课程设计粒子群优化算法求解旅行商问题Matlab实现 】是由【夜紫儿】上传分享，文档一共【18】页，该文档可以免费在线阅读，需要了解更多关于【计算智能课程设计粒子群优化算法求解旅行商问题Matlab实现 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。计算智能课程设计粒子群优化算法求解旅行商问题Matlab实现摘要:,SP是一个典型的NPC问题。本文首先介绍旅行商问题和粒子群优化算法的基本[,],通过控制学****因子和c1、最大速度,尝试求解旅行商问题。本文以中国31个省会城市为例,通过MATL,,cV2max编程实施对旅行商问题的求解,得到了一定优化程度的路径,是粒子群优化算法在TSP问题中运用的一次大胆尝试。关键字:,,P问题;粒子群优化算法;M,TLA,;中国31个城市,SP。,,即TSP问题(T,a,,,,ngSa,,s,,n,roble,)又译为旅行推销员问题货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,。TSP问题是一个组合优化问题,其描述非常简单,但最优化求解非常困难,若用穷举法搜索,对N个城市需要考虑N!种情况并两两对比,找出最优,其算法复杂性呈指数增长,即所谓“指数爆炸”.所以,寻求和研究TSP问题的有效启发式算法,是问题的关键。(,art,c,,Swarmop,,m,zat,,n,,SO)又翻译为粒子群算法、微粒群算法、或微粒群优化算法。是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法。通常认为它是群集智能(S,,rm,n,elligence,S,)的一种。它可以被纳入多主体优化系统(M,ltiage,tOpt,miza,,,nSystem,MAO,)(粒子群优化算法是由Eb,rhar,博士和,en,edy博士发明.,SO模拟鸟群的捕食行为。一群鸟在随机搜索食物,在这个区域里只有一块食物。。PSO从这种模型中得到启示并用于解决优化问题。PS,中,“粒子"。所有的粒子都有一个由被优化的函数决定的适应值(fi,nessva,ue),每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子(随机解),然后通过迭代找到最优解,在每一次叠代中,粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解,这个解叫做个体极值pBest,另一个极值是整个种群目前找到的最优解,这个极值是全局极值gB,,t。另外也可以不用整个种群而只是用其中一部分最优粒子的邻居,、易于描述却难于处理的组合优化问题,并且是一个,P完全难题,其可能的路径数目与城市数目n是成指数型增长的,对n个城市而言,可能的路径总(n—1)~。随着n的增加,路径数将按数率急剧增长,即所谓的“指数爆炸",所以一般很难精确地求出其最优解,因而寻找出其有效的近似求解算法就具有重要的理论意义。而粒子群优化算法是解决复杂问题的有效方法,,,在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。[,,(Particle)组成的群体(,,ar,)在维搜索空间中以一定的速度飞行,每个粒子在搜索时,考虑到了自己搜索到的的历史最好点和群体内(或领域内)其它粒子的最好点,在此基础上进行位置(状态、也就是解),,,,(,,,)xxxiiiiD12i第个粒子的位置表示为:计算智能课程设计粒子群优化算法求解旅行商问题Matlab实现v,,,,(,,,)vvv1,,dDiiiiD12i第个粒子的速度表示为:,p,,,,(,,,)pppiiiiiD121,,im第个粒子所经历的历史最好点表示为:群体内(或领域内)所有粒子所经历过的最好的点表示为:p,,,,(,,,)pppggggD12。一般来说,粒子的位置和速度都是在连续的实数空间内进行取值,粒子的位置和速度根据如下方程进行变化kkkkkk,1,vvcpxcpx,,,,,,,,()()ididididgdid12kkk,1xxv,,ididid其中,(L,ar,i,gFactor),12速系数(,ccele,at,on,oefficient),一般为正常数。学****因子使粒子具有自我总结和向群体中优秀个体学****的能力,从而向自己的历史最优点以及群体内或领域内的历史最优点靠近。c和c通常等于2。12,,U[0,1][0,1],,是在区间内均匀分布的伪随机数。粒子的速度被限,V制在一个最大的范围内。max当把群体内所有粒子都作为领域成员时,得到粒子群优化算法的全局版本;当群体内部分成员组成领域时得到粒子群优化算法的局部版本。局部版本中,一般有两种方式组成领域,一种是索引号相邻的粒子组成领域,[,,的领域定义策略又可以称为粒子群的领域拓扑结构。,陷入局优的可能性很大。然mm而,群体过大将导致计算时间大幅增加。并且当群体树木增长至一定水平时,再增长将不再有显著的作用。当=1时,,SO算法m变成基于个体搜索的技术,一旦陷入局优,将不可能跳出。当,很大时,PSO的优化能力很好,可是收敛速度将非常慢。,从而向群体内或领域内最优点靠近。和通常都等于,,,:Vmax最大速度决定粒子在一次迭代中最大的移动距离。较大,Vmax探索能力增强,但是粒子容易飞过最好的解。较小时,开发能Vmax力增强,但是容易陷入局优。有分析和实验表明,设定的作用Vmax可以通过惯性权重的调整来实现。所以现在的实验基本上使用Vmax进行初始化,将设定为每维变量的变化范围,而不必进行细致Vmax的选择与调节。,探索能力和开发能力的平衡是非常关键的。对于粒子群优化算法来说,这两种能力的平衡就是靠惯性权重来实现的。较大的惯性权重使粒子在自己原来的方向上具有更大的速度,从而在原方向上飞行更远,具有更好的搜索能力;较小的惯性权重使粒子继承了较少的原方向上的速度,从而飞行较近,具有更好的开发能力。通过调节惯性权重能够调节粒子群的搜索能力。,速度快,不过有时会陷入局优;局部版本粒子群优化算法将索引号相近或者位置相近的个体作为粒子的领域,收敛速度慢一点,,全局版本的粒子群优化算法可以看作局部版本粒子群优化算法的一个特例,即将整个群体都作为领域。。,将大大缩短收敛时间。,而在离散上的研究和应用还很少,尤其是用P,,解决TSP问题是一个新的研,2]究方向。最初的P,O是用来解决连续空间的问题的,为了适合求解,,P,3,问题,人们对算法进行了各种改进。本文采用王岚重新定义PSO的运算符号和规则,引入交换子和交换序的概念,构造一种特殊的P,,用于求解TSP的方法。先对这种改进的PSO进行简略介绍:定义,设n个城市的TSP问题的解序列为S=(,),i=1,,,?,in(定义交换子SO(i。,i)为交换解S中的点a和a,则S’,,,121i2,SO(,。。,,)为解S经算子S,(i,,)操作后的新解,这里1212为符号“+”,其解为S=(1,,,5,2,4),交换算子为,O(1,2),则S'=S+SO(,,,)=(1,3,,,计算智能课程设计粒子群优化算法求解旅行商问题Matlab实现2,4)+S,(,,2)=(3,1,5,2,,).定义2一个或多个交换子的有序队列就是交换序,,S,=(SO,SO,?,SO),,,,SO,?,,O是交换子,它们之,,,,即S'=S+SS=,+(,O,SO,?,SO)=[(S+,O)12n1+SO,+?+S,(,n定义3不同的交换序作用于同一解上可能产生相同的新解,所有有相同效果的交换序的集合称为交换序的等价集。定义4若干个交换序可以合并成一个新的交换序,定义为两个交换序的合并算子。例,设两个交换序S,和S,按先后顺序作用于解S上,得12到新解S’.假设另外有一个交换序SS’作用于同一解上,能够得到相同的解S',可定义,S’=S,,SS。S,’和,S,SS属于同一等价集.,112一般来说,,S'不唯一。定义5在交换序等价集中,拥有最少交换子的序称为该等价集的基本交换序。可按如下方法构造一个基本交换序。设给定两个解路径A和B,需要构造一个基本交换序SS,使得,+SS=:(1,2,,,4,5);,:(,,3,1,5,,)可以看出,A(,)=B(3)=1,所以第一个交换子是SO(1,3),B=B+SO1(1,3),得到B(,,3,2,5,4);,(2)=B(,)=2,所以第二个11计算智能课程设计粒子群优化算法求解旅行商问题Matlab实现交换子是SO(2,3),,=B+SO(2,3),得到B。。=(1,2,3,5,4);同理,212第三个交换子是S,(4,5),得到B=,,,O(4,5)=,。这样就,2得到一个基本交换序:SS,,,B,(,O(1,3),SO(2,3),S,(4,5))。kkkkkk,1基本P,O算法中的速度算式在基于vvcpxcpx,,,,,,,,()()ididididgdid12以上交换子和交换序的概念下各符号有了新的定义。其中、12kk学****因子,,、仍为,0,,]内的随机数;表示基本交换cpx,(),,1ididkkkkkk序以的概率保留,表示基本交换序以的cpx,(),()px,c,c,()px,12gdid2gdidididkkk概率保留。由此可以看出的值越大,保留的交换子就越多,c()px,p1idididk的影响就越大;同理,的值越大,p的影响也就越大。,SO算法步骤描述如下:(1).初始化粒子群,即给群体中每一个粒子赋一个随机的初始解和交换序;(2).如果满足条件,转步骤(5);kk,1(3).根据粒子的当前位置,计算下一个位置,即新解:,,A=,其中A是一个基px()px,ididididkk本交换序表示A作用于得到;xpididkk()px,,=,其中B也是一个基本交换序;gdidkkkkkk,1k,1vvcpxcpx,,,,,,,()(),并将交换ididididgdid12id