改进遗传算法求解TSP问题的Matlab程序设计(1).pdf

第21卷第2期 湖南工程学院学报 Vo1.21.No.2

2011年6月 JournalofHunanInstituteofEngineering June2011

改进遗传算法求解TSP问题的Matlab程序设计

缪桂根,高羽佳

(安徽农业大学信息与计算机学院物流工程系,合肥230036)

摘 要:用改进遗传算法求解TSP问题,并编制了完整的Matlab程序予以仿真实现.程序中选择算子

采用最佳个体保存与赌轮选择相结合的策略,最后分析了最佳个体保存比例对寻优效果的影响.关键词:改进遗传算法;TSP问题;Matlab程序

中图分类号:TP391 文献标识码:A 文章编号:1671-119X(2011)02-0042-04

0 引 言

旅行商问题(TravelingSalemanProblem,TSP),又叫货郎担问题,是最基本的路线问题,该问题是在寻求单一旅行者由起点出发,通过所有给定的城市之后,最后再回到原点的最小路径成本.该问题具有广泛的应用性,如物流中的配送车辆调度问题就可看成一个约束性多路旅行商问题.因此,对TSP问题求解具有一定的现实意义.

TSP问题属于组合优化问题,随着问题规模增大,其可行解空间也急剧扩大,有时在当前的计算机上用枚举法很难甚至不能求出最优解,而用启发式算法求解这类问题的满意解是一个很好的方式,遗传算法就是寻求这种满意解的最佳工具之一.遗传算法模拟自然进化过程来搜索最优解,其本质是一种高效、并行、全局搜索的方法.本文采用遗传算法求解TSP问题并编制Matlab程序进行仿真试验.

[1]

2 遗传算法的运行过程

遗传算法是一种"生成+检测"的迭代搜索算法,其运算流程可用图1来表示.

图1 遗传算法的程序

1 TSP问题的数学模型

3 TSP问题的Matlab实现

TSP问题即寻找一条最短的遍历n个城市的最短路径,使得:

n-1

参数说明:POPSIZE表示群体规模,NCITIES表示城市数目,pop表示初始种群,MAXGEN表示进化代数,Pc表示个体交叉概率,Pm表示个体变异概率.

Td=i= 1di,i+1+dn,1

取最小值,di,i+1表示两城市i和i+1之间的距离.

收稿日期:2011-01-17

基金项目:安徽农业大学青年科学基金资助项目(2009zr37)

:(),女,硕士,助教,:.