实验二蚁群算法

《人工智能》课程实验报告之二基于ACO/PSO的TSP问题求解班级:学号：姓名：成绩评定：评阅老师：日期：实验报告正文一、实验目的初步掌握ACO对旅行商问题（TSP）的设计与实现,加深对ACO算法的的理解。二、实验内容根据ACO算法原理，利用带权完全图G=（V，E）其中V={v1,v2,…,vn}是带有n=|V|个城市的集合，E是完全连接这些点的边的集合，来模拟n个城市的tsp问题，设计并编程实现一个城市的TSP最佳路径求解系统系统。三、实验所用智能算法基本原理与流程ACO算法可以直接应用到TSP中，ACO的构建图为G=(C,L)，为一个完全图，构建图与描述TSP实例的图形一致，也就是说C=V且L=E；问题的状态集合与所有可能的部分路径集合相对应；约束条件Ω为蚂蚁建立的路径必须是与城市标号的排列相对应的可行路径。AS算法有两个最主要的步骤及蚂蚁构建问题的解和信息素的更新。在AS中m只蚂蚁并行地构建TSP的路径。算法开始时，将m只蚂蚁放在随机选择出来的城市中。在路径构建过程中，每一只蚂蚁都按随机比例规则的概率行为选择规则来随机的选择下一个城市。当所有的蚂蚁都构建好路径之后，开始进行信息素的更新操作。先进行信息素的蒸发，所有边上的信息素按蒸发率ρ减少四、系统构成与程序设计ACO算法最重要的两个步骤是解的构建和信息素更新，除此之外，在算法中还要加入一些更新统计信息和判断终止条件的方法。另外在解的构建过程中也可以加入局部搜索以提高算法性能，但本次实验中没有加入局部搜索。算法总的框架如下：ACOFORTSP()1InitializeData()//初始化数据2while(terminate()==false)do//判断是否终止3ConstructSolutions()//解的构建4LocalSearch()//局部搜索5UpdatePheromone()//更新信息素6end-while解的构建算法如下：ConstructSolutions()1fork=1tom//1~5行初始化蚂蚁的记忆，把所有蚂蚁访问过的城市设2forI=1ton//为空3ant[k].visited[i]false4end-for5end-for6step1//6~11行，将所有蚂蚁随机地放到n个城市中7fork=1tom8rrandom[1,…,n]9ant[k].tour[step]r10ant[k].visited[r]true11end-for12while(stepn)//12~17行，并行的构建每只蚂蚁的解13stepstep+114fork=1tomdo15ChooseNextCity(k,step)16end-for17end-while18fork=1tom//18~21行，把每只蚂蚁最后一步设为起始城市建立回路19ant[k].tour[n+1]ant[k].tour[1]20ant[k].tourlengthComputeTourLength(k)21end-for信息素更新方法如下：UpdatePheromone()1Evaporate()//信息素蒸发2fork=1tom//2~4行，释放信息素3DepositPheromone(k)4end-for5UpdateGlobalData()//计算一些全局信息其程序流程图为：五、核心代码TSP中的核心代码为：voidPerm(Typelist[],intk,intm)//递归函数，生成排列，寻找最佳路径{intc=1;inta=m;while(a1)//定义Mat数组的行数{c=c*a*(a-1);a-=2;}intd=m+1;//定义Mat数组的列数if(k==m&&list[0]==0){for(inti=0;i=m;i++){Mat[e][i]=list[i];//符合条件时生成排列，存储在数组Mat中}e++;}if(Mat[c-1][m]!=-1&&e==c)//当找出所有可能路径时，计算所有路径长度，并找到最短路径{for(intg=0;gc;g++){for(inth=0;hd;h++){intx=Mat[g][h];//获取路径坐标inty=Mat[g][h+1];Count[g]=Count[g]+G.arcs[x][y];//计算路径长度}}cout所有路径及其路径长度：endl;for(g=0;gc;g++)//输出所有路径及其路径长度{for(inth=0;h=d;h++){intk=Mat[g][h];coutG.vexs[k]-;}coutCount[g]endl;}for(g=0;gc;g++)Help[g]=Count[g];//赋值for(inti=0;ic;i++)//对辅助数组冒泡排序，找最小值{for(intj=1;jc;j++){if(Help[i]Help[j]){inttemp=Help[i];Help[i]=Help[j];Help[j]=temp;}}}intMin_way=Help[0];//Min_way为最短路径for(i=0;ic;i++){if(Count[i]==Min_way){cout旅行商最佳路径为：;for(intj=0;j=d;j++){intk=Mat[i][j];coutG.vexs[k]-;//输出最短路径}cout路径长度为：Min_way;coutendl;}}}}六、屏幕截图与结论分析初始时：运行之后：最后结果为：七、主要参考文献与网页://wenku.baidu.com/view/6e842737f111f18583d05a38.html://wyzxzxj2004.blog.163.com/blog/static/291228592007417550879/