粒子群算法求TSP问题Word格式文档下载.docx
《粒子群算法求TSP问题Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《粒子群算法求TSP问题Word格式文档下载.docx（20页珍藏版）》请在冰点文库上搜索。
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<
iostream>
stdlib.h>
time.h>
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:
endl;
hwj_figure（）;
//cout<
--------------------------1生成完全图-------------------"
hwj_initial_population（）;
--------------------------2初始种群---------------------"
while（Key!
=GENE_NUMBER）{
--------------------------3适应度-----------------------"
hwj_fitness（）;
--------------------------4当前最优粒子位子序列-----------------"
hwj_cross（）;
hwj_A（）;
--------------------------5全局最优位置序列-----------------"
hwj_B（）;
--------------------------6速度更新-----------------"
hwj_V（）;
--------------------------7位置更新-----------------"
hwj_X（）;
--------------------------8找到最优解-----------------"
hwj_best（）;
Key++;
}
Theshortestpathlengthis:
Figure_best<
Shortestpathis:
for（inti=0;
i<
G;
i++）{
cout<
hwj[i]<
'
'
;
return0;
}
//--------------------------------生成完全图----------------------------------//
voidhwj_figure（）{
srand（time（NULL））;
inti,j;
for（i=0;
for（j=i+1;
j<
j++）{
Figure[i][j]=rand（）%100+1;
//只需要上三角信息
cout<
Figure[i][j]<
}
//--------------------------------交换两个数的值------------------------------//
voidhwj_swap（int*a,int*b）{
if（*a!
=*b）{//异或操作交换两个数字的位置
*a^=*b;
*b^=*a;
}
//--------------------------------生初始种群----------------------------------//
voidhwj_initial_population（）{
inta[G];
for（j=0;
a[j]=j;
for（i=0;
NUMBER;
for（j=0;
hwj_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;
v[i][j].a<
//cout<
v[i][j].b<
Unit[i][j]<
//输出验证完全不一样的种群且个体没有重复基因
//cout<
//-----------------------计算适应度---------------------------------------------//
voidhwj_fitness（）{
inttemp;
temp=0;
G-1;
if（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]];
//计算每个个体的环路长度
sum[i]=temp+Figure[Unit[i][0]][Unit[i][G]];
sum[i]<
//---------------------找到粒子与其当前所知道的最佳位置的速度序--------------------//
voidhwj_A（）{
inti,j,k;
inttemp=sum[0];
if（temp<
sum[i]）{
temp=sum[i];
key=i;
for（k=0;
k<
k++）{
if（Unit[key][j]==Unit[i][k]）{
A[i][j].a=j;
A[i][j].b=k;
}
Figure_best=temp;
//-----------------------------找到粒子与全局的最佳位置的速度序-------------------------//
voidhwj_B（）{
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};
a=rand（）%1000/1000;
b=rand（）%1000/1000;
if（a<
=M&
&
b<
=N）{
for（i=0;
V_number[i]=0;
for（j=0;
V[i][j].a=v[i][j].a;
V[i][j].b=v[i][j].b;
for（k=0;
if（（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;
if（T[j]==1）{
temp2=1;
for（k=0;
if（（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;
else{
temp2=0;
elseif（a<
b>
N）{
elseif（a>
M&
for（i=0;
V[i][j].a=v[i][j].a;
V_number[i]=G;
//-------------------------------------更新位置---------------------------------//
voidhwj_X（）{
V_number[i];
Unit[i][V[i][j].a],&
Unit[i][V[i][j].b]）;
//-----------------------------------------找到最短路径--------------------//
voidhwj_best（）{
if（Figure_best>
Figure_best=sum[i];
key=i;
hwj[i]=Unit[key][i];
升级会员 