球隙迁移算法实现全局优化 - 计算机学报

《球隙迁移算法实现全局优化 - 计算机学报》由会员分享，可在线阅读，更多相关《球隙迁移算法实现全局优化 - 计算机学报（9页珍藏版）》请在金锄头文库上搜索。

1、书书书第 卷第期 年月计 算 机 学 报 收 稿 日 期： ；最 终 修 改 稿 收 到 日 期： 本 课 题 得 到 国 家 自 然 科 学 基 金（ ） 、广 东 省 自 然 科 学 基 金（ ） 、广 州市 科 技 计 划 应 用 基 础 项 目（ ）资 助胡 劲 松，男， 年 生，博 士，副 教 授，主 要 研 究 方 向 为 智 能 优 化 算 法 及 应 用 ： 郑 启 伦，男， 年 生，教 授，博 士 生 导 师，主 要 研 究 领 域 为 计 算 智 能 和 优 化 算 法球 隙 迁 移 算 法 实 现 全 局 优 化胡 劲 松 郑 启 伦（华 南 理 工 大 学 计 算 机

2、科 学 与 工 程 学 院广 州 ）摘要给 出 一 种 新 的 优 化 算 法：球 隙 迁 移 法该 方 法 不 是 已 有 方 法 的 融 合 或 改 进，它 利 用 搜 索 过 程 中 积 累 的 极 小点 分 布 信 息 形 成 球 隙，以 此 启 发、指 导 后 来 的 搜 索 区 域，不 但 逃 离 了 当 前 局 部 极 小，还 能 有 效 地 避 免 重 复 历 史 上 的多 个 局 部 极 小目 前 的 智 能 算 法 中，勘 探 和 开 采 行 为 相 耦 合，球 隙 法 实 现 了 勘 探 与 开 采 的 分 离，避 免 了 相 互 干 扰，减小 了 代 价，对 变 量 耦

3、 合 对 象 的 优 化 效 果 好文 中 证 明 了 球 隙 法 能 在 有 限 计 算 次 数 内 确 定 地 找 到 连 续 函 数 的 全 局最 优关 键 词优 化；全 局 极 小；局 部 极 小；连 续 函 数中 图 法 分 类 号 犇 犗 犐号： 犛 狆 犺 犲 狉 犲 犌 犪 狆 犜 狉 犪 狀 狊犳 犲 狉 狉犻 狀 犵 犃 犾犵 狅 狉犻狋 犺 犿 狋 狅 犚 犲 犪犾犻狕 犲 犌 犾狅 犫 犪犾 犗 狆 狋犻 犿 犻狕 犪 狋犻狅 狀 （犛 犮 犺 狅 狅 犾 狅 犳 犆 狅 犿 狆 狌 狋犲 狉 犛 犮犻犲 狀 犮 犲 犪 狀 犱 犈 狀 犵 犻 狀 犲 犲 狉犻 狀 犵

4、，犛 狅 狌 狋 犺 犆 犺 犻 狀 犪 犝 狀 犻 狏 犲 狉 狊犻狋 狔 狅 犳 犜 犲 犮 犺 狀 狅 犾 狅 犵 狔，犌 狌 犪 狀 犵 狕 犺 狅 狌 ）犃 犫 狊狋狉 犪 犮狋 ， ， ， 犓 犲 狔 狑 狅 狉 犱 狊 ； ； ； 引言优 化 问 题 涉 及 几 乎 所 有 的 领 域一 方 面 有 新 算法 提 出，比 较 新 的 有 量 子 退 火、蚂 蚁（蚁 群）算 法、匀场 致 退 火、微 粒（粒 子）群、差（微）分 进 化（ ） 、文 化算 法（ ） 、协 同、免 疫 克 隆 算 法等，另 一 方 面 绝 大 部 分 工 作 集 中 在 对 已 有 算 法 进 行改 进

5、 和 融 合，如 吸 引 与 排 除 粒 子 群 算 法（ ）、多 编 码 等国 内 学 者 在 这 方 面 的 研 究 也 相 当活 跃，如 填 充 函 数 法、拟 人 退 火、混 合 差 分、单 亲遗 传 算 法、人 工 鱼 群 算 法 等以 上 各 种 优 化 算 法（包 括 其 改 进 型） ，各 有 优 点，且 有 不 少 成 功 的 应 用，但 优 化 算 法 的 最 重 要 指标 全 局 能 力，仍 然 有 待 提 高目 前 的 算 法 在 实 际运 行 中 都 难 以 避 免 地、时 不 时 地 陷 入 局 部 极 值，这 是多 年 来 学 者 们 一 直 试 图 解 决 的

6、最 大 难 题；其 次，目 前的 优 化 算 法 只 考 虑 了 克 服 当 前 局 部 极 小，而 缺 乏 有效 的 机 制 防 止 重 复 或 再 次 陷 入 已 经 发 现 的 多 个 局 部极 小 优 化 机 制 导 致 的 矛 盾优 化 搜 索 过 程 可 以 看 作 一 个 或 多 个 搜 索 者 在 一个 有 众 多 山 峰 山 谷 的 区 域，搜 寻 最 低 的 谷 底（山 谷 的最 低 点）克 服 局 部 极 小 的 过 程 就 是 搜 索 者 试 图 从 一个 山 谷 中 爬 出 来，去 寻 找 下 一 个 山 谷 的 谷 底对 模 拟退 火 而 言，当 搜 索 者 进 入

7、 一 个 山 谷 的 范 围，每 走 一 步他 都 有 两 种 选 择：他 可 以 向 下 走 这 种 行 为 称 为“开 采” （ ） ，可 以 找 到 该 山 谷 的 谷 底，即发 现 局 部 极 小（包 括 全 局 极 小） ；他 也 可 以 向 上爬 这 种 行 为 称 为“勘 探” （ ） ，可 以 使得 他 爬 出 这 个 山 谷，去 搜 索 其 它 山 谷，这 个 过 程 称 为克 服 局 部 极 小在 模 拟 退 火 中，勘 探 和 开 采 是 交 织 在一 起 的：即 从 当 前 状 态 到 下 一 状 态 时，既 可 以 选 一 个好 解（开 采） ，也 可 以 选 一 个

8、 劣 化 解（勘 探）于 是 带 来了 一 系 列 矛 盾：（）按 退 火 概 率 机 制，搜 索 者 连 续 向 上 或 向 下的 概 率 是 极 小 的，他 向 上 爬 一 步，向 下 退 几 步，很 多时 候 相 互 抵 消，白 白 增 加 代 价（）如 果 加 强 开 采，他 一 直 下 降 到 谷 底，一 般 从山 谷 底 部 爬 出 来 的 概 率 是 很 小 的，尤 其 是 范 围 较 大、底 部 较 平 的 山 谷，于 是 陷 入 该 局 部 极 小（）如 果 加 强 勘 探，他 可 能 搜 索 到 某 山 谷 的 上部 就 转 而 爬 出 该 山 谷 了，由 于 他 没 到

9、过 该 山 谷 的 谷底，因 此 不 清 楚 谷 底 的 具 体 深 度，而 该 谷 底 有 可 能 就是 全 局 最 小，就 因 此 而 错 失，即 所 谓“浅 尝 辄 止”勘探 虽 然 使 得 搜 索 逃 离 了 局 部 极 小，却 也 可 能 导 致 错失 全 局 极 小克 服 某 个 或 某 些 局 部 极 小 并 不 意 味 着一 定 能 得 到 全 局 极 小（）设 搜 索 者 已 搜 索 过犃、犅两 个 山 谷 并 到 达 了犆山 谷，搜 索 完犆后，他 从犆爬 出，有 可 能 又 进 入 到犃或犅山 谷 重 新 搜 索，显 然 这 是 不 必 要 的 浪 费，还导 致 重 陷

10、局 部 极 小，因 此 不 但 要 能 逃 离 当 前 局 部 极小犆，还 要 能 有 效 地 避 免 重 复 历 史 上 的 多 个 局 部 极小犃、犅目 前 的 启 发 式 算 法 克 服 局 部 极 小 的 机 理 本 质 上都 是 按 某 种 概 率 接 受“劣 化”解，如 遗 传 算 法 以 轮 盘选 择 后 代，蚁 群 算 法 按 信 息 素 概 率 选 择 路 径，这 点 和模 拟 退 火 的 勘 探 行 为 相 似，勘 探 和 开 采 也 是 交 织 在一 起 的，同 样 存 在 以 上 的 矛 盾 和 问 题勘 探 和 开 采的 矛 盾 一 直 是 研 究 热 点，主 要 方

11、 法 是 调 整 参 数，但 这 不 能 从 根 本 上 解 决 问 题，因 为 实 际 问 题 是 复 杂多 样 的，参 数 也 是 多 样 的；其 次 要 增 加 克 服 局 部 极 小的 成 功 率，就 得 加 大 接 受 差 解 的 概 率，导 致 代 价 剧增调 整 参 数 的 结 果 往 往 顾 此 失 彼例 如 将 模 拟 退 火的 初 始 温 度 设 高 一 些，退 火 系 数 小 一 些，全 局 能 力 就强，但 是 代 价 也 增 大将 遗 传 算 法 的 群 体 规 模 设 大些，也 同 样 如 此在 仿 真 实 验 中，如 果 某 次 找 不 到 全局 极 值，下 次

12、加 大 群 体 规 模，或 延 长 迭 代 次 数，一 般会 有 所 改 进，或 者 采 用 随 机 重 启 策 略通 常 是 这 样 反复 实 验，选 取 不 同 的 参 数，直 到 在 某 个“最 佳 参 数”下以 较 小 的 代 价 获 得 全 局 极 值但 对 实 际 优 化 工 程 而言，每 一 次 实 验 都 要 花 费 金 钱、时 间，因 此 衡 量 算 法的 代 价 应 该 是 在 各 种 参 数 情 况 下 的、全 部 实 验 次 数的 代 价 总 和，而 不 仅 仅 只 在 最 佳 参 数 下 统 计 全 局 性 证 明 的 局 限 性遗 传 算 法（包 括 各 种 混 合

13、 和 变 种）研 究 时 间 相 对较 长，成 功 应 用 的 例 子 多，相 关 的 收 敛 性 理 论 研 究 也更 深 入徐 宗 本 等 人指 出 所 给 出 的 收 敛 性结 果 只 适 用 于 满 足 特 定 条 件，且 不 易 找 出 具 体 所 对应 的 参 数 化 函 数 描 述，所 得 结 果 也 很 难 直 接 用 于 实际连 续 变 量 （实 数 编 码）的 全 局 性 更 复 杂，文献在 群 体 无 限 大 的 假 设 下，讨 论 了 分 别 单 独 使 用交 叉 和 变 异 算 子 时 的 收 敛 性，文 献认 为 其 证 明 强加 了 许 多 不 自 然 的 假 设

14、林 丹、李 敏 强 等 人给 出 了特 殊 条 件 下 群 体 充 分 大 且 迭 代 次 数 趋 向 于 无 限 时 的收 敛 性 判 断 法 则当 种 群 规 模 趋 于 无 穷 时，用 于 分 析连 续 优 化 问 题 的 框 架 与 方 法 均 不 完 善，存 在 着 这 样或 那 样 的 限 制 与 不 足，目 前 还 没 有 一 个 好 的 方 法 可用 于 准 确 描 述 连 续 的 动 态 行 为，并 在 不 强 加 任 何 严格 的 或 人 为 的 条 件 下 给 出 相 关 的 收 敛 性 结 果 基 于 图 建 立 了 蚁 群 算 法 解 决 组 合 优化 问 题 的 一

15、 般 框 架，在 特 定 的 条 件 下 选 择 充 分大 的 蚂 蚁 数 量 或 足 够 小 的 信 息 素 挥 发 系 数 来 获 得 任意 小 的 值，证 明 了 基 于 图 的 蚁 群 算 法（ ）可 以保 证 接 近 于的 概 率 收 敛 于 给 定 问 题 的 最 优 解； 和 证 明 了 当 迭 代 次 数 趋 向 于 无 穷时，针 对 一 类 蚁 群 算 法，可 以 保 证 找 到 全 局 最 优 解；文 献 对 不 同 的 蚁 群 算 法 进 行 了 收 敛 性 分 析，朱 庆 保 认 为 以 上 证 明 都 不 同 程 度 地 存 在 一 定 的局 限 性，有 较 多 的

16、条 件 约 束 对 基 本 微 粒 群（ ）算 法 和保 证 收 敛 的 算 法（ ）进 行 了 研 究，指 出 基本 算 法 不 能 保 证 全 局 或 局 部 收 敛，而 则 属 于 局 部 收 敛目 前 对 粒 子 群 算 法 收 敛 性 的 证 明计 算 机 学 报 年都 仅 局 限 于 证 明 算 法 是 收 敛 的，还 没 有 证 明 纯 粹 的粒 子 群 算 法 能 收 敛 到 最 优 解 总 之，目 前 关 于 智 能 优 化 算 法 的 全 局 性 证 明 绝大 多 数 建 立 在 运 算 时 间（次 数）无 限 长 的 前 提 之 上，多 数 证 明 都 强 加 了 一 些

17、 不 自 然 的 约 束 条 件，如 群 体无 限 大、已 接 近 最 优 等，尤 其 对 解 空 间 无 限 的 连 续 优化 问 题，鲜 有 关 于 有 限 步 的 全 局 收 敛 证 明（不 强 加 特殊 条 件）大 量 的 实 验 和 应 用 表 明 目 前 的 优 化 算 法 在运 行 中 不 时 陷 入 局 部 极 值本 文 给 出 一 种 新 的 优 化 方 法它 不 但 能 逃 离 当前 局 部 极 小，还 能 有 效 地 回 避 历 史 上 已 经 发 现 的 多个 局 部 极 小同 时，由 于 实 现 了 勘 探 与 开 采 的 分 离，它 减 小 了 代 价，提 高 了

18、成 功 率本 文 证 明 了 它 能 在 有限 计 算 次 数 内 确 定 地 找 到 连 续 函 数 的 全 局 最 优 球 隙 迁 移 原 理定 义 界 内 间 断 点：函 数犳（狓）在 点犲有 定 义，左 极 限 狓犲 犳（狓）与 右 极 限 狓犲 犳（狓）均 存 在 但 不 相等，且犳（犲）介 于 左 右 极 限 之 间，即 满 足 狓犲 犳（狓）犳（犲） 狓犲 犳（狓）或 者 狓犲 犳（狓）犳（犲） 狓犲 犳（狓） ，则 称犲为 函 数犳（狓）的 界 内 间 断 点多 元函 数 依 此 类 推本 文 目 标：非 随 机 的 连 续 变 量 优 化 问 题（随 机性 问 题 与 随 机

19、 型 算 法 是 不 同 的 概 念） ，数 学 描 述如 下：狀维 连 续 变 量犡（狓，狓， ，狓狀），函 数狔犳（犡）在 闭 区 域内 除 界 内 间 断 点 外 无 其 它 类 型 的间 断 点，犳的 数 学 表 达 式 未 知，求犳的 最 小 值本 文 不 要 求 目 标 函 数 可 导，不 要 求 全 域 连 续，非随 机 的 连 续 或 分 段 连 续 函 数 均 满 足 以 上 要 求文献 附 录 中 的 个 测 试 函 数 中 个 是 该 类 型（另 有个 随 机 型） ，应 该 说 实 际 应 用 中 的 非 离 散 优化 问 题 绝 大 多 数 是 这 类 问 题定 义

20、孤 立 极 小 点：设 函 数犳在 点犃的 邻 域有 唯 一 极 小 值犳（犃） ，称 该 邻 域 为犃的 极 值 域定 义 从 极 值 域中 一 点犅出 发，做 贪 心 搜索，轨 迹 必 趋 向 极 点犃称犅 犃为 起极 对我 们 可 以 把 局 部 极 小 点犃看 做 一 个 吸 引 子，极值 域是 吸 引 子犃的 吸 引 域克 服 局 部 极 小 的 目 的在 于 获 取 新 的 局 部 极 值，所 以 其 实 质 就 是：使 得 搜 索得 到 极 小 点犃之 后，再 摆 脱 它其 难 点 在 于：当 勘 探和 开 采 交 织 在 一 起 时（见 上 节） ，任 何 试 图 取 得 好

21、解（比 当 前 解 好）的 行 为 都 将 被 吸 引 子 吸 引 住，从 而 难以 摆 脱我 们 的 想 法 是 首 先 将 勘 探 与 开 采 分 为个相 互 独 立 的 过 程，从 而 避 免 了 相 互 影 响，之 后 分 而治 之定 义 球 隙：设狀维 空 间 中 有犽个 点 围 成 的一 个 唯 一 确 定 的 超 球犌，这犽个 点 都 在 球 面 上，则 称球犌为 一 个 球 型 的 空 隙（空 心 球） ，简 称 球 隙如 图中，点、围 成 球 隙 图 球 隙、极 值 域 示 意 图图中 小 圆 点、表 示 局 部 极 小 点，每 个 极小 点 有 一 个 包 围 其 的 极

22、值 域，即 图 中 的 不 规 则 的 虚线 框图 中 用 虚 点 线 画 出 了个 圆，即 球 隙图 中 点至的 箭 头 表 示 从 点出 发 做 贪 心 搜 索，找 到 极小 点，因 贪 心 法 无 法 摆 脱 局 部 极 小，我 们 设 想 以 某种 方 式（见 下 文）将 搜 索 从直 接 转 移 到 点，从进 行 局 部 搜 索，发 现 极 小 点 图 中 三 角 形 状 的 点、称 为“转 移 点”因 为 从 点已 经 找 到 点，所以 转 移 到 点再 到是 重 复 搜 索，如 果 一 直 在 点的 极 值 域 搜 索 下 去，将 是 不 断 重 复，于 是 陷 入 局 部 极小

23、 点 我 们 的 想 法 是 在 找 到 点后 将 搜 索 转 移 到的极 值 域 之 外，于 是 自 然 摆 脱 了 局 部 极 小，同 时 不 应 转移 到“老”极 小 点、的 极 值 域，那 样 又 是 重 复（即 上节 的 多 局 部 极 小） ，而 应 该 转 移 到 一 个 新 的 极 值 域 进行 贪 心 搜 索，发 现 新 的 极 值，如 此 不 断 转 移，不 断 找到 新 极 值，当 所 有 极 值 都 发 现 了，从 中 取 最 好 则 为 全局 极 值我 们 给 出 以 下 启 发 式 策 略 以 形 成 新 转 移 点启 发 式 策 略 离 已 找 到 的 极 小 点

24、 越 远，越 不 容易 落 入 其 极 值 域启 发 式 策 略 离 已 使 用 过 的 转 移 点 越 远，越 不容 易 落 入 老 极 值 域，老 转 移 点 表 明 该 区 域 已 被 开采 过这 种“远 离”策 略 无 需 知 道 极 值 域 范 围因 为 存在 多 个 点，不 能 远 离 一 个 却 接 近 另 一 个，所 以 各 点 相互 牵 制，其 次 还 有 边 界 的 限 制注 意 到 球 隙 的 中 心 恰期胡 劲 松 等：球 隙 迁 移 算 法 实 现 全 局 优 化符 合 以 上 要 求图中 绘 出 了个 球 隙（实 际 不 止个） ，一 般 情 况 下 选 最 大 球

25、 隙 的 中 心 为 佳，即 以 球 隙中 心 的 星 型 点为 下 一 个 转 移 点，从 该 点 出 发 搜索 未 知 的 新 极 小 点，之 后 由 于 点和 新 极 小 点 的 加入，当 前 最 大 球 隙分 裂 成 若 干 小 球 隙，刷 新 球 隙 的大 小 排 序，下 一 次 搜 索 将 迁 移 到 其 它 较 大 球 隙，称 之为 球 隙 迁 移 法起极 对（定 义）之 间 的 区 域 存 在 其 它 极 小 点的 概 率 较 小（见 下 节 定 理 ）注 意 到 点、和 点都 是 起极 对，所 以 球 隙虽 然 大 于 球 隙，但 从 其发 现 新 极 点 的 概 率 一 般

26、 不 大启 发 式 策 略 如 果 形 成 球 隙犌的 点 都 是 起极对，则犌的 大 小 应 当 减 半 考 虑球 隙 迁 移 法 包 括 贪 心 搜 索 和 球 隙 转 移 两 个 过程贪 心 搜 索 为 单 一 的 开 采，球 隙 转 移 为 纯 粹 的 勘探，互 不 干 扰，不 但 减 少 了 代 价，而 且 提 高 了 克 服 局部 极 小 的 能 力，其 次，球 隙 转 移 能 减 少 多 局 部 极 小 的重 复 球 隙 迁 移 法 的 全 局 性 证 明从 整 个 优 化 过 程 来 看，球 隙 迁 移 法 可 以 一 直 迁移，而 不 会 只 收 敛 于 一 点，这 和 多

27、数 智 能 算 法 都 不同，然 而 它 却 能 在 有 限 次 内 发 现 全 局 解，下 面 证 明定 理 狀维 空 间 中 的狀 个 线 性 无 关 的 点能 确 定 一 个 唯 一 的 球 隙证 明 设狀维 空 间 有狀 个 点，所 有 点 坐 标已 知令 其 中 第犽个 点犘（犽）的 第犻坐 标 分 量 为狆犻（犽） ，于 是 可 写 出 该 点 所 在 的狀维 超 球 面 方 程：（狆（犽）狉）（狆狀（犽）狉狀）犚（）其 中狉犻为 球 心 的 第犻坐 标 分 量，犚为 球 的 半 径，均 为待 求 的 球 参 数，注 意 到 其 中 共狀 个 参 数 待 定将狀 个 点 分 别 代

28、 入 方 程得 到 一 个 方 程 组：（狆（）狉）（狆狀（）狉狀）犚 （狆（狀 ）狉）（狆狀（狀 ）狉狀）犚烅烄烆以 方 程 组 中 的 第犻个 方 程 减 去 第犻 个 方 程 有（狆（犻）狆（犻 ）狉 （狆狀（犻）狆狀（犻 ）狉狀狆（犻）狆（犻 ）狆狀（犻）狆狀（犻 ）由 以 上 方 式 共 可 得 到狀个 关 于狉狉狀的 一 次 线性 方 程如 果 这狀个 方 程 线 性 无 关，则 能 得 到 唯 一 的一 组狉狉狀，将 它 们 代 入 第狀 个 方 程，因犚为 正数，得 到 唯 一 的犚证 毕当犽狀 点，也 可 和 边 界 组 成 球 隙，即 由犽个点 构 成、球 心 不 超 出

29、边 界 的 最 大 球定 义 狀维 欧 氏 空 间 的 广 义 体 积 为犱 狓狀犱 狓犱 狓狀，其 中为 闭 区 域显 然 闭 区 域 的 广 义 体 积 是 有 限 的定 理 闭 区 域内 的 孤 立 极 小 点 的 个 数 是有 限 的证 明 设内 任 意 孤 立 极 小 点犃的 极 值 域的 广 义 体 积 为犞犃，犞犃不 能 为 无 穷 小设的 广 义 体积 为犞，犞不 能 为 无 穷 大，所 以犞犞犃为 有 限 数，即只 能 包 含 有 限 个，又 因 为 所 有 极 值 域 相 互 不 包 含 且都 在内，所 以 孤 立 极 小 点 的 个 数 是 有 限 的证 毕引 理 如 果

30、 将 连 续 相 等 的 非 孤 立 极 小 点 看做 一 个，则 定 理对 所 有 极 小 点 都 成 立定 理 犅且犅极 小 点犃，则 过 点犅的等 高 线 的 切 线 夹 角不 为 无 穷 小如 图 图 不 为 无 穷 小证 明 反 证 法设为 无 穷 小，则 等 高 线 变 成图所 示，点犆、犇、犈合 为 一 点，注 意 到 图中 等 高线 右 侧 为 下 降 方 向犳（犆）犳（犇）犳（犈）则 图中， 犆犈犳（犡）犳（犆） 犇犈犳（犡）犳（犇）犳（犈） ，即 在犈点 不 连 续如为 连 续 区 域，则 假 设 不 成 立若内 有 间 断 点犈，由 上 述 极 限 式 知犈不 是 界 内

31、 间断 点，与 目 标 函 数 的 条 件 矛 盾，假 设 也 不 成 立证 毕图 为 无 穷 小上 述 结 论 可 以 推 广 到狀维定 理 从 极 值 域内 任 意 一 点犅出 发，通 过均 匀 分 割 角 度，贪 心 法 能 在 有 限 步 数 内 以 给 定 精 度逼 近 极 小 点犃证 明（）在 图中，贪 心 法 欲 从犅点 寻 找 下 降 方 向它 先 在 图中 的个 相 互 垂 直 的 实 箭 头 方 向 做 探测，均 失 败，之 后 对 角 度 进 行 均 分，沿 着个 虚 箭头 进 行 探 测，在 正 右 方 成 功 获 得 下 降 方 向称 这 种 探计 算 机 学 报 年

32、测 为 均 匀 分 割 角 度由 定 理，不 为 无 穷 小，因 此 通过 不 断 对 角 度 均 匀 划 分，总 能 通 过 有 限 次 试 探 找 到下 降 方 向图 均 匀 分 割 角 度（）设 第犻次 成 功 搜 索 后 函 数 值 下 降犳犻，有 犳， ，犳犻， ，犳犽，为 某 个 小 正 数，犽为 到 达 指 定 精 度 的 步 数，犽（犳（犅）犳（犃） ） 犳， ，犳犻， ，犳犽 ，即犽为 有 限 值综 合（） 、 （） ，该 贪 心 法 能 在 有 限 步 数 内 以 给 定精 度 接 近 极 小 点犃证 毕上 述 贪 心 法 是“笨 办 法” ，仅 用 于 证 明 法 能 沿

33、 着“狭 窄”山 谷 快 速 前 进 定 义 如 孤 立 极 小 点犃不 在 定 义 域的 边界 上，从犃到 极 值 域边 界 的 最 小 距 离 称 为 极 值 域半 径如犃在的 边 界 上，则的 边 界 和的 边 界有 部 分 重 合，极 值 域 半 径 改 为 从犃到的 不 重 合 边界 的 最 小 距 离对 非 孤 立 极 小 点 为 从边 界 到 任 意一 处 极 小 的 最 小 距 离定 理 极 值 域 半 径 不 为 无 穷 小由犳的 性 质 和 极 小 点 的 定 义 可 证定 理 如 转 移 点犅到 极 小 点犃的 距 离 小 于其 极 值 域 半 径，则 贪 心 法 可 在

34、 有 限 步 数 找 到犃证 明 由 已 知 条 件 和 定 义可 知犅，根 据定 理，即 证定 理 如犳在 极 小 点犃处 二 阶 连 续 可 微，则在犃附 近犳可 近 似 为 半 正 定 二 次 型 函 数证 明 由 已 知 得犳（犃） ，犳（犃）半 正定 ，其 泰 勒 展 开 式犳（犡）犳（犃） 犜犳（犃） （犡犃） （犡犃）犜犳（犃） （犡犃） （犡犃）证 毕定 理 如 果 对 一 个 二 次 函 数 依 次 沿 着 一 组狀个 线 性 无 关 的、共 轭 的 方 向 极 小 化，则 其 极 小 将 在狀步 或狀步 以 前 到 达，且 与 初 始 点 无 关，称 之 为 二 次 收敛

35、性 定 理 法 具 有 二 次 收 敛 性 定 理和告 诉 我 们，在 局 部 极 小 点 附 近 用 法 能 快 速 精 确 地 找 到 局 部 极 值可 以 将 与 相 结 合， 法 可 以用 来 做 粗 搜 索定 理 内 的 任 意 未 发 现 的 极 小 点 必 包 含在 现 有 的 某 一 个 球 隙 中证 明 所 谓 现 有 球 隙 是 指：已 找 到 的 极 小 点 和已 有 的 转 移 点 及 边 界 所 形 成 的 全 部 球 隙设 图中犡为 某 个 未 发 现 的 极 小 点，点、为 已 有 极 小 点或 转 移 点点为 离犡最 近 的 已 有 点以指 向犡的 射 线（箭

36、头）方 向 扩 展 圆，即 圆 心 在 该 射 线 上 向箭 头 方 向 运 动，且 保 持 点在 圆 上当 圆遇 到 点时 停 止 扩 展以 点和 点的 中 垂 线 向犡一 侧（箭头）扩 展 圆，遇 到 点停 止，即 得 到 包 含犡的 球 隙，如 点不 存 在，则 一 直 扩 展 到 圆 心 不 超 出 边 界以 上为维，上 述 过 程 可 以 扩 展 到 高 维，只 要 保 证 圆 心 所在 的 射 线 过 几 何 垂 心，向犡一 侧 扩 展，且 垂 直 于 已扩 展 的 各 点 所 在 的 面对 于维，以 过 点，形 成的 三 角 形 的 垂 心 且 垂 直 于 该 三 角 形 所 在

37、 平 面，向犡一 侧 扩 展上 述 扩 展 总 是 可 以 包 含犡证 毕图 球 的 扩 展补 充：虽 然犡是 未 知 的，但 该 证 明 并 非 是 构 造包 含犡的 球 隙，而 是 证 明 存 在 一 个 球 隙定 理 说明 在 已 有 点 形 成 的 球 隙 内 进 行 搜 索 就 能 不 断 找 到 新极 小 点，且 不 会 遗 漏 任 何 极 小 点定 理 球 隙 内 接 多 边 形（体）相 互 不 穿 越内 接 多 边 形 由 同 一 球 隙 上 已 有 点 连 线 构 成图 多 边 形（体）相 互 不 穿 越证 明 反 证 法假 设 图中 球 隙的 内 接 三 角（多 边）形 被

38、 球 隙的 内 接 三 角（多 边）形 的 一 条 边 穿期胡 劲 松 等：球 隙 迁 移 算 法 实 现 全 局 优 化越球 隙上 过 点、的 弧 段 被 球 隙包 含点必 在 球 隙中与 球 隙 的 定 义 矛 盾，因 为 点为 球隙 构 成 点（点、不 是） ，它 不 应 在 任 何 一 个 球 隙 内部假 设 不 成 立上 述 证 明 可 以 推 广 到狀维 空 间证 毕定 理 定 义 域内 的 球 隙 数 量 有 限证 明 球 隙 的 内 接 多 边 形 的 广 义 体 积 不 为 无穷 小，且 相 互 不 穿 越，因 此 数 量 有 限证 毕定 理 球 隙 迁 移 法 能 在 有

39、限 步 数 内 发 现 函数犳的 全 局 极 小调 用 一 次 评 估 函 数 为 一 步证 明 设 当 前 由犽个 转 移 点 用犽次 贪 心 搜 索发 现 了犿个 局 部 极 小 点（犽犿，因 有 重 复） ，假 设 全局 极 小 并 不 包 含 其 中，并 设 全 局 极 小 的 极 值 域 半 径为将 这犽犿个 已 有 点 形 成 的 球 隙 按 大 小 排 序：犌，犌， ，以 当 前 最 大 球 隙犌的 球 心 为 新 转 移 点 进行 贪 心 搜 索，找 到 一 个 极 小 点（新 的 或 重 复 老 的） ，所以 至 少 有 一 个 新 点 加 入，该 最 大 球 隙 被 破 坏

40、，相 关 邻近 点 重 组 为 若 干 小 球 隙，如 此 不 断 进 行，当 前 最 大 球隙 不 断 减 小，根 据 定 理 和，必 可 以 使 用 有 限 次贪 心 搜 索 将 当 前 最 大 球 隙 减 小 到由 定 理 和，必 在 这 之 前 发 现 全 局 极 小根 据 定 理，每 次 贪 心 搜索 的 步 数 有 限，因 此 总 的 步 数 为 有 限 值证 毕定 理 采 用 启 发 策 略，算 法 仍 可 以 有 限 步发 现 全 局 极 值证 明 设 当 前 球 隙 序 列 由 大 到 小 排 列：犌，犌， ，犌犻， 设 形 成 球 隙犌的 点 是 起极 对，按 启发 策 略

41、，犌的 大 小 应 减 半 计 算，于 是 重 新 排 列 球 隙序 列：犌， ，犌犻，犌， 当犌， ，犌犻被 分 裂 减 小 之后，必 轮 到犌，所 以 即 使 按 照 重 新 排 列 的 序 列，通 过分 裂 总 可 以 使 得 序 列 的 最 大 球 隙 小 于证 毕定 理 某 次 贪 心 搜 索 中 途 退 出，算 法 仍 可以 有 限 步 发 现 全 局 极 值证 明 贪 心 搜 索 从 点犅出 发，但 中 途 因 为 某种 原 因 在 点犆退 出，未 能 达 到 极 小 点犃设 距 离犆 犃，则 可 将 极 值 域 半 径 视 为通 过 球 隙 序列 不 断 减 小，可 使 得 当

42、 前 最 大 球 隙，根 据 定 理，必 可 发 现犃因犃为 任 意 极 小 点，所 以 算 法 仍 可 以 有限 步 发 现 全 局 极 值证 毕实 际 应 用 中，计 算 机 步 长 有 限，考 虑 到 代 价，不可 能 将 精 度 每 次 都 设 为 最 小，其 次 曲 面 的 某 处 特 别平 坦，可 能 导 致 搜 索 提 前 退 出，由 上 述 定 理 保 证 了 不会 遗 漏 全 局 极 小，同 时 启 示 我 们 先 以 低 精 度 搜 索，以节 省 代 价定 理 对 于 二 阶 连 续 可 微 函 数犳，在 其 任 意极 小 点犃的 极 值 域内 必 存 在 一 个 凸 集犛

43、，犳为犛上 的 凸 函 数证 明 由 已 知 得犳（犃） ，犳（犃）半 正定 当犡犛，犳为犛上 的 凸 函 数 定 理 犳为犛上 的 凸 函 数，如 转 移 点犅犛，则犅与犃之 间 连 线 上 不 存 在 其 它 极 小 点证 明 因 为犛为 凸 集，所 以犛内 任 意 两 点 的连 线 必 在犛内因 为犃犛，犅犛，所 以犃与犅连 线 落 在犛内因 为犃为犛内 唯 一 的 极 小 点，所 以犃与犅连线 上 的 其 它 点 必 不 为 极 小 点证 毕定 理 是 启 发 策 略的 理 论 依 据注 意 到 大 多 数 情 况 下，自 然 界 的 山 越 高，山 脚 的范 围 越 大；湖 越 深，

44、湖 面 越 广对 于 函 数，初 始 值 相同，下 降 梯 度 相 同 的 情 况 下，极 小 值 越 小， “坑 口”越大，于 是 有 以 下 策 略启 发 式 策 略 大 多 数 情 况 下，极 小 点 的 值 越小，其 极 值 域 半 径 越 大由 该 策 略 和 定 理，全 局 极 小 点 及 其 附 近 极 小点 更 有 可 能 先 被 发 现 算 法 实 现第节 已 给 出 球 隙 法 的 基 本 步 骤，其 关 键 是 如何 刷 新 球 隙 序 列 以 求 得 下 一 个 转 移 点可 以 采 用 增量 法 求 得 新 的 球 隙 序 列：设 已 知 当 前犽个 点 形 成 球

45、隙 序 列，新 增 加 第犽 个 点，判 断 新 点落 入 的 那 个 多 边 形（体）内，同 时 修 改 该 多 边 形（体）及 相 应 多 边 形（体）的边 与 顶 点如 新 球 隙 符 合 启 发 式 策 略，还 需 对 新 球隙 的 大 小 进 行 修 正，于 是 得 到 新 的 球 隙 序 列此 处 法 不 是 用 于 逼 近 目 标 函 数犳的 极 小 点，反而 是 远 离 之目 前 智 能 算 法 通 常 以 收 敛 来 判 断 是 否 停 机，而球 隙 迁 移 法 可 以 一 直 迁 移，不 会 最 终 收 敛 到 某 个 点，但 当 所 有 的 极 小 点 都 被 发 现 后

46、，继 续 运 行 将 只 能 重复 已 有 的 极 小 点，因 此 我 们 给 出 以 下 停 机 法 则：连 续若 干 次 没 有 发 现 新 极 小 点 就 可 停 机在 已 找 到 的 极小 值 中 选 最 小 的 那 个如 果 要 更 高 的 精 度，以 最 小 的极 小 点 为 起 点，再 用 贪 心 法 以 更 小 的 步 距 求 精由 启 发 式 策 略，一 般 情 况 下 全 局 最 优 会 在 这之 前 被 发 现用 精 度 保 存 一 个 数，一 个狀维 的 点 要狀个 字 节，有 个 点 的 维 函 数 也 不 过 占 计 算 机 学 报 年内 存，因 此 球 隙 法 的

47、 空 间 代 价 不 太 大当 极 小 点 很 多时，上 述 转 移 点 算 法 比 较 复 杂，虽 然 求 多 边形 无 需 调 用犳，不 增 加 实 际 优 化 代 价，但 会 增 加 计 算 时 间可 以 考 虑 新 转 移 点 只 远 离 当 前 局 部极 小 点 及 重 复 次 数 较 多 的 极 小 点，得 到 以 下 简 化 的转 移 点 算 法设：第犽次 贪 心 搜 索 通 过 转 移 点犅发 现 了 局 部极 小 点犃，欲 求 下 一 个 转 移 点犆令 函 数犌（犡）犡犃犡犅犡犃 犡（）其 中表 示 取 小，犃为 前犽 次 搜 索 中 重 复 次 数最 多 的 局 部 极

48、小 点 犡为犡到 最 近 边 界 的距 离，该 项 是 为 了 防 止犡太 靠 近 边 界可 以 用 贪 心 算 法 求 该 函 数 的 极 大 值 即 得 到犆：犆 （犌（犡） ）犌（犡）可 能 有 多 个 极 大 值，根 据 启 发 式 策 略，只 需犆不 在 起极 对 的 连 线 上式（）要 取 得 极 大 值，每 一 项 都 不 能 小，也 即犡必 须 远 离犃、犃、犅和 边界显 然，该 简 化 算 法 克 服 当 前 局 部 极 小 的 能 力 与 原算 法 是 相 同 的，但 克 服 多 局 部 极 小 的 能 力 有 所 减 弱，因 此 代 价 有 所 增 加注 意 到犌（犡）不

49、 含 目 标 函 数犳，因 此 求 其 极 大 值 不 增 加 实 际 优 化 代 价，所 以犌（犡）本 质 上 不 同 于 隧 道 函 数 法、填 充 函 数 法 中 的 辅 助函 数 仿 真 实 验 结 果目 前 使 用 的 很 多 测 试 函 数 是 可 分 离 的，如 、 等，虽 然 维 数 高 但 难 度 低，而 实际 应 用 中，可 分 离 这 种 特 殊 形 式 不 多，因 此 选 了个不 可 分 离 的、变 量 间 耦 合 的 测 试 函 数，难 度 较 大为公 平 起 见，对 比 算 法 的 结 果 全 部 来 自 文 献（） 多 峰 值 函 数 狓犻 ， （狓狓 ）（ 狓

50、狓 狓 狓狓狓） （狓 狓）（ 狓 狓 狓 狓狓 狓） 将 球 隙 法 在 不 同 的 初 始 点运 行， 次 结 果 取 均 值，与 文 献的种 方 法及 其 结 果 对 比，如 表 球 隙 法 的 代 价 仅 为 的万 分 之 八，正 如 启 发 策 略所 述，全 局 极 值 在 次（不 到 停 机 代 价 的 一 半）就 可 以 发 现虽 然 该 函 数维 数 低，但 变 量 耦 合，难 度 较 高，种 成 功 率较 低表 犌 狅犾 犱 狊狋犲犻 狀 犘 狉犻犮 犲多 峰 值 函 数 平 均 优 化 结 果算 法代 价（函 数评 估 次 数）最 小 值成 功 率差 分 进 化（ ） 微

51、粒 群（ ） （ ） （ ） （ ） （ ） （ ） 球 隙 迁 移 法 （ 初 次 发 现） 图是 优 化 过 程 曲 线，记 录 每 次 贪 心 搜 索 的 当前 最 好 值，而 非 全 局 最 好 值，这 与 大 多 数 论 文 不 同因 为 球 隙 法 不 断 迁 移，在 切 换 到 新 迁 移 点 时 会 有 大幅 度 的 跳 跃 式 上 升，所 以 曲 线 是“非 减 幅 振 荡 式” ，而不 是“收 敛 式” （其 它 算 法 是 减 幅 振 荡 收 敛） ，这 正 是本 方 法 的 独 特 之 处第 一 次 贪 心 搜 索 找 到 局 部 极 小点，继 续 努 力 若 干 次

52、找 不 到 比更 好 之 后，转 移 到新 点，该 点 的 值 太 大，超 出 图 的 显 示 范 围（若 加 大犢轴 刻 度 则 看 不 到 曲 线 底 部 细 节）第 二 次 搜 索 在狓 处 找 到 了 全 局 极 值极 小 点之 后 的 转 移 点 值较 好，上 升 不 大点与 点、点与 点同 值，意 味着 两 个 极 小 点 被 重 复 发 现，此 时 已 经 发 现 了 全 部 极小 点，在 点就 可 以 停 机图 球 隙 法 的 优 化 过 程 图（）六 驼 峰 函 数 狓 狓狓狓狓狓 狓，其 中 狓犻 将 球 隙 法 与 文 献的差 分 进 化（ ） 、微 粒 群（ ）对 比，

53、如 表 本 文 算法 代 价 仅 为 微 粒 群 算 法、差 分 进 化 的 表 六 驼 峰 多 峰 值 函 数 平 均 优 化 结 果算 法代 价（函 数 评 估 次 数）最 小 值 成 功 率差 分 进 化（ ） 微 粒 群（ ） 球 隙 迁 移 法 （ 初 次） （） 函 数 （狓狓）（ 狓） （狓狓）（ 狓） （ （狓 ）（狓期胡 劲 松 等：球 隙 迁 移 算 法 实 现 全 局 优 化） （狓 ） （狓 ） ，其 中 狓犻 ，全局 极 小 值 将 球 隙 法 与 文 献 的 模 糊 文 化 进 化程 序（ ） 、文 献 的 多 编 码 （ ）对比，如 表 表 中 本 文 算 法 的

54、 代 价 仅 为 算 法的 表 中 的 的 成 功 率 为 表 犆 狅犾狏犻犾犾犲函 数 优 化 结 果算 法代 价（函 数 评 估 次 数）最 小 值 成 功 率 球 隙 迁 移 法 （ 初 次） 结 论 与 展 望球 隙 迁 移 法 基 于 新 的 优 化 原 理，不 但 能 避 免 当前 局 部 极 小，还 能 有 效 地 避 免 重 复 历 史 上 的 多 个 局部 极 小，它 实 现 了 勘 探 与 开 采 的 分 离，避 免 了 相 互 干扰，对 耦 合 对 象 的 优 化 效 果 好本 文 证 明 了 球 隙 法 能在 有 限 计 算 次 数 内 确 定 地 找 到 连 续 函

55、数 的 全 局 最优当 然，根 据 定 理，对 于 全 部 的 优化 问 题 集，任 意 两 种 算 法 的 平 均 性 能 是 相 同 的对 于可 分 离 函 数，球 隙 法 不 如 高 效，其 次 球 隙 法 目 前还 仅 限 于 连 续 优 化相 比 当 前 成 熟 的 智 能 算 法，还 有 很 多 工 作 要 做，不 少 地 方 还 需 完 善，目 前 我 们 的 主 要 工 作 内 容 还 是无 约 束 优 化，下 一 步 将 其 扩 展 到 约 束 优文 献 给出 了种 罚 函 数 方 法，这 些 方 法 将 约 束 问 题 转 化 为无 约 束 问 题，球 隙 法 可 以 直

56、接 采 用对 于 非 凸 定 义域，可 以 将 其 分 割 成 若 干 凸 区 域，分 别 求 每 个 子 区 域的 最 小 值，再 求 总 的 最 小 值致谢衷 心 感 谢 华 南 理 工 大 学 李 桂 清 教 授 及 匿 名审 稿 专 家，他 们 对 本 文 提 出 了 宝 贵 建 议！参考文献 ， ， ， ， ， ： ， ， ， ， ： ， （ ： ） ， ， （） ： （ ）（黄 文 奇，何 琨求 解 长 方 体 问 题 的 纯 粹 拟 人 算 法中 国 科 学（辑：信 息 科 学） ， ， （） ： ） ， ， ，（） ： （ ）（刘 三 阳，张 晓 伟混 合 差 分 变 异 策

57、略智 能 系 统 学 报， ，（） ： ） ， ， ，（） ： ， ， ， ， ： ， ， （） ： ， ， ： ， ， （） ： （ ）（徐 宗 本，陈 志 平，章 祥 荪遗 传 算 法 基 础 理 论 研 究 的 新 近 发展数 学 进 展， ， （） ： ） ， ， ， ， （） ： （ ）（梁 艳 春，王 在 申，周 春 光选 择 和 变 异 操 作 下 遗 传 算 法 的 收敛 性 研 究计 算 机 研 究 与 发 展， ， （） ： ） ， ， ， ， （ ） ： （ ）（林 丹，李 敏 强，寇 纪 凇基 于 实 数 编 码 的 遗 传 算 法 的 收 敛 性研 究计 算 机 研

58、究 与 发 展， ， （ ） ： ） ， ， （） ： ， ， ，（） ： ， ， ， ： ， ， （） ： ， ， （） ： （ ）（朱 庆 保蚁 群 优 化 算 法 的 收 敛 性 分 析控 制 与 决 策， ， （） ： ） ， ， ， ， ， ， （） ： （ ）计 算 机 学 报 年（莫 愿 斌，刘 贺 同，陈 德 钊粒 子 群 优 化 算 法 的 发 展 趋 势计算 机 与 应 用 化 学， ， （） ： ） ： ， （ ）（米 凯 利 维 茨周 家 驹 等 译演 化 程 序 遗 传 算 法 和 数据 编 码 的 结 合北 京：科 学 出 版 社， ） ： ， （ ）（粟 塔 山 等最 优 化 计 算 原 理 与 算 法 程 序 设 计长 沙：国 防 科技 大 学 出 版 社， ） ， ： ， （ ）（ ， 等邓 俊 辉 译计 算 几 何算 法与 应 用第版，北 京：清 华 大 学 出 版 社， ）犎 犝 犑犻狀 犵 犛 狅 狀 犵， ， ， 犣 犎 犈 犖 犌 犙 犻 犔 狌 狀， ， ， 犅 犪 犮 犽 犵 狉 狅 狌 狀 犱 ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， 期胡 劲 松 等：球 隙 迁 移 算 法 实 现 全 局 优 化