《智能算法初步》PPT课件.ppt

2 2021-4-21l 蒙 特 卡 罗 算 法l 数 据 拟 合 、 参 数 估 计 、 插 值 等 数 据 处 理 算 法l 线 性 规 划 等 规 划 类 问 题l 图 论 算 法l 动 态 规 划 、 回 溯 搜 索 、 分 支 定 界 等 计 算 机 算 法l 模 拟 退 火 、 神 经 网 络 、 遗 传 算 法 等 最 优 化 理 论 算 法l 网 格 算 法 和 穷 举 法l 一 些 连 续 离 散 化 方 法l 数 值 分 析 算 法l 图 像 处 理 算 法 3 2021-4-213 人 工 智 能 优 化 算 法l 遗 传 算 法l 模 拟 退 火l 人 工 神 经 网 络 算 法l 粒 子 群 算 法l 蚁 群 算 法 4 2021-4-21l 人 工 智 能 (Artificial Intelligence, AI) 概念 是 John McCarthy（ 约 翰 .麦 克 斯 ） 于1956年 在 Dartmouth学 会 上 提 出 的 。l 美 国 计 算 机 科 学 家 ， 因 在 人 工 智 能 领 域的 重 大 贡 献 ， 被 称 为 “ 人 工 智 能 之 父 ”， 并 因 此 获 得 图 灵 奖l 他 于 1948年 获 得 加 州 理 工 学 院 数 学 学 士学 位 ， 1951年 获 得 普 林 斯 顿 大 学 数 学 博士 学 位 John McCarthy 5 2021-4-21l 人 工 智 能 让 机 器 像 人 一 样 思 考l 人 工 智 能 是 计 算 机 科 学 的 前 沿 学 科 ， 是 研 究 、 开 发 用 于 模 拟 、 延伸 和 扩 展 人 的 智 能 的 理 论 、 方 法 、 技 术 及 应 用 系 统 的 一 门 新 的 技术 科 学 .计 算 机 编 程 语 言 和 其 它 计 算 机 软 件 都 因 为 有 了 人 工 智 能 的进 展 而 得 以 存 在 。l 人 工 智 能 涉 及 学 科 ： 哲 学 和 认 知 科 学 ， 数 学 ， 神 经 生 理 学 ， 心 理学 ， 计 算 机 科 学 ， 信 息 论 ， 控 制 论 ， 不 定 性 论 ， 仿 生 学 等 6 2021-4-21l 人 工 智 能 的 目 的 ： 通 过 研 究 人 脑 的 组 成 机 理 和 思 维 方 式 ， 企 图 了解 智 能 的 实 质 ， 并 生 产 出 一 种 能 以 人 类 智 能 相 似 的 方 式 做 出 反 应的 智 能 机 器 让 机 器 具 有 智 慧 ， 像 人 一 样 思 考 .l 计 算 机 的 出 现 人 类 开 始 真 正 有 了 一 个 可 以 模 拟 人 类 思 维 的 工具l 人 工 智 能 的 领 域 研 究 ： 包 括 机 器 人 、 语 言 识 别 、 图 像 识 别 、 自 然语 言 处 理 和 专 家 系 统 等 . 7 2021-4-21意 识 和 人 工 智 能 的 区 别l 人 工 智 能 就 其 本 质 而 言 ， 是 对 人 的 思 维 的 信 息 过 程 的 模 拟 .l 对 于 人 的 思 维 模 拟 可 以 从 两 条 道 路 进 行 ： 结 构 模 拟 ： 仿 照 人 脑 的 结 构 机 制 ， 制 造 出 “ 类 人 脑 ” 的 机 器 ； 功 能 模 拟 ： 暂 时 撇 开 人 脑 的 内 部 结 构 ， 而 从 其 功 能 过 程 进 行 模 拟 。 现 代 电 子 计 算 机 的 产 生 便 是 对 人 脑 思 维 功 能 的 模 拟 ， 是 对 人 脑思 维 的 信 息 过 程 的 模 拟 .l 人 工 智 能 不 是 人 的 智 能 ， 更 不 会 超 过 人 的 智 能 . 8 2021-4-21“机 器 思 维 ” 同 “ 人 类 思 维 ” 的 本 质 区 别 ： 1. 人 工 智 能 纯 系 无 意 识 的 机 械 的 物 理 的 过 程 ， 人 类 智 能 主 要 是 生理 和 心 理 的 过 程 . 2. 人 工 智 能 没 有 社 会 性 . 3. 人 工 智 能 没 有 人 类 的 意 识 所 特 有 的 能 动 的 创 造 能 力 . 4. 两 者 总 是 人 脑 的 思 维 在 前 ， 电 脑 的 功 能 在 后 . 9 2021-4-21 * 1996年 2月 10-17日 , Garry Kasparov以 4:2战 胜 “ 深 蓝 ” (Deep Blue) * 1997年 5月 3-11日 , Garry Kasparov以 3.5:2.5输 于 改 进 后 的 “ 深 蓝 ” * 2003年 2月 Garry Kasparov 3:3战 平 “ 小 深 ” (Deep Junior) * 2003年 11月 Garry Kasparov 2:2战 平 “ X3D德 国 人 ” (X3D-Fritz ) 指 纹 识 别 、 人 脸 识 别 、 语 音 识 别 、 文 字 识 别 、 图 像 识 别 、 车 牌 识 别 等 10 2021-4-21 中 文 名 ： 人 工 智 能 片 名 ： AI 年 代 ： 2001 国 家 ： 美 国 视 读 人 工 智 能 、 人 工 智 能 的 未 来 、 人 工 智 能 哲 学 、 人工 智 能 ： 一 种 现 代 的 方 法 11 2021-4-21l 遗 传 算 法 (Genetic Algorithm， GA)l 人 工 神 经 网 络 算 法 (Artificical Neural Network , ANN)l 模 拟 退 火 (Simulated Annealing, SA)l 粒 子 群 优 化 算 法 (Partical Swam Optimization Algorithm, PSOA)l 蚁 群 优 化 算 法 (Ant Colony Optimization Algorithm, ACOA) 12 2021-4-21 97年 A 题 用 模 拟 退 火 算 法 00年 B 题 用 神 经 网 络 分 类 算 法 01年 B 题 这 种 难 题 也 可 以 使 用 神 经 网 络 美 国 89年 A 题 也 和 BP 算 法 有 关 系 美 国 03年 B 题 伽 马 刀 问 题 也 是 目 前 研 究 的 课 题 ， 目 前算 法 最 佳 的 是 遗 传 算 法 。遗 传 算 法 (GA)、 模 拟 退 火 法 (SA)、 神 经 网 络 (NN)、 近 几 年 的 赛 题 越 来 越 复 杂 ， 很 多 问 题 没 有 什 么 很 好 的模 型 可 以 借 鉴 ， 于 是 这 三 类 算 法 很 多 时 候 可 以 派 上 用 场 。 13 2021-4-21l 遗 传 算 法 (Genetic Algorithm， GA)l 人 工 神 经 网 络 算 法 (Artificical Neural Network , ANN)l 模 拟 退 火 (Simulated Annealing, SA)l 粒 子 群 优 化 算 法 (Partical Swam Optimization Algorithm, PSOA)l 蚁 群 优 化 算 法 (Ant Colony Optimization Algorithm, ACOA) 14 2021-4-21进 化 算 法 (Evolutionary Algorithm) 15 2021-4-21l 遗 传 算 法 是 一 类 模 拟 达 尔 文 生 物 进 化 论 的 自 然 选 择 和 遗 传 算 法 机理 的 生 物 进 化 过 程 的 计 算 模 型 ， 借 鉴 生 物 界 的 进 化 规 律 （ 适 者 生存 ， 优 胜 劣 汰 遗 传 机 制 ） 演 化 而 来 的 随 机 化 搜 索 最 优 化 方 法 。l 遗 传 算 法 最 初 由 美 国 密 歇 根 大 学 J. Holland（ 霍 兰 德 ） 教 授 于 1975年 首 先 提 出 来 的 ， 并 出 版 了 颇 有 影 响 的 专 著 Adaptation in Natural and Artificial Systems , 遗 传 算 法 这 个 名 称 才 逐 渐 为 人 所知 ， 通 常 称 为 “ 简 单 遗 传 算 法 ” 。 16 2021-4-21l 直 接 对 结 构 对 象 进 行 操 作 ， 不 存 在 求 导 和 函 数 连 续 性 的 限 定 ； 具 有 内 在 的 隐 并 行 性 和 更 好 的 全 局 寻 优 能 力 ； 采 用 概 率 化 的 寻 优 方 法 ， 能 自 动 获 取 和 指 导 优 化 的 搜 索 空 间 ， 自适 应 地 调 整 搜 索 方 向 ， 不 需 要 确 定 的 规 则 。l 遗 传 算 法 的 这 些 性 质 ， 已 被 人 们 广 泛 地 应 用 于 组 合 优 化 、 机 器 学习 、 信 号 处 理 、 自 适 应 控 制 和 人 工 生 命 等 领 域 。 它 是 现 代 有 关 智能 计 算 中 的 关 键 技 术 。 遗 传 算 法 的 主 要 特 点 17 2021-4-21l 遗 传 算 法 是 从 代 表 问 题 可 能 潜 在 的 解 集 的 一 个 种 群 （ population）开 始 的 ， 而 一 个 种 群 则 由 经 过 基 因 （ gene） 编 码 的 一 定 数 目 的 个体 (individual)组 成 。l 每 个 个 体 实 际 上 是 染 色 体 (chromosome)带 有 特 征 的 实 体 。l 染 色 体 作 为 遗 传 物 质 的 主 要 载 体 ， 即 多 个 基 因 的 集 合 ， 其 内 部 表现 （ 即 基 因 型 ） 是 某 种 基 因 组 合 ， 它 决 定 了 个 体 的 形 状 的 外 部 表现 ， 如 黑 头 发 的 特 征 是 由 染 色 体 中 控 制 这 一 特 征 的 某 种 基 因 组 合决 定 的 。 因 此 ， 在 一 开 始 需 要 实 现 从 表 现 型 到 基 因 型 的 映 射 即 编码 工 作 。 18 2021-4-21l 由 于 仿 照 基 因 编 码 的 工 作 很 复 杂 ， 我 们 往 往 进 行 简 化 ， 如 二 进 制编 码 ， 初 代 种 群 产 生 之 后 ， 按 照 适 者 生 存 和 优 胜 劣 汰 的 原 理 ， 逐代 （ generation） 演 化 产 生 出 越 来 越 好 的 近 似 解 。l 在 每 一 代 ， 根 据 问 题 域 中 个 体 的 适 应 度 （ fitness） 大 小 选 择 （selection） 个 体 ， 并 借 助 于 自 然 遗 传 学 的 遗 传 算 子 （ genetic operators） 进 行 组 合 交 叉 （ crossover） 和 变 异 （ mutation） ， 产生 出 代 表 新 的 解 集 的 种 群 。 这 个 过 程 将 导 致 种 群 像 自 然 进 化 一 样的 后 生 代 种 群 比 前 代 更 加 适 应 于 环 境 ， 末 代 种 群 中 的 最 优 个 体 经过 解 码 （ decoding） ， 可 以 作 为 问 题 近 似 最 优 解 。 19 2021-4-21l 由 于 遗 传 算 法 的 整 体 搜 索 策 略 和优 化 搜 索 方 法 在 计 算 是 不 依 赖 于梯 度 信 息 或 其 它 辅 助 知 识 ， 而 只需 要 影 响 搜 索 方 向 的 目 标 函 数 和相 应 的 适 应 度 函 数 ， 所 以 遗 传 算法 提 供 了 一 种 求 解 复 杂 系 统 问 题的 通 用 框 架 ， 它 不 依 赖 于 问 题 的具 体 领 域 ， 对 问 题 的 种 类 有 很 强的 鲁 棒 性 。 20 2021-4-21l 遗 传 算 法 是 由 进 化 论 和 遗 传 学 机 理 而 产 生 的 搜 索 算 法 。 1. 创 建 一 个 随 机 的 初 始 状 态 ： 初 始 群 是 从 解 中 随 机 选 择 出 来 的 ， 将这 些 解 比 喻 为 染 色 体 或 基 因 ， 该 种 群 被 称 为 第 一 代 。 2. 评 估 适 应 度 ： 对 每 一 个 解 (染 色 体 )指 定 一 个 适 应 度 的 值 ， 根 据 问 题求 解 的 实 际 接 近 程 度 来 指 定 (以 便 逼 近 求 解 问 题 的 答 案 )。 不 要 把 这 些“ 解 ” 与 问 题 的 “ 答 案 ” 混 为 一 谈 ， 可 以 把 它 理 解 成 为 要 得 到 答 案 ，系 统 可 能 需 要 利 用 的 那 些 特 性 。 21 2021-4-21l 3. 繁 殖 (包 括 子 代 突 变 ) 带 有 较 高 适 应 度 值 的 那 些 染 色 体 更 可 能 产 生 后 代 (后 代 产 生 后 也 将 发 生突 变 )。 后 代 是 父 母 的 产 物 ， 他 们 由 来 自 父 母 的 基 因 结 合 而 成 ， 这 个 过程 被 称 为 “ 杂 交 ” 。 4. 下 一 代 如 果 新 的 一 代 包 含 一 个 解 ， 能 产 生 一 个 充 分 接 近 或 等 于 期 望 答 案 的 输 出， 那 么 问 题 就 已 经 解 决 了 。 如 果 情 况 并 非 如 此 ， 新 的 一 代 将 重 复 他 们 父母 所 进 行 的 繁 衍 过 程 ， 一 代 一 代 演 化 下 去 ， 直 到 达 到 期 望 的 解 为 止 。 22 2021-4-21l 5. 并 行 计 算 * 非 常 容 易 将 遗 传 算 法 用 到 并 行 计 算 和 群 集 环 境 中 。 * 一 种 方 法 是 直 接 把 每 个 节 点 当 成 一 个 并 行 的 种 群 看 待 。 然 后 有 机 体根 据 不 同 的 繁 殖 方 法 从 一 个 节 点 迁 移 到 另 一 个 节 点 。 * 另 一 种 方 法 是 “ 农 场 主 /劳 工 ” 体 系 结 构 ， 指 定 一 个 节 点 为 “ 农 场主 ” 节 点 ， 负 责 选 择 有 机 体 和 分 派 适 应 度 的 值 ， 另 外 的 节 点 作 为“ 劳 工 ” 节 点 ， 负 责 重 新 组 合 、 变 异 和 适 应 度 函 数 的 评 估 。 23 2021-4-21 遗 传 算 法 模 拟 自 然 选 择 和 自 然 遗 传 过 程 中 发 生的 繁 殖 、 交 叉 和 基 因 突 变 现 象 ， 在 每 次 迭 代 中都 保 留 一 组 候 选 解 ， 并 按 某 种 指 标 从 解 群 中 选取 较 优 的 个 体 ， 利 用 遗 传 算 子 (选 择 、 交 叉 和 变异 )对 这 些 个 体 进 行 组 合 ， 产 生 新 一 代 的 候 选 解群 ， 重 复 此 过 程 ， 直 到 满 足 某 种 收 敛 指 标 为 止 。 24 2021-4-21 25 2021-4-21GA-第 0代 26 2021-4-21GA-第 1代 27 2021-4-21GA-第 ?代 28 2021-4-21GA-第 N代 29 2021-4-21生 物 进 化 遗 传 算 法适 者 生 存 适 应 函 数 值 最 大 的 解 被 保 留 的 概 率 最 大个 体 问 题 的 一 个 解染 色 体 解 的 编 码基 因 编 码 的 元 素群 体 被 选 定 的 一 组 解种 群 根 据 适 应 函 数 选 择 的 一 组 解交 叉 以 一 定 的 方 式 由 双 亲 产 生 后 代 的 过 程变 异 编 码 的 某 些 分 量 发 生 变 化 的 过 程环 境 适 应 函 数 30 2021-4-21 选 择 (selection): 根 据 各 个 个 体 的 适 应 值 ， 按 照 一 定 的 规 则 或 方 法 ，从 第 t代 群 体 P(t)中 选 择 出 一 些 优 良 的 个 体 遗 传 到 下一 代 群 体 P(t+1)中 。 交 叉 (crossover): 将 群 体 P(t)内 的 各 个 个 体 随 机 搭 配 成 对 ， 对 每 一 个个 体 ， 以 某 个 概 率 Pc (称 为 交 叉 概 率 ， crossvoer rate)交 换 它 们 之 间 的 部 分 染 色 体 。 变 异 (mutation): 对 群 体 P(t)中 的 每 一 个 个 体 ， 以 某 一 概 率 Pm(称 为 变异 概 率 ， mutation rate)改 变 某 一 个 或 一 些 基 因 座上 基 因 值 为 其 它 的 等 位 基 因 。 31 2021-4-21 如 何 进 行 编 码 ？ 如 何 产 生 初 始 种 群 ？ 如 何 定 义 适 应 函 数 ？ 如 何 进 行 遗 传 操 作 (复 制 、 交 叉 、 变 异 )？ 如 何 产 生 下 一 代 种 群 ？ 如 何 定 义 停 止 准 则 ？ 32 2021-4-21表 现 型 空 间 编 码 (Coding)解 码 (Decoding)基 因 型 空 间 = 0,1L0111010010100010011001001010010001 33 2021-4-21编 码 设 某 一 参 数 的 取 值 范 围 为 （ L， U） ， 使 用 长 度 为 k 的 二 进 制 编 码表 示 该 数 ， 则 共 有 种 不 同 的 编 码 。k2 k 0000000000 00000000001 10000000010 20000000011 31111111111 2 1 34 2021-4-21解 码 解 码 的 目 的 是 为 了 将 不 直 观 的 二 进 制 数 据 串 还 原 成 十 进 制 。( )k ii ki U Lx L b 11 2 2 1设 某 一 个 体 的 二 进 制 编 码 为 ,k k kb b b b b b 1 2 3 2 1 则 对 应 的 解 码 公 式 为 ： 35 2021-4-21适 应 函 数 (Fitness Function) GA在 搜 索 中 不 依 靠 外 部 信 息 ， 仅 以 适 应 函 数 为 依 据 ， 利 用群 体 中 每 个 染 色 体 (个 体 )的 适 应 值 来 进 行 搜 索 。 以 染 色 体适 应 值 的 大 小 来 确 定 该 染 色 体 被 遗 传 到 下 一 代 群 体 中 的 概率 。 染 色 体 适 应 值 越 大 ， 该 染 色 体 被 遗 传 到 下 一 代 的 概 率也 越 大 ； 反 之 ， 染 色 体 的 适 应 值 越 小 ， 该 染 色 体 被 遗 传 到下 一 代 的 概 率 也 越 小 。 因 此 适 应 函 数 的 选 取 至 关 重 要 ， 直接 影 响 到 GA的 收 敛 速 度 以 及 能 否 找 到 最 优 解 。 群 体 中 的 每 个 染 色 体 都 需 要 计 算 适 应 值 适 应 函 数 一 般 由 目 标 函 数 变 换 而 成 36 2021-4-21适 应 函 数 (Fitness Function) 适 应 函 数 常 见 形 式 ： 直 接 将 目 标 函 数 转 化 为 适 应 函 数 若 目 标 函 数 为 最 大 化 问 题 ： Fitness(f(x) = f(x) 若 目 标 函 数 为 最 小 化 问 题 ： Fitness(f(x) = -f(x) 37 2021-4-21适 应 函 数 (Fitness Function) 界 限 构 造 法 min min( ) , ( )Fitness( ( ) 0f x C f x Cf x others ， 目 标 函 数 为 最 大 化 问 题其 中 Cmin为 f(x)的 最 小 估 计 值max max( ), ( )Fitness( ( ) 0C f x f x Cf x others ， 目 标 函 数 为 最 小 化 问 题其 中 Cmaxn为 f(x)的 最 大 估 计 值 38 2021-4-21选 择 (Selection) 选 择 (复 制 )操 作 把 当 前 种 群 的 染 色 体 按 与 适 应 值 成 正 比例 的 概 率 复 制 到 新 的 种 群 中 主 要 思 想 : 适 应 值 较 高 的 染 色 体 体 有 较 大 的 选 择 (复 制 )机 会设 种 群 的 规 模 为 Nxi是 种 群 中 第 i个 染 色 体 1 ( )( ) ( ) is i N jj f xp x f x染 色 体 xi被 选 概 率 39 2021-4-21选 择 (Selection) 实 现 1： ” 轮 盘 赌 ” 选 择 (Roulette wheel selection) l产 生 一 个 在 0与 总 和 之 间 的 的 随 机 数 ml从 种 群 中 编 号 为 1的 染 色 体 开 始 ， 将 其 适 应 值 与 后 续 染 色 体 的 适 应 值 相加 ， 直 到 累 加 和 等 于 或 大 于 m 40 2021-4-21选 择 (Selection)染 色 体 的 适 应 值 和 所 占 的 比 例 轮 盘 赌 选 择 41 2021-4-21选 择 (Selection)随 机 数 23 49 13 38 6 27所 选 号 码 2 6 2 5 1 4所 选 染 色 体 11000 00011 11000 01100 01110 10010染 色 体 编 号 1 2 3 4 5 6染 色 体 01110 11000 00100 10010 01100 00011适 应 度 8 15 2 5 12 8被 选 概 率 0.16 0.3 0.04 0.1 0. 24 0.16适 应 度 累 计 8 23 25 30 42 50染 色 体 被 选 的 概 率被 选 的 染 色 体 42 2021-4-21选 择 (Selection) 轮 盘 上 的 片 分 配 给 群 体 的 染 色 体 ， 使 得 每 一 个 片 的 大 小 与 对 于染 色 体 的 适 应 值 成 比 例 从 群 体 中 选 择 一 个 染 色 体 可 视 为 旋 转 一 个 轮 盘 ， 当 轮 盘 停 止 时 ，指 针 所 指 的 片 对 于 的 染 色 体 就 时 要 选 的 染 色 体 。 模 拟 “ 轮 盘 赌 ” 算 法 ：(1)r=rand(0, 1)， s=0， i=0；(2)如 果 sr， 则 转 (4)；(3)s=s+p(xi)， i=i+1, 转 (2)(4)xi即 为 被 选 中 的 染 色 体 ， 输 出 I(5)结 束 43 2021-4-21选 择 (Selection) 其 他 选 择 法 ： 随 机 遍 历 抽 样 (Stochastic universal sampling) 局 部 选 择 (Local selection) 截 断 选 择 (Truncation selection) 竞 标 赛 选 择 (Tournament selection) 特 点 ： 选 择 操 作 得 到 的 新 的 群 体 称 为 交 配 池 ， 交 配池 是 当 前 代 和 下 一 代 之 间 的 中 间 群 体 ， 其 规 模 为 初始 群 体 规 模 。 选 择 操 作 的 作 用 效 果 是 提 高 了 群 体 的平 均 适 应 值 (低 适 应 值 个 体 趋 于 淘 汰 ， 高 适 应 值 个体 趋 于 选 择 )， 但 这 也 损 失 了 群 体 的 多 样 性 。 选 择操 作 没 有 产 生 新 的 个 体 ， 群 体 中 最 好 个 体 的 适 应 值不 会 改 变 。 44 2021-4-21 交 叉 (crossover, Recombination) 遗 传 交 叉 (杂 交 、 交 配 、 有 性 重 组 )操 作 发 生 在 两 个染 色 体 之 间 ， 由 两 个 被 称 之 为 双 亲 的 父 代 染 色 体 ，经 杂 交 以 后 ， 产 生 两 个 具 有 双 亲 的 部 分 基 因 的 新 的染 色 体 ， 从 而 检 测 搜 索 空 间 中 新 的 点 。 选 择 (复 制 )操 作 每 次 作 用 在 一 个 染 色 体 上 ， 而 交 叉操 作 每 次 作 用 在 从 交 配 池 中 随 机 选 取 的 两 个 个 体 上(交 叉 概 率 Pc)。 交 叉 产 生 两 个 子 染 色 体 ， 他 们 与 其 父 代 不 同 ， 且 彼此 不 同 , 每 个 子 染 色 体 都 带 有 双 亲 染 色 体 的 遗 传基 因 。 45 2021-4-21单 点 交 叉 (1-point crossover) 在 双 亲 的 父 代 染 色 体 中 随 机 产 生 一 个 交 叉 点 位 置 在 交 叉 点 位 置 分 离 双 亲 染 色 体 互 换 交 叉 点 位 置 右 边 的 基 因 码 产 生 两 个 子 代 染 色 体 交 叉 概 率 Pc 一 般 范 围 为 (60%, 90%)， 平 均 约 80% 46 2021-4-21 单 点 交 叉 操 作 可 以 产 生 与 父 代 染 色 体 完 全 不 同 的子 代 染 色 体 ； 它 不 会 改 变 父 代 染 色 体 中 相 同 的 基因 。 但 当 双 亲 染 色 体 相 同 时 ， 交 叉 操 作 是 不 起 作用 的 。假 如 交 叉 概 率 Pc 50%,则 交 配 池 中 50%的 染 色 体 (一 半 染 色 体 )将 进 行 交 叉 操 作 ， 余 下 的 50%的 染 色 体 进 行 选 择 (复 制 )操 作 。 GA利 用 选 择 和 交 叉 操 作 可 以 产 生 具 有 更 高 平 均 适应 值 和 更 好 染 色 体 的 群 体 47 2021-4-21 以 变 异 概 率 Pm改 变 染 色 体 的 某 一 个 基 因 ,当 以 二 进 制编 码 时 ， 变 异 的 基 因 由 0变 成 1， 或 者 由 1变 成 0。 变 异 概 率 Pm 一 般 介 于 1/种 群 规 模 与 1/染 色 体 长 度 之间 ， 平 均 约 1-2% 48 2021-4-21 比 起 选 择 和 交 叉 操 作 ， 变 异 操 作 是 GA中 的 次 要 操 作 ，但 它 在 恢 复 群 体 中 失 去 的 多 样 性 方 面 具 有 潜 在 的 作用 。 在 GA执 行 的 开 始 阶 段 ， 染 色 体 中 一 个 特 定 位 上 的 值 1可 能 与 好 的 性能 紧 密 联 系 ， 即 搜 索 空 间 中 某 些 初 始 染 色 体 在 那 个 位 上 的 值 1可 能 一致 产 生 高 的 适 应 值 。 因 为 越 高 的 适 应 值 与 染 色 体 中 那 个 位 上 的 值 1相 联系 ， 选 择 操 作 就 越 会 使 群 体 的 遗 传 多 样 性 损 失 。 等 到 达 一 定 程 度 时 ， 值 0会 从 整 个 群 体 中 那 个 位 上 消 失 ， 然 而 全 局 最优 解 可 能 在 染 色 体 中 那 个 位 上 为 0。 如 果 搜 索 范 围 缩 小 到 实 际 包 含 全 局最 优 解 的 那 部 分 搜 索 空 间 ， 在 那 个 位 上 的 值 0就 可 能 正 好 是 到 达 全 局 最优 解 所 需 要 的 。 49 2021-4-21 种 群 中 个 体 的 最 大 适 应 值 超 过 预 设 定 值 种 群 中 个 体 的 平 均 适 应 值 超 过 预 设 定 值 种 群 中 个 体 的 进 化 代 数 超 过 预 设 定 值 50 2021-4-21(1) 随 机 产 生 初 始 种 群 ;(2) 计 算 种 群 体 中 每 个 个 体 的 适 应 度 值 ,判 断 是 否 满足 停 止 条 件 ， 若 不 满 足 ， 则 转 第 (3)步 ,否 则 转 第(6)步 ;(3) 按 由 个 体 适 应 值 所 决 定 的 某 个 规 则 选 择 将 进 入 下一 代 的 个 体 ;(4) 按 交 叉 概 率 Pc进 行 交 叉 操 作 ,生 产 新 的 个 体 ;(5) 按 变 异 概 率 Pm进 行 变 异 操 作 ,生 产 新 的 个 体 ;(6) 输 出 种 群 中 适 应 度 值 最 优 的 染 色 体 作 为 问 题 的 满意 解 或 最 优 解 。 51 2021-4-21 52 2021-4-21基 本 遗 传 算 法 （ Simple Genetic Algorithms,简 称 SGA） 是 一 种 统 一 的 最 基 本 的 遗 传 算 法 ， 它 只使 用 选 择 、 交 叉 、 变 异 这 三 种 基 本 遗 传 算 子 ， 其 遗 传进 化 操 作 过 程 简 单 ， 容 易 理 解 ， 是 其 他 一 些 遗 传 算 法的 雏 形 和 基 础 ， 它 不 仅 给 各 种 遗 传 算 法 提 供 了 一 个 基本 框 架 ， 同 时 也 具 有 一 定 的 应 用 价 值 。 53 2021-4-21Procedure Genetic Algorithm begint = 0 ; %遗 传 代 数初 始 化 P(t) ; %初 始 化 种 群 或 染 色 体计 算 P(t) 的 适 应 值 ;while (不 满 足 停 止 准 则 ) do begin t = t+1 ; 从 P(t-1)中 选 择 P(t) ; % selection 重 组 P(t) ; % crossover and mutation 计 算 P(t) 的 适 应 值 ; end end 54 2021-4-21 函 数 优 化 函 数 优 化 是 遗 传 算 法 的 经 典应 用 领 域 ， 也 是 对 遗 传 算 法 进 行 性 能 测 试 评价 的 常 用 算 例 。 对 于 一 些 非 线 性 、 多 模 型 、多 目 标 的 函 数 优 化 问 题 ， 用 其 他 优 化 方 法 较难 求 解 ， 而 遗 传 算 法 却 可 以 方 便 地 得 到 较 好的 结 果 。遗 传 算 法 提 供 了 一 种 求 解 复 杂 系 统 优 化 问 题 的 通 用 框架 ， 它 不 依 赖 于 问 题 的 具 体 领 域 ， 对 问 题 的 种 类 有 很强 的 鲁 棒 性 ， 所 以 广 泛 应 用 于 很 多 学 科 。 下 面 列 举 一些 遗 传 算 法 的 主 要 应 用 领 域 。 55 2021-4-21 组 合 优 化 遗 传 算 法 是 寻 求 组 合 优 化 问 题 满 意解 的 最 佳 工 具 之 一 ， 实 践 证 明 ， 遗 传 算 法 对 于 组 合优 化 问 题 中 的 NP完 全 问 题 非 常 有 效 。 例 如 ， 遗 传 算法 已 经 在 求 解 旅 行 商 问 题 (Traveling Salesman Problem , TSP)、 背 包 问 题 (Knapsack Problem)、装 箱 问 题 (Bin Packing Problem) 等 方 面 得 到 成 功的 应 用 。 生 产 调 度 问 题 生 产 调 度 问 题 在 很 多 情 况 下 所建 立 起 来 的 数 学 模 型 难 以 精 确 求 解 ， 即 使 经 过 一 些简 化 之 后 可 以 进 行 求 解 也 会 因 简 化 得 太 多 而 使 求 解结 果 与 实 际 相 差 太 远 。 现 在 遗 传 算 法 已 经 成 为 解 决复 杂 调 度 问 题 的 有 效 工 具 。 56 2021-4-21 自 动 控 制 遗 传 算 法 已 经 在 自 动 控 制 领 域 中 得到 了 很 好 的 应 用 ， 例 如 基 于 遗 传 算 法 的 模 糊 控 制 器的 优 化 设 计 、 基 于 遗 传 算 法 的 参 数 辨 识 、 基 于 遗 传算 法 的 模 糊 控 制 规 则 的 学 习 、 利 用 遗 传 算 法 进 行 人工 神 经 网 络 的 结 构 优 化 设 计 和 权 值 学 习 等 。 机 器 人 智 能 控 制 机 器 人 是 一 类 复 杂 的 难 以 精确 建 模 的 人 工 系 统 ， 而 遗 传 算 法 的 起 源 就 来 自 于 对人 工 自 适 应 系 统 的 研 究 ， 所 以 机 器 人 智 能 控 制 自 然成 为 遗 传 算 法 的 一 个 重 要 应 用 领 域 。 57 2021-4-21 图 象 处 理 和 模 式 识 别 图 像 处 理 和 模 式 识 别是 计 算 机 视 觉 中 的 一 个 重 要 研 究 领 域 。 在 图 像 处理 过 程 中 ， 如 扫 描 、 特 征 提 取 、 图 像 分 割 等 不 可避 免 地 存 在 一 些 误 差 ， 这 些 误 差 会 影 响 图 像 处 理的 效 果 。 如 何 使 这 些 误 差 最 小 是 使 计 算 机 视 觉 达到 实 用 化 的 重 要 要 求 ， 遗 传 算 法 在 这 些 图 像 处 理中 的 优 化 计 算 方 面 得 到 了 很 好 的 应 用 。 人 工 生 命 人 工 生 命 是 用 计 算 机 、 机 械 等 人工 媒 体 模 拟 或 构 造 出 的 具 有 自 然 生 物 系 统 特 有 行为 的 人 造 系 统 。 自 组 织 能 力 和 自 学 习 能 力 是 人 工生 命 的 两 大 重 要 特 征 。 人 工 生 命 与 遗 传 算 法 有 着密 切 的 关 系 ， 基 于 遗 传 算 法 的 进 化 模 型 是 研 究 人工 生 命 现 象 的 重 要 理 论 基 础 。 58 2021-4-21 遗 传 程 序 设 计 Koza发 展 了 遗 传 程 序 设 计 的概 念 ， 他 使 用 了 以 LISP语 言 所 表 示 的 编 码 方 法 ，基 于 对 一 种 树 形 结 构 所 进 行 的 遗 传 操 作 来 自 动 生成 计 算 机 程 序 。 机 器 学 习 基 于 遗 传 算 法 的 机 器 学 习 ， 在 很 多领 域 中 都 得 到 了 应 用 。 例 如 基 于 遗 传 算 法 的 机 器学 习 可 用 来 调 整 人 工 神 经 网 络 的 连 接 权 ， 也 可 以用 于 人 工 神 经 网 络 的 网 络 结 构 优 化 设 计 。 分 类 器系 统 在 多 机 器 人 路 径 规 划 系 统 中 得 到 了 成 功 的 应用 。 59 2021-4-21SGA参 数 : 编 码 方 式 : 二 进 制 码 e.g. 000000; 01101 13; 1111131 种 群 规 模 : 4 随 机 初 始 群 体 “ 转 盘 赌 ” 选 择 一 点 杂 交 , 二 进 制 变 异 求 函 数 f(x)=x2的 最 大 值 ， x为 自 然 数 且 0 x31.o 手 工 方 式 完 成 演 示 SGA过 程 60 2021-4-21 61 2021-4-21 62 2021-4-21 63 2021-4-21求 下 列 函 数 的 最 大 值 ：( ) sin(10 ) 2.0 1,2f x x x x 64 2021-4-21 高 精 度 10 0( ,., ) ( 2 ) , 2 1 L iL iL iy xb a x b x y 编 码 x,y 0,1L 必 须 可 逆 (一 个 表 现 型 对 应 一 个 基 因 型 ) 解 码 算 子 ： : 0,1L x,y 染 色 体 长 度 L决 定 可 行 解 的 最 大 精 度长 染 色 体 (慢 进 化 ) 实 数 问 题 ： 变 量 z为 实 数 ， 如 何 把 a1,aL 0,1Lz x,y 65 2021-4-21设 定 求 解 精 确 到 6位 小 数 ， 因 区 间 长 度 位 2-(-1)=3,则 需 将 区间 分 为 3X106等 份 。 因 2097152 221 3X1062224194304。 故 编 码 的 二 进 制 串 长 L=22。2121 0 2 1002 ( 1)( ,., ) 1 ( 2 ) 1,22 1 iiL ib b b 将 一 个 二 进 制 串 (b21b20b0)转 化 为 10进 制 数 ：e.g. -1; 2 1.627 888 1.627888 = -1+3x(1110000000111111000101) 2 /(222-1) = -1+3x3674053/(222-1) 66 2021-4-21 随 机 初 始 化 种 群 适 应 函 数 本 实 例 目 标 函 数 在 定 义 域 内 均 大 于 0， 且 是 求 函 数 最大 值 ， 故 直 接 引 用 目 标 函 数 作 为 适 应 函 数 ： f(s) = f(x) 其 中 二 进 制 串 s对 于 变 量 x的 值 。 e.g. s1 = x1= -0.958 973 适 应 值 : f(s1) = f(x1) =1.078 878 s2= x2= 1.627 888 适 应 值 : f(s2) = f(x2) = 3.250 650 67 2021-4-21 选 择 操 作 (“ 轮 盘 赌 ” 选 择 ) 交 叉 操 作 (单 点 交 叉 ) 交 叉 前 (父 ): s1= s2= 交 叉 后 (子 ): s1= s2= 适 应 值 : f(s1) = f(-0.998 113) =1.940 865 f(s2) = f(1.666 028) = 3.459 245 s2的 适 应 值 比 其 双 亲 个 体 的 适 应 值 高 。 68 2021-4-21 变 异 操 作 变 异 前 (父 ): s2= 变 异 后 (子 ): s2= 适 应 值 f(s2) = f(1.721 638) = 0.917 743 比 f(s2)小 变 异 前 (父 ): s2= 变 异 后 (子 ): s”2= 适 应 值 f(s”2) = f(1.630 818) = 3.343 555 比 f(s2)大变 异 操 作 有 ” 扰 动 ” 作 用 ， 同 时 具 有 增 加 种 群多样 性 的 效 果 。 69 2021-4-21遗 传 算 法 的 参 数 : 种 群 规 模 : 50 染 色 体 长 度 : L=22 最 大 进 化 代 数 : 150 交 叉 概 率 : Pc=0.25 变 异 概 率 : Pm=0.01 70 2021-4-21世 代 数 染 色 体 编 码 变 量 x 适 应 值1411173440547189150 1000111000010110001111000001101100010100111101101010111001110011111110101011111101001111110000110111101100111111010010001000110011111000110110100011001111010011011000101100111111010011111100110011111101001111110011001111 1.831 6241.842 4161.854 8601.847 5361.853 2901.848 4431.848 6991.850 8971.850 5491.850 549 3.534 8063.790 3623.833 2863.842 0043.843 4023.846 2323.847 1553.850 1623.850 2743.850 274 71 2021-4-21最 优 化 问题 : 1 21 2( ) ( , , , )( , , , ) nnMinimize f x f x x xsubjectto x x x x S X 组 合 优 化 问 题 (Combinatorial Optimization Problem ) :最 优 化 问 题 中 的 解 空 间 X或 S由 离 散 集 合 构 成 。 72 2021-4-21传 统 的 优 化 方 法 (局 部 优 化 方 法 ) 共 轭 梯 度 法 、 牛 顿 法 、 单 纯 形 方 法 等特 点 : 1)依 赖 于 初 始 条 件 。2)与 求 解 空 间 有 紧 密 关 系 ， 促 使 较 快 地 收 敛 到 局 部 解 ，但 同 时 对 解 域 有 约 束 ， 如 连 续 性 或 可 微 性 。 利 用这 些 约 束 ， 收 敛 快 。 3)有 些 方 法 ， 如 Davison-Fletcher-Powell直 接 依 赖于 至 少 一 阶 导 数 ； 共 轭 梯 度 法 隐 含 地 依 赖 于 梯 度 。 73 2021-4-21全 局 优 化 方 法 下 降 轨 线 法 、 Monte-Carlo随 机 试 验 法 、 模 拟退 火 法 、 GA等特 点 ：1)不 依 赖 于 初 始 条 件 ；2)不 与 求 解 空 间 有 紧 密 关 系 ,对 解 域 无 可 微 或 连 续 的 要 求 ;容 易 实 现 ，求 解 稳 健 。3)但 收 敛 速 度 慢 ,能 获 得 全 局 最 优 ;适 合 于 求 解 空 间 不 知 的 情 况 。4)GA可 应 用 于 大 规 模 、 多 峰 多 态 函 数 、 含 离 散 变 量 等 全 局 优 化 问题 ;求 解 速 度 和 质 量 远 超 过 常 规 方 法 。 74 2021-4-21GA编 码 ：X=(x1,x2,xn)的 各 个 变 量 可 以 按 二 进 制 编 码 方 法 分 别 编 码 。对 于 变 量 xi的 上 、 下 限 约 束 lixi ui(i=1,2,n)， 依 据 解的 精 度 要 求 (有 效 位 数 )求 得 各 个 变 量 X=(x1,x2,xn)的 二 进 制码 位 数 (m1,m2,mn)(确 定 方 法 类 似 于 SGA实 例 2)， 因 此 将n个 二 进 制 位 串 顺 序 连 接 起 来 ， 构 成 一 个 个 体 的 染 色 体 编 码 ， 编码 的 总 位 数 m m1+m2+mn。1 2( , , ) 1,2, ,ni i iMinimize f x x xsubjectto l x u i n 无 约 束 最 优 化 问 题 : 75 2021-4-21GA解 码 ：解 码 时 仍 按 各 个 变 量 的 编 码 顺 序 分 别 实 现 常 规 的 二 进 制 编 码解 码 方 法 。二 进 制 遗 传 编 码 示 意 图 如 下 ： 76 2021-4-21常 规 解 法 ：(1)把 约 束 问 题 转 化 为 无 约 束 问 题 ， 在 用 无 约 束 问 题方 法 求 解 ， 如 罚 函 数 法(2)改 进 无 约 束 问 题 的 方 法 ， 再 用 于 约 束 问 题 ， 如 梯度 投 影 法 、 广 义 简 约 梯 度 法1 2( , , )( ) 0, 1, 2, ,( ) 0, 1, 2, , 1, 2, ,niii i iM inim ize f x x xg x i mh x i ll x u i n 约 束 最 优 化 问 题 : 77 2021-4-21 遗 传 算 法 求 解 关 键 : 约 束 条 件 的 处 理等 式 约 束 可 以 包 含 到 适 应 函 数 ， 仅 考 虑 不 等 式约 束 。 假 设 按 无 约 束 问 题 那 样 求 解 ， 在 搜 索 过 程 中 计 算 目 标 函数 值 ， 并 检 查 是 否 有 约 束 违 反 。 如 果 没 有 违 反 ， 则 表 明 是可 行 解 ， 就 根 据 目 标 函 数 指 定 一 适 应 值 ； 否 则 ， 就 是 不 可行 解 ， 因 而 没 有 适 应 值 (适 应 值 为 0)。 这 样 的 处 理 实 际 不 可行 ， 因 为 找 到 一 个 可 行 解 几 乎 与 找 到 最 优 解 一 样 困 难 。 78 2021-4-21一 般 解 法 ： 通 过 引 入 罚 函 数 ， 从 不 可 行 解 中 得 到 一 些 信息 。 将 罚 函 数 包 含 到 适 应 函 数 中 。 关 键 是 如 何 设 计 罚 函 数 ； 不 同 问 题 需 要 设 计 不 同 的 罚 函 数 ； 对 一 般 的 约 束 处 理 ， 通 常 很 困 难 。 79 2021-4-21典 型 问 题 ：巡 回 旅 行 商 问 题 (Traveling Salesman Problem)作 业 调 度 问 题 (Job Shop Scheduling Problem)背 包 问 题 (Knapsack Problem)图 着 色 问 题 很 多 组 合 最 优 化 问 题 是 NP难 问 题 或 NP完 全 问 题 80 2021-4-21TSP， 也 称 货 郎 担 问 题 ， 是 一 个 NP完 全 问 题 。TSP描 述 ： 图 论 :设 图 G=(V,E),其 中 V是 顶 点 集 ， E是 边 集 。 设C=(cij)是 与 E相 联 系 的 距 离 矩 阵 。 寻 找 一 条 通 过 所有 顶 点 且 每 个 顶 点 只 通 过 一 次 的 最 短 距 离 回 路(Hamilton回 路 )。 实 际 应 用 中 ， C也 可 解 释 为 费用 或 旅 行 时 间 矩 阵 。 实 际 :一 位 推 销 员 从 自 己 所 在 城 市 出 发 ， 必 须 遍 访 所有 城 市 之 后 又 回 到 原 来 的 城 市 ， 求 使 其 旅 行 费 用 最少 的 路 径 。 81 2021-4-21中 国 货 郎 担 问 题 : 城 市 数 : 40 城 市 编 号1,2,40 寻 找 一 条 最 短 路 径 82 2021-4-21搜 索 空 间 庞 大TSP涉 及 求 多 个 变 量 的 函 数 的 最 小 值 ， 求 解 很 困 难 。其 可 能 的 路 径 条 数 随 着 城 市 数 目 n成 指 数 增 长 ， 如 ，5个 城 市 对 应 12条 路 径 ； 10个 城 市 对 应 181 440条路 径 ； 100个 城 市 对 应 4.6663X10155条 路 径 。 如 此庞 大 的 搜 索 空 间 ， 常 规 解 法 和 计 算 工 具 都 遇 到 计 算 上的 困 难 。 只 能 寻 找 近 似 解 法 ， 如 神 经 网 络 方 法 、 模 拟退 火 法 、 遗 传 算 法 等 。 83 2021-4-21染 色 体 表 示 成 所 有 城 市 的 一 个 排 列 ， 若 有 n个 城 市 ， 一条 可 能 路 径 编 码 为 长 度 为 n的 整 数 向 量 (i1,i2,in),其 中ik表 示 第 ik个 城 市 。例 如 : 路 径 编 码 向 量 (5 1 7 8 9 4 6 2 3)直 接 表 示 一 条旅 行 路 程 (5-1-7-8-9-4-6-2-3)。此 向 量 是 1到 n的 一 个 排 列 ， 即 从 1到 n的 每 个 整 数 在 这个 向 量 中 正 好 出 现 一 次 ,不 能 有 重 复 。 这 样 ， 基 本 遗 传算 法 的 基 因 操 作 生 成 的 个 体 不 能 满 足 这 一 约 束 条 件 ， 需寻 求