基于蚁群-模拟退火算法的基站选址研究

赵敏 佘磊 陈炳桥 樊思琪

摘 要：蚁群算法虽然在蚂蚁算法的基础上已经有了改进但仍然会有缺陷，最大的缺点就是会陷入局部最优解。模拟退火算法最大的特点就是有一个蒙地卡洛判断准则，允许其接受一个较差解，不過算法却恰恰因为这点而会非常的耗时。通过理论的研究发现可以将这两种算法融合在一起，两种算法可以实现互补。最终便选择基站选址这个实际应用问题去用matlab仿真看是否真的可以减少基站的建设数量。

关键词：模拟退火;蚁群;基站选址

引言

基站的作用就是来覆盖用户，目前对于被覆盖用户，会根据不同的用户特性分为不同的等级，一般分为高级用户和低级用户。对于覆盖要求是：高级用户全覆盖，普通用户尽可能覆盖但不低于70%。对于基站的选择问题，可以看作是一个多目标智能优化的选择，这样便可以将一些传统算法加在选址中，可以有效地减少基站的建设数量。

1.模拟退火算法

模拟退火实际上算是一种贪心算法的改进，就是为了避免寻找到局部最优解。模拟退火算法是模仿固体降温的一种概率算法。在热力学中温度越高固体内部的状态越无序，而当温度慢慢降低时固体内部的状态变逐渐趋于稳定，在每一个温度下都会有一个平衡状态直到最后在常温下达到平衡状态即最佳状态。需要注意的是降温是一个缓慢的过程不能快速降，否则会破坏物体内部的晶体状态从而导致找不到合适的位置。模拟退火最大的特点就是在于Metropolis的判断准则，在t温度下的平衡概率为                     ，其中k为Boltzmann常数，△E为固体内部能量的变化大小，将E变成目标函数，温度T变成控制参数。整个算法是由初始解和参数t开始，其过程为初始解->得到新解->计算目标差->判断是否接受，在满足该温度下的迭代次数后不断降低参数t的值直到t降为常温。因为其接受较差解的特性可以发现模拟退火算法有全局的优化功能。

2.蚁群算法

蚁群算法就是模仿现实中蚂蚁觅食的过程。现实中的蚂蚁都是通过嗅觉来完成食物的寻找任务，路径上的信息素越多则该路径被选择的概率越大。t时刻第i只蚂蚁由位置i转移到位置j的概率为：

信息素更新的表达式为：

于是可以看出信息素的大小对路径的选择至关重要，所以对信息素的更新蚁群算法还分成了三个不同的模型分别是：蚁密模型，蚁量模型，蚁周模型。蚁密模型和蚁量模型都是在蚂蚁经过两个点后开始更新信息素。区别在于后者的信息素更新会考虑到路径的长度。本文采用的是第三种模型-蚁周模型，因为相比较于其它两种模型的实时更新，蚁周模型的全局更新显得更加的高效，毕竟是从全局出发而前两种只是从局部出发。

3.混合算法

模拟退火算法可以在全局中找到最优解但耗时过长，特别是在处理大规模数据的时候这一点会显得更外得明显，这就是为了找到全局最优解所付出的代价。蚁群算法的耗时短是因为蚂蚁在选择路径时根据信息素的强度来做出判断所以极其容易陷入局部最优解。最开始的时候每条路径上的信息素都一样，如果在蚁群中有一只蚂蚁在第前几轮的迭代过程中便发现了一条较优秀的路径，那么便会对后面蚂蚁的选择产生干扰。随后越来越多的蚂蚁选择这条路径，最终被确定为最优路径，然而从全局来看这并不是一条最优路径。蚁群-模拟退火混合算法正好将这两个算法相融合，用Metropolis判断准则去消除蚁群算法中的陷入局部最优解的情况，在蚁群算法的框架下使用模拟退火算法可以解决模拟退火算法耗时长的缺点。为了证明自己的理论是正确的，这里选用matlab在基站选址这实际问题中进行仿真，来验证混合算法在实际应用的过程中是否会真的像理论上分析的那样可以减少基站的建设数量。

三张仿真图依次是蚁群算法，模拟退火算法，蚁群-模拟退火算法。从仿真图上的运行效果来看，蚁群-模拟退火混合算法所需要的基站数量最少是7个而蚁群算法需要10个，模拟退火算法需要8个。从建设数量上来看，蚁群-模拟退火算法无疑是具有实际效益的，所需要的建设数量均比其它两种算法小，这样便可以减少资金放大投入，很好的达到了我们所需要的预期效果。这恰好证明了本文所提出的蚁群-模拟退火算法不仅仅具有理论上的可行性，而且还具有实际的应用意义。

参考文献：

[1]姜晓涛.基于模拟退火的蚁群算法求解网格任务调度问题 [D] . 安徽大学 2012

[2]周岩，王学瑞.基于模拟退火与蚁群算法的图像边缘检测 [J].兰州工业学院学报， 2016，23（3）

[3]王琛.基于TSP的蚁群退火混合算法研究 [J].山西师范大学学报（自然科学版，2014，28（3）

[4]张弛，涂立.新型蚁群算法在TSP 问题中的应用 [J].中南大学学报（自然科学版）， 2015，46（8）

[5]秦军，董倩倩.基于蚁群模拟退火的云任务调度算法改进 [J].计算机技术与发展， 2017，27（3）