您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 质量控制/管理 > 遗传算法解决tsp问题
//以下是cpp文件完整代码:#includeiomanip#includefstream#includecmath#includetime.h#includealgorithm#includeiostreamusingnamespacestd;constintN=30;//城市个数constintMAXN=50;//最大城市个数constintpopulation=100;//种群个体数constintMAXpopulation=100;//最大种群个数constdoublemutation_rate=0.4;//变异率constdoublecrossover_rate=0.65;//交配率constintiter=200;//迭代次数//城市结构体structcity{//charid;intx,y;};//路径结构体structpath{citycities[MAXN];doublelength;};doubleD[MAXN][MAXN];//存储城市之间的长度citybcity[MAXN];//存储最优路径的各个城市pathbpath[MAXpopulation];//存储种群所有个体doublefitness[MAXpopulation];//存储种群个体的适应度//产生x-y的随机整数intrandInt(intx,inty){returnrand()%(y-x+1)+x;}doublerandDouble(){returnrand()/(RAND_MAX+1.0);}//两城市之间距离函数doubledistance(citycity1,citycity2){returnsqrt(double((city1.x-city2.x)*(city1.x-city2.x)+(city1.y-city2.y)*(city1.y-city2.y)));}//路径总长度函数doubletotaldistance(pathp){inti;doubletotal=0;for(i=0;iN-1;i++){total+=distance(p.cities[i],p.cities[i+1]);}total+=distance(p.cities[N-1],p.cities[0]);returntotal;}//初始化城市、距离voidinit(){inti,j;inta,b;intss=0;charbuffer[256];ifstreammyfile(city1.txt);//从文件读取城市坐标if(!myfile)return;while(!myfile.eof()){myfile.getline(buffer,20);sscanf(buffer,%d%d,&a,&b);bcity[ss].x=a;bcity[ss].y=b;ss++;}myfile.close();//输出城市坐标coutcityorders:endl;for(i=0;iN;i++){coutbcity[i].x;}coutendl;for(i=0;iN;i++){coutbcity[i].y;}coutendl;//计算城市之间距离for(i=0;iN-1;i++){for(j=i+1;jN;j++){D[i][j]=D[j][i]=distance(bcity[i],bcity[j]);}}for(j=0;jN;j++){D[j][j]=0;}for(j=0;jpopulation;j++){fitness[j]=0;}}//随机选择一个城市cityrandcity(){intrand;rand=randInt(0,N-1);returnbcity[rand];}//比较两个城市是否相同boolequalcity(cityp,cityq){if((p.x==q.x)&&(p.y==q.y))returntrue;elsereturnfalse;}//随机产生一条路径pathcreatepath(){pathp;inti;intj=0;p.cities[0]=randcity();for(i=1;iN;i++){p.cities[i]=randcity();while(ji)//随机选择的城市不能重复{if(equalcity(p.cities[i],p.cities[j])){p.cities[i]=randcity();j=0;}elsej++;}j=0;}returnp;}//计算适应度函数voidfit(){inti;doubletotal=0;for(i=0;ipopulation;i++){fitness[i]=100/(totaldistance(bpath[i]));//100除以路径长度,避免fitness值过小。同时保证路径小的,被选中概率更大}for(i=0;ipopulation;i++){total+=fitness[i];}for(i=0;ipopulation;i++){fitness[i]=fitness[i]/total;//是的fitness[]和为1。}}//判断两条路径是否相同boolequalpath(pathp,pathq){inti;for(i=0;iN;i++){if(!equalcity(p.cities[i],q.cities[i]))returnfalse;}returntrue;}//计算种群中最优个体的路径长度doublebestpathlength(pathp[]){inti;doublebest=1000000000;for(i=0;ipopulation;i++){doubletem=totaldistance(p[i]);if(tembest){best=tem;}}returnbest;}//返回种群的最优个体pathbestpath(pathp[],intn){inti;intbindex;doublebest=1000000000;for(i=0;in;i++){doubletem=totaldistance(p[i]);if(tembest){best=tem;bindex=i;}}returnp[i];}//初始化种群voidinitpopulation(){inti;intj=0;bpath[0]=createpath();for(i=1;ipopulation;i++){bpath[i]=createpath();while(ji){if(equalpath(bpath[j],bpath[i]))//保证个体不重复{bpath[i]=createpath();j=0;}elsej++;}j=0;}fit();//初始化完了以后计算种群适应度}//轮盘赌函数intlunpan(){inti;doublerand=randDouble();doubletotal=0;for(i=0;ipopulation;i++){total+=fitness[i];if(totalrand)break;}returni;}//冒泡排序m-n之间数组元素voidsort(intp[],intm,intn){inti,j;for(i=m;in;i++){for(j=n-1;j=i;j--){if(p[j]p[j+1]){inttem=p[j];p[j]=p[j+1];p[j+1]=tem;}}}}//交叉,繁殖产生孩子voidsex2(pathp,pathq,pathpp,pathqq){pp=p;qq=q;inti,j;intm,n;intk1=0;intk2=0;city*t1=newcity[N];city*t2=newcity[N];m=randInt(0,N-1);n=randInt(0,N-1);while(m=n)//保证m小于n,使路径划分为3段{n=randInt(0,N-1);m=randInt(0,N-1);}for(i=m;i=n;i++){for(j=m;j=n;j++){if(equalcity(p.cities[i],q.cities[j])){break;}}if(j==n+1){t1[k1++]=pp.cities[i];//记录中间段qq没有出现的元素}}for(i=m;i=n;i++){for(j=m;j=n;j++){if(equalcity(q.cities[i],p.cities[j])){break;}}if(j==n+1){t2[k2++]=qq.cities[i];//记录中间段pp没有出现的元素}}for(i=m;i=n;i++)//交换中间段的元素{citytem=pp.cities[i];pp.cities[i]=qq.cities[i];qq.cities[i]=tem;}for(i=0;iN;i++)//调整pp,使得路径没有重复城市{if(im||in){for(j=0;jk1;j++){if(equalcity(t2[j],pp.cities[i])){pp.cities[i]=t1[j];}}}}for(i=0;iN;i++)//调整qq,使得路径没有重复城市{if(im||in){for(j=0;jk2;j++){if(equalcity(t1[j],qq.cities[i])){qq.cities[i]=t2[j];}}}}delete[]t1;delete[]t2;}//交叉,繁殖函数,路径划分为等长的两部分,//交叉,使得父亲路径前一半的城市排序,与儿子1的相应城市排序相同。剩余的城市排序与母亲相同。儿子2同理。voidsex(pathp,pathq,pathpp,pathqq){inti,j;intk=0;inthalf=N/2;pp=p;qq=q;if(randDouble()crossover_rate){int*index=newint[MAXN];for(i=0;ihalf;i++){for(j=0;jN;j++){if(equalcity(pp.cities[i],qq.cities[j])){index[k]=j;k++;}}}sort(index,0,half-1);for(i=0;ihalf;i++){qq.cities[index[i]]=pp.cities[i];}k=0;for(i=half;iN;i++){for(j=0;jN;j++){if(equalcity(pp.cities[i],qq.cities[j])){index[k]=j;k++;}}}sort(index,0,N-half-1);for(i=0;iN-half;i++){pp.cities[half+i]=qq.cities[index[i]];}delete[]index;}}//概率变异函数,随机产生两个城市,交换得到新的路径voidmutate1(pathp){if(randDouble()mutation_rate){inti;intj;i=randInt(0,N-1);j=randInt(0,N-1);while(i==j){j=randInt(0,N-1);}cityc=p.cities[i];p.cities[i]=p.cities[j];p.cities[j]=c;}}//交换路径的城市i和城市jpathswap(pathp,inti,intj){pathp1=p;cityc=p1.cities[i];p1.cities[i]=p1.cities[j];p1.cities[j]=c;returnp1;}//变异函数,随机3个城市调换顺序得到的路径相互比较,得到的最优路径为变异结果。pathmutate2(pathp){if(randDouble()mutation_rate){pathpp=p;//cityc;pathbestp=p;pathpath1,path
本文标题:遗传算法解决tsp问题
链接地址:https://www.777doc.com/doc-2009885 .html