毕业论文移动版

此外，旅行商问题还可以用来模拟其他问题，例如在一块电路板上钻孔，在孔的位置已知的条件下，钻头在钻完所有空的时候要回到起始位置以便能够重现为新板钻孔，这就用到了TSP问题模型。由于TSP问题模型的简单性，使得它在许多其他领域也有着广泛的应用【 】，像：[ ]半导体厂家使用CONCORDE（一种主要用于计算TSP的程序代码）中链式Lin-Kernighan启发式样算法来优化整个电路的扫描链路，用来检测的扫描链路包含在一个芯片当中，它可以最小化时间或者能量的消耗；再就是安排收集投币式公用电话中的硬币，CONCORDE中链式Lin-Kernighan启发式算法的改进版可以解决各种各样的硬币收集问题，因为单行道的存在以及城市中交通中的其他问题 

使得从X到Y的旅行费用和从Y到X的旅行费用相等的假设变的不切实际，所以需要改进来解决这些问题。

1.3 TSP问题的研究现状

穷举法虽然是一种最优算法，但是由于在实际的问题中，求解各种最优算法所需要的时间会随问题的规模增加而呈现指数速度增加，这种指数规模的增加会超过目前计算机所能承受的运算能力，所以穷举法不能适应大规模的TSP问题，为了解决这种弊端，人们研究了一种新的算法——启发式算法。启发式算法【 】是一种技术，这种技术使得在可接受的计算费用内去寻找最好的解，但不一定能保证所得解的最优性和可行性，甚至在大多数情况下，无法表明所得的解与最优解之间的近似程度。

现代的智能算法是从80年代初兴起的，1985年，Hopfield和Tank用连续型Hopfield网络求解TSP，同年发表了论文《“Neural”computation of decisionsin in optimization problems》，这也开创了神经网络算法求解TSP问题的新纪元。该文献【 】详细介绍了TSP问题，提出了能量函数的概念，同时对该算法的稳定性进行了研究，在他们研究的基础上，神经网络算法在TSP问题中的应用不断的拓展，又产生了几种其他的求解TSP问题的神经网络算法，如：遗传算法、人工免疫算法、混合优化算法、蚁群算法等。

目前在研究TSP上遇到的最主要的瓶颈问题就是如何避免陷入局部最优和注意计算效率的问题。TSP问题今后的研究热点从攻克问题角度来看可以主要为以下几个方面，收敛效率、解的可行性包括全局最优和局部最优和解的最有性。

下面将从几个方面来阐述TSP问题的研究现状：

1.3.1 模拟退火算法（SA）

模拟退火算法是局部搜索算法的扩展，理论上来说是一个全局最优算法，它是从化学和物理的退火过程中推导而来的，由Metropolis算法和退火过程组成。Metropolis算法于1953年提出，1983年将该思想应用于组合优化问题中，从而建立了模拟退火算法，该算法可以解决凹平面最优化问题并在Multri—pascal设计环境中加以实现。

1.3.2 遗传算法（GA）

该算法是Holland于1975年在模仿生物界的遗传变异的基础上提出来的，是以达尔文的生物进化论为启发而创建的，后来经过采用交换算子操作和模拟退火思想对GA进行改进，求解TSP问题从而显著提高了算法的优化效率，文献[16]基于GA机理提出了解决TSP的一套进化策略，并分析了算法的有效性。文献[17]引入了小生境技术，提升了GA处理多峰函数优化问题的能力；文献[18]提出了新倒位算子，有了新的求解TSP问题的方法，文献[19]将时间窗约束转化为目标约束，使用序列编码，产生了有时间约束TSP的启发式算法。

1.3.3人工神经网络算法（ANN）

1985年Hopfield等人提出的一种新算法，该算法是一种重要的优化算法而且易于硬件的实现，但是容易陷入局部较小。为了解决其弊端，各国的科学家在进行不断的探索，文献[20]采用了波尔兹曼网络求解TSP问题，收敛速度很快；文献[21]对多路旅行商问题根据出发城市的不同和返回的情况分成了四个子问题建立了各个问题的能量函数和迭代公式，从而产生了智能优化算法；文献[22]改进了Hopfield算法；文献[23]把混沌机制和神经网络结合在一起提出了混沌神经网络模型。文献综述 (责任编辑：qin)