遗传算法求解TSP问题的MATLAB实现.pdfVIP

2007 年 6 月 韶关学院学报 ·自然科学 　　　　　　　　　 J un . 2007 第 28 卷 　第 6 期 Journal of Shaoguan University ·Natural Scienc　e 　　　　　　Vol . 28 　No . 6 遗传算法求解 TSP 问题的MATLAB 实现 温清芳 (德化陶瓷职业技术学院 ,福建 德化 362500) ( ) 摘要 : 以遗传算法求解旅行商问题 TSP 为例 ,提出一种改进的交叉和变异算子 ,深入讨论了各个遗传算子的程序实 现 ,并给出其算子的MATLAB 程序编码 ,最后用 5 个城市的非对称 TSP 进行仿真分析. 结果表明,改进的算法比传统 算法收敛速度更快 ,适应值更优 ,说明改进算法是有效的 ,证实 TSP 问题是遗传算法得以成功应用的典型例子. 关键词 :旅行商问题 ; 遗传算法 ; Grefenstettet 编码 ;MATLAB 程序 ( ) 中图分类号 :O242 　　　文献标识码 :A 　　　文章编号 :1007 - 5348 2007 06 - 0018 - 05 尽管对遗传算法的研究方兴未艾[ 1] ,但因其基础理论难有突破性进展 ,要想知道其效果如何就只有利用 [2 ] 计算机进行模拟. 目前大多采用 C 语言编写这类程序 . C 语言作为一种高效的编程语言有它的许多优点 , ( ) 但对于编写遗传算法 GA 程序来说 ,MATLAB 语言则更为合适. 遗传算法是一种全局寻优有哪些信誉好的足球投注网站算法 ,它首先 对问题的可行解进行编码 ,组成染色体 ,然后通过模拟 自然界的进化过程 ,对初始种群中的染色体进行选 择 、交叉和变异 ,通过一代代进化来找出最优适应值的染色体来解决问题. 它具有很强的全局有哪些信誉好的足球投注网站能力和较 [2 ] 强的自适应性 ,适合解决连续变量函数优化问题和离散变量的优化组合问题 . 它比用 C 等其它高级语言 要简单 、灵活 、快捷 ,程序篇幅也将缩小许多. ( ) 旅行商问题 TSP 是一个典型的优化组合问题 ,可具体描述如下 : 已知 n 个城市之间的相互距离 ,现有 一个推销员从某一城市出发 ,必须遍访这 n 个城市 ,并且每个城市只能访问一次 ,最后又必须返回到出发城 市. 如何安排他对这些城市的访问次序 ,可使其旅行路线的总长度最短[2 ,3 ] . 事实上 ,很多实际问题 ,如电路布 [4 ] 线 、输油管路铺设 、连锁店的货物配送路线等 ,经过简化处理后都可建模为 TSP 问题 . 因而 ,对求解 TSP 问 题方法的研究便具有重要的应用价值. 由于 TSP 问题的可行解数 目与城市数 目 n 是成指数型增长的 ,是一个 N P 难问题 ,因而一般只能近似求 ( ) 解 ,遗传算法 GA 是求解该问题较为有效的方法之一 , 目前应用遗传算法解决 TSP 问题 ,主要解决编码问题 和算子的设计问题. 采用所遍历城市的顺序排列来表示各个个体的编码串是最 自然的编码方法 ,但它对应 的交叉和变异运算实现起来较困难 ,因为常规的交叉和变异运算会使群体中产生一些不