内容发布更新时间 : 2024/11/20 14:34:38星期一 下面是文章的全部内容请认真阅读。
TSP问题的遗传算法求解
摘要：遗传算法是模拟生物进化过程的一种新的全局优化搜索算法，本文简
单介绍了遗传算法，并应用标准遗传算法对旅行包问题进行求解。
关键词：遗传算法、旅行包问题
一、 旅行包问题描述：
旅行商问题，即TSP问题（Traveling Saleman Problem）是数学领域的一个著名问题，也称作货郎担问题，简单描述为：一个旅行商需要拜访n个城市（1，2，…，n），他必须选择所走的路径，每个城市只能拜访一次，最后回到原来出发的城市，使得所走的路径最短。其最早的描述是1759年欧拉研究的骑士周游问题，对于国际象棋棋盘中的64个方格，走访64个方格一次且最终返回起始点。
用图论解释为有一个图G=（V,E），其中V是顶点集，E是边集，设D=（dij）是有顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只能通过一次的具有最短距离的回路。若对于城市V={v1，v2，v3，...，vn}的一个访问顺序为T=(t1，t2，t3，…，ti，…，tn)，其中ti∈V(i=1，2，3，…，n)，且记tn+1= t1，则旅行商问题的数学模型为： min L=Σd(t(i),t(i+1)) （i=1，…，n）
旅行商问题是一个典型组合优化的问题，是一个NP难问题，其可能的路径数为（n-1）！，随着城市数目的增加，路径数急剧增加，对与小规模的旅行商问题，可以采取穷举法得到最优路径，但对于大型旅行商问题，则很难采用穷举法进行计算。
在生活中TSP有着广泛的应用，在交通方面，如何规划合理高效的道路交通，以减少拥堵；在物流方面，更好的规划物流，减少运营成本；在互联网中，如何设置节点，更好的让信息流动。许多实际工程问题属于大规模TSP，Korte于1988年提出的VLSI芯片加工问题可以对应于1.2e6的城市TSP，Bland于1989年提出X-ray衍射问题对应于14000城市TSP，Litke于1984年提出电路板设计中钻孔问题对应于17000城市TSP，以及Grotschel1991年提出的对应于442城市TSP的PCB442问题。
二、 遗传算法简介
遗传算法（Genetic Algorithm，GA）是借鉴生物界自然选择和自然遗传机制“适者生存”的一种高度并行、随机化和自适应的全局优化算法，其首先由Holland与1975年提出。其将问题的求解表示成“染色体”的适者生存过程，通过“染色体“群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到”最适应环境“的个体，从而得到问体的最优解。
标准的遗传算法的只要步骤可描述为为：
1、 随机产生一组初始个体构成初始种群，并评价每一个体的适配值； 2、 判断算法的收敛准则是否满足。若满足则输出搜索结果，否则执行下面步骤；
3、 根据适配值大小以一定的方式执行复制操作； 4、 按交叉概率pc执行交叉操作； 5、 按变异概率pm执行变异操作。
6、 返回2执行新一轮的复制、交叉、变异。
在算法中，适配值是对染色体进行评价的一种指标，是遗传算法进行优化所用的主要信息，与个体的目标值存在一种对应关系；复制操作通常采用比例复制，即复制概率正比于个体适配值，适配值高的个体在下一代中复制自身的概率大，从而提高种群的平均适配值；交叉操作通过交换两父代个体的部分信息构成后代个体，使得后代继承父代的有效模式，从而有助于产生优良个体；变异操作通过随机改变个体的某些基因而产生新个体，有助于增加种群的多样性，避免早熟收敛。
遗传算法利用生物进化和遗传的思想实现优化过程，区别与传统优化算法
1、
算法进行全空间并行搜索，并将搜索重点集中于性能高的部分，
从而能够提高效率并且不易陷入局部最小。 2、
算法具有固有并行性，通过对种群的遗传处理可以处理大量的模
式，并且容易并行实现；
其主要设计如下： 1、确定问题的编码方案。 2、确定适配值函数。
3、遗传算子的设计。
4、算法参数（种群数目、交叉与变异概率和进化代数等）的选取。 5、确定函数终止条件。
三、 对TSP问题的遗传算法实现
设计思路： 1、初始化城市距离
采用一个city_xy函数获取n个城市的TSP问题的坐标，保存在city矩阵中，并且用city_dis矩阵表示任意两个城市之间的距离，矩阵中的元素city_dis（i，j)代表第i个城市与第j个城市间的距离。
2、初始化种群
通过randperm函数，生成一个一维随机向量（是整数1，2，3，4，5的任意排列），然后将其赋给二维数组group的第一列，作为一个个体。如此循环N次，生成了第一代种群，种群的每个个体代表一条路径。
3、计算适应度
采用的适应度函数为个体巡回路径的总长度的函数。具体为
adapt(1,i)=(n*maxdis-dis) (1)
在式（1）中，adapt(1,i)表示第i个个体的适应度函数，maxdis为城市间的最大距离，dis为个体巡回路径的总长度，这样定义的适应度，当路经越短时适应度值越大。在适应度值的基础上，给出的计算个体期望复制数的表达式为
adaptnum(1,i)=(N*adapt(1,i)/ sumadapt) (2) 其中，sumadapt为种群适应度之和。
4、复制
采用优秀个体的大比例保护基础上的随机数复制法。具体做法为在生成下一代个体时，先将最大适应度对应的路径个体以较大的比例复制到下一代，然后再用随机数复制法生成下一代的其他个体。其中，有一个问题必须考虑，即若某一次生成的随机数过大，结果能复制一个或极少个样本。为了避免这一情况，采用了限制措施，即压低了随机数的上限。
5、交叉
采用的方法为按步长的单点交叉，为随机选择一对样本，再随机选择一