基于遗传算法的tsp问题研究本科生毕业论文(编辑修改稿)

基于遗传算法的tsp问题研究本科生毕业论文(编辑修改稿)内容摘要：

许多领域，所以寻找出实际而有效的算法就显得比较重要了。 但是遗憾的 是，计算复杂性理论给予我们的结论却是，这种可能性尚属未知。 TSP的应用与价值 TSP 在现实生活中有很多应用。 直观上，最普通的 TSP的运用莫过于找出旅行商为遍历每个地理位置上的点的顺序，使他所经历的路径最短。 了解了对每个城市访问一次的最优旅行路径能够为旅行节约很多潜在的时间。 对提到的实例，图中的节点将通过地理位置顺序连接，而且连接两节点的路径的长度是公制的。 在当前，很多的现实事物，包括城市，建筑和地标都已经有了平面电子地图。 为解决以上提及的实例，仅需要把期望访问的地理位置具体化，然后用旅行商问题的算法进行求解就行了。 TSP 在其他领域还有很多重要的实际应用。 例如在组装线上的机器。 一些机器的目标就是为了在某种材料片上钻削不同的孔。 材料可 能是电路板、汽车底盘甚至是用来做书架的木板。 钻头通过定位装置在材料片上重定位。 在某个局部的区域，钻头可以沿着轨迹移动到任何位置。 钻头的重定位所消耗的时间依赖于钻头需要移动的距离。 旅行商问题的解可以用来找出孔被加工的最优顺序。 在装配线的实例中，对每个工件为完成装配过程节约的少许时间意味着一天的产量的相应增加。 为了通过 TSP 解决这个时间的节约问题，对每个节点做了简化，用需要钻孔的位置来代替，而边用节点之间的距离来代替。 福建农林大学本科毕业论文 9 TSP问题的数学模型 TSP 问题的数学模型如下：设有 n个城 市，寻找一条巡回路径 T=(t1， t2，．．．， tn)，使得下列目标函数最小： f(T)= 1n1di(ti,ti+1)+d(tn,t1) 其中 ti为 城 市号，取值为 1 到 n 之间的自然数， d(i,j)为城市 i 和城市 j 之间的距离，对于对称式 TSP，有 d(i， j)=d(j， i)。 除此之外，模型还有其它一些等价的书写形式，这就不一一列举。 TSP 问题是组合优化领域中的一个典型问题，涉及求多个变量的函数的最小值。 虽然陈述起来很简单 ，但求解却很困难，它一直是运筹学中最富挑战性的问题之一，且已经被证明是 NP 完全问题。 对于具有一个城市的 TSP 问题，其可能的路径数目为 (n1)!／ 2， 5 个城市的情形对应120／ 10=12 条路线， 10个城市的情景对应 3628800／ 20=181440 条路线。 所以对于输入规模为 n个城市 TSP 找到最优解的时间复杂性函数的数量级是 O(n!)，当 n比较大时，耗费的时间己经是个天文数字，至今尚未找到有效的求解方法。 在理论上虽然枚举法可以解这一问题，但是当 n较大时，解题的时间消耗会使枚举法显得没有任何实际价值。 因此寻求一 种求解时间短，能满足实际问题精度要求的解，成为解决该问题的主要途径。 快速、有效地解决 TSP 问题有着极高的实际应用价值，也就吸引了众多领域的学者对它进行研究。 尽管 TSP 仍未找到最优解，但是求解它的算法逐渐在改进。 1954 年 Dantzig， Fulkerson 和 Johnson 解决了 49 个城市数目的 TSP 问题，经过半个世纪的研究，目前，最大的已成功求解的旅行商问题有 24798 个城市。 TSP 问题的分类 从 TSP 问题映射到图的类型 ,可以分为两类 : (1)城市间的距离都是对称的 ,它对应的是图论中的无向图。 (2)两个城市间的距离是非对称的 ,它所对应的是图论中的有向图 . 从问题本身的限制条件的强弱 ,可分为三类 : (但是一般都要求城市间的费用不为负数 ),只是给出距离矩阵 ,求最小回路。 TSP 问题 ,即 EuclidTSP,它给出每个点在欧式平面 上的坐标 ,而城市间的距离就是以他们的欧式距离来定义 . 福建农林大学本科毕业论文 10 现有的求解 TSP 问题的几种算法 在求解 TSP的算法的过程中，人们一直在寻找切实有效的方法，按招时间出现的顺序大致可分为：传统 算法和智能演化算法。 传统算法有精确算法和近似优化算法，精确算法又有线性规划方法、动态规划方法、分支定界方法等，而近似算法有插入法、最近邻算法、 ropt 算法、混合算法、概率算法等。 虽然传统算法能够找 TSP 问题的最优解，但随着问题规模的不断增长，算法所需要的时间非常巨大，因此只适用于求解规模较小的 TSP 问题。 20 世纪 80年代以来，一些新颖的智能优化算法，如模拟退火、遗传算法、禁忌搜索、人工神经网络、蚁群算法、粒子群算法、郭涛算法、免疫算法等，通过模拟或揭示某些自然现象 (或过程 )而得到发展，其思想和内容涉及 数学、物理学、生物进化、人工智能、神经科学和统计力学等方面，为解决复杂问题提供了新的思路和手段．由于这些算法构造的直观性和自然机理，通常称作智能演化算法，或称为现代启发式算法。 引入智能演化算法的原因在于避免陷人局部最优解，希望得到更好的解上界。 (1)禁忌搜索算法 禁忌搜索算法是局部领域搜索算法的推广，主要思想是标记已经得到的局部最优解，并在进一步的迭代中避开这些局部最优解。 此方法需较 强技术性，禁忌长度较难取。 若禁忌长度过长，则所需内存较大，否则， 易陷入局部最优解。 (2)模拟退火算法 这是一种源 于五十年代、基于 Monte Carlo 迭代求解思想的随机搜索算法，八十年代才开始应用于组合优化领域，其出发点是将组合优化问题与统计力学的热平衡作类比，把优化的目标函数视作能量函数，模仿物理学中固体物质的退火处理，先加温使之具有足够高的能量，然后再逐渐降温，其内部能量也相应下降，在热平衡条件下，物体内部处于不同状态的概率服从 Boltzmann分布，若退火步骤恰当，则最终会形成最低能量的基态。 这种算法思想在求解优化问题时，不但接受对目标函数 (能量函数 )有改进的状态，还以某种概率接受使目标函数恶化的状态，从而可使之避免过早收敛到某个局部极值点，也正是这种概率性的扰动能够使之跳出局部极值点，故而得到的解常常很好。 (3)蚁群算法 又称 蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。 它由 Marco Dorigo 于 1992年在他的 博士论文 中提出， 过模拟蚂蚁的觅食行为， 蚂蚁觅食的时候会在所走过的路径上留下信息激素， 同时信息激素会随时间而挥发 .一条路径走过的蚂蚁越多， 留下的信息激素越多。 反过来， 信息激素浓度高的路径上会吸引更多的蚂蚁。 通过这种正向反馈， 最终将找到一条最优路径。 为了避免蚂蚁两次走上同 一条路径 ( 非法路径 ) ， 为每个蚂蚁设置一个禁忌表以记录它福建农林大学本科毕业论文 11 已走过的路径。 该算法的优点是 : 它是一种自 适应 度 、自组织、本质上并 行的方法， 而且是一种正向反馈的方法，可以促使整个系统向最优解进化，而且参数少、易于调整，易于移植到其他组合优化问题。 但是，它存在收敛慢、易于陷人局部最优 的缺点。 (4)人工神经网络 人工神经网络 (Artificial Neural Network， ANN)，是由大量处理单元即神经元 (Neurons)互相连接而成的网络，对人脑进行抽象，简化和模拟的一种工程系统 ，反映人脑的基 本特性。 人工神经网络算法成为近年来的热点研究领域，涉及到 数学 、电气工程、 计算机工程 、 物理学 等诸多学科，其应用领域包括了建模、时间序列分析、模式识别和控制等，并且仍然在一断扩展。 作为神经网络的基本单元 ，神经元模型具备三个基本要素。 其一是有一组突触或连接，常用表示内部神经元的联接强度，或者称 为权值，取值 范围 可在负值和正值之间 ， 其二是 可以 反映生物神经元时空整合功能的输入信号累加器 ， 其三是具有一个激励函数用于限制神经元的输出。 福建农林大学本科毕业论文 12 第 4 章 遗传算法在 TSP 的应用 法在 TSP上的应用 在遗传算法研究中， TSP 问题已被广泛地用于评价不同的遗传操作及选择机制的性能。 TSP问题因其典型性已成为各种启发式的搜索，优化算法的间接比较标准，而遗传算法方法就本质来说，主要处理复杂问题的一个鲁棒性强的启发式随机搜索算法。 因此遗传算法在 TSP 问题求解方面的应用研究，对于构造合适的遗传算法框架，建立有效的遗传操作以及有效地解决 TSP 等有着多方面的重要意义。 图 41遗传算法运用在 TSP上的流图程 福建农林大学本科毕业论文 13 遗传算法的进化过程是建立在编码机制基础上的，编码对 于算法的性能，如搜索能力和种群多样性等影响很大。 如何将问题的解转换为编码表达的染色体是遗传算法的关键问题。 编码机制的主要工作是把对象抽象为由特定符号按一定顺序排成的串。 这就如同研究生物遗传是从染色体着手，而染色体则是由基因排成的串。 遗传算法中经常使用二进制串进行编码，其优点是编码、解码操作简单，交叉、变异等操作也易于实现，且便于应用模式定理进行理论分析；其缺点主要是处理 连续函数的优化问题时存在映射误差：编码长度较小时达不到精度要求， 度较大时又会使算法搜索空间过大。 选择一个群体，就是选择一 个个体的集合。 这个初始群体也就是问题假设解得集合。 在遗传算法求解 TSP 问题中通常以随机方式产生串或者个体的集合。 初始种群个数越多，得到最优解的希望越大，但个数过多会导致每进行一轮的机器时间变长，致使算法效率低下。 在研究自然界中生物的遗传和进化现象时，生物学家常常使用适应度这个术语来衡量某个物种对环境的适应率。 适应度较高的物种将会得到更多的繁殖的机会；从而导致适应度低的物种被淘汰。 度量物种适应度的函数就被称为适应度函数。 本文中适应度函数取为哈密尔顿圈的长度的倒数。 void CalFitness(PTSP city) { int i,j。 int start,end。 for(i=0。 iPOPSIZE。 i++){//求适应值 cityDistance[i]=0。 for(j=1。 j=CITY_NUM。 j++){ start=citycolony[i][j1]。 end=citycolony[i][j]。 cityDistance[i]=cityDistance[i]+CityDistance[start][end]。 } cityfitness[i]=N/(cityDistance[i])。 } } 遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选 取哪 些个体遗传到福建农林大学本科毕业论文 14 下一代群体中的一种遗传运算。 选择操作的目的是为了避免基因缺失，提高全局收敛性和计算效率。 常用的选择可略包括以下几种： (1) 轮盘赌法。 (2) 锦标赛选择。 (3) 最优保存策略。 (4) 期望值方法。 (5) 排序选择方法。 比较常用的就是轮盘赌法，以及最优策略保留法。 本文采用的是 轮盘赌法。 在轮盘赌法中，各个个体的被选择概率和其适应度值成比例。 设群体大小为 N，个体 i 的适应度值 Fi，则个体 i 被选择的概率 Psi为： Psi=Fi／ nj j1F (n=l， 2„．． n) 显然，概率 Psi反映了个体 i的适应度在整个群体的个体适应度总和中所占的比例。 根据个体适应度值的大小，适应度值越大的，其概率 Psi越大，被选择到的机会也越多，从而其基因结构被遗传到下一代的可能性也越大，反 之亦 然。 轮盘赌的具体执行过程如下： a)先计算出种群中所有个体的适应度的总和。 b)其次计算出每个个体的相对适应度的大小，作为被选中的概率。 void Select(PTSP city) { //选择算子 double tempRand,tempflag1。 int i,j。 for(i=0。 iPOPSIZE。 i++)//选 POPSIZE 次 { tempRand=(rand()%100000)/*3。 tempflag1=0。 for(j=0。 jPOPSIZEamp。 amp。 tempflag1==0。 j++) { if(tempRand=cityaddFitness[j])//轮盘赌选中第 j个 { 福建农林大学本科毕业论文 15 tempflag1=1。 //if(i!=cityBestFitCityXuh) if(cityfitness[j]=cityfitness[i]amp。 amp。 i!=j) { copyColony(i,j,city)。 } } } } return。 } 基于 TSP 问题 的顺序编码，若采取简单的一点交叉或多点交叉策略，必然以极大的概率导致未能完全遍历所有城市的非法路径 1 2 3 4| 5 6 7 8。