计算智能--用遗传算法解决TSP问题

2013-1-10计算智能作业ZY1203228于驷男1计算智能作业三用遗传算法求解TSP问题ZY1203228于驷男一、旅行商问题旅行商问题(TravellingSalesmanProblem,TSP)，是典型的、易于描述却难以处理的组合优化问题。由于遗传算法方法的本质是处理复杂问题的一种鲁棒性强的启发性随机搜索算法,故而利用遗传算法求解这类问题是有效的。假设平面上有n个点代表n个城市的位置,寻找一条最短的闭合路径,使得可以遍历每一个城市恰好一次。这就是旅行商问题。旅行商的路线可以看作是对n个城市所设计的一个环形,或者是对一列n个城市的排列。由于对n个城市所有可能的遍历数目可达(n-1)!个,因此解决这个问题需要0(n!)的计算时间。假设每个城市和其他任一城市之间都以欧氏距离直接相连。也就是说,城市间距可以满足三角不等式,也就意味着任何两座城市之间的直接距离都小于两城市之间的间接距离。是一个典型的优化组合问题。二、遗传算法遗传算法是由美国J.Holland教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。遗传算法，在本质上是一种不依赖具体问题的直接搜索方法，是一种求解问题的高效并行全局搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、负载平衡、电磁系统设计、生物科学、社会科学等方面都得到了应用。在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动控制、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”。三、算法实现标准的遗传算法包括群体的初始化，选择，交叉，变异操作。流程图如下所示，其主要步骤可描述如下：2013-1-10计算智能作业ZY1203228于驷男2（1）随机产生一组初始个体构成的初始种群，并评价每一个个体的适配值。（2）判断算法的收敛准则是否满足。若满足输出搜索结果；否则执行以下步骤。（3）根据适配值大小以一定方式执行选择操作。（4）按交叉概率Pc执行交叉操作。（5）按变异概率Pm执行变异操作。（6）返回步骤（2）。对于n个城市的问题，每个个体即每个解的长度为n，用s行,t列的pop矩阵，表示初始群体，s表示初始群体的个数，t为n+1，矩阵的每一行的前n个元素表示城市编码，最后一个元素表示这一路径的长度。城市的位置可以手动输入，使用一个N×N矩阵D存储，D（i，j）代表城市i和城市j之间的距离。D（i，j）=sqrt(（Xi-Xj）.^2+(Yi-Yj).^2)。在TSP的求解中，可以直接用距离总和作为适应度函数。个体的路径长度越小，所得个体优越，距离的总和越大，适应度越小，进而探讨求解结果是否最优。选择就是从群体中选择优胜个体、淘汰劣质个体的操作，它是建立在群体中个体适应度评估基础上。这里采用方法是最优保存方法。本实例中交叉采用部分匹配交叉策略，先随机选取两个交叉点，然后将两交叉点中间的基因段互换，将互换的基因段以外的部分中与互换后基因段中元素冲突的用另一父代的相应位置代替，直到没有冲突。2013-1-10计算智能作业ZY1203228于驷男3变异操作是以变异概率Pm对群体中个体串某些基因位上的基因值作变动，若变异后子代的适应度值更加优异，则保留子代染色体，否则，仍保留父代染色体。这有助于增加种群的多样性，避免早熟收敛（非全局最优）。判断结束准则是固定指定了迭代的次数当算法达到迭代次数时，算法结束，输出当前的最优解。在根据适配值计算并选择的时候，记录下来的当前最优值，在变异后加入跟新的群体，保证新的迭代循环中TSP解越来越好（不会变差）。在选择的一种操作是拿最优的K个替换最差的K个个体，本例是按适配值选择，并使群体数目变少，当每次变异操作后，产生随机路径补充群体是群体数目不变，再次循环，一定程度上防止因初始群体的选择问题而陷入局部最优。四、实验代码及结果#includeiostream#includevector#includecmath#includealgorithm#includectimeusingnamespacestd;typedefvectorintVI;typedefvectorVIVVI;#definePBpush_back#defineMPmake_pairintnext_int(){returnrand()*(RAND_MAX+1)+rand();}doublenext_double(){return(double(rand()*(RAND_MAX+1)+rand()))/((RAND_MAX+1)*RAND_MAX+RAND_MAX);}voidpmx(VI&a,VI&b,intpointcnt)//PMX交叉{inti;intsa=next_int()%pointcnt,sb=next_int()%pointcnt;//随机选择两交叉位inttemp;if(sasb){swap(sa,sb);}//保证交叉位sa=sb2013-1-10计算智能作业ZY1203228于驷男4VIm1(pointcnt,-1);VIm2(pointcnt,-1);for(i=sa;i=sb;++i)//互换交叉位之间的基因{swap(a[i],b[i]);m1[a[i]]=b[i];m2[b[i]]=a[i];}for(i=0;ipointcnt;++i)//调整交叉位之前、之后的基因，防止和交叉位之间的基因重复if(isa||isb){if(m2[b[i]]!=-1){while(m2[b[i]]!=-1)b[i]=m2[b[i]];}if(m1[a[i]]!=-1){while(m1[a[i]]!=-1)a[i]=m1[a[i]];}}}vectordoublex,y;doublefitness(constVI&v,intpointcnt)//计算适应度{doubler=0;for(inti=0;ipointcnt;i++){doubledx=x[v[i]]-x[v[(i+1)%pointcnt]];doubledy=y[v[i]]-y[v[(i+1)%pointcnt]];r+=sqrt(dx*dx+dy*dy);//个体的适应度为相邻两城市之间的距离平方的平方根和}return1.0/r;}voidchange0(vectorint&K,intN)//变异策略:两点互换{inti=next_int()%N;intd=next_int()%(N-1);intj=(i+1+d)%N;swap(K[i],K[j]);}voidmutate(VI&route,intmutate_type,intpointcnt){if(mutate_type==0)//两点互换change0(route,pointcnt);2013-1-10计算智能作业ZY1203228于驷男5}boolpair_dec(constpairdouble,VI*&a,constpairdouble,VI*&b){returnab;}classother_population{public:intpopsize,pointcnt;//种群规模,染色体长度doublepc,pm;//交叉概率,变异概率vectorpairdouble,VI*pop;//种群pairdouble,VI*bestofpop;//最好个体intcross_type;//交叉类型intmutate_type;//变异类型intmake_p;//个体概率分配策略类型intselect_type;//个体选择类型inttoursize;//竞赛规模doublebestp;//最好个体选择概率other_population(inta,intb,intc,intf,intg,doubled,doublee,inth,doublej,intm){popsize=a,pointcnt=b,cross_type=c,mutate_type=f,make_p=g,pc=d,pm=e,toursize=h,bestp=j,select_type=m;for(inti=0;ipopsize;i++)//初始化种群{VI*v=newVI(pointcnt);for(intj=0;jpointcnt;j++)(*v)[j]=j;random_shuffle(v-begin(),v-end());pop.PB(MP(fitness(*v,pointcnt),v));}sort(pop.begin(),pop.end(),pair_dec);bestofpop.first=pop[0].first;//初始时最好个体的适应度bestofpop.second=newVI(*pop[0].second);//初始时最好个体的染色体}~other_population(){for(inti=0;ipop.size();i++)deletepop[i].second;deletebestofpop.second;}voidnext()//产生下一代种群{vectordoubleps(popsize);if(make_p==0)//按适应度比例分配个体的选择概率{2013-1-10计算智能作业ZY1203228于驷男6doublesum=0;for(inti=0;ipopsize;i++)sum+=pop[i].first;for(i=0;ipopsize;i++)ps[i]=pop[i].first/sum;}if(select_type==0)//轮盘赌选择个体{vectorpairdouble,VI*select_res;vectordoubleaddsum(popsize);for(inti=0;ipopsize-1;i++)//计算个体的累计概率{if(i==0)addsum[i]=ps[0];elseaddsum[i]=addsum[i-1]+ps[i];}addsum[popsize-1]=1.5;for(i=0;ipopsize;i++){doublerd=next_double();intr=lower_bound(addsum.begin(),addsum.end(),rd)-addsum.begin();VI*v=newVI(*pop[r].second);select_res.PB(MP(fitness(*v,pointcnt),v));}for(i=0;ipopsize;i++)deletepop[i].second;pop=select_res;}for(intcc=0;ccpopsize/2;cc++)//随机选择两个个体,然后进行交叉{inta=next_int()%popsize;intb=(a+1+(next_int()%(popsize-1)))%popsize;if(next_double()pc)//随机数小于交叉概率,进行交叉{if(cross_type==0)//pmx交叉pmx(*pop[a].second,*pop[b].second,pointcnt);pop[a].first=fitness(*pop[a].second,pointcnt);//计算交叉后个体a的适应度if(bestofpop.firstpop[a].first)//更新最好个体{bestofpop.first=pop[a].first;deletebestofpop.second;bestofpop.second=newVI(*pop[a].second);2013-1-