201515

Transcription

1 ,() Computer Engneerng and Applcatons 计 算 机 工 程 与 应 用 多 智 能 体 布 谷 鸟 算 法 的 网 络 计 划 资 源 均 衡 优 化 宋 玉 坚, 叶 春 明,, 黄 佐 钘 SONG Yujan, YE Chunmng, HUANG Zuoxng,. 上 海 理 工 大 学 管 理 学 院, 上 海. 上 海 期 货 交 易 所, 上 海.Bussness School, Unversty of Shangha for Scence and Technology, Shangha, Chna.Shangha Futures Exchange, Shangha, Chna SONG Yujan, YE Chunmng, HUANG Zuoxng. Mult-agent cuckoo search algorthm for resource levelng problem of network plannng. Computer Engneerng and Applcatons,, ():-. Abstract: Resource levelng problem of network plannng s a combnatoral optmzaton problem. For the purpose of solvng t effcently and effectvely, ths paper proposes a mult-agent cuckoo search algorthm. The mult-agent system s embedded to basc cuckoo search algorthm to counteract the lack of nformaton exchange. The competton & cooperaton operaton enhances agents communcaton and boosts convergence speed. Mutaton operaton can search wdely and mantan the dversty of the populaton. Self-study operaton can explot hgh qualty solutons. Meanwhle, the Levy flght evoluton mechansm can avod trappng to local optma. The case study also ndcates that the modfed algorthm can solve the resource levelng problems more effcently and effectvely when compared wth other algorthms. Key words: resource levelng problem; mult-agent cuckoo search algorthm; competton & cooperaton operaton; mutaton operaton; self-study operaton; Levy flght evoluton mechansm 摘 要 : 网 络 计 划 资 源 均 衡 属 于 组 合 优 化 问 题, 为 了 能 快 速 有 效 地 求 解 此 类 问 题, 提 出 了 一 种 多 智 能 体 布 谷 鸟 算 法 针 对 标 准 布 谷 鸟 算 法 缺 乏 信 息 共 享 的 缺 陷, 将 多 智 能 体 系 统 引 入 布 谷 鸟 算 法 中 多 智 能 体 的 邻 域 竞 争 合 作 算 子 实 现 智 能 体 间 信 息 的 交 流, 加 快 算 法 收 敛 速 度 ; 变 异 算 子 扩 大 搜 索 范 围 增 加 种 群 多 样 性 ; 自 学 习 算 子 提 高 局 部 寻 优 的 能 力 ; 布 谷 鸟 算 法 的 Levy 飞 行 进 化 机 制 能 有 效 地 跳 出 局 部 最 优 实 现 全 局 收 敛 实 例 仿 真 结 果 证 实 了, 与 其 他 算 法 相 比 多 智 能 体 布 谷 鸟 算 法 能 更 有 效 地 求 解 网 络 计 划 资 源 均 衡 优 化 问 题 关 键 词 : 资 源 均 衡 ; 多 智 能 体 布 谷 鸟 算 法 ; 竞 争 合 作 算 子 ; 变 异 算 子 ; 自 学 习 算 子 ;Levy 进 化 机 制 文 献 标 志 码 :A 中 图 分 类 号 :TP do:./j.ssn 引 言 在 项 目 计 划 编 制 阶 段, 初 始 网 络 计 划 主 要 表 达 了 各 项 工 作 间 的 时 序 关 系, 而 没 有 根 据 特 定 的 目 的 形 成 最 优 的 调 度 计 划 资 源 均 衡 优 化 作 为 网 络 计 划 优 化 的 一 种, 是 指 在 项 目 工 期 固 定 的 前 提 下, 合 理 调 整 网 络 计 划 中 某 些 非 关 键 工 作 的 开 始 时 间, 使 资 源 需 求 分 布 趋 于 均 衡 资 源 的 均 衡 化 能 够 削 减 工 程 成 本 提 高 生 产 率 以 及 降 低 项 目 管 理 难 度, 最 大 限 度 地 保 障 项 目 目 标 的 实 现 因 此, 网 络 计 划 的 资 源 均 衡 优 化 是 项 目 开 工 前 的 一 项 重 要 工 作, 具 有 非 常 重 要 的 现 实 意 义 资 源 均 衡 优 化 属 于 一 个 高 维 度 非 线 性 多 约 束 的 离 散 型 最 优 化 问 题, 国 内 外 学 者 提 出 了 多 种 方 法 解 决 此 [-] 问 题, 大 致 可 归 为 三 类 : 精 确 算 法 基 于 优 先 规 则 的 启 [-] [-] 发 式 算 法 智 能 算 法 精 确 算 法 求 解 结 果 精 确 但 是 基 金 项 目 : 国 家 自 然 科 学 基 金 (No.); 上 海 市 教 育 委 员 会 科 研 创 新 项 目 (No.ZS); 上 海 市 一 流 学 科 建 设 项 目 (No.SYLXK) 作 者 简 介 : 宋 玉 坚 (8 ), 男, 硕 士 研 究 生, 主 要 研 究 方 向 为 项 目 管 理 智 能 优 化 ; 叶 春 明 ( ), 男, 博 士, 教 授, 主 要 研 究 方 向 为 工 业 工 程 企 业 战 略 供 应 链 管 理 以 及 企 业 信 息 化 ; 黄 佐 钘 ( ), 男, 博 士, 副 教 授, 主 要 研 究 方 向 为 技 术 创 新 金 融 工 程 E-mal:[email protected] 收 稿 日 期 :-8- 修 回 日 期 :-- 文 章 编 号 :-8()-- CNKI 网 络 优 先 出 版 :--,

2 宋 玉 坚, 叶 春 明, 黄 佐 钘 : 多 智 能 体 布 谷 鸟 算 法 的 网 络 计 划 资 源 均 衡 优 化,() 非 常 耗 时 难 以 适 用 于 大 型 而 又 复 杂 的 问 题 ; 基 于 优 化 规 则 的 启 发 式 算 法 计 算 速 度 快 但 优 化 结 果 的 质 量 取 决 于 规 则 的 优 劣 且 算 法 的 通 用 性 较 差 智 能 算 法 是 模 拟 自 然 界 物 理 现 象 或 生 物 进 化 过 程 的 一 类 元 启 发 式 算 法, 具 有 全 局 并 行 高 效 通 用 性 强 的 特 点, 是 解 决 复 杂 工 程 优 化 问 题 的 常 用 算 法 布 谷 鸟 算 法 是 Yang Xn-she 和 Deb Suash 于 [] 年 提 出 的 一 种 新 型 智 能 算 法, 它 是 模 拟 生 物 界 中 布 谷 鸟 借 窝 产 卵 的 行 为 以 及 果 蝇 蜜 蜂 等 昆 虫 的 Levy 飞 行 轨 迹, 具 有 原 理 简 单 参 数 设 置 少 全 局 收 敛 性 能 强 的 特 点 Lm 等 则 采 用 布 谷 鸟 算 法 寻 找 印 制 电 路 的 最 佳 钻 [8] 孔 路 径, 提 高 印 制 电 路 板 的 生 产 效 率 Azz Ouaarab 等 则 定 义 -opt 变 换 为 基 本 的 短 距 离 搜 索 单 元, 双 桥 变 换 (double-brdge move) 为 长 距 离 搜 索, 利 用 多 次 的 -opt 变 换 和 偶 然 的 双 桥 变 换 模 拟 Levy 飞 行, 提 出 了 求 解 TSP [] 问 题 的 离 散 布 谷 鸟 算 法 刘 长 平 等 利 用 布 谷 鸟 算 法 求 解 置 换 流 水 车 间 调 度 问 题, 取 得 了 比 萤 火 虫 算 法 和 粒 子 [] 群 算 法 更 好 的 优 化 结 果 多 智 能 体 系 统 是 由 多 个 具 备 环 境 感 知 竞 争 合 作 自 学 习 能 力 的 智 能 体 组 成, 该 系 统 根 据 指 派 的 问 题 协 调 各 智 能 体 间 的 行 为, 在 求 解 复 杂 优 化 问 题 时 具 有 非 常 强 的 鲁 棒 性 可 靠 性 以 及 高 效 性 鉴 于 此, 多 智 能 系 统 引 入 到 最 优 化 领 域 与 智 能 算 法 相 融 合 是 当 前 研 究 的 热 点 潘 晓 英 等 将 多 智 能 系 统 与 遗 传 算 法 相 结 合 求 解 网 [] 络 计 划 资 源 受 限 调 度 问 题, 吴 亚 丽 等 则 将 文 化 算 法 与 多 智 能 体 系 统 相 结 合 构 造 了 多 智 能 体 文 化 演 化 算 法 求 [] 解 资 源 受 限 项 目 调 度 问 题, 赵 波 等 提 出 了 多 智 能 体 粒 子 群 算 法 来 求 解 电 力 系 统 无 功 优 化 问 题, 取 得 了 很 好 的 [] 效 果 本 文 将 结 合 布 谷 鸟 算 法 与 多 智 能 体 技 术 提 出 一 种 多 智 能 体 布 谷 鸟 算 法 该 算 法 为 多 智 能 体 系 统 构 造 一 个 网 格 体 系, 布 谷 鸟 算 法 中 的 每 只 布 谷 鸟 被 视 为 一 个 智 能 体 固 定 在 网 格 上, 每 个 智 能 体 通 过 竞 争 合 作 变 异 算 子 自 学 习 行 为 以 及 布 谷 鸟 算 法 的 进 化 机 制 搜 寻 优 化 问 题 的 解 本 文 最 后 通 过 仿 真 测 试 验 证 多 智 能 体 布 谷 鸟 算 法 用 于 解 决 资 源 均 衡 优 化 问 题 的 可 行 性 与 有 效 性 网 络 计 划 资 源 均 衡 数 学 模 型 构 建 经 典 的 资 源 均 衡 优 化 问 题 基 于 以 下 三 项 假 设 : () 网 络 计 划 的 工 作 任 务 数 J 及 其 资 源 消 耗 量 确 定 ; () 各 项 工 作 任 务 的 时 序 关 系 明 确 ; () 各 项 工 作 连 续 执 行 不 间 断 资 源 均 衡 优 化 问 题 描 述 如 下 : 某 工 程 有 M 项 工 作 任 务 集 合 V ={ M }, 工 作 任 务 j( j Î V ) 开 工 时 间 设 为 S j ;d j 表 示 工 作 任 务 j 的 持 续 时 间 ; 工 程 项 目 的 计 划 工 期 为 T ;P j 为 工 作 j 的 紧 前 工 作 集 ;A t 为 (t - t) 这 一 个 时 段 内 正 在 执 行 的 任 务 集 合 ;R j 表 示 工 作 j 资 源 消 耗 量 ;R(t) 表 示 (t - t) 时 段 内 资 源 消 耗 总 量 ; - R 表 示 资 源 在 工 期 内 的 平 均 消 耗 量 评 价 资 源 均 衡 状 态 的 指 标 主 要 有 : 方 差 最 大 绝 对 离 差 极 差 以 及 不 均 衡 系 数 本 文 采 用 常 用 的 方 差 作 为 评 价 指 标 确 定 如 下 目 标 函 数 : T Mn f δ = T å (R(t) - - R) () t = T 其 中 : - R = T å t = R(t),R(t) = å j Î A t R j 由 资 源 均 衡 优 化 问 题 可 知 该 问 题 的 约 束 条 件 包 括 时 序 关 系 约 束 以 及 总 工 期 限 制 时 序 关 系 约 束 要 求 各 项 工 作 任 务 在 其 所 有 紧 前 工 作 任 务 结 束 后 才 能 开 始 执 行, 总 工 期 的 限 制 则 要 求 各 项 工 作 不 能 迟 于 其 最 晚 开 始 时 间 开 工, 用 数 学 公 式 可 将 这 两 项 约 束 条 件 表 达 为 : max{s + d } s j LS j j Î V Î p j () 式 () () 构 成 了 资 源 优 化 的 数 学 模 型 多 智 能 体 布 谷 鸟 算 法. 标 准 布 谷 鸟 算 法 布 谷 鸟 算 法 将 可 行 域 视 为 可 供 产 卵 的 鸟 窝, 全 局 最 优 解 当 作 最 佳 宿 主, 整 个 迭 代 优 化 过 程 模 拟 布 谷 鸟 寻 找 最 理 想 鸟 窝 的 过 程, 建 立 问 题 解 集 与 布 谷 鸟 的 对 应 关 系 为 了 更 简 便 有 效 地 模 拟 自 然 界 中 布 谷 鸟 的 行 为, 同 时 又 能 够 适 用 于 求 解 优 化 问 题, 布 谷 鸟 算 法 设 定 了 以 下 三 种 理 想 状 态 : () 布 谷 鸟 每 代 只 产 一 个 卵, 并 随 机 选 择 鸟 窝 孵 化 ; () 贪 婪 选 择 策 略, 在 找 到 更 好 的 鸟 窝 前 布 谷 鸟 总 是 保 留 目 前 最 好 的 鸟 窝 作 为 宿 主 ; () 每 一 代 可 利 用 的 鸟 窝 数 量 固 定 不 变, 宿 主 鸟 发 现 寄 生 卵 的 概 率 为 Pa 在 此 基 础 上, 布 谷 鸟 试 探 路 径 如 下 所 示 : Y t = X t + αål(λ) () 其 中,X (t) 表 示 第 t 代 第 个 鸟 窝 的 位 置 ;Y (t) 表 示 在 X (t) 基 础 上 的 第 t 代 第 个 试 探 鸟 窝 位 置 ;α 为 控 制 步 长, 可 根 据 求 解 问 题 设 定 ;Å 为 点 对 点 乘 法 ;L(λ) 为 随 机 搜 索 路 径, 其 行 走 步 长 服 从 Levy 分 布 Levy 分 布 具 有 重 尾 的 特 征, 在 Levy 飞 行 中, 短 距 离 步 长 与 长 距 离 步 长 相 间, 在 未 知 或 大 空 间 范 围 内 比 布 朗 运 动 更 加 高 效 [] 布 谷 鸟 算 法 采 用 Levy 飞 行 原 理 更 新 候 选 种 群, 能 扩 大 搜 寻 范 围, 增 加 种 群 的 多 样 性, 有 效 避 免 早 熟 的 现 象 X (t) 布 谷 鸟 采 用 贪 婪 的 选 择 策 略, 试 探 鸟 窝 Y (t) 进 行 一 对 一 的 竞 争, 只 有 适 应 度 高 的 个 体 才 能 保 留 下 来, 其 选 择 规 则 可 表 述 为 : X t + = ì ï íï î Y t t f (Y ) > f (X t ) 与 X t t f (Y ) f (X t ) () 经 过 上 述 选 择 操 作 后, 某 些 较 差 的 个 体 若 被 发 现 则

3 8,() Computer Engneerng and Applcatons 计 算 机 工 程 与 应 用 随 机 迁 移 其 位 置, 以 期 寻 找 到 适 应 度 更 好 的 鸟 窝, 提 高 种 群 的 质 量. 多 智 能 体 系 统 由. 节 描 述 的 标 准 布 谷 鸟 算 法 更 新 与 淘 汰 机 制 可 知, 布 谷 鸟 种 群 间 不 分 享 各 自 知 识 与 经 验, 而 每 个 个 体 接 受 处 理 信 息 的 能 力 是 有 限 的, 缺 乏 有 效 的 信 息 共 享 机 制, 没 有 充 分 利 用 群 体 协 作 机 制 为 此, 本 文 构 建 了 多 智 能 体 系 统 来 改 进 标 准 布 谷 鸟 算 法 多 智 能 体 系 统 是 多 个 具 备 自 治 性 局 部 感 知 能 力 竞 争 合 作 及 自 学 习 能 力 的 智 能 体 为 了 达 到 特 定 的 目 的 而 相 互 作 用 或 协 调 所 形 成 的 计 算 系 统 将 智 能 体 运 用 到 解 决 最 优 化 问 题 通 常 需 要 定 义 一 下 四 个 方 面 的 内 容 [] 定 义 ( 单 个 智 能 体 的 含 义 与 目 的 ) 在 多 智 能 体 布 谷 鸟 算 法 中, 每 一 个 智 能 体 α 等 同 于 一 只 布 谷 鸟, 其 搜 寻 到 的 鸟 窝 位 置 对 应 优 化 问 题 的 一 个 可 行 解 在 求 解 资 源 优 化 问 题 时, 每 个 智 能 体 的 能 量 可 设 定 成 对 应 目 标 函 数 值 的 相 反 数, 从 而 单 个 智 能 体 的 目 标 就 是 要 最 大 化 自 身 能 量, 也 就 是 要 最 小 化 资 源 方 差 定 义 ( 多 智 能 体 系 统 的 结 构 ) 智 能 体 之 间 不 同 的 连 接 方 式 形 成 不 同 的 系 统 结 构 本 文 采 用 能 够 较 好 地 均 衡 智 能 体 多 样 化 和 集 中 化 的 冯 诺 依 曼 结 构 如 图 所 示 : 图 中 的 每 一 个 圆 圈 代 表 一 个 智 能 体, 这 M N 个 智 能 体 各 自 始 终 固 定 在 一 个 格 点 上, 多 智 能 体 系 统 在 物 理 上 呈 现 一 个 M 行 N 列 的 网 格 定 义 ( 单 个 智 能 体 的 邻 域 ) 单 个 智 能 体 的 邻 域 是 指 其 进 行 信 息 交 流 相 互 协 作 的 智 能 体 的 集 合, 它 的 定 义 影 响 着 整 个 多 智 能 体 系 统 的 运 行 效 率 以 及 结 果 的 质 量 记 第 行 第 j 列 的 智 能 体 为 L j ( = N; j = M ), 则 智 能 体 L j 的 邻 域 为 LneghborS j ={L j L j L j L j }( = N; j = M ), 分 别 与 该 智 能 体 相 连 上 左 下 右 四 个 方 向 的 智 能 体, 其 中 : = { - ¹ N = = { + ¹ N = N,, N,, N M M M N 图 冯 诺 依 曼 结 构 j = ì í î j - j ¹ M j = j = ì í î j + j ¹ M j = M () 在 这 样 的 邻 域 环 境 中, 智 能 体 只 与 周 围 的 四 个 智 能 体 交 换 信 息, 使 得 每 个 智 能 体 的 信 息 都 能 够 得 到 充 分 利 用, 维 持 整 个 系 统 的 多 样 性, 同 时 优 良 智 能 体 的 信 息 通 过 多 次 交 流 将 会 传 播 到 系 统 中 的 其 他 智 能 体, 实 现 优 良 信 息 共 享 定 义 ( 单 个 智 能 体 的 行 为 算 子 设 计 ) 行 为 算 子 设 计 是 构 建 多 智 能 体 系 统 中 最 核 心 的 工 作, 决 定 智 能 体 能 量 增 加 的 速 度 本 文 设 计 邻 域 合 作 竞 争 算 子 变 异 算 子 和 自 学 习 算 子 增 加 智 能 体 的 能 量 () 邻 域 竞 争 合 作 算 子 假 设 智 能 体 L j = (l l l n ) 的 邻 域 内 最 大 能 量 的 智 能 体 为 L max j = (l l l n ), 如 果 L j 的 能 量 大 于 L max j 的 能 量 则 L j 保 留, 否 则 随 机 从 以 下 两 种 占 据 策 略 中 选 择 一 种 产 生 一 个 备 选 智 能 体 C j = (c c c n ) 在 占 据 策 略,C j 按 如 下 方 式 生 成 : ìx k m k + U (- )*(m k - l k ) < x k ï- c k = í xk m k + U (- )*(m k - l k ) > - x k () ï îl k + U (- )*(m k - l k ) H(p c - r) otherwse 其 中,k = n,u ( - ) 表 示 在 ( - ) 之 间 取 随 机 数 ;( - x - x) 为 搜 索 范 围 ;H(.) 为 Heavsde 函 数 从 公 式 中 看 出, 落 败 的 智 能 体 保 留 了 部 分 有 用 的 信 息, 同 时 也 借 鉴 了 邻 域 内 优 良 智 能 体 的 信 息 来 更 新 自 己 的 位 置, 实 现 了 不 同 智 能 体 之 间 信 息 交 流 在 占 据 策 略 中, 首 先 将 L j 的 各 分 量 映 射 到 区 间 [,] 上 m k = (m k - - x k )/( - x k - - x k ) (k = n) () 然 后 按 照 下 式 确 定 NC j = (c c c n ) : NC j = (c,c, c n ) = ( m q,m p +, m q -,m p, ) 其 中 < p < q < n 最 后 按 公 式 (8) 将 NC j 映 射 回 ( - x - x) 得 到 C j : e k = x k + e k *( - x - - x) (8) () 变 异 算 子 对 邻 域 竞 争 合 作 产 生 的 C j 按 公 式 () 执 行 变 异 操 作 生 成 新 的 备 选 智 能 体 LC j = (e e e n ) : e = ì í î c r < P m c + L(λ) r P m = n () 其 中,r 为 [,] 的 随 机 数,P m 为 变 异 概 率,L(λ) 为 Levy 变 异 该 变 异 算 子 对 C j 某 些 分 量 增 加 了 扰 动, 能 扩 大 智 能 体 的 搜 索 范 围, 有 利 于 能 量 更 高 的 智 能 体 通 过 邻 域 竞 争 和 变 异 操 作 后 得 到 的 候 选 智 能 体 LC j, 若 其 能 量 f (LC j ) > f (L j ), 则 用 LC j 替 代 L j () 自 学 习 算 子 智 能 体 不 但 可 以 通 过 邻 域 竞 争 合 作 算 子 和 变 异 算 子 实 现 不 同 智 能 体 间 的 信 息 交 流, 增 加 系 统 的 多 样 性,

4 宋 玉 坚, 叶 春 明, 黄 佐 钘 : 多 智 能 体 布 谷 鸟 算 法 的 网 络 计 划 资 源 均 衡 优 化,() 也 可 以 利 用 自 身 的 知 识 进 行 自 学 习, 提 高 局 部 寻 优 能 力 在 自 学 习 算 子 中, 首 先 为 全 局 最 优 智 能 体 L j 构 造 一 个 sl sze sl sze 子 冯 诺 依 曼 结 构 系 统, 子 系 统 内 的 所 有 智 能 体 SL j, j = sl sze 均 按 如 下 公 式 产 生 SL j = ì í î L j = j = New j otherwse () 其 中 New j = (e j e j e j n ) 根 据 如 下 公 式 生 成 ìx k l k *U ( - sr + sr) < x k ï- e j k = í xk l k *U ( - sr + sr) > - x k ï îl k *U ( - sr + sr) otherwse () 式 中,k = n,sr 表 示 局 部 搜 索 半 径,U ( - sr + sr) 表 示 取 ( - sr + sr) 之 间 的 随 机 数 在 该 子 智 能 体 系 统 中, 只 采 用 邻 域 合 作 竞 争 算 子 进 化 方 式 增 强 子 系 统 的 能 量, 并 将 进 化 后 的 最 好 智 能 体 来 更 新 主 系 统 自 学 习 的 智 能 体 L j, 完 成 自 学 习 行 为 资 源 均 衡 优 化 的 多 智 能 体 布 谷 鸟 算 法 实 现. 编 码 方 案 查 阅 已 有 的 文 献 可 知, 智 能 算 法 在 求 解 资 源 均 衡 问 题 时 主 要 采 用 基 于 开 始 时 间 或 基 于 工 序 浮 动 工 时 率 的 编 码 方 案 本 文 选 用 无 需 解 码 操 作 的 基 于 开 始 时 间 的 编 码 方 案 根 据 资 源 均 衡 优 化 的 原 理, 把 资 源 优 化 问 题 的 可 行 解 看 作 是 智 能 体 的 N 维 搜 索 空 间, 其 中 N 表 示 网 络 计 划 中 的 工 作 任 务 数 智 能 体 在 t 代 所 找 到 的 位 置 Lt j = {lt lt lt n } 对 应 一 个 问 题 的 可 行 解, 其 中 lt k (k = N) 表 示 智 能 体 L j 在 第 t 代 时 第 k 维 工 作 任 务 的 实 际 开 始 时 间 由 于 网 络 计 划 图 中 的 工 作 间 存 在 着 时 序 关 系 的 约 束, 某 一 工 序 的 所 有 紧 前 任 务 得 到 合 理 安 排 后 才 能 确 定 该 工 序 的 开 始 时 间 因 此 本 文 根 据 拓 扑 排 序 顺 序 安 排 各 维 度 所 指 代 任 务, 这 样 对 任 意 任 务 开 工 时 间 有 影 响 的 任 务 均 位 于 该 任 务 之 前, 所 有 受 该 任 务 影 响 的 任 务 均 排 在 其 后, 进 而 方 便 从 左 至 右 有 序 地 初 始 化 或 检 查 修 正 Lt j 各 维 度 取 值 产 生 拓 扑 排 序 的 步 骤 如 下 : 列 中 ; () 将 网 络 图 中 的 起 始 任 务 置 入 部 分 拓 扑 排 序 序 () 检 查 未 排 序 的 任 务, 将 紧 前 任 务 均 已 安 排 的 任 务 置 入 部 分 拓 扑 排 序 序 列 中 ; () 重 复 步 骤 () 直 到 网 络 计 划 中 的 所 有 任 务 得 到 安 排 形 成 一 个 完 整 的 拓 扑 排 序 序 列 现 以 图 为 例 说 明 基 于 开 始 时 间 的 编 码 方 案 根 据 拓 扑 方 法 产 生 网 络 计 划 图 的 一 条 拓 扑 排 序 链, 则 个 体 向 量 Lt j ={lt lt lt } 与 排 序 链 的 对 应 关 系 如 表 所 示,lt 指 代 工 作 的 开 始 时 间, lt 指 代 工 作 的 开 始 时 间, 以 此 类 推 图 单 代 号 网 络 图 表 Lt j 与 工 序 的 对 应 关 系 维 数 j 向 量 Lt j 工 作 j lt lt lt lt lt lt lt. 取 值 的 离 散 化 与 非 法 个 体 的 修 正 由 于 标 准 多 智 能 体 布 谷 鸟 算 法 是 针 对 连 续 性 最 优 化 问 题 设 计 的, 因 此 要 将 其 用 来 求 解 资 源 均 衡 优 化 这 一 类 离 散 型 最 优 化 问 题 时, 需 要 对 布 谷 鸟 搜 索 路 径 与 位 置 更 新 公 式 邻 域 竞 争 合 作 算 子 和 自 学 习 算 子 做 必 要 的 改 进 以 适 应 离 散 取 值 的 需 要 目 前 常 见 的 改 进 方 法 有 两 种 : 第 一 种 是 采 用 二 进 制 编 码, 第 二 种 是 直 接 对 浮 点 数 取 整 本 文 采 用 简 便 易 行 的 第 二 种 方 法 多 智 能 体 布 谷 鸟 算 法 是 一 种 随 机 优 化 方 法, 算 法 采 用 基 于 开 始 时 间 的 编 码 方 案 会 在 进 化 过 程 中 产 生 违 背 时 序 约 束 的 非 法 解, 因 此 需 要 对 进 化 形 成 的 新 个 体 进 行 合 法 性 检 验, 对 于 非 法 个 体 进 行 修 正 检 验 修 正 操 作 为 : 从 左 到 右 逐 次 按 公 式 () 重 新 计 算 第 j 维 任 务 开 始 时 间 的 取 值 范 围 (FS j LS j ), 若 新 个 体 第 j 维 的 取 值 不 在 此 范 围, 则 判 定 为 非 法 个 体, 然 后 在 (FS j LS j ) 内 随 机 取 整 数 予 以 修 正. 算 法 流 程 资 源 均 衡 优 化 的 多 智 能 体 粒 子 群 算 法 的 流 程 如 下 : () 设 置 参 数 设 置 智 能 体 系 统 的 规 模 N M ; 迭 代 次 数 N_ter; 发 现 概 率 P a ; 自 学 习 智 能 体 系 统 的 规 模 sl sze sl sze ; 交 叉 概 率 和 变 异 概 率 P c,p m ; 局 部 搜 索 半 径 sr 及 其 迭 代 次 数 sgen () 多 智 能 体 初 始 化 随 机 生 成 N M 个 鸟 窝 ( 多 智 能 体 的 初 始 值 ), 根 据 公 式 () 确 定 每 个 智 能 体 的 邻 域, 计 算 相 应 的 目 标 函 数 值, 并 记 录 当 前 最 优 化 解 F mn () 判 断 是 否 满 足 结 束 条 件 是 则 结 束 迭 代 输 出 最 优 解 F mn, 否 则 转 第 () 步 () 鸟 窝 位 置 更 新 更 新 位 置 形 成 新 一 代 候 选 鸟 窝, 与 上 一 代 的 鸟 窝 一 对 一 对 比 适 应 度, 保 留 较 好 的 作 为 当 前 鸟 窝, 更 新 最 优 解 F mn () 随 机 迁 移 按 概 率 P a 随 机 迁 移 鸟 窝 位 置 得 到 新 一 组 鸟 窝, 同 样 与 上 一 代 比 较 保 留 最 好 的 鸟 窝, 记 录 最 优 解 () 邻 域 竞 争 合 作 与 变 异 依 次 对 每 个 智 能 体 执 行 邻 域 竞 争 合 作 操 作 和 变 异, 更 新 鸟 窝 位 置 和 最 优 解 F mn

5 ,() Computer Engneerng and Applcatons 计 算 机 工 程 与 应 用 () 自 学 习 操 作 对 最 优 的 智 能 体 ( 布 谷 鸟 ) 执 行 自 学 习 操 作, 更 新 最 优 鸟 窝 和 最 优 解 F mn, 转 第 () 步. 算 法 时 间 复 杂 度 分 析 由 上 述 算 法 流 程 可 知, 时 间 复 杂 度 取 决 于 迭 代 过 程, 鸟 窝 位 置 更 新 包 括 Levy 飞 行 探 索 候 选 种 群 以 及 竞 争 选 择 操 作, 时 间 复 杂 度 都 为 O(MN) ; 以 P a 的 概 率 执 行 变 异 操 作 的 最 差 时 间 复 杂 度 为 O(MN), 而 事 实 上, 一 般 不 对 所 有 群 体 执 行 变 异 ; 邻 域 竞 争 算 子 中 每 个 智 能 体 与 其 邻 域 内 的 个 智 能 体 进 行 信 息 交 流, 因 此 竞 争 合 作 算 子 的 时 间 复 杂 度 为 O(MN) ; 多 智 能 系 统 中 的 变 异 算 子 的 时 间 复 杂 度 为 O(MN) ; 自 学 习 算 子 的 时 间 复 杂 度 O(SL sze SL sze sgen), 根 据 O 的 简 化 规 则 可 知 布 谷 鸟 算 法 一 次 迭 代 过 程 的 时 间 复 杂 度 为 :O(MN) + O(sL sze sl sze sgen) 标 准 布 谷 鸟 算 法 只 有 Levy 飞 行 探 索 候 选 种 群 竞 争 选 择 操 作 以 及 变 异 操 作, 因 此 标 准 布 谷 鸟 算 法 一 次 迭 代 过 程 的 时 间 复 杂 度 为 O(MN) 同 理, 可 以 确 定 在 种 群 规 模 为 MN 的 情 况 下 差 分 进 化 算 法 和 粒 子 群 算 法 的 时 间 复 杂 度 为 O(MN) 一 般 情 况 下, sl sze sl sze sgen 大 于 MN, 所 以 改 进 后 的 多 智 能 体 布 谷 鸟 算 法 一 次 迭 代 过 程 的 时 间 复 杂 度 高 于 其 他 三 种 算 法, 但 后 续 实 验 将 证 实 该 算 法 具 备 更 好 的 优 化 性 能 仿 真 测 试 为 了 验 证 多 智 能 体 布 谷 鸟 算 法 求 解 资 源 均 衡 问 题 的 有 效 性, 本 文 以 某 施 工 项 目 网 络 计 划 为 例, 其 基 本 信 息 如 图 所 示, 因 篇 幅 所 限 本 文 不 列 出 各 项 工 作 的 具 体 8() 图 () 双 代 号 网 络 计 划 图 资 源 用 量 ( 工 作 代 号 ) 持 续 时 间 () () 8() () (8) () 8() () () () 8 () () (8) () 8 () () 名 称 分 别 用 多 智 能 体 布 谷 鸟 算 法 标 准 布 谷 鸟 算 法 差 分 进 化 算 法 和 粒 子 群 算 法 对 其 进 行 资 源 优 化, 比 较 运 行 结 果, 分 析 各 算 法 的 求 解 性 能 经 计 算 可 知, 该 项 目 工 期 为, 关 键 路 径 为 8, 因 此 实 验 的 目 的 是 合 理 确 定 关 键 路 径 以 外 非 关 键 工 序 的 开 始 时 间 实 现 资 源 方 差 最 小 本 实 验 硬 件 环 境 为 Intel Core. GHz 的 CPU, 内 存 为 GB DDR; 软 件 环 境 为 Wndows 操 作 系 统 和 Matlab. 的 开 发 环 境 多 智 能 体 布 谷 鸟 算 法 参 数 设 置 为 : 鸟 的 规 模 为 ( ) ;P a =.;P c =.;P m =. 多 智 能 体 布 谷 鸟 算 法 中 自 学 习 系 统 规 模 设 为, 局 部 搜 索 半 径 sr =, 迭 代 次 数 sgen = 标 准 布 谷 鸟 算 法 参 数 设 置 为 : 种 群 规 模 为, 发 现 概 率 P a =. 差 分 算 法 参 数 设 置 : 缩 放 因 子 F =.8, 交 叉 概 率 CR =. ; 设 粒 子 群 算 法 的 学 习 参 数 c = c =., 最 大 速 度 v max = 各 种 算 法 设 定 迭 代 次 数 N_ter =, 重 复 运 行 次, 统 计 次 优 化 结 果 的 最 大 值 F max, 最 小 值 F mn, 平 均 偏 差 A dev 最 优 解 比 例 Opt 以 及 求 得 最 优 解 的 平 均 迭 代 次 数 Iter 与 时 间 CPU, 并 附 上 F mn ( 上 行 ),F max ( 下 行 ) 相 对 应 的 调 度 方 案, 具 体 结 果 如 表 所 示 从 表 可 以 看 出, 多 智 能 体 布 谷 鸟 算 法 以 的 概 率 收 敛 到 最 优 解., 且 找 到 最 优 解 的 耗 时 相 对 最 少, 是 一 种 非 常 有 效 的 全 局 收 敛 算 法 标 准 布 谷 鸟 算 法 平 均 偏 差 指 标 A dev 和 最 优 解 比 例 Opt 这 项 指 标 比 差 分 进 化 算 法 要 好, 而 最 差 解 和 平 均 耗 时 比 较 差 的 原 因 是 布 谷 鸟 算 法 缺 乏 有 效 的 信 息 共 享 机 制 导 致 后 期 收 敛 速 度 慢 通 过 实 验 可 以 发 现, 增 大 进 化 代 数 N_ter 后 标 准 布 谷 鸟 算 法 F max 和 Opt 指 标 有 所 提 升 在 实 验 中 同 样 可 以 发 现, 基 于 种 群 差 异 的 差 分 进 化 算 法 能 快 速 收 敛, 但 是 容 易 因 种 群 多 样 性 降 低 而 出 现 进 化 停 滞 现 象, 即 算 法 陷 入 早 熟 另 外, 通 过 比 较 各 项 指 标 可 以 发 现, 粒 子 群 算 法 的 优 化 性 能 略 差 于 其 他 算 法 图 显 示 算 法 的 寻 优 进 程 多 智 能 体 布 谷 鸟 算 法 在 次 迭 代 后 基 本 能 收 敛 到 最 优 解, 而 其 他 算 法 需 左 右 次 迭 代 才 能 收 敛 到 最 优 解, 结 合 表 中 Iter 与 CPU 指 标 可 知, 多 智 能 体 布 谷 鸟 算 法 虽 然 单 次 迭 代 的 时 间 复 杂 度 最 高, 但 是 求 解 效 率 最 快 这 主 要 是 因 为 多 智 能 体 布 谷 鸟 算 法 很 好 地 实 现 了 多 智 能 体 系 统 和 标 准 布 谷 鸟 表 各 算 法 的 运 行 结 果 对 比 算 法 F mn F max A dev /% Opt/% Iter CPU/s 8 多 智 能 体 布 谷 鸟 算 法 标 准 布 谷 鸟 算 法 差 分 进 化 算 法 粒 子 群 算 法

6 宋 玉 坚, 叶 春 明, 黄 佐 钘 : 多 智 能 体 布 谷 鸟 算 法 的 网 络 计 划 资 源 均 衡 优 化,() 算 法 的 优 势 互 补, 算 法 中 的 邻 域 竞 争 合 作 算 子 弥 补 了 标 准 布 谷 鸟 算 法 缺 乏 信 息 交 流 的 缺 陷 ; 变 异 算 子 对 种 群 进 行 随 机 扰 动, 扩 大 了 搜 索 范 围 ; 自 学 习 算 子 则 通 过 小 范 围 搜 索 技 术 有 效 地 提 高 了 算 法 的 求 解 精 度 ; 同 时 Levy 飞 行 的 高 效 搜 索 机 制 同 样 可 以 扩 大 搜 索 空 间, 增 加 种 群 的 多 样 性, 跳 出 局 部 最 优 解 从 而, 多 智 能 体 布 谷 鸟 算 法 能 以 更 快 的 速 率 收 敛 到 全 局 最 优 解 资 源 方 差 8 结 论 针 对 网 络 计 划 资 源 均 衡 优 化 问 题, 本 文 将 多 智 能 体 系 统 嵌 入 标 准 布 谷 鸟 算 法, 提 出 了 多 智 能 体 布 谷 鸟 算 法 该 算 法 中 每 只 布 谷 鸟 代 表 一 个 智 能 体, 所 有 智 能 体 构 成 冯 诺 依 曼 结 构, 它 们 之 间 通 过 邻 域 竞 争 合 作 算 子 变 异 算 子 自 学 习 算 子 以 及 布 谷 鸟 算 法 的 进 化 机 制 不 断 增 强 能 量 提 高 适 应 度, 能 够 快 速 且 精 准 地 找 到 问 题 最 优 解 实 例 仿 真 也 证 实 了 多 智 能 体 布 谷 鸟 算 法 比 标 准 布 谷 鸟 算 法 粒 子 群 算 法 和 差 分 进 化 算 法 具 有 更 好 的 全 局 优 化 性 能, 是 求 解 资 源 均 衡 优 化 问 题 可 行 有 效 的 方 法 参 考 文 献 : 差 分 进 化 算 法 标 准 布 谷 鸟 算 法 粒 子 群 算 法 进 化 代 数 图 [] Essa S M.Resource levelng n constructon by optmzaton[j].journal of Constructon Engneerng and Management,8,():-. 多 智 能 体 布 谷 鸟 算 法 优 化 进 程 图 [] Bandellon M,Tuee M,Rnald R.Optmal resource levelng usng non-seral dynamc programmng[j].european Journal of Operatonal Research,,8():-. [] Neumann K,Zmmermann J.Resource levelng for projects wth schedule-dependent tme wndows[j].european Journal of Operaton Research,,():-. [] 李 星 梅, 乞 建 勋, 苏 志 雄. 基 于 时 差 分 析 的 资 源 均 衡 问 题 探 究 [J]. 中 国 管 理 科 学,,():8-. [] 郭 云 涛, 白 思 俊, 徐 济 超, 等. 基 于 粒 子 群 算 法 的 资 源 均 衡 [J]. 系 统 工 程,8(). [] 张 连 营, 张 金 平, 王 亮. 工 程 项 目 资 源 均 衡 的 遗 传 算 法 及 其 Matlab 实 现 [J]. 管 理 工 程 学 报,,8():-. [] Yang Xnshe,Deb S.Cuckoo search va Levy flght[c]// Proceedngs of World Congress on Nature & Bologcally Inspred Computng,:-. [8] Lm W C E,Kanagaraj G,Ponnambalam S G.Cuckoo search algorthm for optmzaton of sequence n PCB holes drllng process[j].lecture Notes n Mechancal Engneerng:Emergng Trends n Scence,Engneerng and Technology,:-. [] Ouaarab A,Ahod B,Yang Xnshe.Dscrete cuckoo search algorthm for the travellng salesman problem[j/ol].neural Comput & Applc,. [] 刘 长 平, 叶 春 明. 求 解 置 换 流 水 车 间 调 度 问 题 的 布 谷 鸟 算 法 [J]. 上 海 理 工 大 学 学 报,,():-. [] 潘 晓 英, 焦 李 成. 项 目 优 化 的 多 智 能 体 社 会 进 化 算 法 [J]. 计 算 机 研 究 与 发 展,8,():8-. [] 吴 亚 丽, 张 立 香. 资 源 受 限 项 目 调 度 的 多 智 能 体 文 化 演 化 算 法 [J]. 系 统 工 程,,8():-. [] 赵 波, 曹 一 家. 电 力 系 统 无 功 优 化 的 多 智 能 体 粒 子 群 优 化 算 法 [J]. 中 国 电 机 工 程 学 报,,():-. [] Yang Xnshe.Nature-nspred metaheurstc[m].[s.l.]:lunver Press,:-. [] 钟 伟 才. 多 智 能 体 进 化 模 型 和 算 法 研 究 [D]. 西 安 : 西 安 电 子 科 技 大 学,. ( 上 接 页 ) [] Xa M,Xu Z.Hestant fuzzy nformaton aggregaton n decson makng[j].internatonal Journal of Approxmate Reasonng,,():-. [] Xu Z,Xa M.Dstance and smlarty measures for hestant fuzzy sets[j].informaton Scences,,8(): 8-. [] Xu Z,Xa M.On dstance and correlaton measures of hestant fuzzy nformaton[j].internatonal Journal of Intellgent Systems,,():-. [] Hong D H.A note on correlaton of nterval-valued ntutonstc fuzzy sets[j].fuzzy Sets and Systems,8, ():-. [] Gerstenkorn T,Mańko J.Correlaton of ntutonstc fuzzy sets[j].fuzzy Sets and Systems,,():-. [] Mtchell H B.A correlaton coeffcent for ntutonstc fuzzy sets[j].internatonal Journal of Intellgent Systems,,():8-. [] Xu Z S,Xa M M.Hestant fuzzy entropy and crossentropy and ther use n multattrbute decson-makng[j]. Internatonal Journal of Intellgent Systems,,(): -8. [] Xa M M,Xu Z S.Entropy/cross entropy-based group decson makng under ntutonstc fuzzy envronment[j]. Informaton Fuson,,():-.