机器学习 蚁群算法ACO

蚁群算法(ACO)

  • 蚁群算法可用来旅行商问题、指派问题、Job—shop调度问题、车辆路由问题、图着色问题和网络路由问题等。并且表现出了很大的优越性,因为它分布式特性,鲁棒性(健壮性,稳定鲁棒性和性能鲁棒性)强并且容易与其它算法结合,但是同时也存在这收敛速度慢,容易陷入局部最优(local optimal)等缺点。
  • 蚁群算法的基本原理:
    • 1、蚂蚁在路径上释放信息素。
    • 2、碰到还没走过的路口,就随机挑选一条路走(可用visit集合,防止蚂蚁原地打转)。同时,释放与路径长度有关的信息素(更新信息素)。
    • 3、信息素浓度与路径长度成反比。后来的蚂蚁再次碰到该路口时,就选择信息素浓度较高路径。
    • 4、最优路径上的信息素浓度越来越大。
    • 5、最终蚁群找到最优寻食路径。
  • 参数
    • ALPHA:信息启发因子,值越大,则蚂蚁选择之前走过的路径可能性就越大,值越小,则蚁群搜索范围就会减少,容易陷入局部最优(防止系统演化时间较长)
    • BETA:Beta值越大,蚁群越就容易选择局部较短路径,这时算法收敛速度会加快,但是随机性不高,容易得到局部的相对最优
  • 特点
    • 采用正反馈机制,使得搜索过程不断收敛,最终逼近最优解。
    • 每个个体可以通过释放信息素来改变周围的环境,且每个个体能够感知周围环境的实时变化,个体间通过环境进行间接地通讯。
    • 搜索过程采用分布式计算方式,多个个体同时进行并行计算,大大提高了算法的计算能力和运行效率。
    • 启发式的概率搜索方式不容易陷入局部最优,易于寻找到全局最优解。
  • 补充
    • 城市距离可以用欧氏距离
    • 信息素会挥发,故信息素浓度与经过路径长度成反比