论文部分内容阅读
[摘要]蚁群算法是一种新型的群智能优化算法,自提出以来,因其正反馈性、自组织性以及并行性等优点在很多领域取得了很好的应用。本文介绍了基本蚁群算法的寻优方式和数学模型,并针对其收敛速度慢、易陷入局部最优解的缺点,采用自适应调整信息素挥发因子的值的策略进行改进。并用MATLAB软件运行了改进前后的算法程序,对比求得的结果,证明了所做改进的正确性和有效性。
[关键词]基本蚁群算法改进蚁群算法旅行商问题
中图分类号:K919 文献标识码:K 文章编号:1009―914X(2013)28―0488―01
1、基本蚁群算法
1.1 蚁群算法思想
蚁群寻找食物过程可以这样表示,每只蚂蚁独立地搜索食物,当它们碰到一个障碍物时,就随机挑选一条可行的路径前行,同时释放出与路径长度有关的被称为信息素的化学物质。当后续的蚂蚁再次碰到这个障碍物的时候,能够感知到这种信息素的存在,就会以较大的概率选择信息素浓度较高的路径,且在这条路径上继续释放信息素,影响后来的蚂蚁,整个蚁群就通过这种正反馈过程找到了食物。
1.2 基本蚁群算法求解TSP问题的数学模型
为了更好地理解蚁群算法,本文以求解平面上 n 个城市的 TSP 问题为例来说明该算法的数学模型和寻优过程。TSP问题可以简单地描述為:给定n个城市和它们两两之间的直线距离,寻找一条闭合的路径,使得每个城市刚好经过一次回到出发点且总的距离最短。为模拟蚁群觅食行为,引入以下记号:m——蚁群中蚂蚁总数;n——城市个数; ——¬¬¬¬¬城市i与城市j之间的直线距离; ——路径(i,j)的能见度; ——启发因子; ——期望启发因子; ——信息素挥发因子 , 即为信息素的残留系数; ——蚂蚁完成所有城市周游在所经过的路径上释放的信息素总量; ——时刻t路径(i,j)上残留的信息素量; ——一次循环中蚂蚁在所经路径(i,j)上的信息素增量; ——第k只蚂蚁在一次循环中留在路径(i,j)上的信息素量; ——t时刻蚂蚁k由城市i转移到城市j的概率。
在初始时刻,各条路径上都有一定量且相等的信息素浓度,即设 常数。蚂蚁k在搜索过程中根据各条路径上信息素浓度决定其转移方向,在t时刻,蚂蚁k由城市i选择城市j的概率公式 可表示为:
(1)
其中, 表示蚂蚁k下一步能够选择的城市集合, 为用来记录蚂蚁k当前已经走过的城市集合的。蚂蚁在所经过的路径上留下信息素,同时随着算法的进行,以前留下的信息素也会逐渐流逝,因此,需要对路径上的信息素每隔一段时间进行更新处理。设(t+n)时刻,蚂蚁要对路径(i,j)上的信息素进行更新处理,其更新公式如下:
(2)
(3)
(4)
其中 表示第k只蚂蚁在完成一次循环后所走路径的总长度。
2、自适应蚁群算法
在蚁群算法中,信息素挥发因子 的取值对算法的全局搜索能力及收敛速度有着较大的影响[3]。由于信息素挥发因子 的存在,使那些从未被搜索到路径上的信息量会减小到接近于0,这样就降低了算法搜索全局最优解的能力。根据公式(1)和(2),解的信息素浓度会随着 的增大而增大,那么以前搜索过的解就会以很大的概率被再次搜索到,这就降低了算法搜索全局最优解的能力。然而,减小 虽然可以提高算法的全局搜索能力,但又会增加搜索时间降低收敛速度。因此本文对此进行了改进,让信息素挥发因子 的取值在搜索过程中自适应地改变大小来提高算法的全局搜索能力而又不降低其收敛速度;如果蚁群算法求得的最优值在一定次数循环内没有明显改进,则对信息素挥发因子 按照以下公式作自适应调整:
(5)
上式中,用 作为为 的最小值来防止因它的值过小而降低算法的收敛速度。
3、仿真实验
根据以上所述,本文选用TSP库中的30个城市的TSP问题,用MATLAB软件进行编程求解。30城市的位置坐标为:
[41,94;37,84;54,67;25,62;7,64;2,99;68,58;71,44;54,62;83,69;64,60;18,54;22,60;83,46;91,38;25,38;24,42;58,69;71,71;74,78;87,76;18,40;13,40;82,7;62,32;58,35;45,21;41,26;44,35;4,50],城市距离理论值为423.7406。根据相关文献[4],本文选用的参数组合为: 、 、 、 、 以及信息素初始值取为1。用MATLAB软件对基本蚁群算法和自适应调整信息素的蚁群算法各进行20次仿真,记录每次迭代时间和求得的解,取其中最优解、最差解和计算的平均解、平均时间以及误差率制作表1。其中:
4、结束语
本文对基本蚁群算法做了较详细的介绍,并且针对其容易陷入局部最优和收敛速度慢的问题,采用自适应调整信息素挥发因子的策略来改进算法。用MATLAB软件运行了改进前后的蚁群算法程序,对比改进前后蚁群算法的求解结果可知,改进后的蚁群算法求得的最优解、最差解、平均解、误差率以及所用的平均时间都要优于改进前的基本蚁群算法,即能用较短的时间求得较好的解,而且满足误差条件。
参考文献:
[1]Dorigo M.,Gambardella L M.Ant colonies for the travelling salesman problem[J].Biosystems.1997,43(2):73-81.
[2]孙昌志,曲春雨,陈东阳.改进蚁群算法及其在永磁同步电机设计中的应用[J].沈阳工业大学学报2006,28(6):601.2008,22(1):9-11.
[关键词]基本蚁群算法改进蚁群算法旅行商问题
中图分类号:K919 文献标识码:K 文章编号:1009―914X(2013)28―0488―01
1、基本蚁群算法
1.1 蚁群算法思想
蚁群寻找食物过程可以这样表示,每只蚂蚁独立地搜索食物,当它们碰到一个障碍物时,就随机挑选一条可行的路径前行,同时释放出与路径长度有关的被称为信息素的化学物质。当后续的蚂蚁再次碰到这个障碍物的时候,能够感知到这种信息素的存在,就会以较大的概率选择信息素浓度较高的路径,且在这条路径上继续释放信息素,影响后来的蚂蚁,整个蚁群就通过这种正反馈过程找到了食物。
1.2 基本蚁群算法求解TSP问题的数学模型
为了更好地理解蚁群算法,本文以求解平面上 n 个城市的 TSP 问题为例来说明该算法的数学模型和寻优过程。TSP问题可以简单地描述為:给定n个城市和它们两两之间的直线距离,寻找一条闭合的路径,使得每个城市刚好经过一次回到出发点且总的距离最短。为模拟蚁群觅食行为,引入以下记号:m——蚁群中蚂蚁总数;n——城市个数; ——¬¬¬¬¬城市i与城市j之间的直线距离; ——路径(i,j)的能见度; ——启发因子; ——期望启发因子; ——信息素挥发因子 , 即为信息素的残留系数; ——蚂蚁完成所有城市周游在所经过的路径上释放的信息素总量; ——时刻t路径(i,j)上残留的信息素量; ——一次循环中蚂蚁在所经路径(i,j)上的信息素增量; ——第k只蚂蚁在一次循环中留在路径(i,j)上的信息素量; ——t时刻蚂蚁k由城市i转移到城市j的概率。
在初始时刻,各条路径上都有一定量且相等的信息素浓度,即设 常数。蚂蚁k在搜索过程中根据各条路径上信息素浓度决定其转移方向,在t时刻,蚂蚁k由城市i选择城市j的概率公式 可表示为:
(1)
其中, 表示蚂蚁k下一步能够选择的城市集合, 为用来记录蚂蚁k当前已经走过的城市集合的。蚂蚁在所经过的路径上留下信息素,同时随着算法的进行,以前留下的信息素也会逐渐流逝,因此,需要对路径上的信息素每隔一段时间进行更新处理。设(t+n)时刻,蚂蚁要对路径(i,j)上的信息素进行更新处理,其更新公式如下:
(2)
(3)
(4)
其中 表示第k只蚂蚁在完成一次循环后所走路径的总长度。
2、自适应蚁群算法
在蚁群算法中,信息素挥发因子 的取值对算法的全局搜索能力及收敛速度有着较大的影响[3]。由于信息素挥发因子 的存在,使那些从未被搜索到路径上的信息量会减小到接近于0,这样就降低了算法搜索全局最优解的能力。根据公式(1)和(2),解的信息素浓度会随着 的增大而增大,那么以前搜索过的解就会以很大的概率被再次搜索到,这就降低了算法搜索全局最优解的能力。然而,减小 虽然可以提高算法的全局搜索能力,但又会增加搜索时间降低收敛速度。因此本文对此进行了改进,让信息素挥发因子 的取值在搜索过程中自适应地改变大小来提高算法的全局搜索能力而又不降低其收敛速度;如果蚁群算法求得的最优值在一定次数循环内没有明显改进,则对信息素挥发因子 按照以下公式作自适应调整:
(5)
上式中,用 作为为 的最小值来防止因它的值过小而降低算法的收敛速度。
3、仿真实验
根据以上所述,本文选用TSP库中的30个城市的TSP问题,用MATLAB软件进行编程求解。30城市的位置坐标为:
[41,94;37,84;54,67;25,62;7,64;2,99;68,58;71,44;54,62;83,69;64,60;18,54;22,60;83,46;91,38;25,38;24,42;58,69;71,71;74,78;87,76;18,40;13,40;82,7;62,32;58,35;45,21;41,26;44,35;4,50],城市距离理论值为423.7406。根据相关文献[4],本文选用的参数组合为: 、 、 、 、 以及信息素初始值取为1。用MATLAB软件对基本蚁群算法和自适应调整信息素的蚁群算法各进行20次仿真,记录每次迭代时间和求得的解,取其中最优解、最差解和计算的平均解、平均时间以及误差率制作表1。其中:
4、结束语
本文对基本蚁群算法做了较详细的介绍,并且针对其容易陷入局部最优和收敛速度慢的问题,采用自适应调整信息素挥发因子的策略来改进算法。用MATLAB软件运行了改进前后的蚁群算法程序,对比改进前后蚁群算法的求解结果可知,改进后的蚁群算法求得的最优解、最差解、平均解、误差率以及所用的平均时间都要优于改进前的基本蚁群算法,即能用较短的时间求得较好的解,而且满足误差条件。
参考文献:
[1]Dorigo M.,Gambardella L M.Ant colonies for the travelling salesman problem[J].Biosystems.1997,43(2):73-81.
[2]孙昌志,曲春雨,陈东阳.改进蚁群算法及其在永磁同步电机设计中的应用[J].沈阳工业大学学报2006,28(6):601.2008,22(1):9-11.