人工智能基础07--自动规划系统解读.ppt

群智能算法——群智能理论 以上五条原则现在成为了群智能的最基本理论，现有的群智能方法和策略都符合这些原则。 《Swarm Intelligence》 最重要的观点是：Mind is social, 也就是认为人的智能是源于社会性的相互作用，文化和认知是人类社会性不可分割的重要部分，这一观点成为了群智能发展的基石。 群智能模拟的是社会系统的变化，其最基本单位是 “敏因”(Meme) ，这一词由 Dawkin 在 《The Selfish Gene》中提出，它是指思想文化传播中的基本单位，个体在社会中会根据环境来改变自身的思想，敏因的传播途径是在个体与个体之间，在人类社会中它还可以在人脑与书本之间、 人脑与计算机、 计算机与计算机之间传播。当然，“敏因” 应该如何严格描述和定义还没有定论。 群智能算法——群智能理论 群智能研究的更进一步目标是对人类思想变化的社会行为的模拟。人类心理中存在着群体性、习惯性、一致性, 常常是习惯性地遵循一些习俗和规则。无论什么时候, 人们思想和行为总是因相互影响而变得非常近似, 道德规范以及文化的形成就是这种通过相互间影响而导致近似的结果。 人类的社会思想行为并不简单类似鸟群或鱼群的行为, 人类思想的形成过程是一种在高维认知空间的探索历程。 两种思想意见在认知空间上聚集到一点上, 被称为 “一致” 或 “认同” , 而不是鸟群或鱼群系统中的 “碰撞” 。如果某人认同认知空间某个点, 那么就努力靠近它, 反之则尽量远离它, 这里认知空间中的某个点就是某个人的思想。人类通过这种社会行为达成社会的共识: 习俗、道德规范等。 目前, 群智能理论研究处于基本思想描述阶段, 还未能提出一些较为明确的概念和定义, 尽管已经有人提出广义群智能的模型。 蚁群算法(Ant Colony Optimization—ACO)由 Colorni, Dorigo 和 Maniezzo 于 1991 年提出,它是通过模拟自然界蚂蚁社会的寻找食物的方式而得出的一种仿生优化算法。 自然界种蚁群寻找食物时会派出一些蚂蚁分头在四周游荡, 如果一只蚂蚁找到食物, 它就返回巢中通知同伴并沿途留下 “信息素” ( pheromone)作为蚁群前往食物所在地的标记。 信息素会逐渐挥发, 如果两只蚂蚁同时找到同一食物,又采取不同路线回到巢中, 那么比较绕弯的一条路上信息素的气味会比较淡, 蚁群将倾向于沿另一条更近的路线前往食物所在地。ACO算法设计虚拟的 “蚂蚁” , 让它们摸索不同路线, 并留下会随时间逐渐消失的虚拟 “信息素” 。根据 “信息素较浓的路线更近” 的原则, 即可选择出最佳路线。 群智能算法——蚁群算法 ACO算法首先应用于 TSP 问题中, 这里以 TSP 问题为例对算法作简单介绍。当某一个蚂蚁走到一个城市, 下一步可选的路径集合为 E, 集合中任一条路径 e∈E 上的信息素浓度为τe, 走这条路的代价为 ηe, 那么选择某一条路径 v∈E 的几率为： 群智能算法——蚁群算法 其中, α和 β两个参数分别用来控制信息素和路径长度的相对重要程度。当蚂蚁在所有城市走过一遍之后，路径上的信息素浓度将变为: τ e( t+1) =( 1-ρ )·τe( t) +Δe 其中，0≤ρ 1 用于控制信息素随时间挥发的速度，Δe是上次蚂蚁经过此路段所留下的信息素，未经过则为 0。上式以及Δe可以根据问题进行设计。 目前，ACO算法已被广泛应用于组合优化问题中，在车辆调度问题、 机器人路径规划问题、 路由算法设计等领域均取得了良好的效果。 由于 ACO算法具有广泛实用价值，成为了群智能领域第一个取得成功的实例，曾一度成为群智能的代名词，相应理论研究及改进算法近年来不断取得新的成果。 群智能算法——蚁群算法 粒子群优化算法（Particle Swarm Optimization—PSO)源于 1987 年 Reynolds 对鸟群社会系统boids的仿真研究，boids 也是一个 CAS。 在 boids 中, 一群鸟在空中飞行, 每个鸟遵守以下三条规则: （1）避免与相邻的鸟发生碰撞冲突; （2）尽量与自己周围的鸟在速度上保持协调和一致; （3）尽量试图向自己所认为的群体中心靠近。 仅仅通过使用这三条规则, boids 系统就出现非常逼真的群体聚集行为, 鸟成群地在空中飞行, 当遇到障碍时它们会分开绕行而过, 随后又会重新形成群体。不过 Reynolds 仅仅将其作为 CAS的一个实例作仿真研究, 而并未将它用于优化计算