资源描述：
《改进遗传算法求解tsp问题的matlab程序设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二十六卷第三期楚雄师范学院学报Vol26No32011年3月JOURNALOFCHUXIONGNORMALUNIVERSITYMar2011改进遗传算法求解TSP问题的Matlab程序设计*缪桂根(安徽农业大学信息与计算机学院物流工程系,安徽合肥230036)摘要:本文用改进遗传算法求解TSP问题,编制了完整的Matlab程序予以仿真实现。程序中选择算子使用的是最佳个体保存与赌轮选择相结合的策略,文章最后分析了最佳个体保持比例对寻
2、优效果的影响。关键词:改进遗传算法;TSP问题;Matlab中图分类号:TP18文章标识码:A文章编号:1671-7406(2011)03-0005-06旅行商问题(TravelingSalemanProblem,TSP),又叫货郎担问题,是最基本的路线问题,该问题是在寻求单一旅行者由起点出发,通过所有给定的城市之后,最后再回到原点的最小路径成本。该问题具有广泛的应用性,如物流中的配送车辆调度问题就可看成一个约束性多路旅行商问题。因此,对TSP问题求解具有一定的现实意义。TSP问题是一个组合优化问题,随着问题的
3、增大,其搜索空间也急剧扩大,有时在目前的计算机上用枚举法很难甚至不能求出最优解。对这类问题,用启发式算法求解其满意解是一个很好的方式,而遗传算法就是寻求这种满意解的最佳工具之一。遗传算法模拟[1]自然进化过程来搜索最优解,其本质是一种高效、并行、全局搜索的方法。本文采用遗传算法求解TSP问题并编制Matlab程序进行仿真试验。1TSP问题的数学模型TSP问题即寻找一条最短的遍历n个城市的最短路径,使得:图1遗传算法的程序n-1Td=di,i+1+dn,1i=1取最小值,d,ii+1表示两城市i和i+1之间的距
4、离。*基金项目:安徽农业大学青年科学基金(2009zr37)城市农产品配送车辆调度优化与仿真。收稿日期:2011-01-25作者简介:缪桂根(1984),硕士,助教,主要研究方向为物流系统优化、物流与供应链管理。5楚雄师范学院学报2011年第3期楚雄师范学院学报2011年第3期2遗传算法的运行过程遗传算法是一种生成+检测的迭代搜索算法,其运算流程可用图1来表示。3TSP问题的Matlab实现参数说明:POPSIZE表示群体规模,NC
5、ITIES表示城市数目,pop表示初始种群,MAXGEN表示进化代数,Pc表示个体交叉概率,Pm表示个体变异概率。(1)编码并生成初始种群编码是应用遗传算法时要解决的首要问题,也是设计遗传算法时的一个关键步骤。在遗传算法中把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法就称为编码。而由遗传算法解空间向问题空间的转换称为解码。求解TSP问题时,采用所遍历城市的顺序排列来表示各个个体的编码是最自然的编码方法,而且这种表示方法无需解码过程,占用的内存空间较小。functionpop=TSPiniti
6、alize(POPSIZE,NCITIES)pop=zeros(POPSIZE,NCITIES);fori=1:POPSIZEpop(,i:)=randperm(NCITIES);end(2)适应度评估在遗传算法中用适应度来度量群体中各个个体在优化计算中达到或接近于或有助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概率就较大;而适应度较低的个体遗传到下一代的概率就相对较小一些。此处用个体所表示的循环路线的倒数来作为适应度评估值,路线越短,个体适应度值越大。function[Length,fitness]=T
7、SPLength(POPSIZE,pop,D,NCITIES)fori=1:POPSIZErpop(,i:)=[pop(,i2:NCITIES),pop(,i1)];Length(i)=sum(diag(distmatrix(pop(,i:),rpop(,i:))));fitness(i)=1/Length(i);end(3)选择、交叉、变异选择又称复制,是在群体中选择生命力强的个体产生新的群体的过程。选择操作建立在对个体的适应度进行评价的基础上。选择操作的主要目的是为了避免有用遗传信息的丢失,提高全局收敛性
8、和计算效率。选择算子确定的好坏,直接影响到遗传算法的计算结果。选择算子确定不当,会造成群体中相似度相近的个体增加,使得子代个体与父代个体相近,导致进化停止不前;或使适应度偏大的个体误导群体的发展方向,使遗传失去多样性,产生早熟问题。最佳个体保存策略可保证迄今为止所得到的最优个体不会被交叉、变异等遗传操作所破坏,它是遗传算法收敛性的
