人工智能论文63963

TSP问题的解决方案The solution of TSP problem摘要：旅行商问题(Traveling Salesman Problem，TSP)是一个经典的组合优化问题。本文例举了一些主要的算法，重点选择遗传算法进行介绍，包括其原理，算子和算法优化。最后总结了一下对TSP的看法。关键字：TSP问题，遗传算法，旅行商问题第 1 章 引言旅行商问题( Traveling Sales man Problem，简称 TSP)即给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。其图论描述为，给定图 G = ( V,A)， 其中V为顶点集，A为各顶点相互连接组成的边集， 设D=(Dij)是由顶点 和顶点i和定点j之间的距离所组成的距离矩阵，要求确定一条长度最短的Hamilton回路，即遍历所有顶点当且仅当一次的最短距离。旅行商问题可分为如下两类： 1)对称旅行商问题(Dij=Dji，任意i，j=1， 2， 3n)； 2)非对称旅行商问题(DijDji，存在i ，j=1， 2， 3n)。TSP是一个典型的组合优化问题， 并且是一个 NP完全难题，是诸多领域内出现的多种复杂问题的集中概括和简化形式，并且已成为各种启发式的搜索 、 优化算法的间接比较标准。因此,快速、有效地解决 TSP有着重要的理论价值和极高的实际应用价值。第 2 章 主要计算方法基于TS P的问题特性，构造型算法成为最先开发的求解算法，如最近邻点、 最近合并 、最近插入、最远插入、最近添加、贪婪插入等。但是，由于构造型算法优化质量较差，迄今为止已开发了许多性能较好的改进型搜索算法，主要有： 1)模拟退火算法 2)禁忌搜索算法 3)Hopfiel神经网络优化算法 4)蚁群算法 5)遗传算法 6)混合优化策略这里将主要介绍遗传算法 第 3 章 遗传算法基本思想 遗传算法(Ge n et i c Al g o r i t hms， 简称 GA)是一种高度并行随机自适应的优化算法， 其基本思想是基于Darwin的进化论和Mendel的遗传学说。该算法最早由美国密执安大学的教授于1975年创建，它将问题的求解表示成“染色体”的适者生存过程， 通过“染色体”群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。通常遗传算法的设计是按以下步骤进行的： 确定问题的编码方案 ； 确定适配置函数 ； 算法参数的选取； 遗传算子的设计 ； 确定算法的终止条件。第 4 章 遗传操作算子 选择算子：对于求解 TSP，常用的选择机制有轮盘赌选择( roulette sheel selection)机制、最佳个体保存(elitistmode1 )选择机制 、期望值模型( expected value mode1 )选择机制、排序(ranking)选择机制、联赛选择模型 (tournament selection mode1)机制等。 交叉算子：采用顺序表示技术可以采用基本遗传算法的交叉操作例如单点交叉、 两点交叉、 多点交叉和均匀交叉；采用路径表示的可用部分匹配交叉( Partially Matched Crossover，PMX)、顺序交叉( Ordered Crossover， OX)、 循环交叉(Cycle Crossover，CX)、边重组( Edge Recombination， ER) 交叉；采用布尔矩阵表示的有它独特的交(intersection)和并(union)算子。 变异算子 ：采用顺序表示的可采用基本位变异、均匀变异 、 边界变异 、 非均匀变异和高斯变异；采用路径表示的可用位点变异、逆转变异、对换变异和插入变异 。另外适应度函数可取为哈密尔顿圈的长度的倒数(无惩 罚函数)， 初始种群可用随机方法产生，再确定相应的控制参数及可求解。第 5 章 算法分析优化1.选择操作。本例中算法收敛较慢，改进选择操作如下，选定K个最大适应度的个体，用来代替适应度最小的K个个体，保持群体的数目不变。此方法可以使群体的平均适应度大幅提高，可能使其收敛速度加快。2.每次交叉或变异操作以后，检验子代的适应度。如果子代发生退化，取消操作，用父代代替子代。这种方法可能带来的问题有： 然收敛迭代次数可能减少，但每次运算的计算量增加，增加了运算的时间。不利于种群的多样化，可能收敛解非最优解。解决方法根据某一较小概率 0.1-0.2有选择的进行检验和替换。3.免疫遗传算法。免疫遗传算法在变异以后加入免疫算子，可以大幅减少迭代次数。针对TSP问题，免疫遗传算子设计为先用一个n2的矩阵存储每一个顶点（城市）与其相应的最近城市的编号。如ai,1的最近城市ai,2。根据TSP问题而言，在最终的解决方案中，即在最佳路径中必然包括（或载很大程度上包括）了相邻城市间距离的最短路径。将城市ai,2移到ai,1之后，进行免疫检测，如果个体发生退化，取消免疫。免疫遗传算法可以大幅加快迭代的收敛速度减少迭代次数。 4. 终止条件。终止条件最常用的有事先给定一个最大进化步数，或者是判断最优化值是否连续若干步没有明显变化两种。本实例中只选择了第一种方法。可以设定一百次记录一次最优解，当连续三次的解不变（或相差不大）输出迭代结果。第 6 章 各种方法优缺点和比较由于TSP的典型性， 在过去的几十年里人们研究了许许多多的求解方法。 除了以上介绍的求解方法以及它们的各种 改进型方法(如 very fastsimulated annealing， VFSA 和多种群遗传算法 )外 ，还有一些其他的方法也可求解 TSP， 比如： nopt法，贪心算法，爬山法(HC法)，回溯法，分支限界法，EP混沌搜索、模糊优化等。S A，GA和 Ts作为具有全局优化性能的典型Metaheuristic算法代表，与人工神经网络统称为四大现代启发式算法蚁群算法是 9 0年代初才被提出的全新的算法， 而混合优化策略由于缺乏严格且丰富的理论研究和效率分析也是 近年来也才得到发展和应用。概括地讲 ，S A算法的实验性能 具有质量高、初值鲁棒性强、通用易实现的优点，最大缺点是往往优化过程较长；GA的两个最显著的优点是隐含并行性 和全局解空间搜索，但实际应用时易出现早熟收敛和收敛性能差等缺点；TS算法是一种局部搜索能力很强的全局迭代寻 优算法，不足之处在于对初始解较强的依赖性和串行的迭代 搜索过程；Hopfield神经网络优化算法具有简单、规范、快速等优点但是其优化性和鲁棒性比较差； 蚁群算法是一种本 质并行的算法， 但其搜索时间比较长，也容易陷于局部最优解，使搜索停滞；混合优化策略若能得到有效的设计，真正做到不同方法的取长补短将会产生更好的优化效率第 7 章 结论与展望 用遗传算法对TSP问题进行求解，证明了遗传算法在求解TSP问题时，具有可行性，遗传算法在设计过程中要照顾好两个原则子代要具有父代优良的基因信息即继承性子代要保持群体的多样性，即变异。虽然这两个原则在设计过程中经常会出现冲突，我们必须统筹的把握。既要实现算法的快速运算，又要实现解的最优。本论文认为对标准遗传算法有进行改经的必要，以提高其求解能力。对于TSP，目前还不存在能找到完美解的方法，这个问题是NP难的：目前还没有任何算法能在与城市总数呈多项式关系的时间复杂性下找到完美解。我们只能产生一些近似完美解，在合理的运行时间里使其与完美解尽可能的接近。 从目前发表的各种求解 TSP的论文的结论来看，少于1 0 0个城市的TSP例子很适合于用全局优化技术求解， 但是要考虑城市规模比这大得多的TSP实例则需要采用启发式方法。 为了进一步提高算法的全局优化能力，避免搜索过程陷入局部极小，现已提出的改进策略主要有：并行多邻域搜索，平滑优化曲面形状 ，引进重升温、 熵抽样等高级技术等。对于复杂优化问题，单一机制的优化算法很难实现全局优化，且效率较低。 多种优化机制和邻域搜索结构相混合， 是能较大 程度提高全局优化度和鲁棒性的有力途径，并可一定程度上 放松对单一算法参数选择的苛刻性。 所以混合优化策略会是一