粒子群算法求TSP问题.docx

《粒子群算法求TSP问题.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、智能优化算法第三次作业一分析1）1、基本思想粒子群算法简称PSO，它的基本思想是模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitnessvalue)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜

2、索。PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个"极值"来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest。另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。粒子公式在找到这两个最优值时，粒子根据如下的公式来更新自己的速度和新的位置：v[i]=w*v[i]+c1*rand()*(pbest[i]-present[i])+c2*rand()*(gbest-present[i])  present[i]=pr

3、esent[i]+v[i] 其中v[i]代表第i个粒子的速度，w代表惯性权值,c1和c2表示学习参数，rand()表示在0-1之间的随机数,pbest[i]代表第i个粒子搜索到的最优值,gbest代表整个集群搜索到的最优值,present[i]代表第i个粒子的当前位置算法步骤：(i)初始化粒子群，给每一个粒子一个初始解idx和随机的交换序idv。(ii)判断是否达到最大迭代次数1000。若是，算法结束，输出结果；若不是，转到(iii)。(iii)根据粒子当前位置计算下一个新解：(a)计算A，A是一个基本交换序，表示A作用于idx得到idp；(b)计算B=-，B是一个基本交换序；(c)按

4、照公式v=v^A^B更新速度和位置。(d)如果得到了更好的个体位置，更新。(iv)如果得到了更好的群体位置，更新。1）生成初始种群：1）适应度计算2）当前最优粒子位子序列1）全局最优位置序列2）更新速度1）更新位置2）找到最优路径二、结果：源码：/*问题：用粒子群算法求解TSP问题：为保证有解用完全图做样例*//*洪文杰2016-3-25.智能优化算法第三次作业*/#include#include#includeusingnamespacestd;//--------------------------------宏定义-----

5、-----------------------------//#defineNUMBER50//种群规模#defineGENE_NUMBER1000//迭代次数#defineG20//图的顶点个数#defineM0.45//局部最优解选择概率#defineN0.65//全局最优解选择概率//-------------------------------全局变量定义-----------------------------//intFigure[G][G];//保存图信息intUnit[NUMBER][G];//保存初始种群staticstruct{inta;intb;}v[NUMBER

6、][G],A[NUMBER][G],B[NUMBER][G],V[NUMBER][3*G];//保存种群初始速度,序列A,序列B,更新后的速度。//intPbest[NUMBER][G];//保存每个粒子当前知道的最佳位置//intGbest[G];//保存所有粒子知道的最佳位置intsum[NUMBER];//保存个体环路长度intFigure_best=;//最短路径长度intkey=0;//最短路径的个体编号intV_number[NUMBER];//更新速度的序列个数inthwj[G];//保存最短路径//--------------------------------函数声明

7、--------------------------------//voidhwj_figure();//生成完全图voidhwj_initial_population();//生成初始种群及粒子速度voidhwj_swap(int*a,int*b);//交换两个数的值voidhwj_fitness();//计算适应度voidhwj_A();//找到粒子与其当前所知道的最佳位置的速度序列voidhwj_B();//找到粒子与种群最佳位置的速度序