第5章 蚁群算法

5蚁群算法AntColonyOptimization 2 3 目录 1 蚁群算法起源2 蚁群算法模型3 实例仿真4 蚁群算法特点5 总结 双桥实验 蚁群优化 antcolonyoptimization ACO 是20世纪90年代初由意大利学者M Dorigo等通过模拟蚂蚁的行为而提出的一种随机优化技术 寻找优化路径的机率型算法 研究主要是以蚂蚁寻找食物之后能选择一条最短路径来连接蚁穴和食物源 1991年 M Dorigo在法国巴黎第一届欧洲人工生命会议上最早提出了蚁群算法的基本模型 1992年又在其博士论文中进一步阐述了蚁群算法的核心思想 MacroDorigo 1 蚁群算法起源 蚂蚁觅食过程 在蚁群寻找食物时 能够在它所经过的路径上留下一种称之为信息素 pheromone 的物质进行信息传递 而且蚂蚁在运动过程中能够感知这种物质 并以此指导自己的运动方向 因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象 某一路径上走过的蚂蚁越多 则后来者选择该路径的概率就越大 最优路径上的信息素浓度越来越大 而其它的路径上激素浓度却会随着时间的流逝而消减 最终整个蚁群会找出最优路径 A点为蚁穴 食物在D点 可能随机选择路线ABD或ACD 假设初始时每条路线有一只蚂蚁 每个时间单位行走一步 本图为经过9个时间单位时的情形 走ABD的蚂蚁到达食物 而走ACD的蚂蚁刚好走到C点 为一半路程 简化的蚂蚁寻食过程 本图为从开始算起 经过18个时间单位时的情形 走ABD的蚂蚁到达D点后得到食物又返回了起点A 而走ACD的蚂蚁刚好走到D点 假设蚂蚁每经过一处所留下的信息素为一个单位 则经过36个时间单位后 ABD的路线往返了2趟 每一处的信息素为4个单位 而ACD的路线往返了一趟 每一处的信息素为2个单位 其比值为2 1 按信息素的指导 ABD路线增加一只蚂蚁 共2只 ACD路线仍为一只蚂蚁 再经过36个时间单位后 两条线路上的信息素为12和4 比值为3 1 于是 ABD路线增加一只蚂蚁 共3只 ACD路线仍为一只蚂蚁 再经过36个时间单位后 两条线路上的信息素为24和6 比值为4 1 若继续进行 则按信息素的指导 最终所有的蚂蚁会放弃ACD路线 而都选择ABD路线 蚁群算法通常用于求解复杂的组合优化问题 所谓组合优化 是指在离散的 有限的数学结构上 寻找一个满足给定条件 并使其目标函数值达到最大或最小的解 理论假设1 蚁群之间通过信息素和环境进行通信 2 蚂蚁对环境的反应由其内部模式决定 3 个体水平上 每个蚂蚁相对独立 群体水平上 每只蚂蚁的行为是随机的 2 蚁群算法模型 算法规则 12 1 范围 蚂蚁观察到的范围是一个方格世界 蚂蚁有一个参数为速度半径 一般是3 那么它能观察到的范围就是3 3个方格世界 并且能移动的距离也在这个范围之内 13 2 环境 蚂蚁所在的环境是一个虚拟的世界 其中有障碍物 有别的蚂蚁 还有信息素 信息素有两种 一种是找到食物的蚂蚁洒下的食物信息素 一种是找到窝的蚂蚁洒下的窝的信息素 每个蚂蚁都仅仅能感知它范围内环境信息 环境以一定的速率让信息素消失 14 3 觅食规则 在每只蚂蚁能感知的范围内寻找是否有食物 如果有就直接过去 否则看是否有信息素 并且比较在能感知的范围内哪一点的信息素最多 这样 它就朝信息素多的地方走 并且每只蚂蚁都会以小概率犯错误 从而并不是往信息素最多的点移动 蚂蚁找窝的规则和上面一样 只不过它对窝的信息素做出反应 而对食物信息素没反应 15 4 移动规则 每只蚂蚁都朝向信息素最多的方向移 并且 当周围没有信息素指引的时候 蚂蚁会按照自己原来运动的方向惯性的运动下去 并且 在运动的方向有一个随机的小的扰动 为了防止蚂蚁原地转圈 它会记住最近刚走过了哪些点 如果发现要走的下一点已经在最近走过了 它就会尽量避开 16 5 避障规则 如果蚂蚁要移动的方向有障碍物挡住 它会随机的选择另一个方向 并且有信息素指引的话 它会按照觅食的规则行为 17 6 播撒信息素规则 每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多 并随着它走远的距离 播撒的信息素越来越少 现以平面上n个城市的旅行商问题 TravelingSalesmanProblem TSP 为例说明基本蚁群算法模型 旅行商问题 一商人去n个城市销货 所有城市走一遍再回到起点 使所走路程最短 TSP在许多工程领域具有广泛的应用价值 例如电路板布线 VLSI芯片设计 机器人控制 网络路由等 随着城市数目的增多 问题空间将呈指数级增长 TSP问题的数学描述 TSP问题表示为一个N个城市的有向图G N A 其中城市之间距离目标函数为其中 为城市1 2 n的一个排列 蚁群算法求解TSP 下面以TSP为例说明基本蚁群算法模型 首先将m只蚂蚁随机放置在n个城市 通常 m只蚂蚁同时由一个城市运动到下一个城市 逐步完成它们的搜索过程 整个算法的迭代过程以N为刻度 为预设的最大迭代次数 每次迭代过程中以t为刻度 蚂蚁k根据概率转换规则选择下一个城市 由此生成一个由n个城市组成的行动路线 并伴随信息素的更新 2 能见度定义为距离的倒数 即代表由城市i到城市j的启发性愿望 距离越短 能见度越大 被选择的愿望越大 由此引导蚂蚁搜索 其信息是固定的 3 虚拟信息素当由城市i选择城市j后 将在ij路径上留下虚拟信息素 代表由城市i到j的获知性愿望 是动态的全局信息 在线实时更新 蚂蚁k由城市i转到城市j的决定因素 1 禁忌列表该表用于存储第k只蚂蚁在当前时刻已访问过的所有城市 每只蚂蚁在选择下一个城市前 先检索该表来确定下一步可能选择的城市是否已经走过 如果走过就不在选择范围内 这样可以避免重复访问同一个城市 信息素更新方式体现在信息素的增加和信息素的挥发两个方面 挥发系数信息素更新公式如下 表示当m个蚂蚁都选择了下一个城市后 所有选择由i到j的蚂蚁在该路径上遗留的信息素之和表示第k只蚂蚁在路径ij上留下的信息素为预设参数 表示信息素的强度表示第k只蚂蚁在t时刻选择城市j后经过的所有城市构成的路径长度 其中 表示ij路径上的信息素浓度 是启发信息 能见度 和 反映了信息素与启发信息的相对重要性 表示蚂蚁k已经访问过的城市列表 禁忌列表 4 概率转换规则位于城市i的第k只蚂蚁选择下一个城市j的概率为 注意 处在同一城市i的两只蚂蚁 即使都按照上述概率选择下一个城市 结果也可能是不同的 系统在上述四个因素 禁忌列表 能见度 虚拟信息素 概率转换规则 的控制下 实现路径选择策略和信息素更新策略 上述信息素更新方式与真实蚂蚁觅食过程最为接近 但是在解决TSP问题上 效果并不是特别理想 Dorigo针对信息素更新策略又给出了三种模型 蚁量系统 Ant Quantity 蚁密系统 Ant Density 蚁周系统 Ant Cycle 三种模型 它们的差别在于表达式的不同 即更新信息素的方式和更新量不同 Ant Quantity和Ant Density模型都是利用局部信息 即m个蚂蚁都各自选完下一城市后 就对所走路径并行进行信息素更新 两者的区别仅仅在于更新的信息素量有所不同 Ant Cycle模型是所有蚂蚁选择完所有城市完成一次迭代后 更新所有路径上的信息素 并且每只蚂蚁经过的路径所更新的信息素是相同的 蚁量算法 Ant Quantity 蚁密算法 Ant Density 蚁周算法 Ant Cycle 27 通过实验表明 在这三种算法中 Ant Cycle算法的效果最好 这是因为它用的是全局信息 而其余两种算法用的是局部信息 这种更新方法很好地保证了残留信息不至于无限累积 非最优路径会逐渐随时间推移被忘记 TSP算法流程图 Ant Cycle 蚁群算法的误区与对策 29 误区一 利用最大概率确定被选城市 轮盘赌法 赌轮选择法 在 0 1 区间内产生一个均匀分布的随机数r 若r q1 则城市x1被选中 若qk 1 r qk 2 k N 则城市xk被选中 其中的qi称为城市xi i 1 2 n 的积累概率 其计算公式为 对策一 31 误区二 Q值的影响不大 32 对策二 33 误区三 参数组合选择 34 对策三 3 实例仿真 采用靳潘教授所提出的31个城市的CTSP 求一条从北京出发经过中国31个省会城市及直辖市最后又回到北京的最短回路 36 下图对应31个城市的巡回路线为 北京 福州 南昌 合肥 杭州 南京 西安 台北 太原 呼和浩特 沈阳 上海 石家庄 长春 哈尔滨 济南 天津 武汉 郑州 长沙 银川 兰州 广州 海口 南宁 西宁 成都 乌鲁木齐 昆明 拉萨 贵阳 北京 从仿真结果看最优解为 15708km 目前 公认的TSP问题最优结果为15398km 虽然 不完全相等 但是结果比较相近 这说明蚂蚁算法虽然不是TSP问题的最好算法 但是依据蚂蚁觅食过程提出的蚁群算法具有一定的可行性 一 蚁群大小一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个数 二 终止条件1给定一个外循环的最大数目 2当前最优解连续K次相同而停止 其中K是一个给定的整数 表示算法已经收敛 不再需要继续 蚁群的规模及停止规则 蚂蚁觅食行为与优化问题的对照关系 其原理是一种正反馈机制或称增强型学习系统 它通过 最优路径上蚂蚁数量的增加 信息素强度增加 后来蚂蚁选择概率增大 最优路径上蚂蚁数量更大增加 达到最终收敛于最优路径上 它是一种通用型随机优化方法 它吸收了蚂蚁的行为特点 它是使用人工蚂蚁仿真来求解问题 但人工蚂蚁决不是对实际蚂蚁的一种简单模拟 它融进了人类的智能 具有一定的记忆能力 能够记忆已经访问过的节点 选择路径时不是盲目的 而是按一定规律有意识地寻找最短路径 例如 在TSP问题中 可以预先知道当前城市到下一个目的地的距离 4 蚁群算法的特点 它是一种启发式算法 计算复杂性为 其中Nc是迭代次数 m是蚂蚁数目 n是目的节点数目 它是一种本质上的并行算法 它是一种全局优化的方法 不仅可用于求解单目标优化问题 而且可用于求解多目标优化问题 蚁群算法还不像其它的启发式算法那样已形成系统的分析方法和具有坚实的数学基础 参数的选择更多的是依靠实验和经验 没有定理来确定 而且它的计算时间偏长 国内外的有关研究仍停留在实验探索阶段