一．问题重述
假设有一个旅行商人要拜访 n 个城市，他必须选择所要走的路径，路径的限
制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标
是要求得的路径路程为所有路径之中的最小值。TSP 问题是一个组合优化问题。该
问题可以被证明具有 NPC 计算复杂性。因此，任何能使该问题的求解得以简化的方法，都
将受到高度的评价和关注。
二．遗传算法（GA）概述
遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传
学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的
方法，它最初由美国 Michigan 大学 J.Holland 教授于 1975 年首先提出来的，并
出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》，GA 这
个名称才逐渐为人所知，J.Holland 教授所提出的 GA 通常为简单遗传算法
（SGA）。
三．问题分析
TSP 问题就是寻找一条最短的遍历 n 个城市的最短路径, 即搜索自然数
子集 W= { 1 ,2 , ⋯, n} ( W 的元素表示对 n 个城市的编号) 的一个排列
π( W) = { V1 , V2 , ⋯, Vn} , 使 len = ∑ d ( Vi , Vi+1) + d ( V1 , Vn)取最
小值, 式中的 d ( Vi , Vi+1) 表示城市 Vi 到城市 Vi + 1 的距离.
遗传算法是具有“生成+检测”的迭代过程的搜索算法。它的基本处理流程
如图 1 所示。由此流程图可见，遗传算法是一种群体型操作，该操作以群体中的
所有个体为对象。选择（Selection）、交叉（Crossover）和变异（Mutation）是遗
传算法的 3 个主要操作算子，它们构成了所谓的遗传操作（genetic operation），
使遗传算法具有了其它传统方法所没有的特性。遗传算子包含如下 6 个基本因素：
（1） 参数编码：由于遗传算法不能直接处理解空间的解数据，因此必须通过编
码将它们表示成遗传空间的基因型串结构数据。
（2） 生成初始群体：由于遗传算法的群体型操作需要，所以必须为遗传操作准
备一个由若干初始解组成的初始群体。初始群体的每个个体都是通过随机
方法产生。
（3） 适应度评估检测：遗传算法在搜索进化过程中一般不需要其他外部信息，
仅用适应度（fitness）值来评估个体或解的优劣，并作为以后遗传操作的
依据。
（4） 选择（selection）：选择或复制操作是为了从当前群体中选出优良的个体，
使它们有机会作为父代为下一代繁殖子孙。个体适应度越高，其被选择的
机会就越多。此处采用与适用度成比例的概率方法进行选择。具体地说，
就是首先计算群体中所有个体适应度的总和（
），再计算每个个体的
适应度所占的比例（
），并以此作为相应的选择概率
。
