几种智能算法概述及其应用

几种智能算法概述及其应用 汇报内容几种智能算法概述1. 遗传算法 2. 粒子群算法3. 模拟退火算法 4. 蚁群算法 智能算法概述1、遗传算法遗 传 算 法 （ GeneticAlgorithm， GA） 是 一 种 进 化 算 法 ， 其 基 本原 理 是 仿 效 生 物 界 中 的 “ 物 竞 天 择 、 适 者 生 存 ” 的 演 化 法 则 。 遗 传算 法 的 做 法 是 把 问 题 参 数 编 码 为 染 色 体 ，再 利 用 迭 代 的 方 式 进 行 选 择 、 交 叉 以 及变 异 等 运 算 来 交 换 种 群 中 染 色 体 的 信 息 ，最 终 生 成 符 合 优 化 目 标 的 染 色 体 。 智能算法概述染 色 体 ： 生 物 遗 传 物 质 主 要 载 体 。基 因 ： 扩 展 生 物 性 状 的 遗 传 物 质的 功 能 单 元 和 结 构 单 位 。基 因 座 ： 染 色 体 中 基 因 的 位 置 。等 位 基 因 ： 基 因 所 取 的 值 。 生 物 遗 传 概 念 遗 产 算 法 中 的 应 用适 者 生 存 目 标 值 比 较 大 的 解 被 选 择 的 可 能 性 大个 体 可 能 解染 色 体 解 的 编 码 （ 字 符 串 、 向 量 等 ）基 因 解 中 每 一 分 量 的 特 征适 应 性 适 应 函 数 值群 体 根 据 适 应 函 数 值 选 定 的 一 组 解 （ 解 的 个 数 为 群 体 的 规 模 ）婚 配 交 叉 选 择 两 个 染 色 体 进 行 交 叉 产 生 一 组 新 的 染色 体 的 过 程变 异 编 码 的 某 一 分 量 发 生 变 化 的 过 程1、遗传算法 智能算法概述遗 传 算 法 流 程遗 传 算 法 改 进 方 向 1、 遗 传 算 法 与 非 线 性 规 划 结 合 2、 与 BP神 经 网 络 结 合 3、 基 于 量 子 遗 传 算法 寻 优 4、 多 种 群 遗 传 算 法 5、 多 层 编 码 遗 传 算 法1、遗传算法 智能算法概述TSP（ 旅 行 商 问 题 ） 问题 描 述 与 结 果 ：已 知 n个 城 市 互 相 之间 距 离 ， 某 人 从 某 城 市出 发 访 问 每 个 城 市 且 仅一 次 ， 如 何 安 排 才 能 使其 所 走 路 线 最 短1、遗传算法 智能算法概述制 孔 路 径 优 化在 飞 机 装 配 线 上 用 机 器人 带 动 末 端 执 行 器 进 行 制孔 ， 执 行 器 由 初 始 位 置 依次 移 动 到 每 一 孔 位 ， 最 后返 回 初 始 位 置 ， 目 标 为 所走 路 径 最 短 ， 时 间 最 少 产 品 生 产 安 排一 个 周 期 内 生 产 n种产 品 ， 开 销 包 括 制 造 成本 以 及 产 品 转 换 开 支 ，因 此 生 产 成 本 与 生 产 顺序 有 关 ， 目 标 为 使 转 换成 本 最 低1、遗传算法 智能算法概述2、粒子群算法产生背景粒 子 群 算 法 （ Particle Swarm Optimization， PSO） 源 于对 鸟 类 捕 食 行 为 的 研 究 ， 一 群 鸟 随 机 分 布 在 一 个 区 域 中 ， 在 这片 区 域 只 有 一 块 食 物 ， 鸟 类 捕 食 时 ， 所 有 鸟 都 不 知 道 食 物 在 哪里 ， 但 是 他 们 知 道 当 前 位 置 距 离 食 物还 有 多 远 ， 那 么 找 到 食 物 最 简 单 有 效的 策 略 就 是 搜 寻 当 前 距 离 食 物 最 近 的鸟 的 周 围 区 域 。 智能算法概述2、粒子群算法基本思想每 个 潜 在 解 都 是 搜 索 空 间 的 一 只 鸟 ， 称 之 为 “ 粒 子 ” ， 所 有 粒 子都 有 一 个 由 被 优 化 函 数 决 定 的 适 应 值 ， 还 有 一 个 速 度 决 定 其 飞 行 方向 及 距 离 。 粒 子 们 追 随 当 前 最 优 粒 子 在 解 空 间 搜 索 ， 然 后 通 过 迭 代找 到 最 优 解 。 在 每 一 次 的 迭 代 中 ， 粒 子 根 据 两 个 极 值 来 更 新 自 己 ： 粒 子 本 身 变 化 过 程 中 的 最 优 解 ， 称 为 个 体 极 值 整 个 种 群 目 前 找 到 的 最 优 解 ， 称 为 全 局 极 值有 时 为 了 避 免 陷 入 局 部 最 优 ， 可 使 用 整 体 中 一 部 分 作 为 粒 子 邻 居 ，则 所 有 邻 居 中 的 极 值 就 是 局 部 极 值 。 智能算法概述2、粒子群算法基本模型设 群 体 规 模 为 N， 目 标 搜 索 空 间 为 D维 。 1 1, , , Ti i i iDX v v v 1,2, ,i i N 1 1, , , Ti i i iDV v v v1,2, ,i N 1 1, , , Ti i i iDP p p p表 示 第 个 粒 子 的 位 置 。表 示 i的 飞 翔 速 度表 示 i自 身 搜 索 到 的 最 优 点 1 1 1 2 21 1k k k k k kid id d id id d gd idk k kid id idv v c r p x c r p xx x v 智能算法概述2、粒子群算法基本模型 学 习 因 子 c1：c1=0， 则 只 有 社 会 ，没 有 自 我学 习 因 子 c2：c2=0， 则 只 有 自 我 ，没 有 社 会 智能算法概述2、粒子群算法改进加入惯性权重由 基 本 粒 子 群 算 法 模 型中 粒 子 位 置 进 化 方 程 可 看出 ， 不 同 时 刻 位 置 由 飞 行速 度 决 定 ， 因 此 飞 行 速 度大 小 直 接 影 响 算 法 的 全 局收 敛 性 。 惯 性 权 重 分 类 ：1. 固 定 权 重 ， 种 群 规 模越 大 ， 所 需 权 重 越 小2. 时 变 权 重3. 随 机 权 重 智能算法概述3、模拟退火算法背景退 火 是 指 将 固 体 加 热 到 足 够 高 的 温 度 ， 使 分 子 呈 现 随 机排 列 状 态 ， 然 后 逐 步 降 温 使 之 冷 却 ， 最 后 分 子 以 低 能 状 态 排列 ， 固 体 达 到 某 种 稳 定 状 态 。 该 过程 属 于 热 力 学 范 畴 ， 主 要 由 三 部 分组 成 ： 加 温 过 程 、 等 温 过 程 以 及 冷却 过 程 。 智能算法概述3、模拟退火算法由 统 计 力 学 研 究 表 明 ， 在 温 度 T， 分 子 滞 留 在 状 态 r的 概 率满 足 波 兹 曼 概 率 分 布其 中 ， 为 状 态 r的 能 量 ， 为 概 率 分 布 的 标 准 化 因 子当 时即 分 子 停 留 在 能 量 小 的 状 态 概 率 大 1 2E E 1 2 11 2 BB E -E- = 1-exp - k TE1P E=E P E=E exp -Z T k T 智能算法概述3、模拟退火算法流程 初 始 化 ： 初 始 温 度 T（ 充 分 大 ） ， 初 始 解 状 态 S（ 算 法 迭 代 的起 点 ） ， 每 个 T值 的 迭 代 次 数 L 对 做 第 三 至 第 六 步 ： 对 当 前 解 随 机 扰 动 ， 产 生 新 解 S 计 算 增 量 ， 其 中 为 评 价 函 数 若 0则 接 受 S为 新 的 当 前 解 ， 否 则 以 概 率 接受 S作 为 新 的 当 前 解 如 果 满 足 终 止 条 件 则 输 出 当 前 解 作 为 最 优 解 ， 结 束 程 序 Sf 2 1S Sdf f f exp /df T1, ,k L 智能算法概述4、蚁群算法背景单 个 的 蚂 蚁 为 了 避 免 自 己 迷 路 ， 它在 爬 行 时 ， 同 时 也 会 释 放 一 种 特 殊 的 分泌 物 信 息 素 ， 信 息 素 浓 度 越 高 ， 表示 对 应 路 径 越 短 。 当 一 条 路 上 的 信 息 素越 来 越 多 ， 后 来 的 蚂 蚁 选 择 这 条 路 径 的概 率 也 就 越 来 越 大 ， 从 而 进 一 步 增 加 了该 路 径 的 信 息 素 浓 度 。 智能算法概述4、蚁群算法模型蚁群转移概率公式 信息更新公式Ant cycle system Ant quantity system Ant density system , , , , 0, k kk s J i i j i j if j J ii s i sp i j otherwise 11 1 ,0ijij ij ijn kij kt t / ,0, ij kk Q L 其 他 / ,0,ij ijk Q d 其 他 ,0,ijk Q 其 他 智能算法概述4、蚁群算法二维路径规划问题描述与流程二 维 空 间 中 存 在 4个 障 碍 物 ， 寻 求 一 条从 起 点 S到 终 点 T的 最 优 路 径 智能算法概述4、蚁群算法路径规划结果