遗传算法编程求解TSP问题.pdfVIP

第 27卷第 2期 　 　　　　　　　　　　　　　　　河池学院学报 　　　　　　　　　　　　　　　　Vo l. 27 No. 2 2007年 4 月 　　　　　　　　　　　　　JOURNAL OF HECH I UN IV ER SITY 　　　　　 Ap r. 2007 遗传算法编程求解 TSP 问题 1 2 黎永壹 , 黄泽 ( 1. 钦州学院　数学与计算机科学系 , 广西 　钦州 　535000; 2. 河池学院　计算机与信息科学系 , 广西 　宜州 　546300) [摘 　要 ] 　利用基本遗传算法的思路解决旅行商问题 ,选择仍然采用轮盘选择方法 ;交叉算法采用一个启发 式交叉算法 ,交叉位置随机 ,该算法以一定的概率生成一个比父代好的解 ,交叉概率取 0. 1;变异概率 0. 005。经多 次运行 ,求得最优值 。停止法则为循环最大遗传代数为止 ,另外如果 30 代解没有改进则停止 。编程环境为 M at lab6. 5。 [关键词 ] 　遗传算法 ; TSP;交叉算法 ;启发算法 [中图分类号 ] 　TP30 1. 6　　　[文献标识码 ] 　A 　　　[文章编号 ] 　1672 - 902 1 (2007) 02 - 0008 - 04 ( ) ( ) [作者简介 ] 　黎永壹 1979 - ,男 ,广西武鸣人 ,钦州学院数计系助教 ,主要研究方向为人工智能;黄泽 1980 - , 男 ,广西贵港人 ,河池学院计信系助教 ,主要研究方向为多媒体教学 、网络软件 。 0　引言 ( ) 遗传算法是一种通用性非常强 ,计算性能非常好的算法 ,解决旅行商问题 以下简称 TSP 却存在很多问 题 ,主要问题是解的可行性问题 ,在交叉和变异操作过程中 ,可能产生不可行的解 ,因此交叉和变异算子的设 计是本程序的关键 。 1　TSP 的基本定义 2 ( ) ( ) 定义 1　设 p = x , y i = 0, 1…, n - 1 , p = p 是平面 R 上由 n 点构成的简单多边形, 即, 对任意 i i i n 0 x, y ( i≠j) , i, j = 0, 1, …, n - 1线段 p p 与 p p 或是相邻且相交于一端点或不相交, 简单多边形集合记为 i i + 1 j j + 1 p = { pi | i = 0, 1, …, m - 1} , m为简单多边形的个数 。 定义 2　平面 R2 障碍物集合 O 是简单多边形集合 p 的子集, 即 O ∈p, 每个障碍物 Oi ∈O, i = 0, 1, …, m - 1 对应的各