粒子群算法求TSP问题

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

2、迭代找到最优解。在每一次迭代中,粒子通过跟踪两个极值来更新自己。第一个就是粒子本身所找到的最优解,这个解叫做个体极值pBest。另一个极值是整个种群目前找到的最优解,这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居,那么在所有邻居中的极值就是局部极值。粒子公式在找到这两个最优值时,粒子根据如下的公式来更新自己的速度和新的位置：vi = w * vi + c1 * rand * + c2 * rand * presenti = presenti + vi其中vi代表第i个粒子的速度,w代表惯性权值,c1和c2表示学习参数,rand表示在0-1之间的随机数,pb

3、esti代表第i个粒子搜索到的最优值,gbest代表整个集群搜索到的最优值,presenti代表第i个粒子的当前位置算法步骤： 初始化粒子群,给每一个粒子一个初始解idx和随机的交换序idv。 判断是否达到最大迭代次数1000。若是,算法结束,输出结果；若不是,转到。 根据粒子当前位置计算下一个新解： 计算A,A是一个基本交换序,表示A作用于idx得到idp； 计算B=,B是一个基本交换序； 按照公式v=vAB更新速度和位置。 如果得到了更好的个体位置,更新。 如果得到了更好的群体位置,更新。生成初始种群：适应度计算当前最优粒子位子序列全局最优位置序列更新速度更新位置找到最优路径二、结果：源码

4、：/*问题：用粒子群算法求解TSP问题：为保证有解 用完全图做样例*/*洪文杰 2016-3-25. 智能优化算法 第三次作业*/#include#include#includeusing namespace std;/-宏定义-/#define NUMBER 50 /种群规模#define GENE_NUMBER 1000 /迭代次数#define G 20 /图的顶点个数#define M 0.45 /局部最优解选择概率#define N 0.65 /全局最优解选择概率/-全局变量定义-/int FigureGG; /保存图信息int UnitNUMBERG; /保存初始种群static

5、structint a;int b;vNUMBERG,ANUMBERG,BNUMBERG,VNUMBER3*G; /保存种群初始速度,序列A,序列B,更新后的速度。/int PbestNUMBERG; /保存每个粒子当前知道的最佳位置/int GbestG; /保存所有粒子知道的最佳位置int sumNUMBER; /保存个体环路长度int Figure_best=100000; /最短路径长度int key=0; /最短路径的个体编号int V_numberNUMBER; /更新速度的序列个数int hwjG; /保存最短路径/-函数声明-/void hwj_figure; /生成完全图vo

6、id hwj_initial_population; /生成初始种群及粒子速度void hwj_swap; /交换两个数的值void hwj_fitness; /计算适应度void hwj_A; /找到粒子与其当前所知道的最佳位置的速度序列void hwj_B; /找到粒子与种群最佳位置的速度序列void hwj_V; /速度更新void hwj_X; /位置更新void hwj_best; /找到最短路径 /-主函数-/int mainint Key=0;coutthis is the figure:endl;hwj_figure;/cout-1生成完全图-endl; hwj_initial

7、_population;/cout-2初始种群-endl;while hwj_initial_population;/cout-3适应度-endl; hwj_fitness;/cout-4当前最优粒子位子序列-endl;hwj_cross; hwj_A;/cout-5全局最优位置序列-endl;hwj_B;/cout-6速度更新-endl; hwj_V;/ cout-7位置更新-endl; hwj_X;/ cout-8找到最优解-endl; hwj_best; Key+; cout The shortest path length is:Figure_bestendl; cout Shorte

8、st path is :endl; forint i=0;i couthwji ; coutendl;return 0;/-生成完全图-/void hwj_figuresrandtime;int i,j;for i=0;iforj=i+1;jFigureij=rand%100+1; /只需要上三角信息coutFigureij ;coutendl;/-交换两个数的值-/void hwj_swapif / 异或操作交换两个数字的位置 *a = *b; *b = *a; *a = *b; /-生初始种群-/void hwj_initial_populationsrandtime;int aG;int

9、 i,j;forj=0;jaj=j;fori=0;iforj=0;jhwj_swap&aj, &aj+rand%; Unitij=aj; vij.a=rand%G; vij.b=rand%G;/ coutvij.a ;/coutvij.b ;/coutUnitij ; /输出验证完全不一样的种群且个体没有重复基因/coutendl;/-计算适应度-/void hwj_fitnessint i,j;int temp;fori=0;itemp=0;forj=0;jifUnitij+1temp+=FigureUnitij+1Unitij;elsetemp+=FigureUnitijUnitij+1;

10、 ifUnitiGsumi=temp+FigureUnitiGUniti0; /计算每个个体的环路长度elsesumi=temp+FigureUniti0UnitiG; /coutsumiendl;/-找到粒子与其当前所知道的最佳位置的速度序-/void hwj_Aint i,j,k;int temp=sum0;fori=0;iiftemptemp=sumi;key=i;forj=0;jfork=0;kifAij.a=j;Aij.b=k;Figure_best=temp;/-找到粒子与全局的最佳位置的速度序-/void hwj_Bint i,j,k;fori=0;iforj=0;jfork=0

11、;kifBij.a=j;Bij.b=k;/-速度更新-/void hwj_Vfloat a,b;int i,j,k,t;int temp1=0;int temp2=0;int TG=0;srandtime;a=rand%1000/1000;b=rand%1000/1000;ifa=M&bfori=0;iV_numberi=0;forj=0;jVij.a=vij.a;Vij.b=vij.b;fork=0;kif&temp1=1;if&Tk=1;ifViV_numberi+G.a=Aij.a;ViV_numberi+G.b=Aij.b;V_numberi+;elsetemp1=0;fori=0;i

12、forj=0;jiftemp2=1;elsefork=0;k if&temp2=1; ifViV_numberi+G.a=Bij.a;ViV_numberi+G.b=Bij.b;V_numberi+; elsetemp2=0;else ifaNfori=0;iV_numberi=0;forj=0;jVij.a=vij.a;Vij.b=vij.b;fork=0;kif&temp1=1;ifViV_numberi+G.a=Aij.a;ViV_numberi+G.b=Aij.b;V_numberi+;elsetemp1=0;else ifM&bfori=0;iV_numberi=0;forj=0;jVij.a=vij.a;Vij.b=vij.b;fork=0;kif&temp1=1;ifViV_numberi+G.a=Bij.a;ViV_numberi+G.b=Bij.b;V_numberi+;elsetemp1=0;elsefori=0;iforj=0;j Vij.a=vij.a;Vij.b=vij.b;V_numberi=G;/-更新位置-/void hwj_Xint i,j;fori=0;iforj=0;jhwj_swap;/-找到最短路径-/void hwj_bestint temp;int i,j;fori=0;itemp=0;forj=0;ji