蚁群算法是macro dorigo在1992年博士论文中所阐述的图中寻找最优路径的算法,他是自然蚂蚁群在觅食过程中搜索路径的模拟。蚁群算法具有分布式计算、无中心控制和分布式固溶体之间间接通信等特征,易于与其他优化算法相结合,它通过简单个体之间的写作表现出求解复杂问题的能力,被广泛运用于求解优化问题。蚁群算法不涉及复杂的数学操作,其处理过程对计算机的软件硬件要求也不高,因此对他的研究在理论和实践中都具有重要意义。
1、缺点
(1)收敛速度慢。蚁群算法中信息素初值相同,选择下一个节点时倾向于随机选择。虽然随机选择能探索更大的任务空间,有助于找到潜在的全局最优解,但是需要较长时间才能发挥正反馈的作用,导致算法初期收敛速度较慢。
(2)局部最优问题。蚁群算法具有正反馈的特点,初始时刻环境中的信息素完全相同,蚂蚁几乎按随机方式完成解的构建,这些解必然会存在优劣之分。在信息素更新时,蚁群算法在较优解经过的路径上留下更多的信息激素,而更多的信息激素又吸引了更多的蚂蚁,这个正反馈的过程迅速地扩大初始的差异,引导整个系统向最优解的方向进化。虽然正反馈使算法具有较好的收敛速度,但是如果算法开始得到的较优解为次优解, 那么正反馈会使次优解很快占据优势,使算法陷入局部最优,且难以跳出局部最优。
(3)优化能力问题。蚁群算法中参数众多并且具有一定的关联性,虽然蚁群算法在很多领域都有广泛应用,但是参数选择更多是依赖经验和试错,不恰当的初始参数会减弱算法的寻优能力。当进行路径规划时,为避免形成环形路径或者重复访问某些节点在算法中设置禁忌表,但是禁忌表很容易造成“死锁”现象,减少种群中的有效蚂蚁数量,降低算法的优化效率。
(4)种群多样性与收敛速度的矛盾。种群多样性对应于候选解在问题空间的分布。个体分布越均匀,种群多样性就越好,得到全局最优解的概率就越大,但是寻优时间就越长;个体分布越集中,种群多样性就越差,不利于发挥算法的探索能力。正反馈加快了蚁群算法的收敛速度,却使算法较早地集中于部分候选解,因此正反馈降低了种群的多样性,也不利于提高算法的全局寻优能力。
2、单蚁群算法的改进
主要从以下几个方面:文章来源:https://www.toymoban.com/news/detail-814839.html
- 蚁群算法的结构改进
- 蚁群算法的参数优化
- 信息素初始化方法的改进
- 信息素更新规则的改进
3、关键参数分析
信息素启发因子: α
其值越大,蚂蚁在选择以前走过的路径的可能性就越大,搜索的随机性就会减弱;而当启发式因子 α 的值过小时,则易使蚁群的搜索过早陷于局部最优。根据经验,信息素启发式因子 α 取值范围一般为 [1,4]时,蚁群算法的综合求解性能较好。
启发式因子: β
期望启发因子 β 表示在搜索时路径上的信息素在指导蚂蚁选择路径时的向导性。期望启发因子 β 的值越大,蚂蚁在某个局部点上选择局部最短路径的可能性就越大,虽然这个时候算法的收敛速度得以加快,但蚁群搜索最优路径的随机性减弱,而此时搜索易于陷入局部最优解。根据经验,期望启发因子 β 取值范围一般为[3,5],此时蚁群算法的综合求解性能更好。
信息素蒸发系数: ρ
信息素蒸发系数 ρ 大小的选择将直接影响到整个蚁群算法的收敛速度和全局搜索性能。ρ 表示信息素蒸发系数,1-ρ 则表示信息素持久性系数。因此,ρ的取值范围应该是0~1之间的一个数
ρ 过小时,则表示以前搜索过的路径被再次选择的可能性过大,会影响到算法的随机性能和全局搜索能力;ρ 过大时,说明路径上的信息素挥发的相对变多,虽然可以提高算法的随机搜索性能和全局搜索能力,但过多无用搜索操作势必会降低算法的收敛速度。
蚂蚁数目: m
蚂蚁数目增大后,会使大量的曾被搜索过的解(路径)上的信息素变得趋于平均,信息正反馈的作用不明显。虽然搜索的随机性得到了加强,但收敛速度减慢。反之,(蚂蚁数量少),特别是当要处理的问题规模比较大时,会使那些从来未被搜索到的解(路径)上的信息素减小到接近于0,搜索的随机性减弱,虽然收敛速度加快了,但会使算法的全局性能降低,算法的稳定性差,容易出现过早停滞现象。
m 一般取 10 ~ 50
信息素强度: Q
参数 Q 不必作特别的考虑,可以任意选取。
最大进化代数:G
一般 G 取 100 ∼ 500 文章来源地址https://www.toymoban.com/news/detail-814839.html
到了这里,关于蚁群算法优缺点及改进方法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!