粒子群算法求TSP问题.docx
《粒子群算法求TSP问题.docx》由会员分享，可在线阅读，更多相关《粒子群算法求TSP问题.docx（20页珍藏版）》请在冰点文库上搜索。
粒子群算法求TSP问题
智能优化算法第三次作业
一分析
1）1、基本思想
粒子群算法简称PSO，它的基本思想是模拟鸟群的捕食行为。
设想这样一个场景：
一群鸟在随机搜索食物。
在这个区域里只有一块食物。
所有的鸟都不知道食物在那里。
但是他们知道当前的位置离食物还有多远。
那么找到食物的最优策略是什么呢。
最简单有效的就是搜寻目前离食物最近的鸟的周围区域。
PSO从这种模型中得到启示并用于解决优化问题。
PSO中，每个优化问题的解都是搜索空间中的一只鸟。
我们称之为“粒子”。
所有的粒子都有一个由被优化的函数决定的适应值（fitnessvalue），每个粒子还有一个速度决定他们飞翔的方向和距离。
然后粒子们就追随当前的最优粒子在解空间中搜索。
PSO初始化为一群随机粒子（随机解）。
然后通过迭代找到最优解。
在每一次迭代中，粒子通过跟踪两个"极值"来更新自己。
第一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest。
另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。
另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。
粒子公式
在找到这两个最优值时，粒子根据如下的公式来更新自己的速度和新的位置：
v[i]=w*v[i]+c1*rand（）*（pbest[i]-present[i]）+c2*rand（）*（gbest-present[i]）
present[i]=present[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）按照公式v=v^A^B更新速度和位置。
（d）如果得到了更好的个体位置，更新。
（iv）如果得到了更好的群体位置，更新。
1）生成初始种群：
2）适应度计算
3）当前最优粒子位子序列
4）全局最优位置序列
5）更新速度
6）更新位置
7）找到最优路径
二、结果：
源码：
/*问题：
用粒子群算法求解TSP问题：
为保证有解用完全图做样例*/
/*洪文杰2016-3-25.智能优化算法第三次作业*/
#include
#include
#include
usingnamespacestd;
//--------------------------------宏定义----------------------------------//
#defineNUMBER50//种群规模
#defineGENE_NUMBER1000//迭代次数
#defineG20//图的顶点个数
#defineM0.45//局部最优解选择概率
#defineN0.65//全局最优解选择概率
//-------------------------------全局变量定义-----------------------------//
intFigure[G][G];//保存图信息
intUnit[NUMBER][G];//保存初始种群
staticstruct{
inta;
intb;
}v[NUMBER][G],A[NUMBER][G],B[NUMBER][G],V[NUMBER][3*G];//保存种群初始速度,序列A,序列B,更新后的速度。
//intPbest[NUMBER][G];//保存每个粒子当前知道的最佳位置
//intGbest[G];//保存所有粒子知道的最佳位置
intsum[NUMBER];//保存个体环路长度
intFigure_best=100000;//最短路径长度
intkey=0;//最短路径的个体编号
intV_number[NUMBER];//更新速度的序列个数
inthwj[G];//保存最短路径
//--------------------------------函数声明--------------------------------//
voidhwj_figure（）;//生成完全图
voidhwj_initial_population（）;//生成初始种群及粒子速度
voidhwj_swap（int*a,int*b）;//交换两个数的值
voidhwj_fitness（）;//计算适应度
voidhwj_A（）;//找到粒子与其当前所知道的最佳位置的速度序列
voidhwj_B（）;//找到粒子与种群最佳位置的速度序列
voidhwj_V（）;//速度更新
voidhwj_X（）;//位置更新
voidhwj_best（）;//找到最短路径
//--------------------------------主函数----------------------------------//
intmain（）{
intKey=0;
cout<<"thisisthefigure:
"<hwj_figure（）;
//cout<<"--------------------------1生成完全图-------------------"<hwj_initial_population（）;
//cout<<"--------------------------2初始种群---------------------"<while（Key!
=GENE_NUMBER）{
hwj_initial_population（）;
//cout<<"--------------------------3适应度-----------------------"<hwj_fitness（）;
//cout<<"--------------------------4当前最优粒子位子序列-----------------"<hwj_A（）;
//cout<<"--------------------------5全局最优位置序列-----------------"<hwj_B（）;
//cout<<"--------------------------6速度更新-----------------"<hwj_V（）;
//cout<<"--------------------------7位置更新-----------------"<hwj_X（）;
//cout<<"--------------------------8找到最优解-----------------"<hwj_best（）;
Key++;
}
cout<<"Theshortestpathlengthis:
"<cout<<"Shortestpathis:
"<for（inti=0;icout<}
cout<return0;
}
//--------------------------------生成完全图----------------------------------//
voidhwj_figure（）{
srand（time（NULL））;
inti,j;
for（i=0;ifor（j=i+1;jFigure[i][j]=rand（）%100+1;//只需要上三角信息
cout<}
cout<}
}
//--------------------------------交换两个数的值------------------------------//
voidhwj_swap（int*a,int*b）{
if（*a!
=*b）{//异或操作交换两个数字的位置
*a^=*b;
*b^=*a;
*a^=*b;
}
}
//--------------------------------生初始种群----------------------------------//
voidhwj_initial_population（）{
srand（time（NULL））;
inta[G];
inti,j;
for（j=0;ja[j]=j;
}
for（i=0;ifor（j=0;jhwj_swap（&a[j],&a[j+rand（）%（G-j）]）;
Unit[i][j]=a[j];
v[i][j].a=rand（）%G;
v[i][j].b=rand（）%G;
//cout<//cout<//cout<}
//cout<}
}
//-----------------------计算适应度---------------------------------------------//
voidhwj_fitness（）{
inti,j;
inttemp;
for（i=0;itemp=0;
for（j=0;jif（Unit[i][j]>Unit[i][j+1]）{
temp+=Figure[Unit[i][j+1]][Unit[i][j]];
}
else{
temp+=Figure[Unit[i][j]][Unit[i][j+1]];
}
}
if（Unit[i][0]>Unit[i][G]）{
sum[i]=temp+Figure[Unit[i][G]][Unit[i][0]];//计算每个个体的环路长度
}
else{
sum[i]=temp+Figure[Unit[i][0]][Unit[i][G]];
}
//cout<}
}
//---------------------找到粒子与其当前所知道的最佳位置的速度序--------------------//
voidhwj_A（）{
inti,j,k;
inttemp=sum[0];
for（i=0;iif（temptemp=sum[i];
key=i;
}
for（j=0;jfor（k=0;kif（Unit[key][j]==Unit[i][k]）{
A[i][j].a=j;
A[i][j].b=k;
}
}
}
}
Figure_best=temp;
}
//-----------------------------找到粒子与全局的最佳位置的速度序-------------------------//
voidhwj_B（）{
inti,j,k;
for（i=0;ifor（j=0;jfor（k=0;kif（Unit[key][j]==Unit[i][k]）{
B[i][j].a=j;
B[i][j].b=k;
}
}
}
}
}
//-----------------------------------------速度更新---------------------------------//
voidhwj_V（）{
floata,b;
inti,j,k,t;
inttemp1=0;
inttemp2=0;
intT[G]={0};
srand（time（NULL））;
a=rand（）%1000/1000;
b=rand（）%1000/1000;
if（a<=M&&b<=N）{
for（i=0;iV_number[i]=0;
for（j=0;jV[i][j].a=v[i][j].a;
V[i][j].b=v[i][j].b;
for（k=0;kif（（v[i][k].a==A[i][j].a）&&（v[i][k].b==A[i][j].b））{
temp1=1;
}
if（（B[i][k].a==A[i][j].a）&&（B[i][k].b==A[i][j].b））{
T[k]=1;
}
}
if（temp1==0）{
V[i][V_number[i]+G].a=A[i][j].a;
V[i][V_number[i]+G].b=A[i][j].b;
V_number[i]++;
}
else{
temp1=0;
}
}
}
for（i=0;ifor（j=0;jif（T[j]==1）{
temp2=1;
}
else{
for（k=0;kif（（v[i][k].a==B[i][j].a）&&（v[i][k].b==B[i][j].b））{
temp2=1;
}
}
}
if（temp2==0）{
V[i][V_number[i]+G].a=B[i][j].a;
V[i][V_number[i]+G].b=B[i][j].b;
V_number[i]++;
}
else{
temp2=0;
}
}
}
}
elseif（a<=M&&b>N）{
for（i=0;iV_number[i]=0;
for（j=0;jV[i][j].a=v[i][j].a;
V[i][j].b=v[i][j].b;
for（k=0;kif（（v[i][k].a==A[i][j].a）&&（v[i][k].b==A[i][j].b））{
temp1=1;
}
}
if（temp1==0）{
V[i][V_number[i]+G].a=A[i][j].a;
V[i][V_number[i]+G].b=A[i][j].b;
V_number[i]++;
}
else{
temp1=0;
}
}
}
}
elseif（a>M&&b<=N）{
for（i=0;iV_number[i]=0;
for（j=0;jV[i][j].a=v[i][j].a;
V[i][j].b=v[i][j].b;
for（k=0;kif（（v[i][k].a==B[i][j].a）&&（v[i][k].b==B[i][j].b））{
temp1=1;
}
}
if（temp1==0）{
V[i][V_number[i]+G].a=B[i][j].a;
V[i][V_number[i]+G].b=B[i][j].b;
V_number[i]++;
}
else{
temp1=0;
}
}
}
}
else{
for（i=0;ifor（j=0;jV[i][j].a=v[i][j].a;
V[i][j].b=v[i][j].b;
}
V_number[i]=G;
}
}
}
//-------------------------------------更新位置---------------------------------//
voidhwj_X（）{
inti,j;
for（i=0;ifor（j=0;jhwj_swap（&Unit[i][V[i][j].a],&Unit[i][V[i][j].b]）;
}
}
}
//-----------------------------------------找到最短路径--------------------//
voidhwj_best（）{
inttemp;
inti,j;
for（i=0;itemp=0;
for（j=0;jif（Unit[i][j]>Unit[i][j+1]）{
temp+=Figure[Unit[i][j+1]][Unit[i][j]];
}
else{
temp+=Figure[Unit[i][j]][Unit[i][j+1]];
}
}
if（Unit[i][0]>Unit[i][G]）{
sum[i]=temp+Figure[Unit[i][G]][Unit[i][0]];//计算每个个体的环路长度
}
else{
sum[i]=temp+Figure[Unit[i][0]][Unit[i][G]];
}
if（Figure_best>sum[i]）{
Figure_best=sum[i];
key=i;
}
}
for（i=0;ihwj[i]=Unit[key][i];
}
}
升级会员 