TSP问题的遗传算法求解
摘要：遗传算法是模拟生物进化过程的一种新的全局优化搜索算法，本文简单介绍了遗传算法，并应用标准遗传算法对旅行包问题进行求解。
关键词：遗传算法、旅行包问题
一、旅行包问题描述：
旅行商问题，即TSP问题（Traveli
gSalema
Problem）是数学领域的一个著名问题，也称作货郎担问题，简单描述为：一个旅行商需要拜访
个城市（1，2，…，
），他必须选择所走的路径，每个城市只能拜访一次，最后回到原来出发的城市，使得所走的路径最短。其最早的描述是1759年欧拉研究的骑士周游问题，对于国际象棋棋盘中的64个方格，走访64个方格一次且最终返回起始点。
用图论解释为有一个图G（VE），其中V是顶点集，E是边集，设D（dij）是有顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只能通过一次的具有最短距离的回路。若对于城市Vv1，v2，v3，，v
的一个访问顺序为Tt1，t2，t3，…，ti，…，t
，其中ti∈Vi1，2，3，…，
，且记t
1t1，则旅行商问题的数学模型为：mi
LΣdtiti1（i1，…，
）
旅行商问题是一个典型组合优化的问题，是一个NP难问题，其可能的路径数为（
1）！，随着城市数目的增加，路径数急剧增加，对与小规模的旅行商问题，可以采取穷举法得到最优路径，但对于大型旅行商问题，则很难采用穷举法进行计算。
在生活中TSP有着广泛的应用，在交通方面，如何规划合理高效的道路交通，以减少拥堵；在物流方面，更好的规划物流，减少运营成本；在互联网中，如何设置节点，更好的让信息流动。许多实际工程问题属于大规模TSP，Korte于1988年提出的VLSI芯片加工问题可以对应于12e6的城市TSP，Bla
d于1989年提出Xray衍射问题对应于14000城市TSP，Litke于1984年提出电路板设计中钻孔问题对应于17000城市TSP，以及Grotschel1991年提出的对应于442城市TSP的PCB442问题。
f二、遗传算法简介
遗传算法（Ge
eticAlgorithm，GA）是借鉴生物界自然选择和自然遗传机制“适者生存”的一种高度并行、随机化和自适应的全局优化算法，其首先由Holla
d与1975年提出。其将问题的求解表示成“染色体”的适者生存过程，通过“染色体“群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到”最适应环境“的个体，从而得到问体的最优解。
标准的遗传算法的只要步骤可描述为为：1、随机产生一组初始个体构成初始种群，并评价每一个体的适配值；2、判断算法的收敛准则是否满足。若满足则输出搜索结果，否则r