智能算法实验报告

1、人工智能实验一智能算法实验一蚂蚊算法实验目的：理解蚂蚁算法的本质，会编写蚂蚁算法来求解TSP问题。二、实验原理：蚂蚁在寻找食物源时，能在其走过的路上释放一种特殊的分泌物一一信息素(随着时间 的推移该物质会逐渐挥发)，后来的蚂蚁选择该路径的概率与当时这条路径上该物质的强度 成正比。当一定路径上通过的蚂蚁越来越多时，其留卜的信息素轨迹也越来越多，后来蚂蚁 选择该路径的概率也越高，从而更增加了该路径的信息素强度。而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈机制，通过这种正反馈机制，蚂 蚁最终可以发现最短路径。特别地，当蚂蚁巢穴与食物源之间出现障碍物时，蚂蚁不仅可以 绕过障碍物，而且通过蚁群信

2、息素轨迹在不同路径上的变化，经过一段时间的正反馈，最终 收敛到最短路径上。三、实验内容：#include#include#includeusing namespace std;const int Maxlnt=(unsigned int)0 / 2;/double d55=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

3、RunNum;/运行次数double *d;/表示路径(i,j)之间的长度double *n;/边孤(i,j)的能见度(visibility),或称局部启发因子，一般取l/d表示路径(i,j) 之间的长度；double *t;/ii弧(i,j)的信息素轨迹强度(intensity)double I NITINFO;/初始的信息素值/double *deltaT;蚂蚊k于弧上(i,j)留下的单位长度轨迹信息素数量；double *P;蚂蚁k在结点的转移概率，j是尚未访问结点;int *tab;蚂蚁的禁忌表double MinSum;最短路径长度int *MinRoute;/最优路径double

4、a;信息素轨迹的相对重要性double b;边弧能见度的相对重要性double p;信息素轨迹的持久性(Evaporation)double Q;(轨迹数量)public:Ant(int Num,double position2):NodeNum(Num)srand(time(NULL);AntNum=50;p=0.8;a=l;/(l2)b=2;/(25)P=get2DMemory(P,NodeNum);t=get2DMemory(t,NodeNum);n=get2DMemory(n,NodeNum);d=get2DMemory(d,NodeNum);tab=get2DMemory(tab,A

5、ntNum/NodeNum);posToDistance(position);MinSum=Maxlnt;MinRoute=new intNodeNum;MaxRunNum=200;RunNum=0;INITINFO=200;Q=2000;void posToDistance(double pos2)for(int i=0;iNodeNum;i+)for(int j=0;jNodeNum;j+)dij=sqrt(posi0-posj0)*(posi0-posj0)+(posil-posjl)*(posil-posjl);void getMinRoute(int *CurrentRoute)fo

6、r(int i=0;iNodeNum;i+)MinRouteiJ=CurrentRoutei;double getPossiblity(int i,int jjnt k,int cNode)if(i=j) return 0;else (if(inTab(j,k,cNode)=true)return 0;return Pow(tij,a)*Pow(nij/b)/sumPossiblity(i,k/cNode);bool inTab(int sjnt kJ nt cNode)for(int m=0;mcNode;m+)if(s=tabkm)return true;return false;doub

7、le sumPossiblity(int i,int kjnt cNode)double sum=0;for(int s=0;sNodeNum;s+)(if(i=s) continue;if(inTab(s,k,cNode)=true) continue;sum+=Pow(tis,a)*Pow(nis/b);return sum;void updatelnfomation()for(int k=0;kAntNum;k+)(double sum=sumDistance(k);if(sumMinSum)(MinSum=sum;getMinRoute(tabk);for(int i=0;iNodeN

8、um;i+)for(int j=0;jNodeNum;j+)(if(i=j) continue;tiU=tiU*P；for(i=0;iNodeNum;i+)ttabkitabk(i+l)%NodeNum+=Q/sum;double sumDistance(int k)double sum=0;for(int i=0;iNodeNum;i+)sum+=dtabkitabk(i+l)%NodeNum;return sum;void start()init();run();print();void run()while(RunNumMaxRunNum)(initNode();起点城市moveNext

9、();updatelnfomation();RunNum+;void init()for(int i=0;iNodeNum;i+)for(int j=0;jNodeNum;j+)(if(i=j)nii=0；elseniU=VdiUJ;for(i=0;iNodeNum;i+)for(int j=0;jNodeNum;j+)tij=INITINFO;)void initNode()for(int k=0;kAntNum;k+)int Node=int(double)rand()/RAND_MAX)*NodeNum);if(Node=NodeNum)Node=NodeNum-l;tabk0=Node

10、;int randlnt(int max)int node=int(max)*(double)rand()/RAND_MAX);if(node=max)node=max-l;return node;int greedy(int kJ nt start=O)if(start=O)(tabk0=randlnt(NodeNum);int i=start;double Distance=Maxlnt;int Dlndex=0;for(int j=0;jNodeNum;j+)bool have=false;for(int m=0;mi;m+)if(tabkm=j)have=true;break;if(h

11、ave) continue;if(dil亦Distance)Distance=di-lj;Dlndex=j;return Dlndex;void print()cout最优路径(城市号):endl;for(int i=0;iNodeNum;i+)coutMinRoutei,t;coutendl;cout最短距离:MinSumendl;int getNextNode(int last,double possiblityjnt kjnt cNode)int i=0;while(iNodeNum)(double GetPossiblity=getPossiblity(lastJ/k/cNode);i

12、f(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 Ant Num; k+)for(int i=l;iNodeNum;i+)tabki=getNextNode(tabki-l,(double)rand()/RAND_MAX,k,i)； double *get2DMemory(

13、double *p,int n)p=new double*n;for(int i=0;in;i+) pi=new doublen;return p;)int *get2DMemory(int *p,int mjnt n)p=new int*m;for(int i=O;im;i+)pi=new intn;(return p;double Pow(double a,int n)double m=l;for(int i=0;in;i+)m=m*a;return m;void delete2DMemory(int *a)for(int i=O;iAntNum;i+)delete ai;delete a

14、;void delete2DMemory(double *a)for(int i=0;iNodeNum;i+) delete ai;delete a;Ant()delete2DMemory(tab);delete2DMemory(d);delete2DMemory(n);delete2DMemory(t);delete2DMemory(P);delete MinRoute;void main()(double position312=(1304,2312,3639,1315,4177,2244,3712,1399,3488,1535,3326,1556,3238,1229)44196,1004

15、),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

16、时的结果：(城市号从0开始)最优路径城市号)二1311113111210541531789622181621?2120192324252726293028014最短距离=15665.3n D:A工智育gDebug蚂蚁算法.exen C最优路径城市号：1311121022154563198?21?16182324192021252726293028014最矩距离：156?S.S” D:A工智能Deb u g蚂蚁算法.exen最优路径c城币号；16221531?89645101213140282930262725242319202117218最想距离M742.5实验二遗传算法一、实验目的：理解遗传

17、算法的本质，学会用遗传算法解决TSP问题。一、实验原理:遗传算法类似于自然进化，通过作用于染色体上的基因寻找好的染色体来求解问题。与 自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染 色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。在遗 传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始群体：通 过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗 传操作，经过遗传操作后的个体集合形成下一代新的种群。对这个新种群进行下一轮进化。 这就是遗传算法的基本原理。二、实验内容：#include

18、#include#includeusing namespace std;const int Maxlnt=(unsigned int)0 / 2;class GAprivate:int NodeNum;/节点个数int CNum;/染色体个数double MaxSum;最短路径长度int *MaxRoute;最优路径int MaxRunNum;/最大运行次数int RunNum;/运行次数static double *d;表示路径(i,j)之间的长度int *tab;/所有染色体存放的路径表 double *AF;double totalFitness;/ 总的适应度double Pm;变异概

19、率double Pc;交叉概率public:GA(int Num,double position2):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=new intNodeNum;AF=new doubleCNum;)void select()(int* temp

20、;int leave=0;temp=get2DMemory(temp,CNum,NodeNum);采取精英策略for(int i=O;iCNumA;i+)copyArray(MaxRoute,tempi);for(i=CNumy4;iCNum;i+)double possiblity=(double)rand()/RAND_MAX;leave=leaveWhich(possiblity);copyArray(tableave,tempi);)delete2DMemory(tab);tab=temp;void delete2DMemory(int *a)(for(int i=0;iCNum;i+

21、)delete ai;delete a;void delete2DMemory(double *a)(for(int i=0;iNodeNum;i+)delete ai;delete a;void copyArray(int *ajnt *b)(for(int i=0;iNodeNum;i+)bi=ai;void cross()(交叉操作for(int k=O;kCNum-l;k+)(double rate=(double)rand()/RAND_MAX;if(rate8*Pm/9)int begin=randlnt(NodeNum);取point和point.next进行交叉，形成新的两个染

22、色体 for(int i=begin;iNodeNum;i+)int fir,sec;for(fir=0;tabkfir!=tabk+li;fir+);for(sec=0;tabk+lsec!=tabki;sec+);两个基因互换exchange(tabki,tabk+li);消去互换后重复的那个基因tabkfir=tabk+li;tabk+lsec=tabki;else if(rate0) reverse(k-l);int node=randlnt(NodeNum);greedy(k,node);选择交叉节点，将结点后面的部分用贪婪算法处理 int leaveWhich(double pos

23、siblity)(int i=0;while(iCNum)(if(possiblity=getPossiblity(i)return i;elsepossiblity=possiblity-getPossiblity(i);i+；return CNum-1;void calFitness()(for(int k=O;kMaxSum)MaxSum=A;getMaxRoute(tabk);)totalFitness=sumPossiblity();double getPossiblity(int k)return AFk/totalFitness;void getMaxRoute(int *Cur

24、rentRoute)(for(int i=0;iNodeNum;i+)MaxRoutei=CurrentRoutei;double sumPossiblity()(double sum=0;for(int k=0;kCNum;k+)(sum=sum+AFk;return sum;double adjustFunc(int k)(return 1.0/sumDistance(k);double sumDistance(int k)(double sum=0;for(int i=0;iNodeNum;i+)sum+=dtabkitabk(i+l)%NodeNum;return sum;double

25、 sumDistance()(double sum=0;for(int i=0;iNodeNum;i+)sum+=dMaxRouteiMaxRoute(i+l)%NodeNum;return sum;void print()coutn最优路径(城市号):”endl; for(int i=0;iNodeNum;i+)coutMaxRoutei,t;coutendl;cout最短距离:,sumDistance()endl;void start()(initNodeNum();/ 起点城市run();print();void run()(while(RunNumMaxRunNum)(calFitne

26、ss();select();cross();mutation();RunNum+;void mutation()for(int i=0;iPm) continue;else进行交换变异if(double)rand()/RAND_MAX0.5)(int start=randlnt(NodeNum);int end=randlnt(NodeNum);if(start=end)exchange(start,end);exchange(tabistart,tabiend);else进行部分反转变异int start=randlnt(NodeNum+l);int end=randlnt(NodeNum+

27、l);if(start=end)exchange(start,end);reverse。,start,end);(int randlnt(int max)int node=int(max)*(double)rand()/RAND_MAX);if(node=max)node=max-l;return node;void reverse (int kJ nt start=O,int end=-l)if(end=-l) end=NodeNum;if(start0 11 end=end) return;int *temp=new intNodeNum;for(int i=0;iNodeNum;i+)t

28、empi=tabki;for(i=start;iend;i+)tabkji=tempend+start-l-i;delete temp;void exchange(int &a,int &b)(int temp=a;a=b;b=temp;void initNodeNum()(for(int k=0;kCNum;k+)int i,j；for(i=0;iNodeNum;i+)int city= randlnt(NodeNum);检查有没有city bool exist=false; for(j=0;ji;j+)(己存在if(tabkj = city)i-;/停住，再次随机 exist=true;b

29、reak;)if(exist != true) tabki=city;)初始化节点，随机初始化void greedy(int kjnt start=O)(if(start=O)(tabk0=randlnt(NodeNum);for(int i=start+l;iNodeNum;i+)(double Distance=Maxlnt;int Dlndex=0;for(int j=0;jNodeNum;j+)bool have=false;for(int m=0;mi;m+)(if(tabkm=j)(have=true;break;if(have) continue;if(di-ljDistance)Distance=di-lj；Dlndex=j;)tabki=Dlndex;double *get2DMemory(double *pjnt n)(p=new double*n;for(int i=0;in;i+)pi=new doublen;)return p;int *get2DMemory(int *p,int mjnt