TSP的遗传算法.pdfVIP

1997 年 9 月 系统工程理论与实践 第 9 期 旅行商问题的遗传算法 孟繁桢　胡云昌　徐 慧　张新军　方小安 (天津大学, 300072) 摘要　 旅行商问题属于N P 问题, 现在还没有找到有效的解法。本文应用遗传算法对解决此类问题 的有效性作了探讨。文中对遗传算子的应用, 编码, 参数选择及其对收敛的影响等问题作了分析与探 讨。 关键词　遗传算法　遗传算子　旅行商问题 Genetic A lgo rithm of T raveling Salesm an P rob lem M eng Fanzhen　H u Yunchang　Xu H u i　Zhang X in jun　Fang X iaoan (T ianjin U niversity, 300072) 　 . Abstract T raveling salesm an p roblem belongs to N P comp lete N ow it has no t found the effective so lution yet. In th is paper , using genetic algo rithm has been studied to so lving the effectiveness of th is k ind of question, at sam e tim e, w e analyzed and had a discussion on the app lication of the genetic algo rithm , the coding, the cho ice of the pa ram eter, the influence of the convergence, and so on. Keywords　genetic algo rithm ; genetic operato r; traveling salesm an p roblem 1　前言 在一个网络中, 寻找一条能经过网络中各个点恰好一次, 而后回到出发点的路线, 使其全程路径长度 最短, 这就是所谓的旅行商问题, 旅行商问题属于组合优化问题, 与之相类似的还有最短路径问题, 中国邮 ( ) 递员问题, 最大 小 支撑树问题, 最优边无关集问题, 最小截集问题等。上述各问题中除了旅行商问题外, 都已分别找到了有效的算法。本文针对此旅行商问题的特点, 拟采用遗传算法求解此类问题。 遗传算法是模拟生物遗传进化机制而发展起来的一种新算法, 它的哲学基础是达尔文的“适者生存, ( ) 优胜劣汰”的自然选择学说。遗传算法把人造的最适生存和遗传算子 从自然界中抽象出来的 结合起来形 成一个强有哪些信誉好的足球投注网站过程。该算法最初是由密执根大学John Ho lland 教授提出的, 之后各国学者做了大量的研究 工作, 并应用于很多领域。实践表明, 遗传算法在处理具有离散变量的结构优化问题及网络问题上比较有 效。本文在应用遗传算法解决旅行商问题时, 对遗传算子的应用, 编码, 参数选择及其对收敛的影响等问题 作了分析与探讨。 2　遗传算法的基本原理 和传统的优化方法相比, 遗传算法具有下述特点。 ) 1 　遗传算法不是直接处理设计变量本身, 而是设计变量的代码, 这些代码通常用二进制数码表示。 也可用其它的方法进行编码, 例如, 本文在处理旅行商问题时根据其特点使用自然数进行编码。这些被编 码的设计变量称为位串, 位串中的每个字符相当于一个基因, 由多个位串构成个体位串, 他代表人造的染