龙源期刊网 http://www.qikan.com.cn
基于模拟退火与蚁群融合算法的路径规划问题
作者：刘乐芬
来源：《科学与信息化》2017年第08期
摘 要 模拟退火算法是一种通用的概率算法，用来在一个大的搜索空间内寻找问题的最优解，目前在生产调度、路径优化、神经网络等领域获得了广泛的应用。蚁群算法是一种仿生算法，作为通用型随机优化方法，它吸收了昆虫王国中蚂蚁的行为特征，通过其内在的搜索机制，在一系列困难的组合优化问题求解中取得了成效，蚁群算法最成功的应用是商旅问题（TSP），同模拟退火算法一样在路径规划问题上，蚁群算法也有着出色的表现。本文我们结合模拟退火和蚁群算法两者的优点得到一种新的融合算法，并以淄博市10个旅游景点的数据为基础，对两种算法分别进行了验证，并基于LABVIEW设计了一款简单实用的经纬度与大地坐标转化软件，取得了良好的效果。 关键词 模拟退火；蚁群算法；分析 1 模拟退火算法基本原理 1.1 模拟退火算法基本思想
现代的模拟退火算法形成起源于20世纪80年代初，其思想源于固体的退火过程，即将物体加热至足够高的温度，再慢慢冷却。升温时，固体内部粒子随着温度的升高变为无序状，内能增加，而缓慢冷却时粒子又逐渐趋于有序。从理论上讲，如果冷却过程足够缓慢，那么冷却中任意温度时固体都能达到热平衡，而冷却到低温时，则达到这一低温下的内能最小状态。我们将热力学的理论套用到统计学上，将搜寻空间内每一点想象成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。基于能量下降最快的梯度原理，模拟退火可获得温度下降最快的路径[1]。
1.2 模拟退火算法的基本步骤
模拟退火算法可以分解为解空间、目标函数和初始解三部分。
（1）初始化：初始温度T（充分大），初始解状态S（是算法迭代的起点）， 每个T值的迭代次数L。
（2）对k=1……L做第（3）至第6步：
龙源期刊网 http://www.qikan.com.cn
（3）产生新解S′。
（4）计算增量Δt′=C（S′）-C（S），其中C（S）为评价函数。 （5）若Δt′
（6）如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法。
（7）T逐渐减少，且T->0，然后转第2步。 1.3 模拟退火算法路径优化设计步骤 （1）路径优化问题的解空间和初始解
TSP问题的解空间S是遍访每个城市恰好一次的所有回路，是所有城市排列的组合。它的解空间S可以表示为的所有排列的集合，即
其中，每一个排列表示遍访个城市的一个路径，表示第i次访问城市。模拟退火算法的最优解和初始状态没有强的依赖关系，故初始解为随机函数生成的一个随机排列。 （2）目标函数
TSP问题的目标函数即为访问所有城市的路径总长度，也可以称为代价函数
TSP问题的求解就是通过模拟退火算法找出目标函数的最小值，相应的，即为TSP问题的最优解。
（3）新解的产生
新解的产生对问题的求解非常重要。新解可以通过分别或者交替使用以下两种方法来产生：
①二变化法：任选序号（设），交换之间的访问顺序。 ②三变化法：人选序号（设），将之间的路径插到之后访问。 （4）目标函数差与接受规则
计算变换前的解和变换后目标函数的差值：，以新解与当前解的目标函数差定义接受概率，即：
龙源期刊网 http://www.qikan.com.cn
2.4 基于模拟退火的淄博市旅游景点的路径规划
为了验证模拟退火算法在路径规划中的应用和路径规划的特点，我们选取淄博市鲁山森林公园、开元溶洞、周村古城等10个旅游景点进行路径的优化，根据模拟退火算法的基本思想和上述10个目标点的地理位置信息[2]，我们以MATLAB为程序软件编译平台获得如下的路径优化结果如图所示： 最终执行结果：
最短路径：3、4、10、5、6、8、1、7、2、9、3 收敛迭代次数：100（30） 程序执行时间：12.021秒 3 蚁群算法基本原理 3.1 蚁群算法的定义
蚁群算法（ant colony optimization， ACO），又称蚂蚁算法，是一种用来在图中寻找优化路径的概率型算法。针对PID控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值[3]。
3.2 蚁群算法的数学模型
对于TSP问题，为不失一般性，设整个蚂蚁群体中的数量为，城市的数量为，城市与城市之间的距离为，时刻城市与城市连接路径上的信息素的浓度为。初始时刻蚂蚁被放置在不同的城市里，且各个城市连接路径上信息素的浓度相同，不妨设。然后蚂蚁将按照一定的概率选择路线，不妨设为时刻蚂蚁从城市转移到城市的概率，我们都知道，“蚂蚁TSP”策略会受到两方面的左右，首先是访问城市的期望，另外便是蚂蚁释放信息素的浓度，所以定义： 其中为启发函数，表示蚂蚁从城市转移到城市的期望度为蚂蚁k访问待访问的城市结合，开始时，中个元素，即包括除了蚂蚁出发城市的其他多个城市，随着时间推移中的元素会越来越少，直到为空；为信息素重要程度因子，简称为信息素因子，其值越大，表明信息素强度影响越大；为启发函数重要的银子，简称启发函数因子，其值越大，表明启发函数影响越大。 在蚂蚁遍历各个城市的过程中，与实际情况相似的是，在蚂蚁释放信息素的同时，各个城市间连接路径上的信息素的强度也在通过挥发等方式逐渐消失。为了描述这一特征，不妨令（0