精品毕业论文--基于遗传算法的tsp问题研究

精品毕业论文--基于遗传算法的tsp问题研究内容摘要：

效地解决 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 8 7 6 5 |4 3 2 1 若采取一点交叉，且交叉点随机选为 4，则交叉后产生的两个后代为 8 7 6 5 5 6 7 8 1 2 3 4 4 3 2 1 显然，这两个子路径均未能遍历所有 8 个城市，都违反了 TSP 的约束条件。 针对这一问题，当然可以采取上述构造惩罚函数的方法，但是实验效果不佳。 解决这一约束问题的另一种处理方法是对交叉，变异等遗传操作作适当的修正，使其自动满 足 TSP 的约束条件，本文采用部分匹配交叉法 ： 部分匹配交叉中先依据均匀随机分布产生两个位串交叉点，定义这两点之间的区域为一匹配区域，并使用位置交换操作交换两个父串的匹配区域，两父串及匹配区域为 A=9 8 4 |5 6 7| 1 3 2 0 B=8 7 1 |2 3 0| 9 5 4 6 首先交换 A 和 B 的两个匹配区域，得到 A1=9 8 4 |2 3 0| 1 3 2 0 16 B1=8 7 1 |5 6 7| 9 5 4 6 对于 A1， B1 两个串中匹配区域以外出现的遍历重复，依据匹配区域内的位置映射关系， 逐一进行交换，对于 A1 有 2 到 5,3 到 6,0 到 7 的位置符号映射，对 A1 的匹配区以外的 2， 3， 0分别以 5,6,7 替换，则得 A2=9 8 4 |2 3 0 |1 6 5 7 B2=8 0 1| 5 6 7 |9 2 4 3 这样，每个子串的次序部分有其父串确定。 这 是 在选中用于繁殖下一代的个体中，对 两个不同的个体的相同位置的基因进行交换，从而产生新的个体，也即对两个父染色体的部分结构进行重组，以产生新一代子染色体。 遗传交叉的主要目的是子代尽可能地继承父代的优秀基因。 void Cross(PTSP city,double pc) {//交叉概率是 pc int crossNum,i。 int cityCross[2][CITY_NUM+1]。 int tempXuh[2]。 crossNum=int(POPSIZE*pc)。 for(i=0。 icrossNum/2。 i++) { tempXuh[0]=rand()%(POPSIZE1)。 do { tempXuh[1]=rand()%(POPSIZE1)。 }while(tempXuh[0]==tempXuh[1])。 copyCityXuhTo(city,tempXuh,cityCross)。 crossTwo(city,tempXuh,cityCross)。 } 17。