演化计算问答

细履平沙

问： 演 化 计 算 对 很 多 人 来 说 是 个 完 全 陌 生 的 名 词， 但 是 这 一 领 域 的 研 究 近 年 来 在 国 外 的 影 响 很 大， 颇 具 发 展 前 途。 首 先， 我 们 想 请 您 解 释 一 下 演 化 计 算 的 概 念 以 及 它 的 发 展 由 来。
---- 答： 演 化 在 词 典 中 的 定 义 即 是 演 变， 多 指 自 然 界 的 变 化 过 程。 大 自 然 是 人 类 获 得 灵 感 的 源 泉， 几 百 年 来， 将 生 物 界 提 供 的 答 案 应 用 于 实 际 问 题 求 解 已 被 证 明 是 一 个 成 功 的 办 法， 并 且 已 形 成 仿 生 学 这 个 专 门 的 科 学 分 支。 我 们 知 道， 自 然 界 所 提 供 的 答 案 是 经 过 漫 长 的 自 适 应 过 程（ 即 演 化 过 程） 得 到 的 结 果。 除 了 演 化 过 程 的 最 终 结 果， 我 们 也 可 以 利 用 这 一 过 程 本 身 去 解 决 一 些 较 为 复 杂 的 问 题。 也 就 是 说， 我 们 不 必 非 常 明 确 地 描 述 问 题 的 全 部 特 征， 只 需 要 根 据 自 然 法 则 来 产 生 新 的 更 好 解。 演 化 计 算 正 是 基 于 这 种 思 想 发 展 起 来 的 一 种 通 用 的 问 题 求 解 方 法。 它 采 用 简 单 的 编 码 技 术 来 表 示 各 种 复 杂 的 结 构， 并 通 过 对 一 组 编 码 表 示 进 行 简 单 的 遗 传 操 作 和 优 胜 劣 汰 的 自 然 选 择 来 指 导 学 习 和 确 定 搜 索 的 方 向。
---- 演 化 计 算 发 展 之 初 有 很 多 不 同 的 学 派， 一 是 演 化 规 划(Evolutionary Programming) 学 派， 美 国 人L.J.Fogel 1966 年 在 人 工 智 能 的 研 究 中 发 现， 智 能 行 为 即 是 具 有 能 预 测 其 所 处 环 境 的 状 态 并 按 照 给 定 的 目 标 做 出 适 当 响 应 的 能 力。 在 研 究 中， 他 将 模 拟 环 境 描 述 成 由 有 限 字 符 集 中 的 符 号 组 成 的 序 列， 于 是 问 题 就 转 化 为 如 何 根 据 当 前 观 察 到 的 符 号 序 列 做 出 响 应 以 获 得 最 大 的 收 益， 这 里 收 益 的 计 算 是 按 照 环 境 中 将 要 出 现 的 下 一 个 符 号 及 预 先 定 义 好 的 效 益 目 标 来 确 定 的。1963 年 德 国 柏 林 大 学 的I.Rechenberg 和H.P.Schwefel 等 人 在 进 行 风 洞 实 验 时， 由 于 在 设 计 中 描 述 物 体 形 状 的 参 数 难 以 用 传 统 的 方 法 进 行 优 化， 促 使 他 们 利 用 生 物 变 异 的 思 想 来 随 机 地 改 变 参 数 取 得 了 较 好 的 效 果。 随 后， 他 们 对 这 种 方 法 进 行 了 深 入 的 研 究， 形 成 了 演 化 计 算 的 另 一 个 分 支 — — 演 化 策 略(Evolutionary Strategy) 学 派。 演 化 算 法 的 第 三 个 分 支 是 由 美 国 密 西 根 大 学 的John Holland 提 出 的 遗 传 算 法(Genetic Algorithm) 学 派， 它 的 操 作 对 象 是 称 为 种 群 的 一 组 二 进 制 串（ 即 染 色 体 和 个 体）， 这 里 的 每 个 染 色 体 都 对 应 于 问 题 的 一 个 解。 从 初 始 种 群 出 发， 采 用 基 于 适 应 值 比 例 的 选 择 策 略 在 当 前 种 群 中 选 择 个 体， 使 用 杂 交 和 变 异 来 产 生 下 一 代 种 群， 如 此 一 代 代 演 化 下 去， 直 到 满 足 期 望 的 终 止 条 件。90 年 代 初， 这 些 分 支 相 互 融 合， 就 形 成 了 这 一 门 新 的 学 科 — — 演 化 计 算。
---- 问： 演 化 计 算 的 实 质 是 借 助 生 物 演 化 的 思 想 和 原 理 来 解 决 实 际 问 题。 那 么 演 化 算 法 与 传 统 的 算 法 相 比 有 何 不 同 ？
---- 答： 演 化 算 法 与 传 统 的 算 法 有 很 多 不 同 之 处， 但 最 主 要 的 差 别 在 于 演 化 计 算 具 有 智 能 性 和 本 质 并 行 性 的 特 征。
---- 演 化 计 算 的 智 能 性 包 括 自 组 织、 自 适 应 和 自 学 习 等。 应 用 演 化 计 算 求 解 问 题 时， 在 确 定 了 编 码 方 案、 适 应 值 函 数 及 遗 传 算 子 之 后， 算 法 将 利 用 演 化 过 程 中 获 得 的 信 息 自 行 组 织 搜 索。 由 于 基 于 自 然 的 选 择 策 略 为 适 者 生 存、 不 适 者 淘 汰， 故 而 适 应 值 大 的 个 体 具 有 较 高 的 生 存 概 率。 通 常 适 应 值 大 的 个 体 具 有 更 适 应 环 境 的 基 因 结 构， 再 通 过 杂 交 和 基 因 突 变 等 遗 传 操 作 就 可 能 产 生 更 适 应 环 境 的 后 代。 演 化 算 法 的 这 种 自 组 织、 自 适 应 特 征 同 时 也 赋 予 了 它 具 有 能 根 据 环 境 的 变 化 自 动 发 现 环 境 的 特 性 和 规 律 的 能 力。 此 外， 自 然 选 择 消 除 了 算 法 设 计 过 程 中 的 一 个 最 大 障 碍， 即 需 要 事 先 描 述 问 题 的 全 部 特 点， 并 说 明 针 对 问 题 的 不 同 特 点 算 法 应 采 取 的 措 施。 于 是， 利 用 演 化 计 算 的 方 法 我 们 可 以 解 决 那 些 结 构 尚 无 人 理 解 的 复 杂 问 题。
---- 演 化 计 算 的 本 质 并 行 性 表 现 在 两 个 方 面： 一 是 演 化 计 算 是 内 在 并 行 的， 即 演 化 算 法 本 身 非 常 适 合 大 规 模 并 行。 最 简 单 的 并 行 方 式 是 让 几 百 甚 至 数 千 台 计 算 机 各 自 进 行 独 立 种 群 的 演 化 计 算， 运 行 过 程 中 甚 至 不 进 行 任 何 通 信， 直 到 运 算 结 束 时 才 通 信 比 较， 选 取 最 佳 个 体， 这 种 并 行 处 理 方 式 对 并 行 系 统 结 构 也 没 有 什 么 限 制 和 要 求。 可 以 说， 演 化 计 算 适 合 在 目 前 所 有 的 并 行 机 或 分 布 式 系 统 上 进 行 并 行 处 理， 而 且 对 其 并 行 效 率 没 有 太 大 的 影 响。 二 是 演 化 计 算 的 内 含 并 行 性， 由 于 演 化 计 算 采 用 种 群 的 方 式 组 织 搜 索， 从 而 可 以 同 时 搜 索 解 空 间 的 多 个 区 域， 并 相 互 交 流 信 息。 虽 然 每 次 只 执 行 与 种 群 规 模N 成 比 例 的 计 算， 而 实 质 上 已 进 行 了 大 约O（N3） 次 有 效 搜 索， 使 演 化 计 算 能 以 较 少 的 计 算 获 得 较 大 的 收 益。
---- 演 化 计 算 在 六 七 十 年 代 并 未 受 到 普 遍 的 重 视， 其 主 要 原 因 一 是 因 为 当 时 这 些 方 法 本 身 还 不 够 成 熟； 二 是 由 于 这 些 方 法 需 要 较 大 的 计 算 量， 而 当 时 的 计 算 机 还 不 够 普 及， 而 且 速 度 也 跟 不 上 要 求， 这 样 便 限 制 了 它 们 的 应 用； 三 是 当 时 基 于 符 号 处 理 的 人 工 智 能 方 法 正 处 于 其 顶 峰 状 态， 使 得 人 们 难 以 认 识 到 其 他 方 法 的 有 效 性 和 局 限 性， 并 且 由 于 计 算 机 速 度 的 提 高 以 及 并 行 计 算 机 的 普 及， 使 得 演 化 计 算 对 机 器 速 度 的 要 求 不 再 是 制 约 其 发 展 的 因 素。 此 外 由 于 演 化 计 算 自 身 的 不 断 发 展 及 其 在 机 器 学 习、 过 程 控 制、 经 济 预 测、 工 程 优 化 等 领 域 取 得 的 成 功， 演 化 计 算 已 经 表 现 出 了 良 好 的 应 用 前 景。
---- 问： 演 化 计 算 发 展 至 今 已 有30 年 的 历 程， 也 取 得 了 一 些 阶 段 性 的 成 就。 那 么， 在 您 看 来， 演 化 计 算 未 来 的 发 展 趋 势 是 什 么 ？
---- 答： 我 认 为， 演 化 硬 件 将 是 未 来 演 化 计 算 发 展 的 一 个 重 要 趋 势， 是 一 个 全 新 的 发 展 方 向。 所 谓 演 化 硬 件 即 指 能 像 生 物 一 样 根 据 环 境 的 变 化 改 变 自 身 结 构 以 适 应 其 生 存 环 境 的 硬 件， 它 用 可 编 程 集 成 电 路 中 的 结 构 位 串 当 作 演 化 算 法 中 的 染 色 体， 通 过 演 化 计 算 来 完 成 硬 件 功 能 的 设 计。 演 化 硬 件 是 演 化 算 法 和 可 编 程 逻 辑 器 件 的 结 合， 演 化 计 算 为 演 化 硬 件 提 供 了 理 论 与 方 法 学 基 础， 而 可 编 程 集 成 电 路 特 别 是 新 一 代 现 场 可 编 程 门 阵 列（FPGA） 为 演 化 硬 件 提 供 了 物 质 基 础。
---- 演 化 硬 件 是 演 化 计 算 一 个 颇 具 前 途 的 发 展 方 向。 它 的 出 现 不 过 短 短 几 年 的 时 间， 却 在 电 路 设 计、 控 制 和 机 器 人、 模 式 识 别、 容 错 系 统 和 超 大 规 模 集 成 电 路 的 设 计 等 领 域 都 得 到 了 一 定 的 应 用。 例 如， 在 机 器 人 的 结 构 中 应 用 了 演 化 硬 件 后， 外 部 环 境 一 旦 发 生 变 化， 机 器 人 可 以 自 行 改 变 行 动 的 策 略， 行 动 更 具 灵 活 性。 尽 管 演 化 硬 件 现 在 实 现 的 功 能 还 比 较 简 单， 但 它 为 硬 件 自 动 化 设 计 和 联 机 自 适 应 性 的 实 现 开 辟 了 一 条 崭 新 的 途 径。 随 着 硬 件 复 杂 性 的 不 断 增 加， 整 个 设 计 完 全 由 人 来 承 担 已 不 现 实， 而 利 用 演 化 硬 件， 一 方 面 可 以 大 大 减 轻 设 计 人 员 的 负 担， 另 一 方 面 满 足 了 硬 件 对 环 境 的 适 应 性 要 求。 传 统 硬 件 设 计 方 法 设 计 大 规 模 电 路 系 统 时， 事 先 要 对 问 题 有 全 面、 精 确 的 了 解， 首 先 对 电 路 系 统 进 行 分 解， 然 后 分 层 设 计。 随 着 问 题 的 复 杂 性 的 增 加， 要 想 完 全 把 握 整 个 电 路 系 统 是 相 当 困 难 的。 对 于 复 杂 的 电 路 系 统 即 使 设 计 出 来 了， 想 要 对 它 进 行 分 析 也 是 非 常 困 难 的。 用 演 化 硬 件 则 不 需 要 对 所 设 计 的 电 路 有 很 深 的 了 解， 只 需 知 道 其 外 部 特 性 即 可。 有 人 甚 至 预 言， 一 旦 演 化 硬 件 得 到 充 分 的 实 现， 它 将 成 为 一 个 具 有 广 泛 应 用 前 景 的 新 兴 产 业。
---- 问： 作 为 国 内 演 化 计 算 研 究 方 面 的 专 家， 您 能 否 为 我 们 介 绍 一 下 演 化 计 算 在 国 内 的 发 展 现 状 ？
---- 答： 演 化 计 算 在 国 内 发 展 得 非 常 之 快， 对 它 的 应 用 呼 声 也 非 常 之 高， 例 如 农 业 部、 机 械 部 等 部 门 都 在 应 用 这 个 方 法 来 解 决 他 们 在 领 域 中 遇 到 的 实 际 问 题。 国 内 在 演 化 计 算 方 面 的 研 究 主 要 集 中 于 三 个 方 面， 一 是 搞 演 化 算 法， 即 演 化 计 算 的 理 论 研 究； 其 二 是 搞 演 化 软 件， 主 要 是 做 自 动 程 序 设 计， 由 计 算 机 自 己 来 编 制 程 序； 第 三 是 做 演 化 硬 件， 这 是 一 个 很 有 前 途 的 领 域。 我 们 现 在 正 力 图 设 计 这 样 一 个 硬 件， 使 它 能 像 生 物 一 样 根 据 环 境 的 变 化 改 变 自 身 的 结 构， 其 中 主 要 是 利 用FPGA 芯 片， 用 户 可 以 用 程 序 来 改 变 芯 片 的 结 构， 用 演 化 算 法 来 控 制 它 演 化， 使 它 变 成 各 式 各 样 的 逻 辑 电 路。
---- 总 的 来 说， 我 们 在 这 一 领 域 的 某 些 方 面 已 步 入 国 际 领 先 地 位， 如 用 微 分 方 程 来 描 述 知 识 进 行 自 动 发 现 等 等， 迄 今 为 止 在 国 际 上 还 没 有 人 能 够 使 用 常 微 分 方 程 这 么 复 杂 的 模 型 来 自 动 描 述 知 识， 我 们 却 可 以 用 它 来 描 述 与 时 间 演 化 有 关 的 复 杂 结 构。 就 整 体 发 展 水 平 而 言， 我 们 在 演 化 计 算 方 面 的 发 展 可 以 说 是 与 国 外 站 在 同 一 条 水 平 线 上， 今 后 的 发 展 则 更 加 不 可 限 量。