数学建模之求解TSP问题的遗传算法

遗传算法求解TSP问题丑闻(湖北工业大学机械学院，湖北，武汉)摘要：本文应用了遗传算法(GA)解决传输层问题。此处介绍了逆运算子，该运算子采用以每个城市的存取顺序为基础的编码体系，同时探索影响GA效能的遗传运算子，以提高解决方案的品质。最后，通过在VC 6.0中运行此算法的程序，获得了问题的最佳解决方案。关键词：遗传算法(GA)TSP问题逆算子最优解genetic algorithm for solving tsp problems金文(school of science，Hubei university of technology，Hubei，Wuhan，)abstract : this paper apply genetic algorithm to solve travel salesman problems(tsp)problem . the encoding scheme based On sequence Onkeywords : genetic algorithm(ga)；TSP探测；Inversion optimal solution引言1TSP问题(Traveling Salesman Problems)知道n个城市之间的相互距离，现有销售员必须通过n个城市，每个城市只能访问一次，最后可以说明必须返回出发城市。他对这些城市的访问顺序的确定方法可以使旅行路线的总长度最小。图表理论中的术语，假设图表G=(V，E)。其中v是一组顶点，e是一组边，D=(dij)是由顶点I和顶点j之间的距离组成的距离矩阵。旅行社的问题是通过所有顶点，得到每个顶点只能通过一次的最短距离的循环。城市v=v1，v2，v3，VN的访问顺序之一为t=(t1，T2，T3，ti、TN)，并且记住TN 1=t1，则TSP问题的数学模型为：Min L=i=1ndti，ti 1TSP问题是典型的组合优化问题，是可能路径数和城市数n呈指数增长的NP难题，因此一般很难准确找到自由解决方案，找到其他有效的近似解决算法具有理论意义。另一方面，印刷电路板上的钻孔路径体系、连锁商店的货物配送路径等许多实际应用问题已建模为TSP问题，对解决TSP问题具有重要的应用价值，而研究TSP问题对促进遗传算法具有重要意义。遗传算法(GA)是通过在自然环境中模拟生物的遗传和进化过程而创建的自适应全局优化概率搜索算法。这包括表示可行解决方案的各个编码、选择、交叉和变异等遗传操作。与传统优化算法相比，遗传算法的优越性主要有：(1)即使定义的自适应函数不连续、不规则或噪声大，在搜索过程中也不容易陷入局部优化，并以最大概率找到组最优解。(2)由于其固有的并行性，遗传算法非常适合大规模并行计算机。2初始群体设置基因操作是同时进行很多个体的，因此，这很多个体形成了群体，在基因算法中考虑了早期群体的多样性，群体内的个体是随机生成的。首先随机生成一定数量的对象，然后从其中挑选最好的对象，添加到初始群体中。此过程将不断重复，直到初始组中的对象数达到预定的大小。/*初始化组*/Void initpop()Unsigned char J1Unsigned int j，k，J2，J3，j4，P