智能算法-蚁群算法(3)

智能算法-蚁群算法(3)插图

1. 蚁群算法

蚁群算法基本概念及名词解释请参考 智能算法-蚁群算法(1)

蚁群算法实例详解请参考 智能算法-蚁群算法(2)

蚁群算法通俗概括:一群蚂蚁想寻找食物。在讨论下,它们决定分头去寻找食物,首先为每只蚂蚁随机选择出发地,规定每只蚂蚁爬行速度相同,并且每只蚂蚁在爬过的地方会释放信息素,信息素会随着时间逐渐挥发,残留在地上的浓度会越来越低。之后的蚂蚁会更倾向于去探索信息素残留浓度高的那条路,因为这说明上一只蚂蚁爬过这条路找到当前最优解所用的时间短,从而每只蚂蚁就知道下一个探索节点选择哪里(信息素浓度高的路径概率大)。以这样的方式,构造出每只蚂蚁的完整探索路径。接下来,进行第二轮寻找,更新好每条路径上的信息素浓度。再以上述的方式构造出完整路径。就这样,经过多轮寻找,和不断更新信息素浓度,最终找到最优路径(最优解)。

2. 蚁群算法的改进

2.1 精英策略

蚂蚁系统中的精英策略(Ant System with elitist strategy):

  • 每次循环之后给予最优解以额外的信息素量(最优解就相当于是这群解中的精英)
  • 这样的解被称为全局最优解(global-best solution)
  • 找出这个解的蚂蚁被称为精英蚂蚁(elitist ants)
  • 额外的信息素量相当于一种补偿

特点:

  • 可以使蚂蚁系统找出更优的解
  • 找到这些解的时间更短
  • 精英蚂蚁过多会导致搜索早熟收敛

2.2 基于排列的蚂蚁系统

可以考虑给蚂蚁要释放的信息素大小加上一个权值,进一步加大各边信息素量的差异,以指导搜索。在每一轮所有蚂蚁构建完路径后,它们将按照所得路径的长短进行排名,只有生成了至今最优路径的蚂蚁和排名在前几位的蚂蚁才被允许释放信息素,蚂蚁在边(i,j)上释放的信息素的权值由蚂蚁的排名决定。(排名靠前的蚂蚁才能释放)

2.3 最大最小蚂蚁系统(Max-Min Ant System)

为了充分利用循环最优解和到目前为止找出的最优解,在每次循环之后,只有一只蚂蚁进行信息素更新。这只蚂蚁可能是找出当前循环中最优解的蚂蚁,也可能是找出从实验开始以来最优解的蚂蚁。即只允许迭代最优解蚂蚁或者至今最优解蚂蚁释放信息素。

信息素量大小的取值范围被限制在一个区间内

信息素初始值为信息素取值区间的上限,并伴随着一个较小的信息素蒸发速率

每当系统进入停滞状态,问题空间内所有边上的信息素量都会被重新初始化。 最大最小蚂蚁系统轨迹更新公式如下:

智能算法-蚁群算法(3)插图1

3. 参数配置

3.1 蚂蚁数量

蚂蚁数目的大小对蚁群算法的收敛性能的影响基本呈线性规律变化

  • 过大,搜索能力强但速度慢
  • 过小,搜索能力差,易早熟(可以想象如果只有1只蚂蚁,无论走的好坏,都只能听它的,比较极端)

对于旅行商(TSP)问题蚂蚁数量𝑚取值范围通常为:m=√𝑛∼𝑛/2,其中 n 为问题的规模,即城市的数量。

3.2 信息素权重α与启发式信息权重β

α与β决定算法搜索的导向,影响算法的搜索能力。

设蚂蚁𝑘从城市𝑖选择城市𝑗作为下一个访问对象的概率公式为:智能算法-蚁群算法(3)插图2启发信息因子α:

  • 反映蚂蚁在运动过程中所积累的信息素量在指导搜索中的相对重要程度
  • 反映了蚁群在路径搜索中随机性因素的强度
  • α越大,蚂蚁选择以前走过的路径的可能性大,搜索的随机性减弱
  • α越小,最邻近城市被选中的概率越大,蚂蚁越注重“眼前利益”(比较贪婪)
  • 通常α的取值范围为:2~5

信息素浓度因子β:

  • 反映蚁群在路径搜索中先验性、确定性因素作用的强度
  • β越大,蚂蚁在某个局部点上选择局部最短路径的可能性越大,蚁群搜索最优路径的随机性减弱,易陷入局部最优
  • β越小,蚂蚁越倾向于根据信息素浓度确定路径,算法收敛越快
  • 通常β的取值范围为:2~5

3.3 信息素挥发因子ρ

  • 影响蚂蚁个体之间相互影响的强弱,关系到全局搜索能力和收敛速度
  • ρ较大时,信息素挥发速率大,降低算法的全局搜索能力
  • ρ较小时,算法具有较高的全局搜索能力,但收敛速度较慢
  • 通常情况下对于未进行改进的蚁群算法,ρ的取值为0.5

3.4 初始信息素量

  • 决定算法在初始化阶段的探索能力,影响算法的收敛速度
  • 过小,未被蚂蚁选择过的边上信息素太少,蚂蚁很快就全部集中在一条局部最优的路径上,算法容易早熟
  • 过大,信息素对搜索方向的引导能力增长得十分缓慢,算法收敛慢

3.5 终止条件(准则)

决定算法何时结束,需要由具体的应用和问题本身来进行确定。

  • 将最大循环数设为500,1000,5000等(规定迭代次数)
  • 得到可接受的解即可(测算当前是否在可接受范围内)
  • 当前最优解连续K次相同(当前最优解连续好几次已经不变了)
  • 目标值控制规则,给定优化问题的一个下界和一个误差值,当算法得到的目标值与给定下届之差小于给定的误差值时,算法终止。

发表评论

后才能评论