粒子群算法求TSP问题Word格式文档下载.docx

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

2、本交换序； （c） 按照公式v=vAB更新速度和位置。 （d） 如果得到了更好的个体位置，更新。 （iv） 如果得到了更好的群体位置，更新。1） 生成初始种群： 2） 适应度计算3） 当前最优粒子位子序列4） 全局最优位置序列5） 更新速度6） 更新位置7） 找到最优路径二、结果：源码：/*问题：用粒子群算法求解TSP问题：为保证有解 用完全图做样例*/*洪文杰 2016-3-25. 智能优化算法 第三次作业*/#includestdlib.htime.husing namespace std;/-宏定义-/#define NUMBER 50 /种群规模#define GENE_NUMBER

3、1000 /迭代次数#define G 20 /图的顶点个数 #define M 0.45 /局部最优解选择概率#define N 0.65 /全局最优解选择概率/-全局变量定义-/int FigureGG; /保存图信息int UnitNUMBERG; /保存初始种群static struct int a; int b;vNUMBERG,ANUMBERG,BNUMBERG,VNUMBER3*G; /保存种群初始速度,序列A,序列B,更新后的速度。/int PbestNUMBERG; /保存每个粒子当前知道的最佳位置/int GbestG; /保存所有粒子知道的最佳位置int sumNUMBE

4、R; /保存个体环路长度int Figure_best=100000; /最短路径长度int key=0; /最短路径的个体编号int V_numberNUMBER; /更新速度的序列个数int hwjG; /保存最短路径/-函数声明-/void hwj_figure（）; /生成完全图void hwj_initial_population（）; /生成初始种群及粒子速度void hwj_swap（int *a,int *b）; /交换两个数的值void hwj_fitness（）; /计算适应度void hwj_A（）; /找到粒子与其当前所知道的最佳位置的速度序列void hwj_B（）;

5、 /找到粒子与种群最佳位置的速度序列void hwj_V（）; /速度更新void hwj_X（）; /位置更新void hwj_best（）; /找到最短路径 /-主函数-/int main（） int Key=0; coutthis is the figure: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、6速度更新- hwj_V（）;-7位置更新- hwj_X（）;-8找到最优解- hwj_best（）; Key+; The shortest path length is:Figure_best Shortest path is : for（int i=0;iG;i+） couthwji ; return 0;/-生成完全图-/void hwj_figure（） srand（time（NULL）; int i,j; for（ i=0; for（j=i+1;jj+） Figureij=rand（）%100+1; /只需要上三角信息 coutFigureij /-交换两个数的值-/void hwj

7、_swap（int *a,int *b） if（*a != *b） / 异或操作交换两个数字的位置 *a = *b; *b = *a; /-生初始种群-/void hwj_initial_population（） int aG; for（j=0; aj=j; for（i=0;NUMBER; for（j=0; hwj_swap（&aj, &aj+rand（）%（G-j）; Unitij=aj; vij.a=rand（）%G; vij.b=rand（）%G;vij.a/ coutvij.b Unitij /输出验证完全不一样的种群且个体没有重复基因/ coutUnitij+1） temp+=Fig

8、ureUnitij+1Unitij; else temp+=FigureUnitijUnitij+1; if（Uniti0UnitiG） sumi=temp+FigureUnitiGUniti0; /计算每个个体的环路长度 sumi=temp+FigureUniti0UnitiG;sumi/-找到粒子与其当前所知道的最佳位置的速度序-/void hwj_A（） int i,j,k; int temp=sum0; if（tempsumi） temp=sumi; key=i; for（k=0;kk+） if（Unitkeyj=Unitik） Aij.a=j; Aij.b=k; Figure_bes

9、t=temp;/-找到粒子与全局的最佳位置的速度序-/void hwj_B（） Bij.a=j; Bij.b=k;/-速度更新-/void hwj_V（） float a,b; int i,j,k,t; int temp1=0; int temp2=0; int TG=0; a=rand（）%1000/1000; b=rand（）%1000/1000; if（a=M&b=N） for（i=0; V_numberi=0; for（j=0; Vij.a=vij.a; Vij.b=vij.b; for（k=0; if（vik.a=Aij.a）&（vik.b=Aij.b） temp1=1; if（Bi

10、k.a=Aij.a）&（Bik.b=Aij.b） Tk=1; if（temp1=0） ViV_numberi+G.a=Aij.a; ViV_numberi+G.b=Aij.b; V_numberi+; else temp1=0; if（Tj=1） temp2=1; for（k=0; if（vik.a=Bij.a）&（vik.b=Bij.b） temp2=1; if（temp2=0） ViV_numberi+G.a=Bij.a; ViV_numberi+G.b=Bij.b; else temp2=0; else if（aN） else if（aM& for（i=0; Vij.a=vij.a; V_numberi=G;/-更新位置-/void hwj_X（）V_numberi;UnitiVij.a,&UnitiVij.b）;/-找到最短路径-/void hwj_best（） if（Figure_best Figure_best=sumi; key=i; hwji=Unitkeyi;