遗传算法解决TSP问题

遗传算法解决TSP问题1.TSP问题所谓TSP问题（旅行商问题）即最短路径问题就是在给定的起始点S到终止点T的通路集合中，寻求距离最小的通路，这样的通路成为S点到T点的最短路径。在寻找最短路径问题上，有时不仅要知道两个指定顶点间的最短路径，还需要知道某个顶点到其他任意顶点间的最短路径。用遗传算法解决这类问题，没有太多的约束条件和有关解的限制，因而可以很快地求出任意两点间的最短路径以及一批次短路径。2.遗传算法2.1遗传算法介绍遗传算法是一种模拟生命进化机制的搜索和优化方法，是把自然遗传学和计算机科学结合起来的优化方程，有很强的解决问题的能力和广泛的适应性。其假设常描述为二进制位串，位串的含义依赖于具体应用。搜索合适的假设从若干初始假设的群体集合开始。当前种群成员通过模仿生物进化的方式来产生下一代群体，如随机变异和交叉。每一步，根据给定的适应度评估当前群体的假设，而后使用概率方法选出适应度最高的假设作为产生下一代的种子。下面介绍几个遗传算法的基本概念：（1）染色体（Chromosome）：在使用遗传算法时，需要把问题的解编成一个适合的码子。这种具有固定结构的符号串既是染色体，符号串的每一位代表一个基因。符号串的总位数成为染色体的长度，一个染色体就代表问题的一个解，每个染色体也被称为一个个体。（2）群体（Population）：每代所产生的染色体总数成为群体，一个群体包含了该问题在这一代的一些解的集合。（3）适应度（Fitness）：对群体中每个染色体进行编码后，每个个体对应一个具体问题的解，而每个解对应于一个函数值。该函数值即适应函数，就是衡量染色体对环境适应度的指标，也是反映实际问题的目标函数在前一代群体的基础上产生新一代群体的工作成为遗传操作，基本的遗传操作有：（1）选择（Select）：按一定的概率从上代群体中选择M对个体作为双亲，直接拷贝到下一代，染色体不发生变化。（2）交叉（Crossover）：对于选中进行繁殖的两个染色体X，Y，以X，Y为双亲作交叉操作，从而产生两个后代X1，Y1.（3）变异（Mutation）：对于选中的群体中的个体（染色体），随机选取某一位进行取反运算，即将该染色体码翻转。用遗传算法求解的过程是根据待解决问题的参数集进行编码，随机产生一个种群，计算适应函数和选择率，进行选择、交叉、变异操作。如果满足收敛条件，此种群为最好个体，否则，对产生的新一代群体重新进行选择、交叉、变异操作，循环往复直到满足条件。2.2遗传算法原型：GA(Fitness,Fitness_threshold,p,r,m)Fitness:适应度评分函数,为给定假设赋予一个评估分数Fitness_threshold:指定终止判据的阈值p:群体中包含的假设数量r:每一步中通过交叉取代群体成员的比例m:变异率初始化群体:P←随机产生的p个假设评估:对于P中的每一个h,计算Fitness(h)当[maxFitness(h)]Fitness_threshold,做产生新的一代Ps:1.选择:用概率方法选择P的(1-r)p个成员加入Ps.从P中选择假设hi的概率用下面公式计算:错误!未找到引用源。2.交叉:根据上面给出的错误!未找到引用源。,从P中按概率选择r(p/2)对假设.对于每对假设h1，h2,应用交叉算子产生两个后代.把所有的后代加入Ps3.变异:使用均匀的概率从Ps中选择m%的成员.对于选出的每个成员,在它表示中随机选择一个为取反4.更新:P←Ps5.评估:对于P中的每个h计算Fitness(h)从P中返回适应度最高的假设3.TSP问题的遗传算法设计与实现3.1TSP问题的图论描述求最短路径问题，用图论术语描述如下：在图G(V,A)中，V表示顶点集合，V=(v1,v2,…,vn)对G中的某一边(iv,jv)，相应的有一个数d(iv,jv)，如果G中不存在边(iv,jv)，则令d(iv,jv)无穷大，如果把d(iv,jv)认为是边(iv,jv)的长度，则通路的长度定义为组成路的各条边的长度总和。顶点iv,jv之间是否有边相连，由邻接矩阵来决定。邻接矩阵A：对一个具有v个顶点，e条边的图G的邻接矩阵A=[ija]是一个v×v阶方阵，其中ija=1，表示iv和jv邻接，ija=0表示vi和vj不相邻接（或i=j）。3.2染色体编码对于一个给定的图模型，将图中各顶点序号自然排序，然后按此顺序将每个待选顶点作为染色体的一个基因，当基因值为1时，表示相应的顶点被选入该条路径中，否则反之。此染色体中的基因排列顺序即为各顶点在次条通路中出现的先后顺序，染色体的长度应等于该图中的顶点个数。在本程序的TSP问题中一共有20个城市，也就是在图模型中有20个顶点，因此一个染色体的长度为20。3.3适应函数f(i)对具有n个顶点的图，已知各顶点之间(iv,jv)的边长度d(iv,jv)，把1iv到inv间的一条通路的路径长度定义为适应函数：对该最优化问题，就是要寻找解mx，使f(mx)值最小。3.4选择操作选择作为交叉的双亲，是根据前代染色体的适应函数值所确定的，质量好的个体，即从起点到终点路径长度短的个体被选中的概率较大。3.5交叉与变异操作将被选中的两个染色体进行交叉操作的过程是先产生一个随机数，确定交叉点，位于染色体的第几位基因上.然后在此位置进行部分基因交换。变异操作是将染色体中某位基因逆变，即由1变为0，或反之。变异的意义为在某条路径上去掉或增加某顶点.但这样做的结果并不一定能使路径的长度减少。也就是说有可能使各代中产生的比较好的方案在遗传过程中丢失，迟缓了获得最优解的速度。为了使算法尽可能快地获得更好的解，改善遗传算法的收敛性。在变异操作时，增加了个体求优的自学习过程，即在某位基因变异后.计算新产生的染色体的适应函数值，若适应函数值更小，即获得的路径更短，则保留;否则，保持原来的解不变。如果有连续N/3次没有得到更好的解，则该过程结束。其中N表示从起点到终点的顶点数。3.6TSP问题的遗传算法的具体步骤解最短路径的遗传算法如下：Generate[p(n)];表示程序开始时要首先产生一个群体，群体个数为nEvaluate[p(h)];表示计算每个个体适应度，h是种群中的一个个体RepeatroofGenerationstimes;重复下面的操作，直到满足条件为止Selectp(h)fromp(n-1);表示从前一代群体中选择一对双亲，用于交叉、变异操作，P(n)代表第n代群体Crossoverandmutationp(n);进行交叉和变异操作Learning[p(n)];自学习过程Evaluate[p(h)];计算新生成的种群中每个个体的适应度End;4.实验测试与结果分析交叉率tp不可选择过小，否则，延缓获得最优解的过程，本程序选择tp=0.85。变异率mp的选择对规模大的优化问题影响很大，本程序选mp=0.1。群体中的个体数的选取是算法中一个很重要的参数，群体中的个体数目越大，算法就越能找到更好的解，个体数目过小，有可能找不到最优解。本程序种群大小为300。因为有20个城市，每个城市作为染色体中的一个基因，因此在本程序中染色体的长度为20。本程序的循环终止的条件是迭代次数不大于100，因此，最大迭代次数为100。本程序中总共运行10次，得到每次最好的路径、回路总开销和适应度。程序的运行结果如下：参考文献[1]遗传书算法——理论、应用与软件实现,王小平、曹立明,西安交通大学出版社,2002[2]机器学习,TomM.Mitchell机械工业出版社,2009源代码清单：#includecmath#includectime#includevector#includemap#includestring#includeiostream#includealgorithmusingnamespacestd;floatpcross=0.85;//交叉率floatpmutation=0.1;//变异率intpopsize=300;//种群大小constintlchrom=20;//染色体长度intgen;//当前世代intmaxgen=100;//最大世代数intrun;//当前运行次数intmaxruns=10;//总运行次数floatmax_var=9;//路径最大连接开销!!//基因定义(一个城市)structGene{stringname;mapGene*,floatlinkCost;//该城市到其它城市的路程开销};//染色体定义(到各城市顺序的一种组合)structChrom{vectorGene*chrom_gene;//染色体（到各城市去的顺序）floatvarible;//路程总开销floatfitness;//个体适应度};//种群定义structPop{vectorChrompop_chrom;//种群里的染色体组floatsumfitness;//种群中个体适应度累计};Popoldpop;//当前代种群Popnewpop;//新一代种群vectorGenegenes(lchrom);//保存全部基因//产生一个随机整数(在low和high之间)inlineintrandomInt(intlow,inthigh){if(low==high)returnlow;returnlow+rand()%(high-low+1);}//计算一条染色体的个体适应度inlinevoidchromCost(Chrom&chr){floatsum=0;for(inti=0;ichr.chrom_gene.size()-1;i++){sum+=(chr.chrom_gene[i])-linkCost[chr.chrom_gene[i+1]];}sum+=(chr.chrom_gene.front())-linkCost[chr.chrom_gene.back()];chr.varible=sum;chr.fitness=max_var*(lchrom)-chr.varible;}//计算一个种群的个体适应度之和inlinevoidpopCost(Pop&pop){floatsum=0;for(inti=0;ipop.pop_chrom.size();i++){sum+=pop.pop_chrom[i].fitness;}pop.sumfitness=sum;}voidoutChrom(Chrom&chr);//随机初始化一条染色体inlinevoidinitChrom(Chrom&chr){vectorinttmp(lchrom);for(inti=0;ilchrom;i++)tmp[i]=i;intchoose;while(tmp.size()1){choose=randomInt(0,tmp.size()-1);chr.chrom_gene.push_back(&genes[tmp[choose]]);tmp.erase(tmp.begin()+choose);}chr.chrom_gene.push_back(&genes[tmp[0]]);chromCost(chr);}//随机初始化种群inlinevoidinitpop(Pop&pop){pop.pop_chrom.reserve(popsize);Chromtmp;tmp.chrom_gene.reserve(lchrom);for(inti=0;ipopsize;i++){initChrom(tmp);pop.pop_chrom.push_back(tmp);tmp.chrom_gene.clear();}popCost(pop);}//轮盘赌选择,返回种群中被选择的个体编号inlineintselectChrom(constPop&pop){floatsum=0;floatpick=float(randomInt(0,1000))/1000;inti=0;if(pop.sumfitness!=0){wh