5.2 可行性分析
旅行路线最优化问题是一种TSP问题，不存在多项式时间内找到最优解。蚁群算法和模拟退火算法是解决组合优化问题的有效方法，本文分别采用蚁群算法和模拟退火算法来解决34个城市的TSP问题。
（1）模拟退火算法的可行性
模拟退火算法用于解决组合优化问题的想法，是基于物理中固体的退火过程与一般组合优化问题间的相似性。在对固体物质进行退火处理时，通常先将它加温溶化，使其中的粒子可自由运动。然后随着温度的逐渐下降，粒子也逐渐形成了低能态的晶格。若在凝结点附近的温度下降速度足够慢，则固体物质一定会形成最低能量的基态。对于组合优化问题来说，它也有这样类似的过程。组合优化问题解空间中的每一点都代表一个解，不同的解有着不同的成本函数值，所谓优化，就是在解空间中寻找成本函数值最小（或最大）的解。
模拟退火算法是一种通用、高效、健壮、可行的拟物行随机近似算法，并且可以叫容易地并行实现以进一步提高运行效率，适合求解大规模组合优化问题特别是NP完全问题（如本文中旅行路线最优化问题），因此具有很大的实用价值。 经过计算可以发现模拟退火算法在濒临算法结束时，多次发现不错的解，又多次接受恶化。所以，降低接受解的恶化的概率或许可以取得更好的解。但是，事实上也可能因为太早地陷入局部最优而取得更坏的解。所以，模拟退火算法在搜索过程中需要精确调整接受退化结果的条件才可能取得较优解。
（2）蚁群算法的可行性
蚁群算法是受自然界中真实蚁群的集体行为的启发而提出的一种基于群体的模拟进化算法，属于随机搜索算法。它是一种并行算法，所有蚂蚁（ 智能体）独立行动，没有监督机构，从而使其避开局部最优；它是一种协作算法，每一只蚂蚁选择路径时，有较多信息素的路径被选中的可能性要比较少信息素的路径大得多，由于采用了正反馈机制，加快了该算法的收敛速度；它是一种构造性的贪婪算法，能在搜索的早期阶段找到较好的可接受解；它是一种鲁棒算法，因为只要对算法作小小的修改，就可以运用于别的组合优化问题。
我们充分利用了蚁群搜索食物的过程与旅行路线最优化问题之间的相似性，通过人工模拟蚁群搜索食物的行为（即蚂蚁个体之间通过间接通讯与相互协作最终找到从蚁穴到食物源的最短路径）来求解TSP问题。像蚂蚁这类群居动物，虽然个体的行为极其简单，但由这些简单的个体所组成的蚁群却表现出极其复杂的行为特征，能够完成复杂的任务；不仅如此，蚂蚁还能够适应环境的变化，如在蚁群运动路线上突然出现障碍物时，蚂蚁能够很快地重新找到最优路径。
蚁群算法已在组合优化、计算机网络路由、连续函数优化、机器人路径规划、数据挖掘、电网优化等领域取得了突出的成果。
21
6． 误差分析
基于蚁群算法和模拟退火算法的模型Ⅰ、模型Ⅱ、模型Ⅲ的误差主要体现在两个方面，一个是数据搜集方面，另一个是算法程序方面。
6.1基于数据收集的误差分析
首先在数据收集方面，上文中各城市的经纬度精确到小数点后4位，地球半径取自地球平均半径，由于地球椭球体的特征和地球表面丘陵和盆地等地貌，估算出的城市之间的距离与实际距离存在±2%的误差。
火车票数据均由相关火车票查询网站得到，不考虑临时变动，误差不会太大。 考虑到实际情况中飞机票存在不可忽略的折扣情况，且随时间的变化存在一定的不确定性，因此我们在考虑飞机票时，根据近期内的票价波动曲线获得，在最大限度内减小误差。
6.2 基于算法程序的误差分析
（1）有关模拟退火算法的误差分析
1.温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一。初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。 2.退火速度问题
模拟退火算法全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索（退火）是相当必要的，但这需要计算时间。 3.温度管理问题
温度管理问题也是模拟退火算法难以处理的问题之一。在实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式： T(t?1)?r?T(t)
式中r为正的略小于1.00的常数，t为降温的次数。 因此为保证迭代次数，减小误差，我们取r为0.99 以下是改变相关参数时收敛性变化的比较：
5.554.54路径总长度x 1045.554.54路径总长度x 1043.532.521.513.532.521.510500100015002000退火算法的路径长度演化过程25000500100015002000退火算法的路径长度演化过程2500
图 12 退火算法在不同参数下比较收敛性对比
22
（2）有关蚁群算法的误差分析 蚁群算法中容易出现停滞现象，出现早熟收敛。也就是当搜索到一定时间后，所有蚂蚁个体所发现的解完全一致，不能对解进行搜索，所以不利于发现更好的解。由于改进了基本蚂蚁算法的信息素更新方式，对最优蚂蚁经过的路径的信息素进行更新新，加快了算法收敛的速度。
7． 算法与模型评价
7.1旅行商问题简述
旅行商问题(Traveling Salesman Problem,TSP),也称为货郎担问题,由爱尔兰数学家Sir William Rowan Hamilton和英国数学家Thomas Penyngton Kirkman在19世纪提出的数学问题，它是指给定n个城市并给出每两个城市之间的距离,旅行商必须以最短路径访问所有的城市一次且仅一次,并回到原出发地,现已证明它属于NP难题。历史上的第一个正式用来解决TSP问题的算法诞生于1954年，它被用来计算49个城市的TSP问题。到现在为止，运用目前最先进的计算机技术可解决找出游历24978个城市的TSP问题。由于该问题的描述简单, 而其实际模型在印刷电路板的钻孔路线方案、连锁店的货物配送、网络布线等优化问题中又有着广泛的应用, 故长期以来一直吸引着国内外许多研究人员进行研究, 他们尝试着用各种算法来求解TSP问题, 归纳起来有: 近似解法、局部搜索法、神经网络、遗传算法、克隆算法、模拟退火算法、混合遗传算法等。
7.2 算法的理解与评价
从图论的角度看，该问题实质是在一个带权完全无向图中，找一个权值最小的Hemilton回路。本文尝试着采用模拟退火算法和蚁群算法来求解TSP问题。
蚂蚁算法的生物基础是生物界中蚂蚁的寻食规律。其优点在于：强启发式，能在早期的寻优中迅速找到合适的解决方案；搜索能力强、鲁棒性好，易与其他方法结合。
模拟退火算法的核心思想来自热力学原理，是解决大规模组合优化问题的通用、有效的全局优化方法。
7.2.1 蚁群算法
蚁群算法是一种原理相对简单的新兴仿生进化算法，在众多领域中已展现出它的特点和魅力，但蚁群算法理论与遗传算法、禁忌搜索算法等理论相比还远不成熟，实际应用也远未挖掘出其真正潜力还有许多亟待解决的课题。
⑴加强蚁群算法的基础理论研究，进一步发展新的数学分析和建模工具，尤
23
其对算法的基础理论研究非常重要，包括对解决不同优化问题时收敛性和收敛速度的估计、避免陷入局部最优值、鲁棒性分析以及参数的设计。目前尚未发现有关合理选择蚂蚁数量已经算法运行时间数学分析的论述。
⑵可将蚁群算法与其他类型方法综合使用以开发混合优化方法，进而发展思想更先进、功能更强大、解决更复杂系统的智能行为。
蚁群算法在求解复杂优化问题时具有快速性、分布式和全局优化的特征。其中，寻找最优解的快速性是通过信息素的正反馈机制来完成的，而其分布式计算的特征又避免了算法的早熟性收敛。同时，具有贪婪启发式搜索特征的蚁群系统又能在搜索过程的早期就找到可接受的解。
从复杂系统和复杂性科学的角度看，蚁群系统是一个复杂系统。蚁群系统寻找蚁穴到食物源最短路径的过程，是整个蚁群之间相互作用、相互影响、相互联系、相互协调的结果。蚁群算法本质上具有概率搜索的特征。对于蚁群算法理论问题的深入研究，可以为推广蚁群算法的应用领域奠定重要的理论基础。比如机器人系统、图像处理、制造系统、车辆路径系统、通信系统等领域。
7.2.2 模拟退火算法
模拟退火算法的随机优化思想，算法实现的质量和效率是与城市的坐标、城市之间的距离以及城市的个数密切相关的，要根据具体的情况选择合适的参数(初始温度、温度迭代参数、温度终止条件、内层循环次数、城市个数等)，然后对参数进行合理的优化，才能得到最理想的结果。可以说，这些参数的设置才是算法好坏的关键。本文主要是对模拟退火算法中的几个重要参数做了比较研究，并选择了经典的TSP问题作为求解对象得出了一组比较有效的参数组合。 大量实践表明模拟退火算法非常适合求解组合优化问题。它在一定程度上解决了旅游商问题，值得指出，模拟退火算法以二个引入注目的特性跻身于众多优化算法之中，并独树一帜。
（1）模拟退火方法不“贪婪”，它在解优化问题的过程中，解点可以在问题的局部极小的附近游荡，正因为如此，算法不会被容易找到但不能满足的局部极小点所蒙蔽，从而找到整体极小点。
（3）解点的决定具有逻辑倾向性，当控制参数T值大时，优于新解的当前解被新解替代的可能性大，随着T的减小，这种可能性随之减小，特别当T?0?时，这种可能性趋向于0.
模拟退火算法并不完善，虽然它具有较强的局部搜索能力，并能使搜索过程避免陷入局部最优解，但其的运行效率不高，如果把模拟退火算法和其他算法融合，将是提高运行效率和求解质量的有效手段。并且由于它是一种随机优化近似算法，一般只能求出近似最优解，且性能受到所用随机数序列的影响，这一缺点是模拟方式带来的，目前尚无法彻底解决。
总之，虽然模拟退火算法还不完善，但在无法得到实际问题精确最优解的情况下，无论从存储空间还是计算效率考虑，模拟退火算法都不失为一种优越的近似方法，特别是对解大规模NP–难道问题更是如此。
在问题规模较小时，蚂蚁算法和模拟退火算法都能取得不错的结果。在本文34个城市的TSP问题中，模拟退火算法的解的质量甚至优于蚂蚁算法；但是，
24
随着问题规模的增大，模拟退火算法的解开始恶化，这与模拟退火算法参数的选择有关。
7.3 模型的评价
本文分别对两个算法进行了编程计算与比较。计算所得到的最优解能很好的满足问题的需要。对于周先生的外出旅行提供了良好的参考方案。 模型的优点：
（1） 搜集了大量的数据，紧密的与实际相结合，得到的方案可行性强，能很好
的解决旅行方案的优化问题。
（2） 能较好的解决类似的组合优化问题。
（3） 对模型稍加修改，就可以应用于印刷电路板的钻孔路线方案、连锁店的货
物配送、网络布线等其他问题。
（4） 综合采用了蚁群算法与模拟退火算法，并进行收敛性与计算结果上的比较
分析，改进了算法的性能，提高了求解精度。
模型的缺点：
（1） 对于大规模优化问题，算法需要较长的搜索时间。 （2） 容易出现局部最优的情况
参考文献
[1] 韩忠庚.数学建模竞赛.北京:科学出版社，2007. [2] 姜启源，谢金星，叶俊.北京:高等教育出版社,2005.
[3] 郑宝东.线性代数与空间解析几何.北京:高等教育出版社,2003.
[4] 张志涌，杨祖樱.matlab教程.北京：北京航空航天大学出版社,2006. [5] 叶其孝.大学生数学建模辅导教材.长沙：湖南教育出版社，1993. [6] 韩中庚.实用运筹学.北京：清华大学出版社，2007.
25