产安排问题等，使得TSP问题的有效求解具有重要的意义。本文中的TSP算法主要采用遗传算法。遗传算法是一种进化算法，其基本原理是仿效生物界中的“物竞天择，适者生存”的演化法则。遗传算法把问题参数编码为染色体，再按照所选择的适应度函数，利用迭代的方式进行选择、交叉以及等运算对个体进行筛选和进化，使适应值大的个体被保留，适应值小的个体被淘汰，新的群体继承了上一代的信息，又优于上一代，这样反复循环，直至满足条件，最后留下来的个体集中分布在最优解的周围，筛选出最优个体作为问题的解。2问题描述本案例为20个城市，分别为120，根据全程路径最短为目的，制定最优的顺序依次经过这20个城市。这类问题就由TSP算法来解决，寻找出一条最短遍历这20个城市的路径。随机给出20个城市坐标，下表为这20个城市的位置坐标如表21所示。
2
f表2120个城市的位置坐标城市编号12345678910X坐标60180801402010020014040100Y坐标200200180180160160160140120120城市编号11121314151617181920X坐标18060120180201002002060160Y坐标100808060404040202020
3基于遗传算法TSP算法31基于遗传算法的TSP算法总体框架TSP问题的遗传算法包括编码设计、种群初始化、适应度函数选择、变异操作设定、选择操作设定、交叉操作设定以及终止条件设定。为简化TSP问题的求解，假设每个城市和其它任意一个城市之间都直接相连遗传算法TSP问题的流程图如图21所示
3
f开始随机产生初始种群
执行选择操作
执行交叉操作
否
Mutatio
Rate0015
是
执行变异操作
进化种群
否
繁殖代数100
是
结束
图21算法流程框架图32算法的详细设计
4
f321解空间的表示方式遗传算法对解空间的表示大多采用二进制编码形式，但是二进制编码方式不适合TSP问题的解的表示，要是给出城市编号，用十进制数编码来表示解更合适，例如：近邻表示、次序表示和路径表示等等这里采用了最简单的路径表示法。它是最自然、最接近人类思维的表示法因此对20个城市依次编号为120。例如，下面的路径（闭合的）：104281762016171311181514191295310表示从城市10出发，经过120个城市最后回到城市10的一条路径，可以自然地用一维数组来表示：（10，4，2，8，1，7，6，20，16，17，13，11，18，15，14，19，12，9，5，3，10）20个旅游城市的TSP问题，如果将种群规模设为50，则解空间就用二维数组来表示：tour5020。322种群初始化种群的规模选择应适当，盲目的增大种群规模不能使r