蚁群算法与粒子群算法优缺点
蚁群算法(ACO)是受自然界中蚂蚁搜索食物行为的启发,是一种群智能优化算法。它
基于对自然界真实蚁群的集体觅食行为的研究,模拟真实的蚁群协作过程。算法由若干个
蚂蚁共同构造解路径,通过在解路径上遗留并交换信息素提高解的质量,进而达到优化的
目的。蚁群算法作为通用随机优化方法,已经成功的应用于 TSP 等一系列组合优化问题中,
并取得了较好的结果。但由于该算法是典型的概率算法,算法中的参数设定通常由实验方
法确定,导致方法的优化性能与人的经验密切相关,很难使算法性能最优化。
蚁群算法中每只蚂蚁要选择下一步所要走的地方,在选路过程中,蚂蚁依据概率函数
选择将要去的地方,这个概率取决于地点间距离和信息素的强度。
(t+n) = (t)+ Δ (t+n)
上述方程 表示信息素的保留率,1- 表示信息素的挥发率,为了防止信息的无限积累,
取值范围限定在 0~1。Δ ij 表示蚂蚁 k 在时间段 t 到 (t +n)的过程中,在 i 到 j 的路径上留下
的残留信息浓度。
在上述概率方程中,参数 α 和 β:是通过实验确定的。它们对算法性能同样有很大的影
响。α 值的大小表明留在每个节点上信息量受重视的程度,其值越大,蚂蚁选择被选过的
地点的可能性越大。β 值的大小表明启发式信息受重视的程度。
这两个参数对蚁群算法性能的影响和作用是相互配合,密切相关的。但是这两个参数只能
依靠经验或重复调试来选择。
在采用蚁群-粒子群混合算法时,我们可以利用 PSO 对蚁群系统参数 α 和 β 的进行训
练。具体训练过程:假设有 n 个粒子组成一个群落,其中第 i 个粒子表示为一个二维的向
量 xi = ( xi1 , xi2 ) , i = 1, 2, ⋯,n,即第 i 个粒子在搜索空间的中的位置是 xi。换言之,每个
粒子的位置就是一个潜在的解。将 xi 带入反馈到蚁群系统并按目标函数就可以计算出其适
应值,根据适应值的大小衡量解的优劣。
蚁群算法的优点:
蚁群算法与其他启发式算法相比,在求解性能上,具有很强的鲁棒性(对基本蚁群算
法模型稍加修改,便可以应用于其他问题)和搜索较好解的能力。
蚁群算法是一种基于种群的进化算法,具有本质并行性,易于并行实现。
蚁群算法很容易与多种启发式算法结合,以改善算法性能。
蚁群算法存在的问题:
TSP 问题是一类经典的组合优化问题,即在给定城市个数和各城市之间距离的条件下,
找到一条遍历所有城市且每个城市只能访问一次的总路程最短的路线。蚁群算法在 TSP 问
题应用中取得了良好的效果,但是也存在一些不足:
(1),如果参数 α 和 β 设置不当,导致求解速度很慢且所得解的质量特别差。
(2),基本蚁群算法计算量大,求解所需时间较长。
(3),基本蚁群算法中理论上要求所有的蚂蚁选择同一路线,该线路即为所求的最优线路
但在实际计算中,在给定一定循环数的条件下很难达到这种情况。
另一方面,在其它的实际应用中,如图像处理中寻求最优模板问题,我们并不要求所
有的蚂蚁都找到最优模板,而只需要一只找到最优模板即可。如果要求所有的蚂蚁都找到
最优模板,反而影响了计算效率。
蚁群算法收敛速度慢、易陷入局部最优。蚁群算法中初始信息素匮乏。蚁群算法一般
需要较长的搜索时间,其复杂度可以反映这一点;而且该方法容易出现停滞现象,即搜索
进行到一定程度后,所有个体发现的解完全一致,不能对解空间进一步进行搜索,不利于
发现更好的解。
评论0