论文部分内容阅读
摘要：旅行商问题(TSP)是遗传算法得以成功应用的典型问题。文章对遗传算法加以改进，提出了新的选择策略和交叉算子，并且引入了兄弟竞争的策略来加快收敛速度和全局搜索能力。把该算法应用在不同类型的TSP问题的求解上，表现出了比传统遗传算法更好的收敛性和计算效率。说明改进算法是有效的。关键词：旅行商问题(TSP)；遗传算法(GA)；交叉算子；兄弟竞争策略
0 引言
旅行商问题(Traveling salesman Problem，简记为TSP)自1932年K．Menger提出以来，已引起各个领域许多研究者的兴趣。它是一个古老而又困难的问题，是一种典型组合优化问题(combinatorial Optimization Problem)，并且也是一种NP完全问题(Nondeterministic Polynomial Complete Problem)。TSP问题可以描述为：一个推销员要到n(n>2)个城市推销货物，从某个城市出发，经过其余各个城市一次且仅仅一次，然后回到出发点，求其最短行程，即寻找一条巡回路径。
TSP问题主要有两类：一类是任两个城市间的距离都是对称的，假设点i和点j之间的距离为dij则dij=dji，它对应的是图论中的无向图；另一类是两个城市间的距离是非对称的，即dij≠dji它对应的是图论中的有向图。
TSP问题中，可能的路径总数与城市数目n是成指数型增长的，一般很难精确地求出其最优解，因而寻找出有效的近似求解算法就具有重要的意义。很多实际应用问题，如印制电路板的钻孔路线方案，连锁店的货物配送路线，列车编组等，经过简化处理后，均可建模为TSP问题，因而对TSP问题求解方法的研究具有重要实际价值。另外，所有NP完全问题在数学上都等价于TSP问题，它的研究对于科学和工程技术领域中大量组合优化问题，尤其是其中的NP完全问题的求解有着极为重要的价值。
目前针对TSP问题已有许多种解法，如穷举搜索法(Ex-hansfive Search Method)、贪心法(Greedy Method)、动态规划法(Dynamic Programming Method)、分支界定法(Branch-And-Bound)等。这些方法都存在着一个共同的问题就是当城市数目N较大时，会产生所谓的“组合爆炸”问题。如当N=50时，用每秒计算一亿次的巨型计算机采用穷举搜索法计算，所需时间为5×10“年。数年来，又有人提出了一些优化技术，如模拟退火、遗传算法和神经计算等，并且取得了一定的进展。其中遗传算法具有良好的全局搜索能力，是目前解决各种优化问题的有效方法。
1 遗传算法
遗传算法(genetic algorithms，简称GA)是J.Holland于1975年受生物进化论的启发而提出的。遗传算法是一种借鉴生物界自然选择和自然遗传学机理的迭代自适应概率性搜索算法，是基于“适者生存”的一种高度并行、随机和自适应的优化算法，它将问题的求解表示成“染色体”的适者生存过程，通过“染色体”群的一代代不断变化，包括复制、交叉和变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。其具体算法如下：
(1)初始化：确定解的基因表示，设置遗传算法的重要参数(群体规模n，迭代次数gen，交叉概率Pc，变异概率Pm)，并随机产生n个初始个体P(0)={a1，a2，...，an}作为初始种群，其中ai表示第i个个体。
(2)计算适应度评价函数：对群体P(t)中的每一个个体ai计算它的适应度函数fitness(ai)，i=l，2，3，...，n。
(3)选择操作：根据个体适应度，以一定的选择算子，从P(t)解集中选择一些优良个体进入下一代。
(4)交叉操作：以交叉概率P。对当前群体中个体的部分结构加以替换和重组。
(5)变异操作：以较小的变异概率Pm改变当前群体中个体的某个或某些基因。群体P(t)经过选择、交叉和变异后得到下一个群体P(t+1)；
(6)终止条件判断：如果满足终止条件，则将当前群体中具有最大适应度的个体作为最优解，终止计算。否则返回(2)。
遗传算法具有良好的全局搜索能力，常用于求解TSP问题。但传统的遗传算法收敛速度慢并且易于陷入局部最优解。针对这一缺点，本文提出了一种求解TSP问题的改进遗传算法，对适应度函数的选择、遗传操作的设计以及重要参数的设置，都进行了改进。该算法应用于TSP问题的求解，表现出比传统遗传算法更好的收敛性和计算效率。
2 对求解TSP问题遗传算法的改进设计
在上一节所述的利用遗传算法求解问题的过程中，主要技术问题有：问题的表述和编码；适应函数的构造；初始群体的选取；选择、交叉、变异策略的选取；重要参数的设定；算法终止条件。下面将根据TSP问题的特点以及传统遗传算法求解TSP所存在的问题，对GA求解过程进行改进。
2.1问题的表述和编码
问题的表述和编码是构造遗传算法的第一步，一个好的编码可以清楚地表达问题的特征，它将影响整个算法的每一步。对于求解TSP问题，通常有Grefenstette编码、近邻表示、路径表示、矩阵表示等多种方法。
Grefenstette编码方式在进行单点杂交时，左侧部分的旅程-不发生变化，所以这种方法的适用性存在一定的问题。近邻表示法的缺点是排列不一定对应一合法回路，产生小圈现象，从而使得操作比较复杂，且遗传算子打断好路径的概率较大，因此，该算法的性能较差。矩阵表示的遗传操作比较复杂，并具有盲目性，也未充分利用城市间距离的信息。而路径表示是旅程对应的基因编码的最自然、简单和符合逻辑的表示方法，并且由于编码遍历了每一个节点，所以不会产生子回路。
考虑到路径表示是最符合逻辑也是最自然的表示方法，所以本文中选择此编码表示方法。例如：2-5-4-8-9—7-6-1-3-10可以表示为[2 5 4 8 9 7 6 1 3 10]，表示从城市2出发，依次经过城市5、4、8、9、7、6、1、3、10然后返回城市2的一条路径。
2.2初始群体的选取
在求解TSP问题的传统遗传算法中，初始种群的产生都采用完全的随机方式。本文综合考虑所采用的路径编码的特点以及算法的效率，采用在随机产生个体基因的同时加入了对所产生的非法基因判定和启发式修改的机制。所谓的启发式修改即找出距离较近的城市。
2.3适应度函数的构造 适应度函数的设计是遗传算法的—个重要方面。一般来说，所设计的适应度函数要求具有单值、非负、最大化、合理、一致性、计算量小、通用性强的特点。由于TSP问题是—个求解最小值的问题，考虑到路径编码的特点以及适应度函数的设计要求，本文对遗传算法的适应度函数设计如下：
为所获得路径的距离之和。显然，距离之和越小，则适应度函数的数值就越大，该路径也就越好。
2.4选择策略
选择算子设计为两部分：复制选择算子和生存选择算子。复制选择是指为了进行交叉操作对种群中的个体进行的选择，生存选择是从进行了交叉操作之后的群体中进行的选择。在具体求解中复制选择算子采用顺序(ranking)选择：首先根据适应度对各个个体进行排序，然后依据概率选择个体进行交叉操作。生存选择采用父辈个体和子代个体共同竞争的机制。
2.5交叉策略
本文结合贪心方法和边重组交叉算子的特点提出了一种适合求解TSP问题的新的交叉算子，其具体描述如下：
假设有n个城市1，2，…，n，染色体编码采用路径表示。现有待交叉的双亲：
Parl=(a11，a12，a13，…a1n)，Par2=(a21，a22，a23，…，a2n)。
因为采用的是路径表示，所以将上述染色体看成一个环，即a1n的下—个城市为a11。
(1)首先随机确定—个当前城市currentcity，并将其加入到子代中。假设产生—个随机数为2，则选出Parl中的第二个城市a12为当前的城市，即currentcity=a12，将a12加入到子代中。
(2)在Par2中找到与currentcity相同的城市，并判断cur-rentcity在两个父代中的左、右邻接城市是否在子代中，如不在则比较它们与currentcity之间的距离，记与currentcity距离最小的那个邻接城市为下一个currentcity，并将其加入到子代中。假设a12在Par2中为的a23，判断a11、a13、a22、a24是否在子代中，如不在则比较出da11,a12、da12,a13、da22,a23和da23,a24，设da22,a23为距离最小的，则currentcity=a22，将a22加入到子代中。
(3)如果左、右邻接城市中已存在于子代中，选择不在子代中的左、右次邻接的城市来进行距离的比较。假设上述的a11已经在子代中了，则选取a11的左邻接城市a1n(因为相对于currentcity=a12来说，a11是a11左邻接城市)，如果a1n不在子代中则比较da1n,a12。如果在则选择a1n的左邻接城市进行距离的比较，依此类推直至所选取的城市不在子代中。
(4)重复(2)、(3)步骤直至完整地生成子代。
由上述介绍可以看出，结合边重组交叉算子和贪心方法的这种交叉算子可以使交叉后的子代在保证可行性的同时，又在很大程度上很好地继承了父代的优秀基因，迅速优化适应值，达到交叉的目的。
2.6变异策略
为了改善遗传算法的局部搜索能力，并且考虑到所采用的编码方式，本文采用逆转变异，并在过程中加入了小范围竞争、择优的操作。
所谓逆转变异是在染色体上随机地选择两点，将两点之间的子串反转插入。如染色体[1 5 2 4 8 3 9 6 10 7]，假设随机的两个点为2和6，则将2和6之间的[4 8 3 9]按照反向顺序插入到原来的染色体中，即为[1 5 2 9 3 8 4 6 10 7]。
加入小范围竞争、择优操作是从加快收敛速度和全局搜索性能两方面考虑的。具体操作为：对待变异的染色体进行n次(3～5次)变异操作，生成n个不同的个体，选出其中最高适应度的个体加入到子代中。
2.7算法终止条件和重要参数选择
本文设定一个最大迭代次数maxgen来结束算法。maxgen的具体取值要根据所要解决的TSP问题的具体的城市规模来确定。
遗传算法中需要选择的参数主要有：染色体的长度、群体规模、交叉概率Pc和变异概率Pm等。这些参数对遗传算法的性能影响很大，它们的具体数值要根据所要解决的TSP问题来确定。
2.8实现流程
(1)确定重要参数的具体数值，随机生成多个染色体群体(初始化中有非法路径判断机制)作为父群体，代数gen=0；
(2)对父代中的个体计算其适应度并排序；
(3)若gen>maxgen，则输出该代中最优的个体的适应度的倒数；
(4) gen=gen+1；
(5)依据概率选择个体进行n(n=3～5)次交叉、变异操作，选取适应度最高的放入子代；
(6)计算子代的适应度，并将其和父代放在一起进行适应度的排序，选取最高的popsize(popsize为群体规模)个作为新一代的群体，返回(3)。
3 实例应用验证
笔者使用matlab6.5对改进的遗产算法在Win2000 pro-fessional操作系统上作了大量的仿真实验，并且针对不同类型的TSP问题作了算法的测试。对典型的TSP问题的测试结果如下。
3.1非对称TSP问题仿真实验
表1为非对称9个城市的TSP问题。在算例中，取种群规模popsize=20，Pc=0.3，Pm=0.8。将算法运行了100次，每次最多只是遗传到第3代就收敛到最优化解9(3-9-5-4-2-7-8-6-1)，平均占用CPU时间为0.0703s。
3.2对称TSP问题仿真实验
在表2所示的对称10个城市TSP问题的算例中，同样取种群规模popsize=20，为Pc=0.3，Pm=0.8。将算法运行了100次，每次最多只是遗传到第5代就收敛到最优化解151(1-3-6-4-5-7-8-9-2-10)，平均占用CPU时间为0.1203s。
以上两个TSP实例的城市规模都不大，再把该改进算法用于求解著名的中国旅行商问题，取种群规模为50，最大迭代次数为100，Pc=0.3，Pm=0.8。将算法运行了50次，最差解得到15608公里，大多数情况下可以得到最优解15404公里(也是目前中国旅行商问题的最优解)及其附近的解，其中一条最优路线为：北京－哈尔滨－长春－沈阳－天津－济南－合肥－南京－上海－杭州－台北－福州－南昌－武汉－长沙－广州－海口－南宁－贵阳－昆明－成都－拉萨－乌鲁木齐－西宁－兰州－银川－西安－郑州－石家庄－太原－呼和浩特。平均占用CPU时间为8.1032s。
3.3结果分析
从上述的TSP实例中可以看出：
(1)两个规模较小的实例计算都找到了最优解，而且收敛速度非常快。
(2)即使对于规模较大的TSP问题，该改进算法也能很快地找到最优解，而且解的质量非常好，非常稳定，说明了该改进算法具备很强的全局搜索能力。
(3)无论是对称的TSP问题或是非对称的TSP问题，该改进算法都可以对其进行求解，说明该改进算法的适应性很广。
4 结束语
本文提出了一种针对TSP问题的改进遗传算法。考虑到TSP问题的特点以及传统的遗传算法在求解TSP问题上表现出来的收敛速度慢并且易于陷入局部最优解的弱点，文中对传统的遗传算法进行了一系列的改进：设计一个新的选择策略和交叉算子，并且引入了兄弟竞争的策略来加快收敛速度和全局搜索能力。把该算法应用在不同类型的TSP问题的求解上，表现出了比传统遗传算法更好的收敛性和计算效率。因此，具有一定的实用价值。
0 引言
旅行商问题(Traveling salesman Problem，简记为TSP)自1932年K．Menger提出以来，已引起各个领域许多研究者的兴趣。它是一个古老而又困难的问题，是一种典型组合优化问题(combinatorial Optimization Problem)，并且也是一种NP完全问题(Nondeterministic Polynomial Complete Problem)。TSP问题可以描述为：一个推销员要到n(n>2)个城市推销货物，从某个城市出发，经过其余各个城市一次且仅仅一次，然后回到出发点，求其最短行程，即寻找一条巡回路径。
TSP问题主要有两类：一类是任两个城市间的距离都是对称的，假设点i和点j之间的距离为dij则dij=dji，它对应的是图论中的无向图；另一类是两个城市间的距离是非对称的，即dij≠dji它对应的是图论中的有向图。
TSP问题中，可能的路径总数与城市数目n是成指数型增长的，一般很难精确地求出其最优解，因而寻找出有效的近似求解算法就具有重要的意义。很多实际应用问题，如印制电路板的钻孔路线方案，连锁店的货物配送路线，列车编组等，经过简化处理后，均可建模为TSP问题，因而对TSP问题求解方法的研究具有重要实际价值。另外，所有NP完全问题在数学上都等价于TSP问题，它的研究对于科学和工程技术领域中大量组合优化问题，尤其是其中的NP完全问题的求解有着极为重要的价值。
目前针对TSP问题已有许多种解法，如穷举搜索法(Ex-hansfive Search Method)、贪心法(Greedy Method)、动态规划法(Dynamic Programming Method)、分支界定法(Branch-And-Bound)等。这些方法都存在着一个共同的问题就是当城市数目N较大时，会产生所谓的“组合爆炸”问题。如当N=50时，用每秒计算一亿次的巨型计算机采用穷举搜索法计算，所需时间为5×10“年。数年来，又有人提出了一些优化技术，如模拟退火、遗传算法和神经计算等，并且取得了一定的进展。其中遗传算法具有良好的全局搜索能力，是目前解决各种优化问题的有效方法。
1 遗传算法
遗传算法(genetic algorithms，简称GA)是J.Holland于1975年受生物进化论的启发而提出的。遗传算法是一种借鉴生物界自然选择和自然遗传学机理的迭代自适应概率性搜索算法，是基于“适者生存”的一种高度并行、随机和自适应的优化算法，它将问题的求解表示成“染色体”的适者生存过程，通过“染色体”群的一代代不断变化，包括复制、交叉和变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。其具体算法如下：
(1)初始化：确定解的基因表示，设置遗传算法的重要参数(群体规模n，迭代次数gen，交叉概率Pc，变异概率Pm)，并随机产生n个初始个体P(0)={a1，a2，...，an}作为初始种群，其中ai表示第i个个体。
(2)计算适应度评价函数：对群体P(t)中的每一个个体ai计算它的适应度函数fitness(ai)，i=l，2，3，...，n。
(3)选择操作：根据个体适应度，以一定的选择算子，从P(t)解集中选择一些优良个体进入下一代。
(4)交叉操作：以交叉概率P。对当前群体中个体的部分结构加以替换和重组。
(5)变异操作：以较小的变异概率Pm改变当前群体中个体的某个或某些基因。群体P(t)经过选择、交叉和变异后得到下一个群体P(t+1)；
(6)终止条件判断：如果满足终止条件，则将当前群体中具有最大适应度的个体作为最优解，终止计算。否则返回(2)。
遗传算法具有良好的全局搜索能力，常用于求解TSP问题。但传统的遗传算法收敛速度慢并且易于陷入局部最优解。针对这一缺点，本文提出了一种求解TSP问题的改进遗传算法，对适应度函数的选择、遗传操作的设计以及重要参数的设置，都进行了改进。该算法应用于TSP问题的求解，表现出比传统遗传算法更好的收敛性和计算效率。
2 对求解TSP问题遗传算法的改进设计
在上一节所述的利用遗传算法求解问题的过程中，主要技术问题有：问题的表述和编码；适应函数的构造；初始群体的选取；选择、交叉、变异策略的选取；重要参数的设定；算法终止条件。下面将根据TSP问题的特点以及传统遗传算法求解TSP所存在的问题，对GA求解过程进行改进。
2.1问题的表述和编码
问题的表述和编码是构造遗传算法的第一步，一个好的编码可以清楚地表达问题的特征，它将影响整个算法的每一步。对于求解TSP问题，通常有Grefenstette编码、近邻表示、路径表示、矩阵表示等多种方法。
Grefenstette编码方式在进行单点杂交时，左侧部分的旅程-不发生变化，所以这种方法的适用性存在一定的问题。近邻表示法的缺点是排列不一定对应一合法回路，产生小圈现象，从而使得操作比较复杂，且遗传算子打断好路径的概率较大，因此，该算法的性能较差。矩阵表示的遗传操作比较复杂，并具有盲目性，也未充分利用城市间距离的信息。而路径表示是旅程对应的基因编码的最自然、简单和符合逻辑的表示方法，并且由于编码遍历了每一个节点，所以不会产生子回路。
考虑到路径表示是最符合逻辑也是最自然的表示方法，所以本文中选择此编码表示方法。例如：2-5-4-8-9—7-6-1-3-10可以表示为[2 5 4 8 9 7 6 1 3 10]，表示从城市2出发，依次经过城市5、4、8、9、7、6、1、3、10然后返回城市2的一条路径。
2.2初始群体的选取
在求解TSP问题的传统遗传算法中，初始种群的产生都采用完全的随机方式。本文综合考虑所采用的路径编码的特点以及算法的效率，采用在随机产生个体基因的同时加入了对所产生的非法基因判定和启发式修改的机制。所谓的启发式修改即找出距离较近的城市。
2.3适应度函数的构造 适应度函数的设计是遗传算法的—个重要方面。一般来说，所设计的适应度函数要求具有单值、非负、最大化、合理、一致性、计算量小、通用性强的特点。由于TSP问题是—个求解最小值的问题，考虑到路径编码的特点以及适应度函数的设计要求，本文对遗传算法的适应度函数设计如下：
为所获得路径的距离之和。显然，距离之和越小，则适应度函数的数值就越大，该路径也就越好。
2.4选择策略
选择算子设计为两部分：复制选择算子和生存选择算子。复制选择是指为了进行交叉操作对种群中的个体进行的选择，生存选择是从进行了交叉操作之后的群体中进行的选择。在具体求解中复制选择算子采用顺序(ranking)选择：首先根据适应度对各个个体进行排序，然后依据概率选择个体进行交叉操作。生存选择采用父辈个体和子代个体共同竞争的机制。
2.5交叉策略
本文结合贪心方法和边重组交叉算子的特点提出了一种适合求解TSP问题的新的交叉算子，其具体描述如下：
假设有n个城市1，2，…，n，染色体编码采用路径表示。现有待交叉的双亲：
Parl=(a11，a12，a13，…a1n)，Par2=(a21，a22，a23，…，a2n)。
因为采用的是路径表示，所以将上述染色体看成一个环，即a1n的下—个城市为a11。
(1)首先随机确定—个当前城市currentcity，并将其加入到子代中。假设产生—个随机数为2，则选出Parl中的第二个城市a12为当前的城市，即currentcity=a12，将a12加入到子代中。
(2)在Par2中找到与currentcity相同的城市，并判断cur-rentcity在两个父代中的左、右邻接城市是否在子代中，如不在则比较它们与currentcity之间的距离，记与currentcity距离最小的那个邻接城市为下一个currentcity，并将其加入到子代中。假设a12在Par2中为的a23，判断a11、a13、a22、a24是否在子代中，如不在则比较出da11,a12、da12,a13、da22,a23和da23,a24，设da22,a23为距离最小的，则currentcity=a22，将a22加入到子代中。
(3)如果左、右邻接城市中已存在于子代中，选择不在子代中的左、右次邻接的城市来进行距离的比较。假设上述的a11已经在子代中了，则选取a11的左邻接城市a1n(因为相对于currentcity=a12来说，a11是a11左邻接城市)，如果a1n不在子代中则比较da1n,a12。如果在则选择a1n的左邻接城市进行距离的比较，依此类推直至所选取的城市不在子代中。
(4)重复(2)、(3)步骤直至完整地生成子代。
由上述介绍可以看出，结合边重组交叉算子和贪心方法的这种交叉算子可以使交叉后的子代在保证可行性的同时，又在很大程度上很好地继承了父代的优秀基因，迅速优化适应值，达到交叉的目的。
2.6变异策略
为了改善遗传算法的局部搜索能力，并且考虑到所采用的编码方式，本文采用逆转变异，并在过程中加入了小范围竞争、择优的操作。
所谓逆转变异是在染色体上随机地选择两点，将两点之间的子串反转插入。如染色体[1 5 2 4 8 3 9 6 10 7]，假设随机的两个点为2和6，则将2和6之间的[4 8 3 9]按照反向顺序插入到原来的染色体中，即为[1 5 2 9 3 8 4 6 10 7]。
加入小范围竞争、择优操作是从加快收敛速度和全局搜索性能两方面考虑的。具体操作为：对待变异的染色体进行n次(3～5次)变异操作，生成n个不同的个体，选出其中最高适应度的个体加入到子代中。
2.7算法终止条件和重要参数选择
本文设定一个最大迭代次数maxgen来结束算法。maxgen的具体取值要根据所要解决的TSP问题的具体的城市规模来确定。
遗传算法中需要选择的参数主要有：染色体的长度、群体规模、交叉概率Pc和变异概率Pm等。这些参数对遗传算法的性能影响很大，它们的具体数值要根据所要解决的TSP问题来确定。
2.8实现流程
(1)确定重要参数的具体数值，随机生成多个染色体群体(初始化中有非法路径判断机制)作为父群体，代数gen=0；
(2)对父代中的个体计算其适应度并排序；
(3)若gen>maxgen，则输出该代中最优的个体的适应度的倒数；
(4) gen=gen+1；
(5)依据概率选择个体进行n(n=3～5)次交叉、变异操作，选取适应度最高的放入子代；
(6)计算子代的适应度，并将其和父代放在一起进行适应度的排序，选取最高的popsize(popsize为群体规模)个作为新一代的群体，返回(3)。
3 实例应用验证
笔者使用matlab6.5对改进的遗产算法在Win2000 pro-fessional操作系统上作了大量的仿真实验，并且针对不同类型的TSP问题作了算法的测试。对典型的TSP问题的测试结果如下。
3.1非对称TSP问题仿真实验
表1为非对称9个城市的TSP问题。在算例中，取种群规模popsize=20，Pc=0.3，Pm=0.8。将算法运行了100次，每次最多只是遗传到第3代就收敛到最优化解9(3-9-5-4-2-7-8-6-1)，平均占用CPU时间为0.0703s。
3.2对称TSP问题仿真实验
在表2所示的对称10个城市TSP问题的算例中，同样取种群规模popsize=20，为Pc=0.3，Pm=0.8。将算法运行了100次，每次最多只是遗传到第5代就收敛到最优化解151(1-3-6-4-5-7-8-9-2-10)，平均占用CPU时间为0.1203s。
以上两个TSP实例的城市规模都不大，再把该改进算法用于求解著名的中国旅行商问题，取种群规模为50，最大迭代次数为100，Pc=0.3，Pm=0.8。将算法运行了50次，最差解得到15608公里，大多数情况下可以得到最优解15404公里(也是目前中国旅行商问题的最优解)及其附近的解，其中一条最优路线为：北京－哈尔滨－长春－沈阳－天津－济南－合肥－南京－上海－杭州－台北－福州－南昌－武汉－长沙－广州－海口－南宁－贵阳－昆明－成都－拉萨－乌鲁木齐－西宁－兰州－银川－西安－郑州－石家庄－太原－呼和浩特。平均占用CPU时间为8.1032s。
3.3结果分析
从上述的TSP实例中可以看出：
(1)两个规模较小的实例计算都找到了最优解，而且收敛速度非常快。
(2)即使对于规模较大的TSP问题，该改进算法也能很快地找到最优解，而且解的质量非常好，非常稳定，说明了该改进算法具备很强的全局搜索能力。
(3)无论是对称的TSP问题或是非对称的TSP问题，该改进算法都可以对其进行求解，说明该改进算法的适应性很广。
4 结束语
本文提出了一种针对TSP问题的改进遗传算法。考虑到TSP问题的特点以及传统的遗传算法在求解TSP问题上表现出来的收敛速度慢并且易于陷入局部最优解的弱点，文中对传统的遗传算法进行了一系列的改进：设计一个新的选择策略和交叉算子，并且引入了兄弟竞争的策略来加快收敛速度和全局搜索能力。把该算法应用在不同类型的TSP问题的求解上，表现出了比传统遗传算法更好的收敛性和计算效率。因此，具有一定的实用价值。