缪桂根,高羽佳

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

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

缪桂根,高羽佳

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

用改进遗传算法求解TSP问题,并编制了完整的Matlab程序予以仿真实现.程序中选择算子采用最佳个体保存与赌轮选择相结合的策略,最后分析了最佳个体保存比例对寻优效果的影响.

改进遗传算法;TSP问题;Matlab程序

0 引 言

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

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

1 TSP问题的数学模型

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

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

2 遗传算法的运行过程

遗传算法是一种"生成+检测"的迭代搜索算……