《蚁群算法课程设计报告(共37页).doc》由会员分享，可在线阅读，更多相关《蚁群算法课程设计报告(共37页).doc（37页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上 计算机学院计算机科学与技术专业程序设计综合课程设计报告 （2010/2011学年 第一学期）学生姓名： 学生班级： 学生学号： 指导教师： 2011年1月8日蚁 群 算 法蚁群算法求解问题目录专心-专注-专业第一章 课程设计目的和要求1.1 程序设计目的学习C+程序设计不能满足于“懂得了”，满足于了解了语法和能看懂书上的程序，而应当掌握程序设计的全过程，即能独立编写出源程序，独立上机调试程序，独立运行程序和分析结果。设计C+的初衷是为了方便开发大型程序，虽然现在还没接触大型程序，更不可能编写出能供实际应用的大型程序，而只能接触比较简单的程序。但通过学习C+课程，对C
2、+有比较全面的 、然而是初步的认识，为今后进一步学习和应用C+打下良好的基础。学习程序设计的目的是：加深对讲授内容的理解，尤其是一些语法的规定，光靠课堂讲授，既枯燥无味又难以记忆，但它们是很重要的，通过设计来掌握语法规则是有效的方法。在程序设计中，可以了解运行一个C+程序需要哪些必要的外部条件（例如硬件配置、软件配置。学会上机调试程序。也就是善于发现程序中的错误，并且很快地排除这些错误，使程序能正常运行。1.2 程序设计要求利用蚁群算法求解TSP问题。程序中给出51个城市的坐标为：X轴：37,49,52,20,40,21,17,31,52,51, 42,31,5,12,36,52,27,17,
3、13,57, 62,42,16,8,7,27,30,43,58,58, 37,38,46,61,62,63,32,45,59,5, 10,21,5,30,39,32,25,25,48,56, 30.轴：52,49,64,26,30,47,63,62,33,21, 41,32,25,42,16,41,23,33,13,58, 42,57,57,52,38,68,48,67,48,27, 69,46,10,33,63,69,22,35,15,6, 17,10,64,15,10,39,32,55,28,37, 40.求出最短的旅行距离。求出如何旅行城市，求出每个城市是第几个旅行能使旅行距离最优。第二
4、章 程序设计内容2.1关于蚁群智能和昆虫学家们在研究类似蚂蚁这样的视盲动物如何沿最佳路线从其巢穴打达食物源的过程中发现，蚂蚁与蚂蚁之间最重要的通信媒介就是他们在移动过程中所释放的特有的分泌物信息素，当一个孤立的蚂蚁随机移动时，它能检测到其他同伴所释放的信息素，并沿着该路线移动，同时又释放自身的信息素，从而增强了该路线上的信息素数量，随着越来越多的蚂蚁通过该路线，一条最佳的路径就会逐渐形成。已经总结出来蚂蚁行为具有以下如下一些显著特征：能够察觉前方小范围区域内的状况，并判断是否有食物或其他同类的信息素轨迹；能够释放出两种类型的信息素：“食物”信息素和“巢穴”信息素；仅当携带食物或是将食物带回到巢
5、穴时才会释放信息素；所释放的信息素数量会随着其不断移动而逐步减少。并且蚂蚁的运动还遵循以下简单规则：按随机方向离开巢穴，仅受其巢穴周围的信息素影响；按随机方向移动，仅受其周围“食物”信息素的影响；当察觉到“食物”信息素轨迹时，将沿着强度最大的轨迹运动；一旦找到食物，将取走部分，并开始释放“食物”信息素；移动过程中，将受到“巢穴”信息素的影响；一旦回到巢穴，将放下食物，并开始释放“巢穴”信息素。自然界中的蚂蚁没有视觉，既不知道像何处去寻找和获得食物，也不知道发现食物后如何返回巢穴，它们仅仅依靠于同类散发在周围环境中的特殊物质信息素的轨迹，从而决定自己何去何从。蚂蚁还是有能力找到从其巢穴到食物源的
6、最佳路径，甚至在该路线上放置障碍物之后，它们让然能很快重新找到新的最佳路径。蚁群算法就是模拟蚂蚁的这种特性，来找到优化最佳的路径（如图2-1）蚂蚁在相同的时间区间内，短的路线会有更多的机会被选择。食物障碍物巢穴图2-1 TSP问题可以描述为：有N个城市，一售货员从起始城市出发，访问所有的城市一次，最后回到起始城市，求最短路径。TSP问题除了具有明显的实际意义外，有许多问题都可以归结为TSP问题。2.2解决的问题用蚁群算法来解决在旅行商旅中有51个城市的最优路径，并求出如何行走才是距离最短和城市走的顺序。第三章 详细设计说明3.1模块描述本程序共有void addcity(); void Cle
7、ar(); void UpdateResult(); void move(); void move2last(); void shucout()；void project:initmap()；void project:GetAnt()；void project:StartSearch() ；void project:UpdateTrial() 。子程序模块和int main()一个主程序。void shucout()显示欢迎信息模块 void ant:move2last() 只剩下一个城市没走过时才调用，直接移动到最后一个城市void ant:Clear() 清空数据，蚂蚁周游完各个城市后，要
8、重新开始周游各个城市时调用 void ant:addcity(int city) 增加一个城市到走过的城市数组中，并改变没走过的城市数组中的标志 void ant:UpdateResult() 计算周游完城市后，走过的路径长度 void ant:move() 移动到下一个城市 void project:initmap() 初始化 void project:GetAnt() 初始化随机种子 void project:StartSearch() 开始寻找最好的解决方法void project:UpdateTrial() 更新环境信息素 ，每只蚂蚁周游完城市后才更新 3.2性能本程序按原理来说迭代次
9、数越大，程序得出的结果越精确，但当数值超过1000以后，结果基本不变。要求城市数量 / 蚂蚁数量 = 1.5左右 dbMin=.0; 叠迭中的最小路径长度。3.3输入项和输出项本程序的需要输入项有：需要输入迭代次数，就是搜索次数 N_IT_COUNT 蚂蚁数量 N_ANT_COUNT = 34（一般取值原则为：城市数量 / 蚂蚁数量 = 1.5左右 ）城市数量 N_CITY_COUNT = 51; 总的信息素 DB_Q=100; 信息素重要程度 DB_ALPHA=1; 引导蚂蚁往信息素大的地方走的数DB_BETA=3; 环境信息素挥发速度 DB_ROU=0.5。城市坐标数据int x_Ary5
10、1= 37,49,52,20,40,21,17,31,52,51, 42,31,5,12,36,52,27,17,13,57, 62,42,16,8,7,27,30,43,58,58, 37,38,46,61,62,63,32,45,59,5, 10,21,5,30,39,32,25,25,48,56, 30 ; int y_Ary51= 52,49,64,26,30,47,63,62,33,21, 41,32,25,42,16,41,23,33,13,58, 42,57,57,52,38,68,48,67,48,27, 69,46,10,33,63,69,22,35,15,6, 17,10,
11、64,15,10,39,32,55,28,37, 40 ; 输出项：优化后旅行的最短距离（图3-1）图3-1每个城市走的顺序（图3-2）图3-23.4算法本程序是基于蚁群算法求解问题，设为城市，之间的几何距离，。设 表示时刻位于城市的蚂蚁的个数，蚂蚁总数，表示时刻在 连线上残留的信息量，初始时刻各条路径上的信息量为（为常数）。用参数表示信息量的保留度，则经过个时刻后，路径 上的信息量根据下式作调整： 表示第只蚂蚁在本次循环中留在路径 上的信息量，表示本次循环所有经过的蚂蚁留在 上的信息量。 定义。蚂蚁（，）在运动过程中，表示在时刻蚂蚁由位置转移到位置的概率： 我们用tabuN_CITY_COU
12、NT记录蚂蚁目前已经走过的城市集合，AllowedCityN_CITY_COUNT表示蚂蚁下一步允许选择的城市集合，它等于全部的城市集合除去第只蚂蚁已走过的集合tabuN_CITY_COUNT。 定义为第只蚂蚁在本次循环中走过的路径和。 用蚁群算法解决问题是一个递推过程 ，当时，将蚂蚁放在各城市，设定每条路径上的信息量初值，每只蚂蚁根据公式决定的概率从城市到城市。表示曾经有多少蚂蚁经过路径；说明较近的城市有更大的可能性被选中。用来控制两者对蚂蚁选择的影响力程度。经过一个循环后，根据公式；计算更新每条路径的信息量。将所有的复原，最后求出本次循环的最短路径。这个过程不断重复，直到所有的蚂蚁都选择同
13、样的路径，或者循环次数达到预先设定的最高次数。解决个城市的问题算法设计如下：初始化： 设定，循环计数器，对每条路径设定初始信息量,将只蚂蚁放在个城市上（为了使问题简化，设定）。设定集合的索引，对从到，把第只蚂蚁放在起始位置，对应的设定集合重复下面的步骤，直到集合满为止（这一步将重复次）：设定；对从到，根据公式确定的概率，选择下一步移动的目标城市在时间时，第只蚂蚁所在的城市是;将第只蚂蚁移到城市；把加入到集合中。对从到：将第只蚂蚁从移动到；计算第只蚂蚁所走过的路程和，并更新最小路径；对每条路径：； 对每条路径根据计算；设定；设定；对每条路径，设定。如果，则清空所有的集合转到第二步；否则，得出最短
14、的路径。在这儿我们用的是算法，这种算法，每当结束一个循环后，根据公式 计算。3.5流程逻辑开始初始化设定集合,对每只蚂蚁=计算蚂蚁所走过的路程和更新最小路径对每条路径计算设定acbacbNY清空所有的集合得出最短路径N集合满Y结束图3-53.6接口程序中的子函数：void addcity(int city); void Clear(); void UpdateResult(); void move(); void move2last(); void shucout();void UpdateTrial(); void initmap(); void GetAnt(); void StartSe
15、arch(); 子函数的接口void ant:Clear() void ant:move2last()void addcity(i)void addcity(i)图3-2图3-1void project:GetAnt()void ant:move() void addcity(i)void addcity(i)图3-4 图3-3主函数void project:StartSearch() void shucout();void ant:move() project TSPvoid ant:move2last()TSP.GetAnt()void UpdateTrial();TSP.StartSea
16、rch()void Clear(); 图3-6图3-53.7数据存储说明本程序没有数据存储，每次需要换叠代数时重新运行本程序。3.8注释设计 注释可以让程序更具有可读性，本程序在每个数据类型后都有注释（如图3-1）；在每个不易理解的语句中也有注释设计（如图3-2，3-3）；在每个子程序中都加入注释（如图3-4,3-5）图3-1图3-2图3-3图3-4图3-53.9限制条件 在操作系统和条件下运行本程序。3.10测试计划打开程序后会出现一个欢迎界面，输入迭代次数后运行程序。先令城市数分别为1,2,3然后得到的结果与。进行比较，求出最优接合最优路线，进行比较。来测试程序运行结果的对错。第四章 程序
17、使用说明本程序操作简单易于上手，已经给出51坐城市坐标求最优距离，和每个城市旅行的顺序。只需要要输入迭代数。欢迎界面，输入迭代次数。图4-当次数为时：图4-2图4-3图4-4图4-5图4-6图4-7图4-8图4-9图4-10最后运行结果：图4-11The shortest tours is : 430.下面的数字是51个城市所旅行的顺序，只要按照程序给出的城市顺序数进行旅行，所走的距离是最优的为430如果想更换蚂蚁数量和城市数量（图4-12）以及城市的坐标（图4-13）只需把源代码中数和坐标更改就可以。图4-12图4-13第五章 程序设计心得与体会通过一个学期对程序设计的学习，对于的基本的理论
18、知识有了点了解，初步形成了基本的语言程序设计的思想，但对于大型程序的编程还是不了解。在为期三周的课程设计，检查这一个学期来计算机语言的学习成果，也是为了让我们进一步掌握和熟练地运用它，与此同时，也能够让我们认清自己在学习方面的不足之处和薄弱环节，并加以弥补和巩固。通过对蚁群算法程序设计，不仅让我巩固了知识而且还让我了解了关于蚁群算法的很多知识，着对于我来说，是不小的收获，以前根本就不知道蚁群算法，现在有了基本的了解，感觉自己收获不少。经过这次设计我体会颇多，我懂得了用Microsoft Visual C+ 6.0对程序进行调试，纠正错误，我加强了对程序设计这门课程的认识，并且复习了自己以前学习
19、到的知识，自己的逻辑思考能力也提高不少。这些都使得我对计算机语言的学习有了更深入的认识！总之，通过这次课程设计，我收获颇丰，相信会为自己以后的学习和工作带来很大的好处。最重要的还是激发了我编程和对算法的兴趣和热情，让我从一个只懂理论变成了能做一些小型程序。整体地评价这次课程设计，我认为收获很大，正如上面所说的那样，通过课程设计，既复习了以前的旧知识，又学到了一些新的知识。像应用程序的设计和创建，经历了平时在课堂和考试中不会出现的难题和考验。而这些问题，又都是课本上很少提到的、更深一层的实践与知识相结合的问题，这并不是我们平时只靠课本，就可以轻易解决的。所以，锻炼了我们面对难题，学会用已掌握的知
20、识去解决具体问题的能力，进一步培养了独立思考问题和解决问题的能力。特别是学会了在Visual 中如何调试程序的方法。当然，老师的指导和同学的帮助也是不可忽视的，他们给了我许多提示和帮助，教会了我编译复杂程序的方法。总而言之，这次程序设计实践让我收获很大。附录一：参考文献 谭浩强著 程序设计.北京：清华大学出版社；1999谭浩强著 程序设计题解与上机指导.北京：清华大学出版社；1999 马良朱刚宁爱兵著蚁群优化算法；2008蚁群算法贴吧。附录二：程序清单/ ANT.cpp : 定义控制台应用程序的入口点。 /城市坐标数据直接写在代码里面，使用的是eil51.tsp中的数据 #include #i
21、nclude #include using namespace std; const int N_ANT_COUNT = 34; /蚂蚁数量，一般取值原则为：城市数量 / 蚂蚁数量 = 1.5左右 const int N_CITY_COUNT = 51; /城市数量 int N_IT_COUNT; /= 5000; /迭代次数，就是搜索次数 const double DB_Q=100; /总的信息素 const double DB_ALPHA=1; /信息素重要程度 const double DB_BETA=3; /这个数越大，则蚂蚁往信息素大的地方走的概率就越大 const double D
22、B_ROU=0.5; /环境信息素挥发速度 int besttourN_CITY_COUNT;/最佳路径列表 /获得指定范围内的一个随机数 double rnd(int low,double uper) double p=(rand()/(double)RAND_MAX)*(uper)-(low)+(low); return (p); ; /获得指定上限范围内的一个随机数 int rnd(int uper) return (rand()%uper); ; /tsp地图信息，包含了信息素，城市距离，和信息素变化矩阵 class GInfo public: double m_dDeltTrialN
23、_CITY_COUNTN_CITY_COUNT; /临时保存信息素，更新环境信息素的时候使用，每只蚂蚁周游完各个城市后开始计算 double m_dTrialN_CITY_COUNTN_CITY_COUNT; /城市间的信息素，就是环境信息素 double distanceN_CITY_COUNTN_CITY_COUNT; /城市间距离 ; GInfo Map; /定义蚂蚁类 class ant private: int ChooseNextCity(); /选择下一个城市 double probN_CITY_COUNT; /临时变量数组，选择下一个城市的时候，保存各个城市被选中的概率值 in
24、t m_nCityCount; /记录蚂蚁已经走过的城市数目 int AllowedCityN_CITY_COUNT;/没有走过的城市，数组索引对应城市编号 public: double m_dLength; double m_dShortest; int tabuN_CITY_COUNT; /记录走过的城市，里面存的是城市的编号，数组索引表示走的顺序。 public: ant(); void addcity(int city); void Clear(); void UpdateResult(); void move(); void move2last(); void shucout();
25、/只剩下一个城市没走过时才调用，直接移动到最后一个城市 void ant:move2last() for(int i=0;iN_CITY_COUNT;i+) if (AllowedCityi=1) addcity(i); break; /清空数据，蚂蚁周游完各个城市后，要重新开始周游各个城市时调用 void ant:Clear() m_dLength=0; for(int i=0; iN_CITY_COUNT;i+) probi=0; AllowedCityi=1; i=tabuN_CITY_COUNT-1; /用最后一个城市作为出发城市 m_nCityCount=0; addcity(i);
26、 /初始化 ant:ant() m_dLength=m_dShortest=0; m_nCityCount=0; for(int i=0;iN_CITY_COUNT;i+) AllowedCityi=1; probi=0; /增加一个城市到走过的城市数组中，并改变没走过的城市数组中的标志 void ant:addcity(int city) /add city to tabu; tabum_nCityCount=city; m_nCityCount+; AllowedCitycity=0; int ant:ChooseNextCity() /更新概率的路径选择 /选择一条路径,从 tabum_
27、nCityCount-1到下一个 int j=10000; double temp=0.0; int curCity=tabum_nCityCount-1; /当前走到那个城市了 /先计算当前城市和没有走过的城市，两两之间的信息素的总和 for (int i=0;iN_CITY_COUNT;i+) if (AllowedCityi = 1) temp=temp+pow(1.0/Map.distancecurCityi),DB_BETA)*pow(Map.m_dTrialcurCityi),DB_ALPHA); /计算没有走过的城市被选中的概率 double sel=0; for (i=0;iN
28、_CITY_COUNT;i+) if (AllowedCityi = 1) probi=pow(1.0/Map.distancecurCityi),DB_BETA)*pow(Map.m_dTrialcurCityi),DB_ALPHA)/temp; sel+=probi; else probi=0; /下面的操作实际上就是遗传算法中的轮盘选择 double mRate=rnd(0,sel); double mSelect=0; for ( i=0;i=mRate) j=i; break; /这种情况只有在temp=0.0的时候才会出现 if (j = 10000) for (i=0;iN_CI
29、TY_COUNT;i+) if (AllowedCityi = 1) j=i; break; return j; /计算周游完城市后，走过的路径长度 void ant:UpdateResult() / 修正旅行距离for(int i=0;iN_CITY_COUNT-1;i+) m_dLength+=Map.distancetabuitabui+1; m_dLength+=Map.distancetabuN_CITY_COUNT-1tabu0; /最后城市和开始城市间的距离 /移动到下一个城市 void ant:move() /the ant move to next town and add
30、town ID to tabu. int n=ChooseNextCity(); addcity(n); class project public: double m_dLength; ant antsN_ANT_COUNT; public: project(); void UpdateTrial(); void initmap(); void GetAnt(); void StartSearch(); ;/更新环境信息素 /这里采用的是 ANT-CYCLE 模式，即每只蚂蚁周游完城市后才更新 void project:UpdateTrial() /calculate the changes
31、of trial information int m=0; int n=0; for(int i=0;iN_ANT_COUNT;i+) /计算每只蚂蚁在两两城市间留下的信息素，蚂蚁走过的路径越短，留下的信息素数值越大 for (int j=0;jN_CITY_COUNT-1;j+) /计算两两城市间的信息素 m=antsi.tabuj; n =antsi.tabuj+1; Map.m_dDeltTrialmn+=DB_Q/antsi.m_dLength; Map.m_dDeltTrialnm+=DB_Q/antsi.m_dLength; /最后城市到开始城市间的信息素 m=antsi.tabu
32、N_CITY_COUNT-1; n =antsi.tabu0; Map.m_dDeltTrialmn+=DB_Q/antsi.m_dLength; Map.m_dDeltTrialnm+=DB_Q/antsi.m_dLength; /最新的环境信息素 = 消失掉的信息素 + 新留下的信息素 for (int a=0;aN_CITY_COUNT;a+) for (int j=0;jN_CITY_COUNT;j+) Map.m_dTrialaj=(DB_ROU*Map.m_dTrialaj+Map.m_dDeltTrialaj ); Map.m_dDeltTrialaj=0; /初始化 void
33、project:initmap() for(int i=0;iN_CITY_COUNT;i+) for (int j=0;jN_CITY_COUNT;j+) Map.m_dTrialij=1; Map.m_dDeltTrialij=0; project:project() /initial map initmap(); m_dLength=10e9; struct city int num; int x; int y; ccN_CITY_COUNT; /城市坐标数据来自国际通用的数据 eil51.tsp int x_Ary51= 37,49,52,20,40,21,17,31,52,51, 4
34、2,31,5,12,36,52,27,17,13,57, 62,42,16,8,7,27,30,43,58,58, 37,38,46,61,62,63,32,45,59,5, 10,21,5,30,39,32,25,25,48,56, 30 ; int y_Ary51= 52,49,64,26,30,47,63,62,33,21, 41,32,25,42,16,41,23,33,13,58, 42,57,57,52,38,68,48,67,48,27, 69,46,10,33,63,69,22,35,15,6, 17,10,64,15,10,39,32,55,28,37, 40 ; for (
35、int i=0;iN_CITY_COUNT;i+) cci.x=x_Aryi; cci.y=y_Aryi; cci.num=i; /计算两两城市间距离，需要进行四舍五入取整 /eil51.tsp的最短路径426，是按四舍五入取整后的距离算出来的。 for(int b=0;bN_CITY_COUNT;b+) for (int j=0;jN_CITY_COUNT;j+) Map.distancebj=(int)(sqrt(pow(ccb.x-ccj.x),2)+pow(ccb.y-ccj.y),2)+0.5); void project:GetAnt() /初始化随机种子 srand(unsign
36、ed)time(NULL); /为每只蚂蚁随机分配一个出发城市 int city=0; for (int i=0;iN_ANT_COUNT;i+) city=rnd(N_CITY_COUNT); antsi.addcity(city); void project:StartSearch() /begin to find best solution int max=0;/every ant tours times double temp; int temptourN_CITY_COUNT; double dbMin=0.0; while (max N_IT_COUNT) dbMin=.0; /本
37、次叠迭中的最小路径长度 for(int j=0;jN_ANT_COUNT;j+) for (int i=0;iN_CITY_COUNT-1;i+) antsj.move(); for(int c=0;cN_ANT_COUNT;c+) antsc.move2last(); antsc.UpdateResult(); /计算路径总长度 /find out the best solution of the step and put it into temp temp=ants0.m_dLength; for (int t=0;tN_CITY_COUNT;t+) temptourt=ants0.tab
38、ut; for(int d=0;dantsd.m_dLength) temp=antsd.m_dLength; for (int t=0;tantsj.m_dLength) dbMin=antsj.m_dLength; if (tempm_dLength) m_dLength=temp; for (int t=0;tN_CITY_COUNT;t+) besttourt=temptourt; printf(%d : %.0fn,max,m_dLength); UpdateTrial(); /全部蚂蚁遍历各个城市后，更新环境信息素 for(int e=0;eN_ANT_COUNT;e+) /再搜索一次 antse.Clear(); max+; printf(The shortest toure is : %fn,m_dLength); for (int t=0;tN_CITY_COUNT;t+) printf( %d ,besttourt); void shucout()cout*endl;cout*欢迎使用本程序*endl;cout*