《粒子群算法求tsp问题》由会员分享，可在线阅读，更多相关《粒子群算法求tsp问题（16页珍藏版）》请在金锄头文库上搜索。
1、智能优化算法第三次作业智能优化算法第三次作业一分析一分析1）1、基本思想粒子群算法简称 PSO，它的基本思想是模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO 从这种模型中得到启示并用于解决优化问题。PSO 中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追
2、随当前的最优粒子在解空间中搜索。PSO 初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值“来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值 pBest。另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。粒子公式在找到这两个最优值时，粒子根据如下的公式来更新自己的速度和新的位置：vivi = = w w * * vivi + + c1c1 * * rand()rand() * * (pbesti(pbesti - - pres
3、enti)presenti) + + c2c2 * * rand()rand() * * (gbest(gbest - - presenti)presenti) presentipresenti = = presentipresenti + + vivi 其中 vivi代表第 i i 个粒子的速度，w w 代表惯性权值,c1c1 和 c2c2 表示学习参数，rand()rand()表示在 0-10-1 之间的随机数,pbestipbesti代表第 i i 个粒子搜索到的最优值,gbestgbest 代表整个集群搜索到的最优值,presentipresenti代表第 i i 个粒子的当前位置算法
4、步骤：(i) 初始化粒子群，给每一个粒子一个初始解 idx 和随机的交换序 idv。 (ii) 判断是否达到最大迭代次数 1000。若是，算法结束，输出结果；若不是，转到(iii)。 (iii) 根据粒子当前位置计算下一个新解： (a) 计算 A，A 是一个基本交换序，表示 A 作用于 idx 得到 idp； (b) 计算 B=，B 是一个基本交换序； (c) 按照公式v=vAB 更新速度和位置。 (d) 如果得到了更好的个体位置，更新。 (iv) 如果得到了更好的群体位置，更新。1）生成初始种群：2）适应度计算3）当前最优粒子位子序列4）全局最优位置序列5）更新速度6）更新位置7）找到最优路
5、径二、结果：源码：/*问题：用粒子群算法求解 TSP 问题：为保证有解 用完全图做样例*/ /*洪文杰 2016-3-25. 智能优化算法 第三次作业*/ #include #include #include using namespace std;/-宏定义-/ #define NUMBER 50 /种群规模 #define GENE_NUMBER 1000 /迭代次数 #define G 20 /图的顶点个数 #define M 0.45 /局部最优解选择概率 #define N 0.65 /全局最优解选择概率 /-全局变量定义-/ int FigureGG; /保存图信息 int Uni
6、tNUMBERG; /保存初始种群 static struct int 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; /
7、保存最短路径 /-函数声明-/ void hwj_figure(); /生成完全图 void hwj_initial_population(); /生成初始种群及粒子速度 void hwj_swap(int *a,int *b); /交换两个数的值 void hwj_fitness(); /计算适应度 void hwj_A(); /找到粒子与其当前所 知道的最佳位置的速度序列 void hwj_B(); /找到粒子与种群最佳 位置的速度序列 void hwj_V(); /速度更新 void hwj_X(); /位置更新 void hwj_best(); /找到最短路径 /-主函数-/ int
8、main() int Key=0;coutUnitij+1) temp+=FigureUnitij+1Unitij; else temp+=FigureUnitijUnitij+1; if(Uniti0UnitiG)sumi=temp+FigureUnitiGUniti0; /计算每个个体的环路长度 else sumi=temp+FigureUniti0UnitiG; /coutN) for(i=0;iM else temp+=FigureUnitijUnitij+1; if(Uniti0UnitiG)sumi=temp+FigureUnitiGUniti0; /计算每个个体的环路长度 else sumi=temp+FigureUniti0UnitiG; if(Figure_bestsumi) Figure_best=sumi; key=i; for(i=0;iG;i+) hwji=Unitkeyi;
