Ant group can’t be jump.

学习一个单词: 绕过(bypass).

蚁群算法是工作中无法绕过的

步骤:
  1. 蚂蚁爬过所有点, 算一次成功爬行后,
    1. 做一下信息素的挥发.
    2. 再迭代增加更新路径上所有路段的信息素(爬的越快, 信息越浓).
  2. 蚂蚁每次都随机选择路径, 但是这个随机性会受信息素影响.
  3. 一系列迭代之后, 比如1000次之后, 得到的最短路径就被认为是最短路径.
数据结构:
  1. 一堆点, 分三种(这个也是输入的数据结构)
    1. 起点, 路径的起点, 终点(如果需要的话)
    2. 出发/到达点对, 要接触到达点, 必须先经过了出发点.
    3. 到达点, 任何时候都可以触达的点.
  2. 点点距离
    1. 所有点的互相距离.
    2. 信息素也是这个结构中的数据.
  3. 点的访问性分类
    1. 可以访问的.
    2. 已经访问的.
    3. 不一定可以访问的. 这里的点可以被确认为是可以访问的, 并且移动到可以访问的组里面.
核心:
int select;
double randomNo = random.nextDouble() * totalWeight;
double w = 0;
//这里是轮盘, 随机下一个点出来.
for (select = 0;; ++select) {
    w += weights[select];
    if (w >= randomNo) {
        break;
    }
}

((信息素)的a次方 X (能见度)的b次方 )/ 当前点到所有可能点之间关系的上面这个值的总和

阅读3-4分文档, 给大家推荐一个最好的,

信息素更新有3个模型
  1. 蚁周模型, 一次完整的周游再更新信息素, 信息素使用的是总路径长度.
  2. 蚁量模型, 当前一步就更新, 参照这一步的长度.
  3. 蚁密模型, 当前一步就更新, 增加的量是固定的.
主要常量
  1. a, 跟随信息素. 越大越容易走老路. 信息素的a次方再分子.
  2. b, 收敛速度. 时效性的b次方也在分子. 这个越大, 局部贪婪效果越明显. 距离越短值越大.
  3. m 蚁群数量
  4. p 挥发因子, 残留信息量因子
概念
  • 时效性 可以很好地替代能见度的翻译. 距离的倒数.
    • 能见度 就是距离的倒数, 这个咋是能见度呢? 但是这个肯定是挥发效应的核心参数, 距离越远, 时间就越久, 挥发效果越强烈. 词不达意的翻译.
蚁群的分类和扩展
  • 蚁群 aco : ant colony opitmization
  • 精英蚂蚁, 加强了当前最优解的信息, 这个会促进收敛, 但是, 未必是好事.
  • 最大最小蚂蚁mmas, 考虑的比较全面, 限制了最大最小信息量, 避免了局部最优解对解法发散造成的不良影响.
  • 蚁群系统acs, 蚁群原作者的升级, 加入了当前轮次信息素抑制, 扩大算法发散性.
  • 排序蚁群, asrank. 对解决方案进行排序, 难道说这个是求了z值吗? 并不是的, 其实实际上等于截掉了尾部的信息素.
  • 正交蚁群, coac, 探索的时候正交???? 这个咋正交的呢? todo.