《智能算法及应用》PPT课件

智能优化算法及应用Intelligent Optimization Algorithms西安工程大学贺兴时 背 景 传 统 实 际 问 题 的 特 点 ： 连 续 性 问 题 主 要以 微 积 分 为 基 础 ， 且 问 题 规 模 较 小 传 统 的 方 法 （ 运 筹 学 ） ： 线 性 与 非 线 性 规 划 、动 态 规 划 、 多 目 标 规 划 、 整 数 规 划 等 ； 排 队 论 、库 存 论 、 对 策 论 、 决 策 论 等 。 追 求 准 确 精 确 解 理 论 的 完 美 结 果 漂 亮 传 统 的 评 价 方 法 ： 算 法 收 敛 性 （ 从 极 限 角 度 考 虑 ） 收 敛 速 度 （ 线 性 、 超 线 性 、 二 次 收 敛 等 ） 传 统 方 法 面 临 的 挑 战 现 代 问 题 的 特 点 离 散 性 问 题 主 要 以 组 合 优 化 理 论 为 基 础 不 确 定 性 问 题 随 机 性 数 学 模 型 半 结 构 或 非 结 构 化 的 问 题 计 算 机 模 拟 、决 策 支 持 系 统 大 规 模 问 题 并 行 计 算 、 大 型 分 解 理 论 、近 似 理 论 现 代 优 化 方 法追 求 满 意 近 似 解 ； 实 用 性 强 解 决 实 际 问 题 现 代 优 化 算 法 的 评 价 方 法 算 法 复 杂 性 内 容 简 介1、 组 合 优 化 问 题 是 解 决 离 散 问 题 的 优 化 问题 运 筹 学 分 支 。 通 过 数 学 方 法 的 研 究 去寻 找 离 散 事 件 的 最 优 编 排 、 分 组 、 次 序 或 筛选 等 ， 可 以 涉 及 信 息 技 术 、 经 济 管 理 、 工 业工 程 、 交 通 运 输 和 通 信 网 络 等 许 多 方 面 。典 型 的 优 化 问 题 ： 0-1背 包 问 题 ， 旅 行 商 问 题 ，机 器 排 序 问 题 等 内 容 简 介2、 模 拟 退 火 算 法 （ simulated annealing ）退 火 是 一 种 物 理 过 程 ， 金 属 物 体 在 加 热 至 一定 的 温 度 后 ， 它 的 所 有 分 子 在 状 态 空 间 中 自由 运 动 。 随 着 温 度 的 下 降 ， 这 些 分 子 逐 渐 停留 在 不 同 的 状 态 。 在 温 度 最 低 时 ， 分 子 重 新以 一 定 的 结 构 排 列 。 模 拟 退 火 算 法 的 直 观 理解 是 ： 在 一 个 给 定 的 温 度 ， 搜 索 从 一 个 状 态随 机 的 变 化 到 另 一 个 状 态 ， 每 一 个 状 态 到 达的 次 数 服 从 一 个 概 率 分 布 。 当 温 度 很 低 时 ，以 概 率 1停 留 在 最 优 解 。 内 容 简 介3、 遗 传 算 法 （ genetic algorithms）遗 传 算 法 主 要 借 用 生 物 进 化 中 “ 适 者 生 存 ”的 规 律 而 设 计 。 遗 传 算 法 包 含 以 下 主 要 步骤 ： 第 一 是 对 优 化 问 题 的 解 进 行 编 码 ； 第二 是 适 应 函 数 的 构 造 和 应 用 ， 适 应 函 数 基本 上 依 据 优 化 问 题 的 目 标 函 数 而 定 ； 第三 是 染 色 体 的 结 合 ； 最 后 是 变 异 。 内 容 简 介3、 蚁 群 优 化 算 法 （ Ant_Algorithm ） 的 基 本思 想 是 模 仿 蚂 蚁 依 赖 信 息 素 进 行 通 信 而 显 示 出的 社 会 行 为 。 蚂 蚁 在 行 动 中 ， 会 在 他 们 经 过 的地 方 留 下 一 些 化 学 物 质 ， 称 之 为 “ 信 息 素 ” ，这 些 物 质 能 被 同 一 蚁 群 中 后 来 的 蚂 蚁 感 受 到 ，并 作 为 一 种 信 号 影 响 后 者 的 行 动 ， 蚂 蚁 选 择 这条 路 径 的 可 能 性 比 选 择 没 有 这 些 物 质 的 路 径 的可 能 性 大 ， 后 到 者 留 下 的 信 息 素 会 对 原 有 的 信息 素 进 行 加 强 ， 这 样 越 短 的 路 径 会 被 越 多 的 蚂蚁 访 问 ， 这 个 过 程 一 直 持 续 到 所 有 的 蚂 蚁 都 走最 短 的 那 一 条 路 径 为 止 。 内 容 简 介4、 粒 子 群 优 化 算 法 (Particle Swarm optimization)是一 种 进 化 计 算 技 术 (Evolutionary Computation)，由 Eberhart博 士 和 K ennedy博 士 发 明 。 源 于 对 鸟群 捕 食 的 行 为 研 究 。 PSO中 ， 每 个 优 化 问 题 的解 都 是 搜 索 空 间 中 的 一 只 鸟 。 我 们 称 之 为 “ 粒子 ” 。 所 有 的 粒 子 都 有 一 个 由 被 优 化 的 函 数 决定 的 适 应 值 (fitness value)， 每 个 粒 子 还 有 一 个 速度 决 定 他 们 飞 翔 的 方 向 和 距 离 。 然 后 粒 子 们 就追 随 当 前 的 最 优 粒 子 在 解 空 间 中 搜 索 。 内 容 简 介5、 人 工 神 经 网 络 (ARTIFICIAL NEURAL NETWORK， 简 称 ANN)是 在 对 人 脑 组 织 结 构 和 运行 机 制 的 认 识 理 解 基 础 之 上 模 拟 其 结 构 和 智 能行 为 的 一 种 工 程 系 统 。 神 经 网 络 的 基 本 原 理 为 ：大 脑 皮 层 每 一 点 的 活 力 是 由 其 他 点 势 能 释 放 的综 合 效 能 产 生 。 这 一 势 能 同 下 面 的 因 数 有 关 ：相 关 其 他 点 的 兴 奋 次 数 ； 兴 奋 的 强 度 ； 与 其 不相 连 的 其 他 点 所 接 受 的 能 量 。 人 工 神 经 网 络 的建 立 和 应 用 可 以 归 结 为 三 个 步 骤 ： 网 络 结 构 的确 定 ， 关 联 权 的 确 定 和 工 作 阶 段 。 参 考 资 料 参 考 资 料 参 考 资 料 参 考 资 料 决 策 变 量有 限 点 集约 束 函 数目 标 函 数 , . ,0)(. )( min Dx xgts xf .|)(min)(,: : ,0)(,|: ),( FxxfxfFxx Fxf xgDxxFD fFD 最 优 解 ， 如 果可 行 解 （ 点 ）目 标 函 数 有 限 点 集可 行 域决 策 变 量 定 义 域 装 包 ？问 题 ： 如 何 以 最 大 价 值件 物 品 单 位 价 值 ，第 件 物 品 单 位 体 积 ，第背 包 容 积 .,1: .,1: niic niiabii .1,0 i0 i 1 (1.3) .,1,1,0 (1.2) ,as.t. (1.1) maxn1i i1i nii in iiD x nix bx xc 物 品， 不 装 第 物 品装 第，其 中 决 策 变 量包 容 量 限 制总 价 值数 学 模 型 ： ij1 ij1min (1.4) s.t. 1. 1,2, , , (1.5) i 1. 1,2, , , ij iji jnjni d xx i nx j n 数 学 模 型 ： 总 路 长只 从 城 市 出 来 一 次 , (1.6) 1,2 1, 1,2, , , (1.7) 0,1 , , 1,2, , , . (1.8) : i j , s : s 1, iji j sij ij ij jx s s n s nx i j n i jd i jx 只 走 入 城 市 一 次在 任 意 城 市 子 集 中 不 形 成 回 路决 策 变 量其 中 城 市 与 城 市 之 间 的 距 离 集 合 中 元 素 的 个 数 ，走 城 市 和 城 市0 .: , ,: , ,ij jiij jii jTSP d d i jTSP d d i j 之 间 的 路 径 ， 不 走 城 市 和 城 市 之 间 的 路 径对 称 距 离非 对 称 距 离 1 2 , ,. na a a 11m in. . 1, 1, 2 , , , 1, 1, 2 , , , 0 ,1 , 1, 2 , , ; 1, 2 , , , B : 1, 0 .B ibb n i ibi ibibBs t x i na x b Bx i n b Bi bx i b 数 学 模 型 ：其 中 装 下 全 部 物 品 需 要 的 箱 子 ，第 物 品 装 在 第 个 箱 子 ， 第 物 品 不 装 在 第 个 箱 子 随 城 市 增 多 ， 计 算 时 间 增 加 很 快 。 到 31个 城 市 时 ，要 计 算 325年 。 描 述 算 法 的 好 坏 计 算 复 杂 性 讨 论 计 算 时 间 与 问 题 规 模 之 间 的 关 系 。 以 目 前 二进 制 计 算 机 中 的 存 储 和 计 算 为 基 础 ， 以 理 论 的 形 式系 统 描 述 ， 是 评 估 算 法 性 能 的 基 础 。 启 发 式 算 法 （ heuristic algorithm）定 义 1. 基 于 直 观 或 经 验 构 造 的 算 法 ， 在 可 接 受的 花 费 （ 时 间 、 空 间 ） 下 ， 给 出 待 解 组 合 优 化问 题 的 每 个 实 例 的 一 个 可 行 解 ， 该 可 行 解 与 最优 解 偏 差 事 先 不 一 定 可 以 预 计 .定 义 2. 启 发 式 算 法 是 一 种 技 术 ， 在 可 接 受 的 计算 费 用 内 寻 找 最 好 解 ， 但 不 保 证 该 解 的 可 行 性与 最 优 性 ， 无 法 描 述 该 解 与 最 优 解 的 近 似 程 度 。特 点 （ 与 传 统 优 化 方 法 不 同 ） ： 凭 直 观 和 经 验给 出 算 法 ； 不 考 虑 所 得 解 与 最 优 解 的 偏 离 程 度 . 20世 纪 90年 代 意 大 利 学 者 M Dorigo， V Maniezzo，A Colorni等 从 生 物 进 化 的 机 制 中 受 到 启 发 ， 通 过 模拟 自 然 界 蚂 蚁 搜 索 路 径 的 行 为 ， 提 出 来 一 种 新 型 的 模拟 进 化 算 法 蚁 群 算 法 ， 是 群 智 能 理 论 研 究 领 域的 一 种 主 要 算 法 。 用 该 方 法 求 解 TSP问 题 、 分 配 问 题 、job-shop调 度 问 题 ， 取 得 了 较 好 的 试 验 结 果 特 别 蚁群 算 法 在 求 解 复 杂 优 化 问 题 （ 特 别 是 离 散 优 化 问 题 ）方 面 有 一 定 优 势 ， 蚂 蚁 从 A点 出 发 ， 速 度 相 同 ， 食 物 在 D点 ， 可 能 随 机 选 择 路 线ABD或 ACD。 假 设 初 始 时 每 条 分 配 路 线 一 只 蚂 蚁 ， 每 个 时间 单 位 行 走 一 步 ， 本 图 为 经 过 9个 时 间 单 位 时 的 情 形 ： 走ABD的 蚂 蚁 到 达 终 点 ， 而 走 ACD的 蚂 蚁 刚 好 走 到 C点 ， 为 一半 路 程 。 本 图 为 从 开 始 算 起 ， 经 过 18个 时 间 单 位 时 的 情 形 ：走 ABD的 蚂 蚁 到 达 终 点 后 得 到 食 物 又 返 回 了 起 点 A， 而 走 ACD的 蚂 蚁 刚 好 走 到 D点 。 , |j), (iA n1,2,.,N Nji nnijd )( nl ii lldwf 1 1)( ),( 21 niiiw 11 ii n 初 始 的 蚁 群 算 法 是 基 于 图 的 蚁 群 算 法 ， graph-based ant system,简 称 为 GBAS， 是 由 Gutjahr W J在2000年 的 Future Generation Computing Systems提 出 的 .算 法 步 骤 如 下 ：STEP 0 对 n个 城 市 的 TSP问 题 ，城 市 间 的 距 离 矩 阵 为 ， 给 TSP图 中 的每 一 条 弧 赋 信 息 素 初 值 ， 假设 m只 蚂 蚁 在 工 作 ， 所 有 蚂 蚁 都 从 同 一 城 市 出 发。 当 前 最 好 解 是 。 , |j), (iA n1,2,.,N Nji nnijd )(),( ji |1)0( Aij ),2,1( nw 0i STEP 1 （ 外 循 环 ） 如 果 满 足 算 法 的 停 止 规 则 ， 则 停 止 计 算并 输 出 计 算 得 到 的 最 好 解 。 否 则 使 蚂 蚁 s从 起 点 出 发 ， 用 表 示 蚂 蚁 s行 走 的 城 市 集 合 ， 初 始 为 空 集 ， 。STEP 2 (内 循 环 ) 按 蚂 蚁 的 顺 序 分 别 计 算 。 当蚂 蚁 在 城 市 i， 若 完 成 第 s只 蚂 蚁 的 计 算 。 否 则 ， 若， 则 以 概 率 ，到 达 j， ； 若则 到 达 重 复 STEP 2。 ms 1)(sL)(sL 0i1 s m ( ) |(, ) , ( )Ls N l i l Al Ls 或 0( ) | ( , ) , ( ) L s N T l i l A l L s i 且 ( 1) ,( 1)ijij ijl T kp j Tk 0,ijp j T ( ) ( ) , :Ls Ls j i j 0( ) |(, ) , ( ) Ls N T l il Al Ls i 且0 0 0, ( ) ( ) , : ;i Ls Ls i i i STRP 3 对 ， 若 ， 按 中 城 市 的 顺序 计 算 路 径 程 度 ； 若 ， 路 径 长 度 置 为 一 个无 穷 大 值 （ 即 不 可 达 ） 。 比 较 m只 蚂 蚁 中 的 路 径 长度 ， 记 走 最 短 路 径 的 蚂 蚁 为 t。若 ， 则 。 用 如 下 公 式 对W路 径 上 的 信 息 素 痕 迹 加 强 ， 对 其 他 路 径 上 的 信 息素 进 行 挥 发 。 得 到 新 的 ， 重 复 步 骤 STEP 1。1 s m ( )L s N ( )L s( )L s N( ( ) ( ( )f L t f L W ( )W L t 111( ) (1 ) ( 1) ( , )( ) (1 ) ( 1) ( , )kij k ijij k ijk k i j WWk k i j W 为 上 的 一 条 弧不 是 上 的 一 条 弧( ), : 1ij k k k 在 STEP 3 中 ， 挥 发 因 子 对 于 一 个 固 定 的 ，满 足并 且 经 过 k次 挥 发 ， 非 最 优 路 径 的 信 息 素 逐 渐 减 少 至 消 。ln1 ,ln( 1)k k k Kk k 1K 1 kk 以 上 算 法 中 ， 在 蚂 蚁 的 搜 寻 过 程 中 ， 以 信 息 素 的概 率 分 布 来 决 定 从 城 市 i到 城 市 j的 转 移 。 算 法 中 包 括 信 息 素 更 新 的 过 程 1 信 息 素 挥 发 （ evaporation): 信 息 素 痕 迹 的 挥 发 过程 是 每 个 连 接 上 的 信 息 素 痕 迹 的 浓 度 自 动 逐 渐 减 弱 的过 程 ， 由 表 示 ， 这 个 挥 发 过 程 主 要用 于 避 免 算 法 过 快 地 向 局 部 最 优 区 域 集 中 ， 有 助 于 搜索 区 域 的 扩 展 。(1 ) ( ) k ij k 2 信 息 素 增 强 （ reinforcement):增 强 过 程 是 蚁 群 优化 算 法 中 可 选 的 部 分 ， 称 为 离 线 更 新 方 式 （ 还 有 在 线更 新 方 式 ） 。 这 种 方 式 可 以 实 现 由 单 个 蚂 蚁 无 法 实 现的 集 中 行 动 。 也 就 是 说 ， 增 强 过 程 体 现 在 观 察 蚁 群 （m只 蚂 蚁 ） 中 每 只 蚂 蚁 所 找 到 的 路 径 ， 并 选 择 其 中 最优 路 径 上 的 弧 进 行 信 息 素 的 增 强 ， 挥 发 过 程 是 所 有 弧都 进 行 的 ， 不 于 蚂 蚁 数 量 相 关 。 这 种 增 强 过 程 中 进 行的 信 息 素 更 新 称 为 离 线 的 信 息 素 更 。在 STEP 3中 ， 蚁 群 永 远 记 忆 到 目 前 为 止 的 最 优 解 。 可 以 验 证 ， 下 式 满 足 ：即 是 一 个 随 机 矩 阵 。四 个 城 市 的 非 对 称 TSP问 题 ， 距 离 矩 阵 和 城 市 图 示 如 下 ：( , ) ( ) 1, 0iji j A k k ( )k 0 1 0.5 11 0 1 1( ) 1.5 5 0 11 1 1 0 ijD d 假 设 共 4只 蚂 蚁 ， 所 有 蚂 蚁 都 从 城 市 A出 发 ， 挥 发 因 子 。 此 时 ， 观 察 GBAS的 计 算 过 程 。 矩 阵 共 有 12条 弧 ， 初 始 信 息 素 记 忆 矩 阵 为 ：1 , 1,2,32k k 0 112 112 112112 0 112 112(0) ( (0) 112 112 0 112112 112 112 0 ij 执 行 GBAS算 法 的 步 骤 2， 设 蚂 蚁 的 行 走 路 线 分 别 为 ：当 前 最 优 解 为 ， 这 个 解 是 截 止 到 当 前 的 最 优 解 ， 碰 巧 是实 际 最 优 解 1: , ( 1) 4;2: , ( 2) 3.5;3: , ( 3) 8;4: , ( 4) 4.5;W A B C D A f WW A C D B A f WW A D C B A f WW A B D C A f W 第 一 只第 二 只第 三 只第 四 只 按 算 法 步 骤 3的 信 息 素 更 新 规 则 ， 得 到 更 新 矩 阵这 是 第 一 次 外 循 环 结 束 的 状 态 。0 1 24 1 6 1 241 6 0 1 24 1 24(1) ( (1) 1 24 1 12 0 1 61 24 1 6 1 24 0ij 重 复 外 循 环 ， 由 于 上 一 次 得 到 的 W2已 经 是 全 局最 优 解 ， 因 此 按 算 法 步 骤 3的 信 息 素 更 新 规 则 ，无 论 蚂 蚁 如 何 行 走 ， 都 只 是 对 W2路 线 上 的 城 市信 息 素 进 行 增 强 ， 其 他 的 城 市 信 息 素 进 行 挥 发 。得 到 更 新 矩 阵这 是 第 一 次 外 循 环 结 束 的 状 态 。0 1 48 5 24 1 485 24 0 1 48 1 48(2) ( (2) 1 48 1 48 0 5 241 48 5 24 1 48 0 ij 重 复 外 循 环 ， 由 于 W2全 局 最 优 解 ， GBAS只 记录 第 一 个 最 优 解 ， 因 此 一 但 得 到 了 全 局 最 优 解 ，信 息 素 的 更 新 将 不 再 依 赖 于 以 群 的 行 走 路 线 ，而 只 是 不 断 增 强 最 优 路 线 的 信 息 素 ， 同 时 进 行挥 发 。 第 三 次 外 循 环 后 得 到 的 信 息 素 矩 阵 为 ：0 1 96 11 48 1 9611 48 0 1 96 1 96(3) ( (3) 1 96 1 96 0 11 481 96 11 48 1 96 0 ij 蚂 蚁 以 一 定 的 概 率 从 城 市 i到 城 市 j进 行 转 移 ， 信息 素 的 更 新 在 STEP 3 完 成 ， 并 随 K而 变 化 。 假设 第 K次 外 循 环 后 得 到 信 息 素 矩 阵 ，得 到 当 前 最 优 解 。第 K次 循 环 前 的 信 息 素 和 最 优 解 为 ，经 过 第 K次 外 循 环 后 ， 得 到 。 由于 蚂 蚁 的 一 步 转 移 概 率 是 随 机 的 ， 从 到 也 是 随 机 的 ， 是 一 个 马 尔 可 夫 过 程 。( ) ( ( )|(, ) )ijk k i j A ( )W k ( 1), ( 1)k W k ( ), ( )k W k ( 1), ( 1)k W k ( ), ( )k W k 一 般 蚁 群 算 法 的 框 架 和 GBAS基 本 相 同 ， 有 三 个 组 成部 分 ： 蚁 群 的 活 动 ； 信 息 素 的 挥 发 ； 信 息 素 的 增 强 ；主 要 体 现 在 前 面 的 算 法 中 步 骤 2和 步 骤 3中 的 转 移 概 率公 式 和 信 息 素 更 新 公 式 。