《智能理论与技术》PPT课件.ppt

智 能 理 论 与 技 术杨 启 文 薛 云 灿 课 程 纲 要l 传 统 最 优 化 技 术无 约 束 最 优 化 方 法 （ 9学 时 ）有 约 束 最 优 化 方 法 （ 自 学 ， 3学 时 ）l 智 能 优 化 计 算进 化 计 算 （ 15学 时 ）模 糊 逻 辑 （ 9学 时 ）人 工 神 经 网 络 （ 18学 时 ） 最 优 化 技 术 的 重 要 性2 优 化 问 题 求 的 极 小 值 |34|)( 2 xxxf 034)( 2 xxxf1 求 解 问 题 求 的 根 1 32 xf(x) 1 32 xf(x)一 个 求 解 可 以 问 题 转 变 为 一 个 优 化 问 题 传 统 最 优 化 方 法 优 化 模 型 的 一 般 形 式l Opt. f ( xi, yj, k )l s.t. gh ( xi, yj, k ) , 0l h = 1,2, ,ml 其 中 ： xi 为 决 策 变 量 （ 可 控 制 ） yj 为 已 知 参 数 k 为 随 机 因 素 f 为 目 标 函 数 gh 为 约 束 条 件 传 统 最 优 化 方 法 无 约 束 最 优 化 方 法非 梯 度 搜 索l 概 述 x2 x1o (k)S(k) S(k)x(k+1)x(k) x*F(x(k) F(x(k+1)x(k+1)=x(k)+(k)s(k)迭 代 公 式在 优 化 设 计 的迭 代 运 算 中 ，在 搜 索 方 向 s(k)上 寻 求 最 优 步长 (k) 的 方 法称 一 维 搜 索 法 。 传 统 最 优 化 方 法 无 约 束 最 优 化 方 法直 接 搜 索l 概 述l 基 本 方 法1、 黄 金 分 割 法 （ 0.618法 ）2、 二 次 插 值 法 （ 抛 物 线 法 ）3、 单 纯 形 算 法 5.1 黄 金 分 割 法 黄 金 分 割 法 适 用 于 a,b区 间 上 的 任 何 单 峰 函 数求 极 小 值 问 题 。 对 函 数 除 要 求 单 峰 外 不 作 其 它 要 求 ，甚 至 可 以 不 连 续 。 因 此 ， 这 种 方 法 的 适 应 面 相 当 广 。一 、 黄 金 分 割 法 的 原 理 在 搜 索 区 间 a,b内 适 当 插 入 两 点 x1,x2 ， 并 计算 其 函 数 值 。 x1,x2 将 区 间 分 为 三 段 ， 通 过 比 较 函 数值 的 大 小 ， 删 除 其 中 的 一 段 ， 使 搜 索 区 间 缩 短 。 然后 再 在 保 留 下 来 的 区 间 上 作 同 样 处 理 ， 如 此 迭 代 下去 ， 使 搜 索 区 间 无 限 缩 小 ， 从 而 得 到 极 小 点 的 近 似值 。 5.1 黄 金 分 割 法 （ 图 5.1.1） 5.1 黄 金 分 割 法l 插 入 点 x1,x2的 位 置 相 对 于 区 间 a,b两 端点 有 对 称 性 要 求 ， 除 对 称 性 要 求 外 ， 还 要 求每 次 迭 代 区 间 长 度 缩 短 的 比 率 是 相 同 的 。 设原 区 间 长 度 为 l如 图 所 示 ， 保 留 区 间 长 度 为 l ，区 间 缩 短 率 为 。 进 行 第 二 次 缩 短 时 ， 新 点为 x3 ,设 y1f(x3)则 新 区 间 为 a,x1为 保 持 相 同的 区 间 缩 短 率 ， 5.1 黄 金 分 割 法 （ 图 5.1.1） 5.1 黄 金 分 割 法 应 有 （ 1- ） / = 故 ： 1- = 2 2 + -1=0由 此 可 得 ： =0.618黄 金 分 割 法 可 使 相 邻 两 次 搜 索 区 间 都 具 有相 同 的 缩 短 率 0.618。 x1=a+ 0.382(b-a)x2=a+ 0.618(b-a)b-x2=x1-ax2-x1= (b-a) 列 题 ： min f(x)=2x2-x-1 初 始 区 间 a1,b1=-1,1,精 度 L 0.16k ak bk k uk f( k) f( uk)1 -1 1 -0.236 0.236 -0.653 -1.1252 -0.236 1 0.236 0.528 -1.125 -0.9703 -0.236 0.528 0.056 0.236 -1.050 -1.1254 0.056 0.528 0.236 0.348 -1.125 -1.1065 0.056 0.348 0.168 0.236 -1.112 -1.1256 0.168 0.348 0.236 0.279 -1.125 -1.1237 0.168 0.279 5.1 黄 金 分 割 法l 二 、 黄 金 分 割 法 的 搜 索 过 程 1、 给 出 初 始 搜 索 区 间 a,b及 收 敛 精 度 。 2、 按 坐 标 点 计 算 公 式 计 算 ， 并 计 算 相 应 的函 数 值 ,取 出 较 大 点 3、 用 这 个 较 大 点 做 为 区 间 的 一 端 ,另 一 端 不变 来 缩 短 搜 索 区 间 4、 检 查 是 否 满 足 收 敛 条 件 5、 若 满 足 收 敛 条 件 ， 则 取 最 后 两 点 的 平 均值 作 为 极 小 点 的 近 似 解 。 5.2 二 次 插 值 法一 、 插 值 法 概 念 假 定 我 们 给 定 的 问 题 是 在 某 一 确 定 区 间内 寻 求 函 数 的 极 小 点 的 位 置 ， 但 是 没 有 函 数 表达 式 ， 只 有 若 干 试 验 点 处 的 函 数 值 。 我 们 可 以根 据 这 些 函 数 值 ， 构 成 一 个 与 原 目 标 函 数 相 接近 的 低 次 插 值 多 项 式 ， 用 该 多 项 式 的 最 优 解 作为 原 函 数 最 优 解 的 近 似 解 ， 这 种 方 法 是 用 低 次插 值 多 项 式 逐 步 逼 近 原 目 标 函 数 的 极 小 点 的 近似 求 解 方 法 ， 称 为 插 值 方 法 或 函 数 逼 近 法 。 5.2 二 次 插 值 法二 、 插 值 法 与 试 探 法 的 异 同 点 相同点：都 是 利 用 区 间 消 去 法 原 理将 初 始 搜 索 区 间 不 断 缩 短 ， 从 而 求 得 极 小点 的 数 值 近 似 解 。 5.2 二 次 插 值 法不同点：试 验 点 位 置 的 确 定 方 法 不 同 。 在 试 探 法中 试 验 点 的 位 置 是 由 某 种 给 定 的 规 律 确 定 的 ，并 未 考 虑 函 数 值 的 分 布 。 例 如 ： 黄 金 分 割 法 是按 照 等 比 例 0.618缩 短 率 确 定 的 。 而 在 插 值 法 中 ，试 验 点 的 位 置 是 按 函 数 值 近 似 分 布 的 极 小 点 确定 的 。 试 探 法 仅 仅 利 用 了 试 验 点 函 数 值 进 行 大小 的 比 较 ， 而 插 值 法 还 要 利 用 函 数 值 本 身 或 其导 数 信 息 。 所 以 ， 当 函 数 具 有 较 好 的 解 析 性 质时 ， 插 值 方 法 比 试 探 方 法 效 果 更 好 。 5.2 二 次 插 值 法三 、 二 次 插 值 法 的 概 念 利 用 原 目 标 函 数 上 的 三 个 插 值 点 ，构 成 一 个 二 次 插 值 多 项 式 ， 用 该 多 项 式 的最 优 解 作 为 原 函 数 最 优 解 的 近 似 解 ， 逐 步逼 近 原 目 标 函 数 的 极 小 点 ， 称 为 二 次 插 值方 法 或 抛 物 线 法 。 p1 p(x) p3f(x)f1 x 1=a p2f2x2 x* xP* f3x3=b 5.2 二 次 插 值 法 四 、 二 次 插 值 函 数 的 构 成 过 函 数 曲 线 上 的 三 点 P1(x1 , f 1)、 P2(x2 , f 2)、 P3(x3 , f 3) 作 二 次 插 值 多 项 式 p(x)=Ax2+Bx+C 它 应 满 足 条 件 p(x1)=Ax12+Bx1+C 1=f 1 p(x2)=Ax22+Bx2+C = f 2 p(x3)=Ax32+Bx3+C = f 3 5.2 二 次 插 值 法l 解 方 程 组 ， 得 待 定 系 数 A、 B、 C分 别 为)()( )()()( 133221 321213132 xxxxxx fxxfxxfxxA )()( )()()( 133221 322212212312322 xxxxxx fxxfxxfxxB )()( )()()( 133221 321122313113223 xxxxxx fxxxxfxxxxfxxxxC 5.2 二 次 插 值 法 令 插 值 函 数 p(x)的 一 阶 导 数 为 0， 即 p(x)=2ax+b=0 得 p(x)极 小 点 为 xp* = B / 2 A 代 入 A、 B得 321213132 322212212312322* )()()( )()()(21 fxxfxxfxx fxxfxxfxxxp 5.2 二 次 插 值 法l 令l 则 13 131 xx ffc 32 112122 )/()( xx cxxffc ) 2131(21* ccxxxP 5.2 二 次 插 值 法若 c2=0， 则 即 说 明 三 个 插 值 点 位 于 同 一 条 直 线 上 ， 因 此 说明 区 间 已 经 很 小 ， 插 值 点 非 常 接 近 ， 故 可 将 x2、y 2输 出 作 为 最 优 解 。 0)/()( 32 112122 xx cxxffc 13 13112 12 xx ffcxx ff 5.2 二 次 插 值 法 五 、 区 间 的 缩 短 为 求 得 满 足 收 敛 精 度 要 求 的 最 优 点 ， 往往 需 要 多 次 进 行 插 值 计 算 ， 搜 索 区 间 不 断 缩短 ， 使 xp*不 断 逼 近 原 函 数 的 极 小 点 x*。 第 一 次 区 间 缩 短 的 方 法 是 ， 计 算 xp*点 的函 数 值 fp*， 比 较 fp*与 f2， 取 其 中 较 小 者 所 对 应的 点 作 为 新 的 x2， 以 此 点 的 左 右 两 邻 点 作 为新 的 x1和 x3， 得 到 缩 短 后 的 新 区 间 x1， x3，如 图 所 示 。 xP*x2f2 f3x*x1=a x3=b 5.2 二 次 插 值 法l 以 后 ， 根 据 fp*相 对 于 x2的 位 置 ， 并 比 较 fp*与 f2 ，区 间 的 缩 短 可 以 分 为 以 下 四 种 情 况 。xP* x P*xP*xP*x2 x2x2 x2 x3=bx3=bx1=ax1=a 5.2 二 次 插 值 法 入 口xp*x2? f2*fP*?f2fH? XS=XF-b(XF-XH), fSfsfH? 单 纯形 为HFLSGLf RfG?XS=XF+b(XF-XH) SGL fRfL? RGLX E=XF+a(XF-XH), fEfEfR? GLERGL NN N N Y YY Y YN 图 5.3.2 单 纯 形 算 法 框 图 传 统 最 优 化 方 法 无 约 束 最 优 化 方 法l 概 述l 基 本 方 法l 1. 最 优 梯 度 法l 2. 共 轭 梯 度 法l 3. 牛 顿 法 与 阻 尼 牛 顿 法 梯 度 搜 索 梯 度 与 HESSE阵称 为 f在 点 x处 的 梯 度 最 优 梯 度 法 优 化 设 计 是 追 求 目 标 函 数 值 最 小 ， 因 此 ， 自 然 可 以 设想 从 某 点 出 发 ， 其 搜 索 方 向 取 该 点 的 负 梯 度 方 向 ， 使 函 数 值在 该 点 附 近 下 降 最 快 。 这 种 方 法 也 称 为 最 优 梯 度 法 。一 、 基 本 原 理梯 度 法 的 迭 代 公 式 为 ： x(k+1)=x(k)-(k)g(k)其 中 g(k)是 函 数 F(x)在 迭 代 点 x(k)处 的 梯 度 f(xk) ， (k)一 般 采 用 一 维 搜 索 的 最 优 步 长 ， 即 f(x(k+1)=f(x(k)-(k)g(k)=min f(x(k)- (k)g(k)=min()据 一 元 函 数 极 值 条 件 和 多 元 复 合 函 数 求 导 公 式 ， 得 ()= 0 即 得 (k) 的 值 由 ()= -( f(x(k)-(k)g(k)T g(k) =0即 （ f(x(k+1)T g(k) =0或 (g(k+1)Tg(k)=0 此 式 表 明 ， 相 邻 的两 个 迭 代 点 的 梯 度 是 彼此 正 交 的 。 也 即 在 梯 度的 迭 代 过 程 中 ， 相 邻 的搜 索 方 向 相 互 垂 直 。 梯度 法 向 极 小 点 的 逼 近 路径 是 锯 齿 形 路 线 ， 越 接近 极 小 点 ， 锯 齿 越 细 ，前 进 速 度 越 慢 。 最 优 梯 度 法二 、 迭 代 终 止 条 件 采 用 梯 度 准 则 ： | g(k) | 三 、 迭 代 步 骤（ 1） 任 选 初 始 迭 代 点 x(0)， 选 收 敛 精 度 。（ 2） 确 定 x(k)点 的 梯 度 （ 开 始 k=0)（ 3） 判 断 是 否 满 足 终 止 条 件 | g(k) | ？ 若 满 足 输 出最 优 解 ， 结 束 计 算 。 否 则 转 下 步 。（ 4） 从 x(k)点 出 发 ， 沿 -g(k)方 向 作 一 维 搜 索 求 最 优 步长 (k)。 得 下 一 迭 代 点 x(k+1)=x(k)-(k)g(k) ， 令 k=k+1 返回 步 骤 （ 2） 。 最 优 梯 度 法四 、 梯 度 法 流 程 图 入 口给 定 ： x(0)， k=0|g (k)| ？x*=x(k)f*=f(x(k)出 口x(k)= x(0计 算 ： g(k) k=k+1沿 g(k)方 向 一 维 搜 索 ，求 最 优 步 长 (k)。NY l 最 优 梯 度 法 解 下 题 ： min f(x)=2x12+x22 初 点 x(2) =(1,1)T , =1/10l 先 求 出 函 数 的 梯 度 ： g(k) = 4x1 2x2l 第 一 次 迭 代 :求 出 -g(1),并 运 算 是 否 满 足 终 止 条 件l 不 满 足 终 止 条 件 后 ,沿 -g(1)做 一 维 搜 索 ， 求 出 (1)l 利 用 x( )=x( )-( )g( )， 得 -g( )后 跳 到 第 一 步 共轭梯度法是共轭方向法的一种，因为该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称作共轭梯度法。一 、 共 轭 梯 度 法 的 搜 索 方 向 共 轭 梯 度 法 的 搜 索 方 向 采 用 梯 度 法 基 础 上 的 共 轭方 向 ， 如 图 所 示 ， 目 标 函 数 F(x)在 迭 代 点 xk+1处 的负 梯 度 为 - f(xk+1)， 该 方 向 与 前一 搜 索 方 向 Sk互 为 正 交 ， 在 此基 础 上 构 造 一 种 具 有 较 高 收 敛速 度 的 算 法 ， 该 算 法 的 搜 索 方向 要 满 足 以 下 两 个 条 件 ： （ 1） 以 xk+1点 出 发 的 搜 索 方向 S k+1是 - f(xk+1)与 Sk的 线 性组 合 。 即 xk x*xk+1- f(xk+1) Sk+1Sk Sk+1 = - f(xk+1) + kSk （ 2） 以 与 为 基 底 的 子 空 间 中 ， 矢 量 与 相 共 轭 ， 即满 足 Sk+1T G Sk = 0二 、 k的 确 定 记 住三 、 共 轭 梯 度 法 的 算 法 （ 1） 选 初 始 点 x0和 收 敛 精 度 。 （ 2） 令 k=0， 计 算 S0 = - f(x0) 。 （ 3） 沿 Sk方 向 进 行 一 维 搜 索 求 (k)， 得 x(k+1)=x(k)+(k)S(k) （ 4） 计 算 f(xk+1) ， 若 | f(xk+1)| ， 则 终 止迭 代 ， 取 x*=xk+1； 否 则 进 行 下 一 步 。 21)( )( kkk xf xf （ 5） 检 查 搜 索 次 数 ， 若 k=n， 则 令 x0=xk+1， 转 （ 2） ，否 则 ， 进 行 下 一 步 。 （ 6） 构 造 新 的 共 轭 方 向 Sk+1 = - f(xk+1) + kSk 令 k=k+1， 转 （ 3） 21)( )( kkk xf xf 四 、 共 轭 梯 度 法 流 程 图 入 口k=0， 计 算 ： - f(x0) | f(x k+1) | ？ 出 口求 (k) ， x(k+1)= x(k) +(k)S(k)计 算 ： f(xk+1) x*=xk+1f(x*)=f(xk+1)YN给 定 ： x(0)， k n ？ x0=xk+1NYSk+1 = - f(xk+1) + kSkK=K+1 牛 顿 法 是 求 无 约 束 最 优 解 的一 种 古 典 解 析 算 法 。 牛 顿 法 可 以分 为 原 始 牛 顿 法 和 阻 尼 牛 顿 法 两种 。 实 际 中 应 用 较 多 的 是 阻 尼 牛顿 法 。 一 、 原 始 牛 顿 法 的 基 本 思 想 在 第 k次 迭 代 的 迭 代 点 xk邻 域 内 ， 用 一 个 二 次 函数 去 近 似 代 替 原 目 标 函 数 f(x)， 然 后 求 出 该 二 次 函 数的 极 小 点 作 为 对 原 目 标 函 数 求 优 的 下 一 个 迭 代 点 ， 依次 类 推 ， 通 过 多 次 重 复 迭 代 ， 是 迭 代 点 逐 步 逼 近 原 目标 函 数 的 极 小 点 。如 图 所 示 。 F(x) 1(x)0(x) x0 x1x2x* 二 、 原 始 牛 顿 法 的 迭 代 公 式 设 目 标 函 数 f(x)具 有 连 续 的 一 、 二 阶 导 数 ，在 x(k)点 邻 域 内 取 f(x)的 二 次 泰 勒 多 项 式 作 近 似 式 ，即取 逼 近 函 数 (x)为设 xk+1为 (x)极 小 点 ， 根 据 极 值 的 必 要 条 件 ， 应有 (xk)=0， 即 f(xk)+ G(xk)x=0 又 x= xk+1 - xk 得 xk+1 = xk- G(xk)-1 f(xk) 即 牛 顿 法 迭 代 公 式 ， 方 向 - G(xk)-1 f(xk)称 为牛 顿 方 向 xxGxxxfxfxf kTTkk )(21)()()( xxGxxxfxfx kTTkk )(21)()()( 一 、 对 原 始 牛 顿 法 的 改 进 为 解 决 原 始 牛 顿 法 的 不 足 ， 加 入 搜 索 步 长 (k)因 此 ， 迭 代 公 式 变 为 ： xk+1 = xk - (k)G(xk)-1 f(xk) 二 、 阻 尼 牛 顿 法 的 迭 代 步 骤 （ 1） 给 定 初 始 点 和 收 敛 精 度 （ 2） 计 算 f(xk) ,若 f(xk)满 足 收 敛 条 件 ,则 停 止 计 算 ;否 则 ,计算 G(xk)=- 2f(xk)-1 f(xk) （ 3） 从 x(k)出 发 ,沿 G(xk)做 一 维 搜 索 ,求 步 长 (k),使 它 满 足 f( x(k)+ (k)d(k)=min f( x(k)+ d(k) 令 x (k+1)= x(k)+ (k)d(k) 。 （ 4） 检 查 收 敛 精 度 ， 若 | xk+1- xk |则 x*=xk+1， 停 止 ， 否 则 k=k+1， 返 回 （ 2） 继 续 三 、 阻 尼 牛 顿 法 的 特 点 优 点 ： 由 于 阻 尼 牛 顿 法 每 次 迭 代 都 在 牛 顿 方向 进 行 一 维 搜 索 ， 避 免 了 迭 代 后 函 数 值 上 升 的 现象 ， 从 而 保 持 了 牛 顿 法 的 二 次 收 敛 性 ， 而 对 初 始点 的 选 择 没 有 苛 刻 的 要 求 。 缺 点 ： 1、 对 目 标 函 数 要 求 苛 刻 ， 要 求 函 数 具 有连 续 的 一 、 二 阶 导 数 ； 为 保 证 函 数 的 稳 定 下 降 ，海 赛 矩 阵 必 须 正 定 ； 为 求 逆 阵 要 求 海 赛 矩 阵 非 奇异 。 2、 计 算 复 杂 且 计 算 量 大 ， 存 储 量 大 222141 )1()( xxxxxf 20)( )1(xf 20)( )1(xf 牛 顿 方 向 为 : 02 )()( )1(1)1(2)1( xfxfd从 x(1)出 发 ,沿 d(1)作 一 维 搜 索 .得 116)()( 4)1()1( dxf 从 x(1)出 发 ,沿 d(1)作 一 维 搜 索 .得 116)()( 4)1()1( dxf0 064)( 1 3 显 然 ,用 阻 尼 牛 顿 法 不 能 产 生 新 点 .原 因 在于 Hessian矩 阵 非 正 定 . 变 尺 度 法 也 称 拟 牛 顿 法 ， 它 是 基 于 牛 顿 法 的 思 想而 又 作 了 重 大 改 进 的 一 类 方 法 。 我 们 所 介 绍 的 变 尺 度法 是 由 Davidon于 1959年 提 出 又 经 Fletcher和 Powell加 以 发 展 和 完 善 的 一 种 变 尺 度 法 ， 故 称 为 DFP变 尺 度法 。 拟 牛 顿 法 的 基 本 思 想 是 用 不 包 含 二 阶 导 数 的 矩阵 近 似 牛 顿 法 中 的 Hessian矩 阵 的 逆 矩 阵 . 1、 选 定 初 始 点 和 收 敛 精 度 2、 计 算 初 始 点 处 的 梯 度 g1， 选 取 初 始 对 称 正 定 矩阵 H1=In。 3、 计 算 搜 索 方 向 Sk= - Hkgk 4、 沿 Sk方 向 一 维 搜 索 ， 求 步 长 (k),使 它 满 足 f( x(k)+ (k)d(k)=min f( x(k)+ d(k) 令 x(k+1)= x(k)+ (k)d(k) 。 5、 判 断 是 否 满 足 终 止 准 则 ， 若 满 足 输 出 最 优 解 ，否 则 转 6。 6、 当 迭 代 n次 还 未 找 到 极 小 点 ， 重 置 Hk为 单 位 矩阵 ， 并 以 当 前 点 为 初 始 点 返 回 2， 否 则 转 7。 7、 计 算 gk+1= ,p(k)= xk+1 xk,q(k)= gk+1 -gk . 利 用计 算 Hk+1置 k=k+1,返 回 3. )( )1( kxf )()( )()()()( )()(1 kkTk KTkkkkTk Tkkkk qHq HqqHqp ppHH 求 min取 初 始 点 及 初 始 矩 阵 为且 梯 度 为 242 12221 xxx 12)1(x 10 011H 212 )1(4 xxg 第 1次 迭 代 :从 x(1)出 发 作 一 维 搜 索 ,得得 x(2) =x(1)+(k)d(1)= ,g2= 241g 2411)1( gHd 98949498 185)1( 第 2次 迭 代 :p(1)= (k)d(1)=q(1)=g2-g1= ,利 用 公 式 可 得 H2= 95910 910940 30538 38863061 令 d(2)=-H2g2=从 x(2)出 发 作 一 维 搜 索 ,得得 得 x(3) =x(2)+(2)d(2)= , g3 = .得 最 优 解 为 x(3) 411512 3617)2( 01 00