人工智能实验—智能算法实验一蚂蚁算法一、实验目的：理解蚂蚁算法的本质，会编写蚂蚁算法来求解TSP问题。
二、实验原理：蚂蚁在寻找食物源时，能在其走过的路上释放一种特殊的分泌物——信息素(随着时间的推移该物质会逐渐挥发), 后来的蚂蚁选择该路径的概率与当时这条路径上该物质的强度成正比。
当一定路径上通过的蚂蚁越来越多时，其留下的信息素轨迹也越来越多，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度。
而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈机制, 通过这种正反馈机制，蚂蚁最终可以发现最短路径。
特别地，当蚂蚁巢穴与食物源之间出现障碍物时，蚂蚁不仅可以绕过障碍物，而且通过蚁群信息素轨迹在不同路径上的变化，经过一段时间的正反馈，最终收敛到最短路径上。
三、实验内容：#include<iostream>#include<math.h>#include<time.h>using namespace std;const int MaxInt=~(unsigned int)0 / 2;/*double d[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)之间的长度*/class Ant{private:int AntNum;//蚂蚁个数;int NodeNum;//节点个数;int MaxRunNum;//最大运行次数int RunNum;//运行次数double **d;//表示路径(i,j)之间的长度double **n;//边弧(i,j)的能见度(visibility), 或称局部启发因子，一般取1/d 表示路径(i,j)之间的长度;double **t;//边弧(i,j)的信息素轨迹强度（intensity）double INITINFO;//初始的信息素值//double **deltaT;//蚂蚁k 于弧上(i,j)留下的单位长度轨迹信息素数量;double **P;//蚂蚁k 在结点的转移概率，j 是尚未访问结点;int **tab;//蚂蚁的禁忌表double MinSum;//最短路径长度int *MinRoute;//最优路径double a;//信息素轨迹的相对重要性double b;//边弧能见度的相对重要性double p;//信息素轨迹的持久性（Evaporation）double Q;//(轨迹数量)public:Ant(int Num,double position[][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=new int[NodeNum];MaxRunNum=200;RunNum=0;INITINFO=200;Q=2000;}void posToDistance(double pos[][2]){for(int i=0;i<NodeNum;i++)for(int j=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]));}}void getMinRoute(int *CurrentRoute){for(int i=0;i<NodeNum;i++)MinRoute[i]=CurrentRoute[i];}double getPossiblity(int i,int j,int k,int cNode){if(i==j) return 0;else {if(inTab(j,k,cNode)==true)return 0;}return Pow(t[i][j],a)*Pow(n[i][j],b)/sumPossiblity(i,k,cNode); }bool inTab(int s,int k,int cNode){for(int m=0;m<cNode;m++)if(s==tab[k][m])return true;return false;}double sumPossiblity(int i,int k,int cNode){double sum=0;for(int s=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);}return sum;}void updateInfomation(){for(int k=0;k<AntNum;k++){double sum=sumDistance(k);if(sum<MinSum){MinSum=sum;getMinRoute(tab[k]);}for(int i=0;i<NodeNum;i++)for(int j=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;}}double sumDistance(int k){double sum=0;for(int i=0;i<NodeNum;i++)sum+=d[tab[k][i]][tab[k][(i+1)%NodeNum]]; return sum;}void start(){init();run();print();}void run(){while(RunNum<MaxRunNum){initNode();//起点城市moveNext();updateInfomation();RunNum++;}}void init(){for(int i=0;i<NodeNum;i++)for(int j=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(int j=0;j<NodeNum;j++)t[i][j]=INITINFO;}void initNode(){for(int k=0;k<AntNum;k++){int Node=int(((double)rand()/RAND_MAX)*NodeNum);if(Node==NodeNum)Node=NodeNum-1;tab[k][0]=Node;}}int randInt(int max){int node=int((max)*(double)rand()/RAND_MAX);if(node==max)node=max-1;return node;}int greedy(int k,int start=0){if(start==0){tab[k][0]=randInt(NodeNum);}int i=start;double Distance=MaxInt;int DIndex=0;for(int j=0;j<NodeNum;j++){bool have=false;for(int m=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;}}return DIndex;}void print(){cout<<"最优路径(城市号):"<<endl;for(int i=0;i<NodeNum;i++){cout<<MinRoute[i]<<"\t";}cout<<endl;cout<<"最短距离:"<<MinSum<<endl;}int getNextNode(int last,double possiblity,int k,int cNode){int i=0;while(i<NodeNum){double GetPossiblity=getPossiblity(last,i,k,cNode);if(last==i){i++;continue;}if(GetPossiblity==0){i++;continue;}if(possiblity<=GetPossiblity)return i;elsepossiblity=possiblity-GetPossiblity;i++;}return greedy(k,cNode);}void moveNext(){for(int k=0;k<AntNum;k++)for(int i=1;i<NodeNum;i++){tab[k][i]=getNextNode(tab[k][i-1],(double)rand()/RAND_MAX,k,i);}}double **get2DMemory(double **p,int n){p=new double*[n];for(int i=0;i<n;i++){p[i]=new double[n];}return p;}int **get2DMemory(int **p,int m,int n){p=new int*[m];for(int i=0;i<m;i++){p[i]=new int[n];}return p;}double Pow(double a,int n){double m=1;for(int i=0;i<n;i++)m=m*a;return m;}void delete2DMemory(int **a){for(int i=0;i<AntNum;i++)delete a[i];delete a;}void delete2DMemory(double **a){for(int i=0;i<NodeNum;i++)delete a[i];delete a;}~Ant(){delete2DMemory(tab);delete2DMemory(d);delete2DMemory(n);delete2DMemory(t);delete2DMemory(P);delete MinRoute;}};void main(){double position[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}};Ant ant(31,position);ant.start();}四、实验结果：当城市数量为31，蚁群数量为50，迭代次数为200时的结果:（城市号从0开始）实验二遗传算法一、实验目的：理解遗传算法的本质，学会用遗传算法解决TSP问题。