《群集智能算法》PPT课件

第 7章 群 集 智 能 算 法 第 7章 群 集 智 能 算 法 7.1群 集 智 能 算 法 的 研 究 背 景 7.1群 集 智 能 算 法 的 研 究 背 景对 群 集 智 能 的 研 究 是 受 社 会 性 昆 虫 行 为 的 启 发 ，从 事 计 算 研 究 的 学 者 通 过 对 社 会 性 昆 虫 的 模 拟 产 生了 一 系 列 对 传 统 问 题 的 新 的 解 决 方 法 ， 这 些 研 究 就是 群 集 智 能 的 研 究 。群 体 (Swarm)指 的 是 “ 一 组 相 互 之 间 可 以 进 行 直接 通 信 或 者 间 接 通 信 (通 过 改 变 局 部 环 境 )的 主 体 ，这 组 主 体 能 够 合 作 进 行 分 布 问 题 求 解 ” ；群 集 智 能 (Swarm Intelligence)指 的 是 “ 无 智 能 的主 体 通 过 合 作 表 现 出 智 能 行 为 的 特 性 ” 。 7.2群 集 智 能 的 基 本 算 法 介 绍 蚁 群 算 法 是 受 到 上 世 纪 五 十 年 代 仿 生 学 的 启 发 ，由 意 大 利 学 者 M.Dorigo等 人 首 先 提 出 的 一 种 新 型 的模 拟 进 化 算 法 ， 该 算 法 在 求 解 组 合 优 化 问 题 中 体 现出 优 良 的 特 性 。作 为 一 种 基 于 种 群 的 启 发 式 搜 索 算 法 ， 它 能 很 好的 利 用 蚁 群 的 集 体 寻 优 特 征 来 寻 找 蚁 穴 和 食 物 之 间的 最 短 路 径 。 因 此 ， 被 广 泛 应 用 于 旅 行 商 问 题（ TSP） 、 Job-shop调 度 问 题 、 指 派 问 题 等 等 ， 都取 得 了 良 好 的 仿 真 试 验 结 果 。 7.2.1蚁 群 算 法蚁 群 算 法 的 模 拟 试 验l该 试 验 在 各 个 蚂 蚁 在 没 有 事 先 告 诉 它 們 食 物 在 什 么地 方 的 前 提 下 开 始 寻 找 食 物 。 当 一 只 找 到 食 物 以 后 ，它 会 向 环 境 释 放 一 种 信 息 素 ， 吸 引 其 他 的 蚂 蚁 过 来 ，这 样 越 来 越 多 的 蚂 蚁 会 找 到 食 物 ！l但 有 些 蚂 蚁 并 没 有 像 其 它 蚂 蚁 一 样 总 重 复 同 样 的 路 ，它 們 会 另 辟 蹊 径 ， 如 果 令 开 辟 的 道 路 比 原 来 的 其 他道 路 更 短 ， 那 么 更 多 的 蚂 蚁 被 吸 引 到 这 条 较 短 的 路上 来 。 最 后 ， 经 过 一 段 时 间 运 行 ， 可 能 会 出 现 一 条最 短 的 路 径 被 大 多 数 蚂 蚁 重 复 着 。 这 个 试 验 程 序 的 每 个 蚂 蚁 的 核 心 程 序 编 码 不 过 100多 行 。 为 什 么 这 么 简 单 的 程 序 会 让 蚂 蚁 干 这 样 复 杂的 事 情 ？答 案 是 ： 巧 妙 地 利 用 简 单 规 则 来 实 现 集 体 智 慧 。 每 只 蚂 蚁 并 不 是 像 我 们 想 象 的 需 要 知 道 整 个 世 界 的信 息 ， 它 們 其 实 只 关 心 很 小 范 围 内 的 眼 前 信 息 ， 而且 根 据 这 些 局 部 信 息 利 用 几 条 简 单 的 规 则 进 行 决 策 ，这 样 在 蚁 群 这 个 集 体 里 ， 复 杂 性 的 行 为 就 会 凸 现 出来 。 这 些 规 则 就 是 下 面 所 述 的 简 单 的 6条 规 则 ACO 基 本 规 则 （ 一 、 二 ）l 范 围 ： 蚂 蚁 观 察 到 的 范 围 是 一 个 方 格 世 界 ， 蚂 蚁 有 一 个 参 数为 速 度 半 径 （ 一 般 是 3） ， 那 么 它 能 观 察 到 的 范 围 就是 3*3个 方 格 世 界 。l 环 境 ： 蚂 蚁 所 在 的 环 境 是 一 个 虚 拟 的 世 界 ， 其 中 有 障 碍 物 ，有 别 的 蚂 蚁 ， 还 有 信 息 素 ， 信 息 素 有 两 种 ， 一 种 是 找到 食 物 的 蚂 蚁 洒 下 的 食 物 信 息 素 ， 一 种 是 找 到 窝 的 蚂蚁 洒 下 的 窝 的 信 息 素 。 环 境 以 一 定 的 速 率 让 信 息 素 消失 。 ACO 基 本 规 则 （ 三 ） ACO 基 本 规 则 （ 四 ） ACO 基 本 规 则 （ 五 、 六 ） 有 两 条 路 径 通 向 食 物 蚂 蚁 聚 集 到 较 短 的 路 径 l 其 次 ， 蚂 蚁 要 有 一 定 的 随 机 性 ， 虽 然 有 了 固 定 的方 向 ， 但 它 也 不 能 像 一 个 小 球 一 样 直 线 运 动 下 去 ，而 是 有 一 个 随 机 的 干 扰 。 这 样 就 使 得 蚂 蚁 运 动 起来 具 有 了 一 定 的 目 的 性 ， 尽 量 保 持 原 来 的 方 向 ，但 又 有 新 的 试 探 ， 尤 其 当 碰 到 障 碍 物 的 时 候 它 会立 即 改 变 方 向 。l 这 可 以 看 成 一 种 选 择 的 过 程 ， 也 就 是 环 境 的 障 碍物 让 蚂 蚁 沿 着 是 某 个 方 向 正 确 ， 而 其 他 方 向 则 不正 确 。 在 有 一 只 蚂 蚁 找 到 了 食 物 后 ， 其 他 蚂 蚁 会沿 着 信 息 素 很 快 找 到 食 物 。 蚁 群 算 法 过 程 模 拟 用 蚁 群 算 法 解 决 问 题 的 步 骤1. 能 够 把 待 解 决 的 问 题 用 图 的 形 式 抽 象 表 达 出 来 ；2. 具 体 定 义 各 种 参 数 ， 如 范 围 、 信 息 素 消 逝 函 数 等 ；3. 为 算 法 中 的 蚂 蚁 制 定 相 应 的 移 动 规 则 ；4. 选 择 一 种 适 应 的 蚁 群 优 化 算 法 并 将 其 合 理 地 应 用到 自 己 的 问 题 解 决 方 案 中 去 ；5. 适 当 调 整 所 应 用 的 蚁 群 算 法 中 的 对 应 参 数 以 达 到较 好 的 实 验 效 果 . 2. 应 用 蚁 群 算 法 求 解 TSP问 题 1 ( ) ( ) ij ij ijt n t 1 m ki j i jk , k ij 0,k kij QL 若 第 只 蚂 蚁 在 本 次 循 环 中 经 过否 则 否 则 之 间 经 过和只 蚂 蚁 在 时 刻若 第,0 ij1ttk,ijkij dQ 否 则 之 间 经 过和只 蚂 蚁 在 时 刻若 第,0 ij1ttk,Qkij 7.2.2 flock算 法 7.2.2 flock算 法分 离 列 队 聚 合 l 躲 避 规 则 的 作 用 是 为 主 体 提 供 了 使 它 绕 过 障 碍 和避 免 碰 撞 的 能 力 。 这 种 控 制 行 为 是 这 样 完 成 的 ：通 过 赋 予 每 个 主 体 “ 向 前 看 ” 一 段 距 离 的 能 力 ，决 定 与 一 些 对 象 的 碰 撞 是 否 可 能 ， 然 后 调 整 航 向以 避 免 碰 撞 。l Flock技 术 通 过 这 四 个 简 单 的 规 则 最 终 模 拟 出 逼真 的 群 体 行 为 ， 更 有 意 思 的 是 这 种 移 动 算 法 本 身是 无 状 态 的 ： 在 移 动 更 新 中 ， 不 记 录 任 何 信 息 。 l 在 每 次 更 新 循 环 中 ， 每 只 boid都 将 重 新 评 估 其 环境 。 这 样 不 但 降 低 了 内 存 需 求 ， 同 时 让 物 群 能 够对 不 断 变 化 的 环 境 状 况 做 出 实 时 的 反 应 。 因 此 ，物 群 将 具 备 突 发 行 为 的 （ Emergent Behavior） 特性 ， 即 物 群 中 的 所 有 成 员 都 对 要 前 往 何 方 一 无 所知 ， 但 作 为 一 个 整 体 行 动 ， 避 开 障 碍 物 和 天 敌 ，并 保 持 若 即 若 离 。 7.3 集 智 系 统 介 绍 7.3.1 人 工 鱼人 工 鱼 群 体 是 一 种 典 型 的 多 智 能 主 体 （ Multiple Intelligent Agent） 的 分 布 式 人 工 智 能 系 统（ distributive artificial intelligent system） 。中 国 青 年 学 者 涂 晓 媛 研 究 开 发 的 新 一 代 计 算 机 动 画“ 人 工 鱼 ” 被 学 术 界 称 之 为 “ 晓 媛 鱼 ” （ Xiaoyuans fish） ， 她 发 表 的 论 文 “ 人 工 动 物 的 计 算 机 动画 ” (artificial animals for computer animation: biomechanics , locomotion, perception and behavior)，在 1996年 获 国 际 计 算 学 会 ACM最 佳 博 士 论 文 奖 。 l 涂 晓 媛 研 究 开 发 的 “ 人 工 鱼 ” 构 成 了 栖 息 在 虚 拟海 底 世 界 中 人 工 鱼 群 的 社 会 ， 其 中 ， 每 条 “ 人 工鱼 ” 都 是 一 个 自 主 的 智 能 体 （ autonomous intelligent agent） ， 都 可 以 独 立 地 活 动 ， 也 可 以相 互 交 往 。 每 条 鱼 都 表 现 出 某 些 人 工 智 能 ， 如 ：自 激 发 （ self-animating） 、 自 学 习 （ self-learning） 、 自 适 应 （ self-adapting） 等 智 能 特 性 . l 会 产 生 相 应 的 智 能 行 为 ， 如 ： 因 饥 饿 而 激 发 寻 食 、进 食 行 为 ； 有 性 欲 而 激 发 求 爱 行 为 ； 能 吸 取 其 他鱼 被 鱼 钩 钓 住 的 教 训 ， 而 不 去 吞 食 有 钩 的 鱼 饵 ；能 适 应 有 鲨 鱼 的 社 会 环 境 ， 逃 避 被 捕 食 的 危 险 等 。人 工 鱼 群 的 社 会 具 有 某 些 自 组 织 （ self-organizing）能 力 和 智 能 集 群 行 为 ， 如 ： 人 工 鱼 群 体 在 漫 游 中遇 到 障 碍 物 等 ， 会 识 别 障 碍 改 变 队 形 ， 绕 过 障 碍后 ， 又 重 组 队 列 ， 继 续 前 进 。 7.3.1 人 工 鱼人 工 鱼 与 动 画 鱼区 别 ：l “ 人 工 鱼 ” 具 有 “ 人 工 生 命 ” 和 自 然 鱼 的 某 些 生 命特 征 。 l 在 一 般 的 计 算 机 动 画 中 ， 创 作 者 需 要 在 动 画 设 计 和程 序 编 制 中 确 定 动 画 鱼 的 所 有 动 作 的 细 节 ， 预 先 知道 动 画 鱼 的 全 部 动 作 过 程 。 然 而 ， 人 工 鱼 的 创 作 者并 不 去 设 计 和 规 定 每 条 鱼 的 动 作 和 行 为 的 细 节 ， 也不 能 预 知 人 工 鱼 群 中 可 能 发 生 的 各 种 具 体 动 作 和 实际 行 为 。 7.3.1 人 工 鱼 7.3.1 人 工 鱼“ 人 工 鱼 ” 的 动 画 创 作 方 法 和 技 术 ， 已 经 突 破 了传 统 的 计 算 机 动 画 的 框 架 。 首 先 ， “ 人 工 鱼 ” 不 仅 有 逼 真 于 “ 自 然 鱼 ” 的 外形 和 彩 色 ， 而 且 具 有 类 似 于 “ 自 然 鱼 ” 的 运 动 和 姿态 。 其 次 ， “ 人 工 鱼 ” 不 仅 具 有 “ 自 然 鱼 ” 的 形 态 ，而 且 具 有 “ 自 然 鱼 ” 类 似 的 生 命 特 性 “活 性 ” 。 再 次 ， “ 人 工 鱼 ” 是 具 有 人 工 智 能 的 “ 灵 巧 鱼 ” ，而 传 统 的 “ 动 画 鱼 ” 是 程 序 化 的 “ 木 偶 鱼 ” 。 最 后 ， “ 人 工 鱼 ” 是 具 有 各 种 不 同 的 人 工 鱼 的 鱼群 社 会 。 “人 工 鱼 ” 的 形 态 （ 外 形 、 颜 色 、 姿 态 ） 和 “ 自 然鱼 ” 非 常 相 似 ， 几 乎 达 到 了 “ 以 假 乱 真 ” 的 程 度 。在 一 次 国 际 会 议 上 ， 涂 晓 媛 演 示 了 “ 人 工 鱼 ” 的录 像 ， 人 们 看 到 屏 幕 上 一 群 色 彩 美 丽 、 活 泼 可 爱的 热 带 鱼 ， 在 海 水 中 漫 游 ， 逼 真 的 外 形 、 生 动 的姿 态 ， 伴 随 着 水 流 的 运 动 ， 还 以 为 是 在 水 族 馆 中拍 摄 的 真 热 带 鱼 的 录 像 。 直 到 涂 晓 媛 把 “ 人 工 鱼 ”的 彩 色 消 隐 ， 变 成 黑 白 的 鱼 ， 再 把 “ 人 工 鱼 ” 的肌 肉 剥 离 ， 剩 下 一 群 热 带 鱼 的 骨 架 在 游 泳 ， 才 确信 这 是 计 算 机 动 画 的 ” 人 工 鱼 ” 。 “人 工 鱼 ” 和 一 般 的 “ 动 画 鱼 ” 的 不 同 之 处 还 在 于 ：l “ 人 工 鱼 ” 具 有 某 些 自 然 鱼 的 “ 本 能 ” 性 。l “ 人 工 鱼 ” 能 感 知 其 他 的 ” 人 工 鱼 ” 和 海 底 环 境 ，有 “ 鱼 肉 ” 、 “ 鱼 骨 ” 、 “ 鱼 嘴 ” 、 “ 鱼 头 ” 、“ 鱼 尾 ” 、 “ 鱼 鳍 ” 等 ， 能 产 生 类 似 于 自 然 鱼 的随 意 动 作 和 行 为 。 例 如 ： 人 工 鱼 有 性 欲 ； 人 工 鱼有 饥 饿 感 ； 人 工 鱼 有 学 习 能 力 ， 若 一 条 鱼 误 吞 了鱼 饵 ， 被 鱼 钩 钩 上 ， 会 进 行 挣 扎 ， 而 其 他 的 “ 人工 鱼 ” ， 就 会 吸 取 教 训 不 再 上 当 ， 不 去 吞 食 带 钩的 鱼 饵 ， 离 开 钓 鱼 的 水 域 ； “ 人 工 鱼 ” 有 恐 惧 感 ，如 果 发 现 凶 恶 的 鲨 鱼 来 侵 犯 ， 都 迅 速 散 开 ， 东 奔西 逃 ， 脱 离 危 险 ， 。 7.3.1 人 工 鱼 图 12.8 雄 鱼 向 雌 鱼 求 爱 图 12.9 侵 略 者 鲨 鱼 偷 袭 被 扑 食 的 小 鱼 群 7.3.1 人 工 鱼 饲 养 场 模 式 （ Terrarium Mode） ： 这 种 模 式 给 用户 提 供 了 两 种 选 择 。l 用 户 可 以 独 立 运 行 ， 无 须 与 其 他 节 点 连 接 。 在 这种 情 况 下 ， 屏 幕 上 显 示 的 生 态 系 统 就 代 表 了 整 个生 态 环 境 。 这 种 模 式 最 适 合 于 对 我 们 开 发 出 来 的生 物 进 行 测 试 。l 用 户 也 可 以 选 择 加 入 到 一 组 特 定 的 节 点 环 境 中 ，所 有 连 入 此 环 境 的 计 算 机 共 同 组 成 一 个 小 型 生 态系 统 。 7.3.2 Terrarium世 界 加 入 特 定 节 点 组 的 方 法 非 常 简 单 ， 每 个 用 户 选 择一 个 特 定 的 专 网 ， 并 在 Terrarium控 制 台 的“ Channel”一 项 中 输 入 一 个 事 先 约 定 好 的 字 串 ，就 可 以 加 入 该 网 络 了 。 输 入 字 串 后 ， 用 户 的 计算 机 只 与 那 些 输 入 了 相 同 字 串 的 计 算 机 构 成 一个 独 立 的 对 等 网 络 ， 并 一 同 组 建 生 态 系 统 。 生 物 圈 模 式 （ Ecosystem Mode） ： 这 是 游 戏 的 标准 模 式 。 全 世 界 所 有 连 入 游 戏 的 计 算 机 共 同 构 成 一 个完 整 的 生 态 系 统 。 每 个 参 与 者 的 计 算 机 只 是 该 生 态 系统 的 一 个 局 部 场 景 。 在 上 述 两 种 模 式 下 ， 开 发 者 都 可 以 使 用 Terrarium类 库 、 .NET框 架 开 发 包 和 Visual Studio .NET工 具 随意 创 建 它 們 自 己 的 生 物 。 或 者 ， 可 以 简 单 地 把Terrarium当 作 一 个 独 立 运 行 的 应 用 程 序 或 是 屏 幕 保护 程 序 运 行 ， 并 通 过 Terrarium观 看 其 他 开 发 者 创 建的 生 物 在 生 态 系 统 中 为 生 存 而 战 。 7.4 群 集 智 能 的 优 缺 点 7.4 群 集 智 能 的 优 缺 点 7.4 群 集 智 能 的 优 缺 点