蚁群算法

蚁群算法是对自然界蚂蚁的寻径方式进行模拟而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下信息素进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此来指导自己的运动方向。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大

蚁群算法

• 1. 蚁群算法理论
  • I. 人工蚁群优化过程
    • 根据信息素浓度的高低，寻找蚁巢到食物的最短路径
    • 较短路径信息素浓度高
    • 人工蚁群选择吓一跳路径的时候是按着一定算法规律有意识的寻找最短路径， 而不是盲目的
    • m只蚂蚁在图的相邻节点间移动，转移概率参数决定 运用当前所在节点存储的信息，计算下一步可达节点的概率
      • 1.信息素值——信息素痕迹
        • 信息素更新方式
          • 1.挥发
          • 2.增强
      • 2.可见度——先验值
  • II. 真实蚂蚁与人工蚂蚁的异同
    • 相同点
      • 1. 一群相互协作的个体
      • 2. 使用信息素的迹和蒸发机制
      • 3. 搜索到最短路径和局部移动
      • 4. 随机状态转移策略
        • 按照概率鞠策规则从一种状态转移到另一种相邻状态
    • 不同点
      • 1. 人工蚂蚁生活在离散的时间
        • 从一种离散状态到另一种离散状态
      • 2. 人工蚂蚁具有内部状态
        • 具有记忆性，记住自己走过的地方
      • 3. 人工蚂蚁释放信息素的数量是生成解的质量的函数
      • 4. 人工蚂蚁更新信息素的时机依赖于特性的问题
  • III. 算法特点
    • 并行性
    • 自组织性
    • 鲁棒性
    • 正反馈性
• 2. 基本算法及其流程
  • I. 参数初始化
    • 时间t=0和循环次数Nc = 0，设置最大循环次数G，将m个蚂蚁置于n个元素（城市）上，令有向图上每条边(i，j)的初始化信息量τij (t) = c，其中c表示常数，且初始时刻Δτij (0) = 0。
  • II. 循环次数Nc = Nc + 1
  • III. 蚂蚁的禁忌表索引号k = 1
  • IV. 蚂蚁数目k = k + 1
  • V. 蚂蚁个体根据状态转移概率公式计算的概率选择元素j并前进，j∈{ Jk (i)}
  • VI. 修改禁忌表指针，即选择好之后将蚂蚁移动到新的元素，并把该元素移动到该蚂蚁个体的禁忌表中。
  • VII. 若集合C中元素未遍历完，即k < m，则跳转到第（4）步；否则执行第（8）步
  • VIII. 记录本次最佳路线
  • IX. 更新每条路径上的信息量
    • 标准更新方法
    • Ant-cycle
    • Ant-quality
  • X. 若满足结束条件，即如果循环次数Nc ≥ G，则循环结束并输出程序优化结果；否则清空禁忌表并跳转到第（2）步。
• 3. 改进的蚁群算法
  • I. 精英蚁群算法
    • 相应的信息素修改公式为
  • II. 最大最小蚂蚁系统
    • 与蚂蚁系统不同，只对一只蚂蚁进行信息素的更新
    • 每个解元素上的信息素轨迹量的值域范围被限制在
    • 将信息素初始化为
  • III. 基于排序的蚂蚁算法
    • 在修改信息素路径前，蚂蚁按照它们的旅行长度进行排名（短的靠前）， 蚂蚁释放信息素的量要和蚂蚁的排名相乘
  • IV. 自适应蚁群算法
    • 在每次循环结束后求出最优解，并且保留
    • 自适应的改变p的值
• 4. 关键参数说明
  • 信息素启发因子
    • 反映了蚁群在路径搜索中随机性因素作用的强度， 其值越大，蚂蚁在选择以前走过的路径的可能性就越大，搜索的随机性就会减弱；而当启发式因子α的值过小时，则易使蚁群的搜索过早陷于局部最优 一般为[1,4]
  • 期望启发因子β
    • 反映了蚁群在搜索最优路径的过程中的先验性和确定性因素的作用强度。 值越大，蚂蚁在某个局部点上选择局部最短路径的可能性就越大， 虽然这个时候算法的收敛速度得以加快，但蚁群搜索最优路径的随机性减弱，而此时搜索易于陷入局部最优解。 一般为[3,5]
  • 信息素蒸发系数p
    • 大小的选择将直接影响到整个蚁群算法的收敛速度和全局搜索性能 ρ过小时，则表示以前搜索过的路径被再次选择的可能性过大，会影响到算法的随机性能和全局搜索能力； ρ过大时，说明路径上的信息素挥发的相对变多，虽然可以提高算法的随机搜索性能和全局搜索能力，但过多无用搜索操作势必会降低算法的收敛速度。 一般为0~1之间的一个数
  • 蚂蚁数目m
    • m只蚂蚁在一次循环中所经过的路径，则表现为问题解集中的一个子集 蚂蚁数目增大后，会使大量的曾被搜索过的解（路径）上的信息素的变化趋于平均，信息正反馈的作用不明显 一般为10~50
  • 信息素强度Q
    • 不做特别考虑，可任意选取
  • 最大进化代数G
    • 一般为100~500