优化算法-模拟退火-粒子群-遗传算法.ppt

《优化算法-模拟退火-粒子群-遗传算法.ppt》由会员分享，可在线阅读，更多相关《优化算法-模拟退火-粒子群-遗传算法.ppt（19页珍藏版）》请在装配图网上搜索。

1、优 化 算 法 1 模 拟 退 火 算 法2 遗 传 算 法3 粒 子 群 算 法 1 模 拟 退 火 算 法一 、 模 拟 退 火 算 法 概 念 模 拟 退 火 算 法 来 源 于 固 体 退 火 原 理 ， 将 固 体 加 温 至 充 分 高 ， 再 让 其慢 慢 冷 却 ， 加 温 时 ， 固 体 内 部 粒 子 随 温 升 变 为 无 序 状 ， 内 能 增 大 ， 而 慢慢 冷 却 时 粒 子 渐 趋 有 序 ， 在 每 个 温 度 都 达 到 平 衡 态 ， 最 后 在 常 温 时 达 到基 态 ， 内 能 减 为 最 小 。 用 固 体 退 火 模 拟 组 合 优 化 问 题

2、， 将 内 能 E模 拟 为 目 标 函 数 值 f， 温 度 T演 化 成 控 制 参 数 t， 即 得 到 解 组 合 优 化 问 题 的 模 拟 退 火 算 法 ： 由 初 始 解 i 和 控 制 参 数 初 值 t开 始 ， 对 当 前 解 重 复 “产 生 新 解 计 算 目 标 函 数 差 接受 或 舍 弃 ”的 迭 代 ， 并 逐 步 衰 减 t值 ， 算 法 终 止 时 的 当 前 解 即 为 所 得 近 似最 优 解 1 模 拟 退 火 算 法二 、 模 拟 退 火 算 法 模 型 模 拟 退 火 算 法 可 以 分 为 解 空 间 、 目 标 函 数 和 初 始 解 三 部

3、 分 。 三 、 模 拟 退 火 的 基 本 思 想(1 ) 初 始 化 ： 初 始 温 度 T(充 分 大 )， 初 始 解 状 态 S(算 法 迭 代 的 起 点 )， 每 个 T值 的 迭代 次 数 L ；(2 ) 对 k=1 ， ， L做 第 (3 )至 第 6 步 ： (3 ) 产 生 新 解 S (4 ) 计 算 增 量 t=C(S)-C(S)， 其 中 C(S)为 评 价 函 数 (5 ) 若 t0 ， 然 后 转 第 2 步 。 1 模 拟 退 火 算 法四 、 模 拟 退 火 算 法 特 点1 .最 终 求 得 的 解 与 初 始 值 无 关 ， 与 初 始 解 状 态 S无

4、 关 ；2 .具 有 渐 近 收 敛 性 ， 在 理 论 上 是 一 种 以 概 率 1 收 敛 于 全 局 最 优 解 的全 局 优 化 算 法 ；3 .具 有 并 行 性 。 2 遗 传 算 法一 、 遗 传 算 法 概 念 遗 传 算 法 简 称 GA， 是 模 拟 自 然 界 遗 传 机 制 和 生 物 进 化 论 而 成 的 一种 并 行 随 机 搜 索 最 优 化 方 法 。 遗 传 算 法 将 “ 优 胜 劣 汰 ， 适 者 生 存 ” 的 生物 进 化 原 理 引 入 优 化 参 数 形 成 的 编 码 串 联 群 体 中 ， 按 所 选 择 的 适 应 度 函数 并 通 过

5、遗 传 中 的 复 制 、 交 叉 及 变 异 对 个 体 进 行 筛 选 ， 使 适 应 度 高 的 个体 被 保 留 下 来 ， 组 成 新 的 群 体 ， 新 的 群 体 既 继 承 了 上 一 代 的 信 息 ， 又 优于 上 一 代 。 这 样 周 而 复 始 ， 群 体 中 个 体 适 应 度 不 断 提 高 ， 直 到 满 足 一 定 的 条 件 。 2 遗 传 算 法二 、 遗 传 算 法 基 本 操 作（ 1） 复 制 ： 复 制 操 作 可 以 通 过 随 机 方 法 来 实 现 。 首 先 产 生 01之 间 均 匀 分 布的 随 机 数 ， 若 某 串 的 复 制 概

6、率 为 40%， 则 当 产 生 的 随 机 数 在 0.401.0之 间 时 ，该 串 被 复 制 ， 否 则 被 淘 汰（ 2 ） 交 叉 ： 在 匹 配 池 中 任 选 两 个 染 色 体 ， 随 机 选 择 一 点 或 多 点 交 换 点 位 置 ；交 换 双 亲 染 色 体 交 换 点 右 边 的 部 分 ， 即 可 得 到 两 个 新 的 染 色 体 数 字 串 。（ 3 ） 变 异 ： 在 染 色 体 以 二 进 制 编 码 的 系 统 中 ， 它 随 机 地 将 染 色 体 的 某 一 个 基 因 由 1变 为 0， 或 由 0变 为 1。 2 遗 传 算 法三 、 遗 传 算

7、 法 特 点（ 1） 对 参 数 的 编 码 进 行 操 作 ， 而 非 对 参 数 本 身 ；（ 2） 同 时 使 用 多 个 搜 索 点 的 搜 索 信 息 ；（ 3） 直 接 以 目 标 函 数 作 为 搜 索 信 息 ；（ 4） 使 用 概 率 搜 索 技 术 ；（ 5） 遗 传 算 法 在 解 空 间 进 行 高 效 启 发 式 搜 索 ， 而 非 盲 目 地 穷 举 或 完 全 随 机 搜索 ；（ 6） 对 于 待 寻 优 的 函 数 基 本 无 限 制 ， 它 既 不 要 求 函 数 连 续 ， 也 不 要 求 函 数 可 微 ；（ 7） 具 有 并 行 计 算 的 特 点 .

8、2 遗 传 算 法三 、 遗 传 算 法 的 应 用（ 1 ） 函 数 优 化 ； （ 2） 组 合 优 化 ； （ 3） 生 产 调 度 问 题 ；（ 4） 自 动 控 制 ： 利 用 遗 传 算 法 进 行 控 制 器 参 数 的 优 化 、 基 于 遗 传 算法 的 模 糊 控 制 规 则 的 学 习 、 基 于 遗 传 算 法 的 参 数 辨 识 、 基 于 遗 传 算 法的 神 经 网 络 结 构 的 优 化 和 权 值 学 习 ；（ 5） 机 器 人 ； （ 6） 图 像 处 理 ； （ 7 ） 人 工 生 命 ；（ 8 ） 遗 传 编 程 ； （ 9 ） 机 器 学 习 ； 2

9、遗 传 算 法四 、 遗 传 算 法 的 应 用 步 骤一 ： 确 定 决 策 变 量 及 各 种 约 束 条 件 ， 即 确 定 出 个 体 的 表 现 型 X和 问 题 的 解 空 间 ；二 ： 建 立 优 化 模 型 ， 即 确 定 出 目 标 函 数 的 类 型 及 数 学 描 述 形 式 或 量 化 方 法 ；三 ： 确 定 表 示 可 行 解 的 染 色 体 编 码 方 法 ， 即 确 定 出 个 体 的 基 因 型 x及 遗 传 算 法 的 搜 索 空间 ；四 ： 确 定 解 码 方 法 ， 即 确 定 出 由 个 体 基 因 型 x到 个 体 表 现 型 X的 对 应 关 系

10、或 转 换 方 法 ；五 ： 确 定 个 体 适 应 度 的 量 化 评 价 方 法 ， 即 确 定 出 由 目 标 函 数 值 到 个 体 适 应 度 的 转 换 规则 ； 六 ： 设 计 遗 传 算 子 ， 即 确 定 选 择 运 算 、 交 叉 运 算 、 变 异 运 算 等 遗 传 算 子 的 具 体 操 作 方法 。七 ： 确 定 遗 传 算 法 的 有 关 运 行 参 数 ， 即 M,G,Pc,Pm等 参 数 。 2 遗 传 算 法四 、 遗 传 算 法 的 应 用 步 骤 3 粒 子 群 算 法一 、 粒 子 群 算 法 （ PSO） 的 基 本 思 想 它 是 通 过 模 拟

11、鸟 群 觅 食 行 为 而 发 展 起 来 的 一 种 基 于 群 体 协 作 的 随 机 搜索 算 法 。 通 常 认 为 它 是 群 集 智 能 的 一 种 。 它 可 以 被 纳 入 多 主 体 优 化 系 统 。搜 寻 目 前 离 的 食 物 最 近 的 鸟 的 周 围 区 域根 据 自 己 飞 行 的 经 验 判 断 食 物 所 在已知 鸟的位置鸟当前位置和食物之间的距离 求解 找 到 食 物 的 最 优 策 略 3 粒 子 群 算 法q 每 个 寻 优 的 问 题 解 都 被 想 像 成 一 只 鸟 ， 称 为“粒 子 ;q 所 有 的 粒 子 都 由 一 个 Fitness Fu

12、nction 确 定 适 应 值 以 判 断 目 前 的 位 置 好 坏 ;q 每 一 个 粒 子 必 须 赋 予 记 忆 功 能 ， 能 记 住 所 搜 寻 到 的 最 佳 位 置 ;q 每 一 个 粒 子 还 有一个 速 度 以 决 定 飞 行 的 距 离 和 方 向 ， 这 个 速 度 根 据 它 本 身的 飞 行 经 验 以 及 同 伴 的 飞 行 经 验 进 行 动 态 调 整 。 3 粒 子 群 算 法二 、 粒 子 群 算 法 求 解 最 优 解q D维 空 间 中 ， 有 m个 粒 子 ； 粒 子 i位 置 ： xi=(xi1 ,xi2 ,xiD)， 将 xi代 入 适 应 函

13、 数 F(xi)求 适 应 值 ； 粒 子 i速 度 ： vi=(vi1 ,vi2 ,viD) 粒 子 i个 体 经 历 过 的 最 好 位 置 ： pbesti=(pi1 ,pi2 ,piD) 种 群 所 经 历 过 的 最 好 位 置 ： gbest=(g1 ,g2 ,gD) 通 常 ， 在 第 d（ 1 dD） 维 的 位 置 变 化 范 围 限 定 在 Xmin,d ,Xmax,d内 ， 速 度 变 化 范 围限 定 在 -Vmax,d ,Vmax,d内 。 pbestxi gbestvi 3 粒 子 群 算 法q 粒 子 i的 第 d维 速 度 更 新 公 式 ： q 粒 子 i的

14、第 d维 位 置 更 新 公 式 ： 第 k次 迭 代 粒 子 i飞 行 速 度 矢 量 的 第 d维 分 量 第 k次 迭 代 粒 子 i位 置 矢 量 的 第 d维 分 量 c1 ,c2 加 速 度 常 数 ， 调 节 学 习 最 大 步 长 r1 ,r2 两 个 随 机 函 数 ， 取 值 范 围 0 ， 1 ， 以 增 加 搜 索 随 机 性 w 惯 性 权 重 ， 非 负 数 ， 调 节 对 解 空 间 的 搜 索 范 围kidxkidv 1 1k k kid id idx x v k k-1 1 1id id 1 1 2 2v =wv ( ) ( )k kid id d idc r

15、 pbest x c r gbest x pbest gbest 3 粒 子 群 算 法三 、 粒 子 群 算 法 流 程 3 粒 子 群 算 法1.群 族 初 始 化 ： 以 随 机 的 方 式 求 出 每 一 粒 子 的 初 始 位 置 与 速 度 ；2.计 算 适 应 度 ： 根 据 适 应 度 函 数 计 算 出 其 适 应 度 值 以 作 为 判 断 每 个 粒 子 的 好 坏 ；3.寻 找 Pbest：找出每个粒 子到目前为止， 搜 寻 过 程 中 的 最 优 解 ；4.寻 找 gbest： 找 出 所 有 粒 子 到 目 前 为 止 所 搜 寻 到 的 全 体 最 优 解 ；5.

16、更 新 速 度 与 位 置 ： 根 据 速 度 和 位 移 更 新 公 式 ， 更 新 每 个 粒 子 的 移 动 方 向 与 速 度 ；6.判 断 是 否 收 敛 ： 通 常 算 法 达 到 最 大 迭 代 次 数 Gm ax或 者 最 佳 适 应 度 函 数 值 的 增 量小 于 某 个 给 定 的 罚 值 时 算 法 停 止 。 3 粒 子 群 算 法四 、 粒 子 群 算 法 构 成 要 素群 体 大 小 m： m很 小 ： 陷 入 局 部 最 优 解 的 可 能 性 很 大 ； m很 大 ： PSO的 优 化 能 力很 好 ， 计 算 量 大 ； 一 般 取 10-30个 。权 重

17、因 子 惯 性 权 重 w： w=0： 粒 子 很 容 易 趋 向 于 同 一 位 置 w小 ： 倾 向 于 局 部 探 索 ,精 细 搜 索 目 前 的 小 区 域 w大 ： 扩 展 新 的 搜 索 区 域 ,利 于 全 局 搜 索一 般 取 0 .9 ,1 .2 即 可 。权 重 因 子 学 习 因 子 c 1 ， c2 ： 一 般 c1 等 于 c2 ,并 且 范 围 在 0和 4之 间 ；最 大 速 度 Vm： Vm较 大 时 ， 探 索 能 力 增 强 ， 但 粒 子 容 易 飞 过 最 优 解 ； Vm较 小 时 ， 开 发 能 力 增 强 ， 但 容 易 陷 入 局 部 最 优 Vm一 般 设 为 每 维 变 量 的 取 值 范 围 。 1234 3 粒 子 群 算 法四 、 粒 子 群 算 法 优 点1、 参 数 较 少 ， 容 易 调 整2、 局 部 与 全 局 结 合 ， 收 敛 速 度 快