智能算法实验报告剖析

人工智能实验—智能算法实验一 蚂蚁算法一、 实验目的：理解蚂蚁算法的本质，会编写蚂蚁算法来求解 TSP问题。二、

实验原理：蚂蚁在寻找食物源时， 能在其走过的路上释放一种特殊的分泌物——信息素 (随着时间的推移该物质会逐渐挥发 ),后来的蚂蚁选择该路径的概率与当时这条路径上该物质的强度成正比。当一定路径上通过的蚂蚁越来越多时， 其留下的信息素轨迹也越来越多， 后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度。而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈机制 ,通过这种正反馈机制，蚂蚁最终可以发现最短路径。 特别地，当蚂蚁巢穴与食物源之间出现障碍物时， 蚂蚁不仅可以绕过障碍物，而且通过蚁群信息素轨迹在不同路径上的变化， 经过一段时间的正反馈， 最终收敛到最短路径上。三、 实验内容：#include<iostream>#include<math.h>#include<time.h>usingnamespacestd;constintMaxInt=~(unsignedint)0/2;/*doubled[5][5]={{0,7,6,10,13},{7,0,7,10,10},{6,7,0,5,9},{10,10,5,0,6},{13,10,9,6,0}};//表示路径(i,j)之间的长度*/classAnt{private:intAntNum;//蚂蚁个数;intNodeNum;//节点个数;intMaxRunNum;//最大运行次数intRunNum;//运行次数double**d;// 表示路径(i,j)之间的长度double**n;// 边弧(i,j)的能见度(visibility), 或称局部启发因子，一般取之间的长度;double**t;// 边弧(i,j)的信息素轨迹强度（ intensity）doubleINITINFO;//初始的信息素值//double**deltaT;// 蚂蚁k于弧上(i,j)留下的单位长度轨迹信息素数量

;

1/d

表示路径

(i,j)double**P;//蚂蚁k在结点的转移概率， j是尚未访问结点int**tab;// 蚂蚁的禁忌表doubleMinSum;//最短路径长度int*MinRoute;// 最优路径doublea;//信息素轨迹的相对重要性doubleb;//边弧能见度的相对重要性doublep;//信息素轨迹的持久性（ Evaporation）doubleQ;//(轨迹数量)

;public:Ant(intNum,doubleposition[][2]):NodeNum(Num){srand(time(NULL));AntNum=50;p=0.8;a=1;//(1~2)b=2;//(2~5)P=get2DMemory(P,NodeNum);t=get2DMemory(t,NodeNum);n=get2DMemory(n,NodeNum);d=get2DMemory(d,NodeNum);tab=get2DMemory(tab,AntNum,NodeNum);posToDistance(position);MinSum=MaxInt;MinRoute=newint[NodeNum];MaxRunNum=200;RunNum=0;INITINFO=200;Q=2000;}voidposToDistance(doublepos[][2]){for(inti=0;i<NodeNum;i++)for(intj=0;j<NodeNum;j++){d[i][j]=sqrt((pos[i][0]-pos[j][0])*(pos[i][0]-pos[j][0])+(pos[i][1]-pos[j][1])*(pos[i][1]-pos[j][1]));}}voidgetMinRoute(int*CurrentRoute){for(inti=0;i<NodeNum;i++)MinRoute[i]=CurrentRoute[i];}doublegetPossiblity(inti,intj,intk,intcNode){if(i==j)return0;else{if(inTab(j,k,cNode)==true)return0;}returnPow(t[i][j],a)*Pow(n[i][j],b)/sumPossiblity(i,k,cNode);}boolinTab(ints,intk,intcNode){for(intm=0;m<cNode;m++)if(s==tab[k][m])returntrue;returnfalse;}doublesumPossiblity(inti,intk,intcNode){doublesum=0;for(ints=0;s<NodeNum;s++){if(i==s)continue;if(inTab(s,k,cNode)==true)continue;sum+=Pow(t[i][s],a)*Pow(n[i][s],b);}returnsum;}voidupdateInfomation(){for(intk=0;k<AntNum;k++){doublesum=sumDistance(k);if(sum<MinSum){MinSum=sum;getMinRoute(tab[k]);}for(inti=0;i<NodeNum;i++)for(intj=0;j<NodeNum;j++){if(i==j)continue;t[i][j]=t[i][j]*p;}for(i=0;i<NodeNum;i++)t[tab[k][i]][tab[k][(i+1)%NodeNum]]+=Q/sum;}}doublesumDistance(intk){doublesum=0;for(inti=0;i<NodeNum;i++)sum+=d[tab[k][i]][tab[k][(i+1)%NodeNum]];returnsum;}voidstart(){init();run();print();}voidrun(){while(RunNum<MaxRunNum){initNode();起点城市moveNext();updateInfomation();RunNum++;}}voidinit(){for(inti=0;i<NodeNum;i++)for(intj=0;j<NodeNum;j++){if(i==j)n[i][i]=0;elsen[i][j]=1/d[i][j];}for(i=0;i<NodeNum;i++)for(intj=0;j<NodeNum;j++)t[i][j]=INITINFO;}voidinitNode(){for(intk=0;k<AntNum;k++){intNode=int(((double)rand()/RAND_MAX)*NodeNum);if(Node==NodeNum)Node=NodeNum-1;tab[k][0]=Node;}}intrandInt(intmax){intnode=int((max)*(double)rand()/RAND_MAX);if(node==max)node=max-1;returnnode;}intgreedy(intk,intstart=0){if(start==0){tab[k][0]=randInt(NodeNum);}inti=start;doubleDistance=MaxInt;intDIndex=0;for(intj=0;j<NodeNum;j++){boolhave=false;for(intm=0;m<i;m++){if(tab[k][m]==j){have=true;break;}}if(have)continue;if(d[i-1][j]<Distance){Distance=d[i-1][j];DIndex=j;}}returnDIndex;}voidprint(){cout<<"最优路径(城市号):"<<endl;for(inti=0;i<NodeNum;i++){cout<<MinRoute[i]<<"\t";}cout<<endl;cout<<"最短距离:"<<MinSum<<endl;}intgetNextNode(intlast,doublepossiblity,intk,intcNode){inti=0;while(i<NodeNum){doubleGetPossiblity=getPossiblity(last,i,k,cNode);if(last==i){i++;continue;}if(GetPossiblity==0){i++;continue;}if(possiblity<=GetPossiblity)returni;elsepossiblity=possiblity-GetPossiblity;i++;}returngreedy(k,cNode);}voidmoveNext(){for(intk=0;k<AntNum;k++)for(inti=1;i<NodeNum;i++){tab[k][i]=getNextNode(tab[k][i-1],(double)rand()/RAND_MAX,k,i);}}double**get2DMemory(double**p,intn){p=newdouble*[n];for(inti=0;i<n;i++){p[i]=newdouble[n];}returnp;}int**get2DMemory(int**p,intm,intn){p=newint*[m];for(inti=0;i<m;i++){p[i]=newint[n];}returnp;}doublePow(doublea,intn){doublem=1;for(inti=0;i<n;i++)m=m*a;returnm;}voiddelete2DMemory(int**a){for(inti=0;i<AntNum;i++)deletea[i];deletea;}voiddelete2DMemory(double**a){for(inti=0;i<NodeNum;i++)deletea[i];deletea;}~Ant(){delete2DMemory(tab);delete2DMemory(d);delete2DMemory(n);delete2DMemory(t);delete2DMemory(P);deleteMinRoute;}};voidmain(){doubleposition[31][2]={{1304, 2312},{3639, 1315},{4177, 2244},{3712, 1399},{3488,1535},{3326,1556},{3238,1229},{4196,1004},{4312,790},{4386,570},{3007,1970},{2562,1756},{2788,1491},{2381,1676},{1332,695},{3715,1678},{3918,2179},{4061,2370},{3780,2212},{3676,2578},{4029,2838},{4263,2931},{3429,1908},{3507,2367},{3394,2643},{3439,3201},{2935,3240},{3140,3550},{2545,2357},{2778,2826},{2370,2975}};Antant(31,position);ant.start();}四、实验结果：当城市数量为 31，蚁群数量为 50，迭代次数为 200时的结果:（城市号从 0开始）实验二 遗传算法一、实验目的：理解遗传算法的本质，学会用遗传算法解决 TSP问题。一、实验原理：遗传算法类似于自然进化， 通过作用于染色体上的基因寻找好的染色体来求解问题。 与自然界相似，遗传算法对求解问题的本身一无所知， 它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体， 使适应性好的染色体有更多的繁殖机会。 在遗传算法中，通过随机方式产生若干个所求解问题的数字编码， 即染色体，形成初始群体；通过适应度函数给每个个体一个数值评价， 淘汰低适应度的个体， 选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的种群。对这个新种群进行下一轮进化。这就是遗传算法的基本原理。二、实验内容：#include<iostream>#include<math.h>#include<time.h>usingnamespacestd;constintMaxInt=~(unsignedint)0/2;classGA{private:intNodeNum;//节点个数intCNum;//染色体个数doubleMaxSum;//最短路径长度int*MaxRoute;//最优路径intMaxRunNum;//最大运行次数intRunNum;//运行次数staticdouble**d;// 表示路径(i,j)之间的长度int**tab;// 所有染色体存放的路径表double*AF;doubletotalFitness;//总的适应度doublePm;//变异概率doublePc;//交叉概率public:GA(intNum,doubleposition[][2]):NodeNum(Num){srand(time(NULL));totalFitness=0;CNum=1000;d=get2DMemory(d,NodeNum);tab=get2DMemory(tab,CNum,NodeNum);posToDistance(position);MaxRunNum=200;RunNum=0;Pm=0.2;Pc=0.6;MaxSum=0;MaxRoute=newint[NodeNum];AF=newdouble[CNum];}voidselect(){int**temp;intleave=0;temp=get2DMemory(temp,CNum,NodeNum);采取精英策略for(inti=0;i<CNum/4;i++)copyArray(MaxRoute,temp[i]);for(i=CNum/4;i<CNum;i++){doublepossiblity=((double)rand())/RAND_MAX;leave=leaveWhich(possiblity);copyArray(tab[leave],temp[i]);}delete2DMemory(tab);tab=temp;}voiddelete2DMemory(int**a){for(inti=0;i<CNum;i++)deletea[i];deletea;}voiddelete2DMemory(double**a){for(inti=0;i<NodeNum;i++)deletea[i];deletea;}voidcopyArray(int*a,int*b){for(inti=0;i<NodeNum;i++)b[i]=a[i];}voidcross(){交叉操作for(intk=0;k<CNum-1;k++){doublerate=(double)rand()/RAND_MAX;if(rate<8*Pm/9){intbegin=randInt(NodeNum);取point和point.next进行交叉，形成新的两个染色体for(inti=begin;i<NodeNum;i++){intfir,sec;for(fir=0;tab[k][fir]!=tab[k+1][i];fir++);for(sec=0;tab[k+1][sec]!=tab[k][i];sec++);两个基因互换exchange(tab[k][i],tab[k+1][i]);消去互换后重复的那个基因tab[k][fir]=tab[k+1][i];tab[k+1][sec]=tab[k][i];}}elseif(rate<Pm){if(k>0)reverse(k-1);intnode=randInt(NodeNum);greedy(k,node);}//选择交叉节点，将结点后面的部分用贪婪算法处理}}intleaveWhich(doublepossiblity){inti=0;while(i<CNum){if(possiblity<=getPossiblity(i))returni;elsepossiblity=possiblity-getPossiblity(i);i++;}returnCNum-1;}voidcalFitness(){for(intk=0;k<CNum;k++){doubleA=adjustFunc(k);AF[k]=A;if(A>MaxSum){MaxSum=A;getMaxRoute(tab[k]);}}totalFitness=sumPossiblity();}doublegetPossiblity(intk){returnAF[k]/totalFitness;}voidgetMaxRoute(int*CurrentRoute){for(inti=0;i<NodeNum;i++)MaxRoute[i]=CurrentRoute[i];}doublesumPossiblity(){doublesum=0;for(intk=0;k<CNum;k++){sum=sum+AF[k];}returnsum;}doubleadjustFunc(intk){return1.0/sumDistance(k);}doublesumDistance(intk){doublesum=0;for(inti=0;i<NodeNum;i++)sum+=d[tab[k][i]][tab[k][(i+1)%NodeNum]];returnsum;}doublesumDistance(){doublesum=0;for(inti=0;i<NodeNum;i++)sum+=d[MaxRoute[i]][MaxRoute[(i+1)%NodeNum]];returnsum;}voidprint(){cout<<"最优路径(城市号):"<<endl;for(inti=0;i<NodeNum;i++){cout<<MaxRoute[i]<<"\t";}cout<<endl;cout<<"最短距离:"<<sumDistance()<<endl;}voidstart(){initNodeNum();// 起点城市run();print();}voidrun(){while(RunNum<MaxRunNum){calFitness();select();cross();mutation();RunNum++;}}voidmutation(){for(inti=0;i<CNum;i++){if((double)rand()/RAND_MAX>Pm)continue;else{//进行交换变异if((double)rand()/RAND_MAX>0.5){intstart=randInt(NodeNum);intend=randInt(NodeNum);if(start>=end)exchange(start,end);exchange(tab[i][start],tab[i][end]);}else{//进行部分反转变异intstart=randInt(NodeNum+1);intend=randInt(NodeNum+1);if(start>=end)exchange(start,end);reverse(i,start,end);}}}}intrandInt(intmax){intnode=int((max)*(double)rand()/RAND_MAX);if(node==max)node=max-1;returnnode;}voidreverse(intk,intstart=0,intend=-1){if(end==-1)end=NodeNum;if(start<0||end<0)return;if(start>=end)return;int*temp=newint[NodeNum];for(inti=0;i<NodeNum;i++){temp[i]=tab[k][i];}for(i=start;i<end;i++){tab[k][i]=temp[end+start-1-i];}deletetemp;}voidexchange(int&a,int&b){inttemp=a;a=b;b=temp;}voidinitNodeNum(){for(intk=0;k<CNum;k++){inti,j;for(i=0;i<NodeNum;i++){intcity=randInt(NodeNum);检查有没有cityboolexist=false;for(j=0;j<i;j++){已存在if(tab[k][j]==city){i--;//停住，再次随机exist=true;break;}}if(exist!=true)tab[k][i]=city;}}}//初始化节点,随机初始化voidgreedy(intk,intstart=0){if(start==0){tab[k][0]=randInt(NodeNum);}for(inti=start+1;i<NodeNum;i++){doubleDistance=MaxInt;intDIndex=0;for(intj=0;j<NodeNum;j++){boolhave=false;for(intm=0;m<i;m++){if(tab[k][m]==j){have=true;break;}}if(have)continue;