C语言程序课程设计报告-正文参考模板.doc

目 录1 前言12 需求分析12.1要求12.2任务12.3运行环境12.4开发工具13 概要设计与详细设计13.1系统流程图23.2访问流程图34 编码与实现44.1分析44.2具体代码实现65 课程设计总结15参考文献.15致 谢151 前言使用C语言编程，设计一个有效的算法，模拟蚂蚁觅食的过程。2 需求分析2.1要求（1）各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。（2）当一只找到食物以后，它会向环境释放一种信息素，吸引其他的蚂蚁过来，这样越来越多的蚂蚁会找到食物。（3）有些蚂蚁并没有象其它蚂蚁一样总重复同样的路，他们会另辟蹊径，如果令开辟的道路比原来的其他道路更短，那么，渐渐，更多的蚂蚁被吸引到这条较短的路上来。（4）最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复着。2.2任务（1）构建二维数组将每条路径的信息素量、相应路径的信息素增量和城市距离放入其中。（2）输入两个城市间的坐标，并得到两个城市间的最近距离。（3）画出所有模块的流程图；（4）编写代码；（5）程序分析与调试。2.3运行环境（1）WINDOWS2000/XP系统（2）TurboC2.0编译环境2.4开发工具C语言3 概要设计与详细设计3.1系统流程图如图3.1所示。开始初始化各参数，输入城市坐标为各蚂蚁设置其固定的起始城市每只蚂蚁开始访问，并记录其访问的路径及长度和处在同一次迭代的其他蚂蚁路径相比，是否是最 优？将其存为系统求解结果Y更新路径上的信息素N迭代是否结束？NY是否对结果进行检验？用户进行测试检验Y结束N图3.1 系统流程图3.2访问流程图如图3.2所示。蚂蚁访问过程从起始城市出发，并将初始城市设为被访问选择一个未访问的城市，开始判断是否符合？NY计算其转移概率，用得出的概率赌轮盘方式选择候选路径访问该城市，并设置其为被访问Y所有城市是否访问完？出口N图3.2访问流程图4 编码与实现4.1分析程序开始运行，蚂蚁们开始从窝里出动了，寻找食物；他们会顺着屏幕爬满整个画面，直到找到食物再返回窝。其中，D点表示食物，A表示窝，白色块表示障碍物，+就是蚂蚁了。预期的结果：各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种信息素，吸引其他的蚂蚁过来，这样越来越多的蚂蚁会找到食物！有些蚂蚁并没有象其它蚂蚁一样总重复同样的路，他们会另辟蹊径，如果令开辟的道路比原来的其他道路更短，那么，渐渐，更多的蚂蚁被吸引到这条较短的路上来。最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复着。1、范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。 2、环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。 3、觅食规则：在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。 4、移动规则：每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。 5、避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。 6、播撒信息素规则：每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。图1图2假设蚂蚁每经过一处所留下的信息单位为1，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点得到了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而从ACD的路线往返了一趟，每一处的信息素为2个单位。其比值为2:1。寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD的路线上增只蚂蚁（2只），而ACD路线上仍然只有一只蚂蚁，再经过36个时间两条路线上的信息素单位积累为12和4，比值为3:1。若继续进行，则按信息素指导，最终选择ABD路线的蚂蚁会越来越多，选择ACD路线上的蚂蚁也就越来越少。同理可以得出整个大环境也是按照这种方式进行路线的选择的。这也就解释了（3）有些蚂蚁并没有象其它蚂蚁一样总重复同样的路，他们会另辟蹊径，如果令开辟的道路比原来的其他道路更短，那么，渐渐，更多的蚂蚁被吸引到这条较短的路上来。最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复着。4.2具体代码实现写上源程序，并加上必要的注释。#include #include #include #include #define N 6 /*城市的数目*/#define M 48 /*蚂蚁的数目*/double inittao=1; /*初始信息素量*/double taoNN; /*每条路径的信息素量*/double detataoNN; /*相应路径的信息素增量*/double distanceNN; /*保存城市距离的数组*/double yitaNN; /*启发函数，一般初始其值为*/int tabuMN; /*禁忌表，tabuij=1表示蚂蚁i已经走过了j城市*/int routeMN; /*保存蚂蚁k的路径的数组为routekN */int i,j,k; /*循环变量*/double solutionM; /*蚂蚁k访问的路径的长度为solutionk*/int BestRouteN; /*当前最优的访问路径序列*/double BestSolution=10000000; /*当前最优的访问路的长度*/int aa=1;int NcMax;double alfa,beta,rou,Q;/* alfa是信息启发式因子，表示轨迹的相对重要性,其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间的协作性越强。beta是期望启发式因子，表示能见度?其值越大，则该状态转移概率越接近于贪心规则。rou是信息残留因子，Q为信息素强度，用于计算蚂蚁留在路径上的信息量*/int coordinateN2; /*城市的坐标,由用户输入*/int jianyan(int a,int n) /*用于检验用户输入的路径序列数组是否合法*/for(i=0;in-1;i+) /*判断数组的元素是否有重复*/for(j=i+1;jn;j+)if(ai = aj)k=0;break;elsek=1;if(jn)break;j=1;for(i=0;i=n)j=0;break;return k*j;int zjianyan(int a2,int n) /*判断用户输入的城市坐标是否有相同*/for(i=0;in-1;i+)for(j=i+1;jn;j+)if(ai0 = aj0&ai1 = aj1)k=0;break;elsek=1;if(jn)break;return k;void Intial()doprintf(please input the coordinate of cities:n);for(i = 0;i N;i+)for(j = 0;j 2;j+)scanf(%d,&coordinateij);aa=zjianyan(coordinate,N);if(aa=0)printf(Error!Please input again!n);while(aa=0);void initparameter(void) /*初始化各参数*/ alfa=1.0; beta=5.0; rou=0.9; Q=100;NcMax=250; double EvalueSolution(int a)/*评估路径，测试路径长度*/ double dist=0; for(i=0;iN-1;i+) dist+=distanceaiai+1; dist+=distanceaia0; /*循环到最后要返回起点，形成回路*/return dist; void dotest(void) /*测试结果准确性*/int rp;int testN;dorp = 0;printf(make a test: n);dofor(i=0;iN;i+)scanf(%d,&testi);aa=jianyan(test,N);if(aa=0)printf(Error!Please input again!n);while(aa=0);printf(the result of test is %4f n,EvalueSolution(test);printf(would you want to continue?(1 for yes and 0 for no):);scanf(%d,&rp);while(rp=1);void main()int NC=0;Intial();initparameter();for(i=0;iN;i+) for(j=i+1;jN;j+) distanceji=sqrt(pow(coordinatei0-coordinatej0,2)+pow(coordinatei1-coordinatej1,2);distanceij=distanceji; for(i=0;iN;i+) for(j=0;jN;j+) taoij=inittao; if(j!=i) yitaij=1/distanceij; for(k=0;kM;k+) for(i=0;iN;i+) routeki=-1; srand(time(NULL); for(k=0;kM;k+) routek0=k%N; /*设置初始城市*/tabukroutek0=1; /*设置初始城市被访问标记*/ do int s=1; double partsum; /*为方便计算转移概率而设的变量,本身没有实际意义*/double pper; /*转移概率*/double drand; while(sN) for(k=0;kM;k+) int jrand=rand()%3000; /*jrand是随机生成，不一定要3000，其他数字也可，另外需要保证drand=jrand/3001.0; drand比1要小，故这里除以3001*/partsum=0; pper=0; for(j=0;jN;j+) /*根据概率函数计算蚂蚁的转移概率*/ if(tabukj=0) partsum+=pow(taorouteks-1j,alfa)*pow(yitarouteks-1j,beta); /*routeks-1表示蚂蚁k第s-1步走到的城市，s=1表示蚂蚁从初始城市出发 taorouteks-1j表示蚂蚁k经过的前一个城市到下一个没被访问的城市j的信息量*/ for(j=0;jdrand)break; tabukj=1; /*禁忌表置访问标志*/routeks=j; /*保存蚂蚁k的第s步经过的城市*/ s+; for(i=0;iN;i+) for(j=0;jN;j+)detataoij=0; for(k=0;kM;k+) /*计算每个蚂蚁经过路径的长度，保存到当前代最好的路径及其长度*/ solutionk=EvalueSolution(routek); if(solutionkBestSolution) BestSolution=solutionk; for(s=0;sN;s+) BestRoutes=routeks; for(k=0;kM;k+) /*计算各个路径上的信息素增量*/ for(s=0;sN-1;s+) detataorouteksrouteks+1+=Q/solutionk; detataoroutekN-1routek0+=Q/solutionk; for(i=0;iN;i+) /*更新路径上的信息素*/for(j=0;jN;j+) taoij=rou*taoij+detataoij; if(taoij20)taoij=20; for(k=0;kM;k+) /*将蚂蚁的路径再重新置空,为下一次循环做准备*/for(j=1;jN;j+) /*注意起始城市，即j=0没有被清空*/ tabukroutekj=0; routekj=-1; NC+; while(NCNcMax); printf(*-*n);printf(the initialized parameters of ACA are as follows:n);printf(alfa=%.1f, beta=%.1f, rou=%.1f, Q=%.1f n,alfa,beta,rou,Q);printf(the best route is:);for(i=0;iN;i+) printf(%d ,BestRoutei); printf(n);printf(the shortest length of the path is:%2f n,BestSolution);printf(*-*n);system(PAUSE);dotest();程序提示输入信息程序运行结果5 课程设计