模拟退火算法在飞机巡航最佳路线问题中的应用

2015-09-18牛迎春曾璐璐包勇

软件导刊 2015年8期

牛迎春　曾璐璐　包勇

摘要：飞机巡航最佳路线问题可归结为大型TSP问题。TSP问题是典型的NP完全问题，模拟退火算法是求解NP完全问题的一种理想方法。在构造了飞机巡航路线问题的模型后，采用加权的哈密頓方法，结合模拟退火策略对该问題进行分析求解。重点介绍了模拟退火解决此问题的具体算法和过程。试验结果表明：采用模拟退火算法求解飞机巡航线路问题效果很好，与其它算法相比优势明显。

关键词：飞机巡航；哈密尔顿圈；模拟退火

DOIDOI：10.11907/rjdk.151318

中图分类号：TP312

文献标识码：A 文章编号文章编号：16727800（2015）008009402

0 引言

本文首先介绍了旅行商[1]问题，先列举TSP问题的应用，对其进行数学描述，然后介绍了哈密尔顿圈。之后重点介绍模拟退火算法，主要介绍其基本思想和关键技术，在此基础上将模拟退火的思想引入飞机巡航问题求解，并用MATLAB语言编程予以实现。

旅行商问题（Traveling Salesman Problem，TSP）是一个经典的图论问题，在物流配送、计算机网络、电子地图、

交通诱导、电气布线、VLSI 单元布局等方面都有重要的工程和理论价值，引起了许多学者的关注。TSP可简单描述为：设所有城市间两两连通，旅行商需要跑遍n个城市去推销其商品，而这些城市之间的距离都不一样。推销员要从其中一个城市出发把所有城市跑遍，最后回到出发地。

飞机巡航问题是典型的旅行商问题。假设我方有一个基地，派一架飞机从基地出发，侦察完敌方所有目标，再返回原来的基地。敌方每一目标点侦察时间不计，求该飞机所花费的最短时间。

模拟退火（Simulated Annealing）算法[2]是一种通过模拟金属物理退火过程的一种启发式算法，利用了物理中固体物质的退火过程与一般优化问题的相似性，从某一初始温度开始，伴随温度的不断下降，结合概率突跳特性，在解空间中随机寻找全局最优解。

1 数学规则模型

VRP[3]问题在图论上一般描述为：记G=（V，E）为无向图，其中V={vi|i=0，1，2，，n-1}为顶点集合，E={（vi，vj）|vi，vj∈V，i≠j}为各顶点相互连接组成的边集，在该无向图中顶点v1，v2，…，vn-1表示飞机巡航的目标数，dij表示vi，vj两点的距离。

2 飞机巡航问题的求解方法

人们解决问题一般采用就近原则。本文先给出了一个在随机状态下的路径图，这在实际生产生活中会对资源造成巨大浪费，影响生产效率。

图1 随机路径

2.1 哈密顿回路算法解决飞机巡航问题

给定图G，若存在一条路，经过图中每个节点恰好一次，这条路称作哈密尔顿路。若存在一条回路，经过图中每个节点恰好一次，这条路称为哈密尔顿回路。具有汉密尔顿回路的图称作哈密尔顿图。上述问题就是在哈密顿图中找到一个权数最小的哈密顿圈C，然后用Matlab编程得到哈密尔顿最优路径总长度为：

图2 最优哈密尔顿路径

从图2可以看出，哈密尔顿最优路径与随机路径比起来，访问目标有了巨大进步，有了最优路径。但由于初始路径不同，得到的最终路径也不一样，为解决这一问题，引入模拟退火算法。

2.2 模拟退火算法

模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却。加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解[4]。

2.2.1 模拟退火算法步骤

模拟退火算法[5]可以分解为解空间、目标函数和初始解3部分。

①初始化：初始温度T（充分大），初始解状态S（是算法迭代的起点），每个T值的迭代次数L；②对k=1，……，L做第（3）至第6步；③产生新解S′；④计算增量Δf=C（S′）-C（S），其中C（S）为评价函数；⑤若Δf<0，则接受S′作为新的当前解，否则以概率exp（-ΔfT）接受S′作为新的当前解；⑥如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常为连续若干个新解都没有被接受；⑦T逐渐减少，且T→0，然后转第②步。

2.2.2 模拟退火算法过程描述（1）解空间S可表示为{1，2，3…102}的所有固定起点和终点的集合，为了方便编程，把出发地定位编号1，最后回到出发地的编号定位102，中间的目标位置为{2，3，4，…101}。

（2）目标函数：目标函数就是代价函数为巡视所有目标的路径长度，满足：

为产生明显对比，本文给出3种方法求解飞机巡航问题。随机路径图在数据量较小的情况下，对资源没有太大影响。但随着数据量的增大，对资源的损耗也会成倍增长。哈密尔顿最优路径与随机路径比有了很大进步，但哈密尔顿最优路径是由局部最优逐步扩充到全局最优的，选取不同的初始圈，得到的最终结果就会不一样。模拟退火

算法是一种随机性解决组合优化方法，结合了概率突跳性，可以求解出优化问题的全局最优或近似全局最优解[6]。

图3 模拟退火求得的最优路径

通过实验数据的比较与分析，可知模拟退火是3种方法中最优的。因此，用模拟退火算法求解飞机巡航问题最有效。

3 结语

本文给出了图论中的哈密尔顿圈算法、模拟退火算法，通过算法对比，使问题得到了很好的解决。模拟退火算法可以有限度地接受劣解、跳出局部最优解、原理简单、使用灵活、适合求解出优化问题的全局最优或近似全局最优解。

参考文献：

[1] 曲晓丽，潘昊，柳向斌.旅行商问题的一种模拟退火算法求解[J].现代电子技术，2007（18）：7882.

[2] 高尚.求解旅行商问题的模拟退火算法[J].华东船舶工业学院学报：自然科学版，2003，17（3）：1316.

[3] 左孝凌.离散数学[M].北京：经济科学出版社，2000：117134.