学海网

改进的蚁群算法在2D HP模型中的应用

第 51卷 第 1期

2005年 2月

武 汉大 学学 报 (理 学版 )

J．W uhan Univ．(Nat．Sci．Ed．)

Vo1．51 N0．1

Feb．2005，033～ 038

文章编 号 ：1671—8836(2005)01—0033—06

改进的蚁群算 法在 2D HP模型 中的应 用

何 莲 莲 ，石 峰”，周 怀北

(1．武 汉 大 学 数 学与 统计 学 院 ，湖 北 武 汉 430072；2．武 汉 大 学 计 算 机 科 学 学 院 ，湖 北 武 汉 430072)

摘 要 ：针对 蛋 白质 二维格 模型 (2D HP)折 叠 问题 提 出了一 种改 进 的蚁 群算 法 (Ant Colony Optimization AI—

gorithm)，在 算法 的搜 索 阶段 采用 了牵 引移 动 (pull moves)的方 法 ：首 先按 照一 定规 则 移动 一个 或两 个顶 点 的位 置 ．

然后将 其 他顶 点 沿着链 依 次 向前 移 动两 个位 置 ，一旦 达 到 一 个 新 的有 效 构 象 则 停 止该 移 动．该 方 法 的优 点 是 大 多

数移 动 只需改 变很 少 的顶点 位置 ，使得 改进 后 的蚁 群算 法具 有较快 的收敛 速度 ．求 解基 准 实 例 的结 果 表 明 ，该 算法

在保证 解 的质 量 的前提 下能 大大 缩 短计算 时 间．

关 键 词 ：蛋 白质 折叠 ；格模 型 ；蚁 群算 法 ；生 物信 息学

中图分 类号 ：0 242．28 文献 标识 码 ：A

0 引 言

由 意 大利 学 者 Dorigo M．等 人 首 先 提 出 的蚁 群

算 法 (Ant Colony Optimization Algorithm)是 受 到

人 们 对 自然 界 中 真 实 的蚁 群 集 体 行 为 的研 究 成 果 的

启 发 而 提 出 的一 种 基 于 种 群 的 模 拟 进 化 算 法 ，属 于

随 机 型 智 能 搜 索 算 法 _l ]，它 充 分 利 用 了 蚁 群 搜 索

食 物的过程与著名 的旅行商 问题 (TSP)之 间的相似

性 ，通 过 人 工 模 拟 蚂 蚁 搜 索 食 物 的 过 程 (即 ：通 过 个

体之 间的信息交流与相互协作最终找 到从蚁 穴到食

物 源 的 最短 路 径 )来 求 解 TSP问 题 ．自从 蚁 群 算 法

在 TSP问题 和工作排序 问题 上取得成效 以来 ，

已陆 续 渗 透 到 其 他 问题 领 域 中 ，如 图 的着 色 问 题 L5J、

车辆调 度 问题 ]、蛋 白质折 叠 问题_7 等等 ，在许 多

方面表现出相 当好 的性能．

蛋 白质 是生命 活动 的重要 承担者 ，蛋 白质 的生

物 功 能 由其 空 间 结 构 决 定 ，在 天 然 蛋 白质 中 ，蛋 白质

的最 终 构 象 是 由 氨 基 酸 序 列 唯 一 确定 的_9]．蛋 白质

折 叠 问题 就 是 确 定 一 个 给 定 氨 基 酸 序 列 的蛋 白质 的

天 然 结 构 的 问题 ．确 定 天 然 结 构 有 一 些 物 理 化 学 方

法 ，如 X 射 线 晶 体 衍 射 、核 磁 共 振 等．但 是 ，这 些 方

法 耗 资 巨 大 而 且 耗 时 耗 力 ，而 且 能 测 的 结 构 也 很 受

限制 ．随 着 计 算 机 技 术 的 发 展 ，在计 算 机 上 进 行 蛋 白

质 折 叠 模 拟 已经 成 为 蛋 白 质 结 构 预 测 的 重 要 方 法 ．

计 算 机模 拟 中用 的最 多 的 是 一 些 简 化 模 型 ，而 简 化

模 型 中最 重 要 的 一 类 就 是 格 模 型 ，这 些 模 型 的 共 同

特 征 为 ：① 单 体 (或 残 基 )用 一 个 统 一 的 尺 寸 代 表 ；

② 键长是统一 的；③ 单 体 的位 置被 严 格 的 限制 在

格 位 置 上 ；④ 简 化 的 能 量 函 数 ¨ ．然 而 即 使 是 简 化

模 型 ，该 问题 仍 然 是 NP困难 的 _l ]．

用 蚁 群 算 法 求 解 2D HP模 型 时 ，在 局 部 搜 索 阶

段文献 E7]采 用 了单 点 变异 (point mutations)和 宏

变 异 (macro mutations)的 方 法 ，该 方 法 容 易 产 生 不

可行构 象 ；而 文 献 [8]则 采 用 了大 范 围移 动 (1ong

range move)的方 法 ，该 方 法 的 计 算 量 较 大 ．本 文 结

合文献 [13]对 此做 了 改进 ，采 用 了牵 引 移 动 (pull

moves)的 方 法 ，该 方 法 比较 简 单 直 观 ，计 算 量 小 ，结

果 表 明 改 进 后 的蚁 群 算 法 能 够 大 大缩 短 运 行 时 间 ．

1 蛋 白质 的 2D HP折 叠 问题

格 模 型 的种 类 很 多 ，Dill提 出 的疏 水 性 一亲 水 性

(HP)模 型 是 最 简 单 的一 种 ，也 是 应 用 较 为 广 泛 的一

种 口 ]．HP模 型 提 出 的 理 论 基 础 是 氨 基 酸 的 疏 水

性 是 小 的 球 蛋 白形 成 天 然 构 象 的 主要 驱 动 力 _】 ．

HP模 型 中 ，20种 氨 基 酸 按 疏 水 性 和 亲 水 性 被

分 为两类 ：疏水性残基 (H)和极性 残基 (P)，因此 蛋

白质 序 列 被 抽 象 为 一 个 由 H 和 P组 成 的序 列 ．这 个

收稿 日期 ：2004—06—10 十通讯 联系 人 E-mail：shifeng@public．wh．hb．cn

基金项 目：国家 自然科学 基金 资助项 目(30170214)

作者简 介 ：何 莲莲 (1981一)，女 ，硕 士生 ，现从事 生物 信息学 研究． E mail：gonewithhll@sohu．corn

维普资讯 http://www.cqvip.com



34 武汉 大学 学 报 (理学 版 ) 第 51卷

序 列 根据 自避 免 原 则 被 限 制 在 一 个 格 上 (本 文 考 虑

的是 二 维 平 方 格 )．图 1是 一 个 以 2D HP模 型 表 示

的蛋 白质 构 象 ．图 中所 示 序 列 为 表 1中序 列 2．

卜 J

】 [ ]

】 I |_乇卜司

_ l- -

I - ．．

． 上 ．

：工 工 。

图 1 以 2D HP模 型 表示 蛋 白质 构象 的例 子

蛋 白 质 序 列 为 ：HHPPHPPHPPHPPHPPHPPHPPH H，

黑色 方格 表示 疏 水性 氨基 酸 ，白色方 格表 示 极性 氨 基酸 ．实 线

表示键 长 ，虚线表 示计 入能量 的 H—H 接触

在 HP模 型 中 ，一 个 构 象 的 能 量 定 义 为 ：序 列 中

并 不 相 邻 但 是 拓 扑 相 邻 的 疏 水 氨 基 酸 接 触 数 目．也

就 是 说 ，一 个 有 个 H—H 接 触 的 构 象 r的 自 由 能

E(f)一 ·(一 1)．例 如 ，图 1所 示 构 象 的 能 量 为 一 9，

同 时也 是 该 序 列 的 最 优 构 象 ．

蛋 白质 的 2D HP折 叠 问 题 正 规 提 法 如 下 ：给 定

一 个 氨 基 酸序 列 —S ，S ，? ，S ，找 到 S的最 低 能 量

构 象 ，也 就 是 找 到 f E C( )，使 得 E 一 E(f )一

min{E(f)『fE C}，其 中 C(s)是 S的 所 有 有 效 构 象

集 ．蛋 白质 的天 然 构 象 是 吉 布 斯 (Gibbs)自由 能 最 低

的构 象 ，这 是 利 用 能 量 极 小 化 方 法 预 测 蛋 白 质 结 构

的热 力 学 基 础 _】 ．

表 1 求解 2D HP蛋 白质 折 叠 问题 的基准 实例 及 其最低 能 量 E

2 用 于 求解 HP模 型 的 蚁群 算 法

对 一 个 给 定 的 HP序 列 ，由 ACO 算 法 中 的 蚂

蚁构 建候 选解 ，为了进一 步提高解 的质量 ，按 照一定

的原则对候 选解应 用 局部 搜索 策略 ，并且 根据 解 的

质 量 进 行 信 息 素 的更 新 ，框 架 如 图 2．

图 2 求解组 合 优化 问题 的蚁 群 算法 框架 图

候选解采取文 献 [17]中的局 部结 构基 元表 示 ：

直 走 (S)、左 转 (L)和右 转 (R)，在 二 维 格 上 氨 基 酸 的

位 置 分 别 如 图 3所 示 ．

经 过 旋 转 的 构 象 认 为 是 不 变 的 ，所 以 不 失 一 般

性 的假 设 开 始 的 两 个 氨 基 酸 位 置 是 固 定 的 ．则 可 以

通 过 一2个 局 部 结 构 基 元 表 示 一 个 长 度 为 的 蛋

白质 序 列 的候 选 构 象 ．图 1中 的 构 象 可 以 表 示 为 序

列 ：SRRLRRI SSRRSI SRLRRI RRS．

图 3 算 法 在 解 的 构 建 和 局 部 搜 索

阶段 采用 的 局部 结构 基元

2．1 解 的构 建 、信 息 素 表 示

ACO 算 法 的构 建 阶段 ，每 只蚂 蚁 随 机 的在 给 定

序 列 中 选择 一 个 初 始 点 ．从 初 始 点 开 始 ，序 列 同 时 向

两 个 方 向折 叠 ，每 次 增 加 一 个 氨基 酸 ．构 建 的 每 一 步

根 据 由期 望 值 ， 和 信 息 素 (轨 迹 强 度 ) 共 同 决 定

的 概 率 选 择 折 叠 方 向 ，其 中 是 序 列 位 置 ，dE {S，

L，R}是 在 位 置 i的 折 叠 方 向．该 方 向 与 由 三 个 连 续

的序 列 位置 S SiS川 组 成 的结 构 基 元 相 对 应 ，这 些

维普资讯 http://www.cqvip.com



第 1期 何莲 莲 等 ：改 进的 蚁群 算法 在 2D HP模 型 中的 应用 35

方 向相 当于旅行 商(TSP)问题中城市之 间的边 ．

当折叠方 向是 由位置 向位置 一1进 行 时 信

息素和期望值分 别用 r：， 和 表示．算 法 中 ，r：， 一

Vi， ， ， 一

，

， ，s—r， 的值 依 此 类 推．这 些 关 系

反 映 了折 叠 过程 的 一 种 基 本 对 称 的特 征 ：从 i到 +

1扩展 ，把 置 于 5 的 右 转 (从 5H 看 )或 者 从 i到

i一1扩 展 ，把 。置 于 5 的 左 转 (从 。看 )，得 到 的

是 5H SiS? 的 同 一局 部 构 象 ．

期 望 值 玑 将 解 的 构 建 过 程 引 向 高 质 量 候 选

解 ，也 就 是 说 ，引 向增 大 H-H 接触 数 目 的构 象 ．本 文

中 r／i， 是 根 据 变 量 h ， 定 义 的 ，向前 折 叠 时 (向 后

折 叠 类 似 )h? ， 是 指 将 s 置 于 5 和 5H 的 方 向

时 新 增 加 的 H—H 接 触 数 目．需 要 注 意 的 是 ，如 果

5? 一P，则 h ， 一 ^ ，L一^? ，R一0；而 且 对 于 1<

< 一 1有 关 系 式 h? ， ≤ 2，并 且 h ≤ 3；h ． 的 值

通 过 检 查 二 维 平 方 格 上 s 的 7个 邻 位 (显 然 ，s 位

不需 检查)很容易得 出．为 了保证对所有 的 和 d都

满 足 刁 > 0，定 义 7li， 一h川 ， + 1，这 对 保 证 在 解 的

构建过程 中不排 除 。的任何优先位子很 重要．

在算法 的构 建 阶段 ，假 设 构 象 已经 扩展 为 ，

? ， 即 将 扩 展 。，则 。相 对 于 S 5 的 方 向 取

决 于下式 由期 望值和信息素决定 的概率 ：

Pi,d一 > (

，

)。(玑 )

∈ ，s}

如 果 构 象 已 扩 展 为 s，? ， ，即将 扩 展 ，情 况 类

似 ．

当蚂 蚁 从 一 个随 机 初 始 位 置 (每 只 蚂 蚁 的 初 始

位 置 的选择 相 互 独 立 )开 始 折 叠 时 ，折 叠 随 机 的 向 两

个方向进行扩展 ，而向每个方向扩展 的概率等于该方

向未 折 叠 的残 基 数与 总 的 未折 叠 的残 基 数 的 比值 ．

在解的构建阶段 ，尤其是对较长 的蛋 白质序列而

言 ，经 常会 碰 到 不 可 行 的 构 象 ．这 种 情 况 的 发 生 是 由

于一个未完成 的构象在折叠 时因为所有 的邻 位都 已

经被 其 他 氨基 酸 占据 而不 能 继续 扩 展 下 去 ．本 文在 构

建过 程 中遇 到 该情 况 时 采 取 了一 种 回溯 机 制 ：短 序 列

( ≤ 64)回 退 一 步 重 新 开 始 构 建 过 程 ，而 较 长 序 列 (

>64)则回溯至 已折叠 的的一半位置处重新开始构建

过 程 ． ’

2．2 局 部 搜 索

局 部搜索 是蚁群 算法 中很重 要 的一 部分．解 的

构建 阶段结束后 ，选择 一 定数 目的蚂 蚁根 据候选 解

分别进行局部搜 索．文献[7，8]中所采取 的局部搜索

较为复杂 ，计算量大 ，本 文对 此作 了改进 ，采用 了文

献[73中提出的“牵 引移 动(pull moves)”方法．

首 先 定 义 几 个 概 念 ：格 上 的 一 个 节 点 称 为 一 个

位 置 (1ocation)，对 应 于 一 个 坐 标 对 ( ， )；两 个 位置

不管是水 平 相 邻 还 是 垂 直相 邻 均称 为相 邻 (adja—

cent)；和 同 一 个 位 置 分 别 水 平 相 邻 和 垂 直 相 邻 的 两

个 位 置 称 为对 角 相 邻 (diagonally adjacent)．链 上 的

节点称 为顶 点 (vertex)，均 有一 个 标签 ，H 或 P．链

上 的 顶 点 有 从 1到 的 连 续 标 号 ．一 个 构 象 如 果 在

格 上 的路 径 C遵 守 不 交 叉 (non-self-intersecting)原

则 并 且 相 邻 的 顶 点 占有 相 邻 的 位 置 则 称 为 有 效 构

象 ．为 了 方 便 描 述 该 移 动 ，构 象 将 随 时 间 变 化 ：C(f)

表 示 时 刻 t的 构 象 ．顶 点 i在 时 刻 t的 位 置 表 示 为

( (f)， (f))．如 果 在 时 刻 t一 个 位 置 没 有 被 顶 点

占有则说 其是 自由的(free)，称为空位．

假 设 顶 点 在 时 刻 t的位 置 为 ( ，(f)，Y，(f))，空

位 F是 ( 『+l(f)，y? (f))的邻 位 ，同时 也是 (z，(f)，

y (f))的对 角 相邻 位 置 ．具 体 可 参 考 图 4．由 图 可 知 ，

( (f)，y。(t))，(z? (t)，y? (t))和 空 位 F 构 成 了

一 个 正方形 的三个角落 ，假设 第 四个角落 为 c．只有

满足 以下 两种情况 之一 才能 进行 牵 引移 动 ：c为空

位 ；C恰 好 为 (zH (f)，yH (f))．

图 4 牵 引 移 动 详 解

(a)将 顶点 i移至 空位 F；(b)若 C恰 为顶点 一1，移 动完

成 ；(c)否 则 ，将 顶点 i--1移 至空 位 C，移 动 可能 已 完成 ；(d)

若移 动仍 未完成 ，将 顶 点 一2移 至顶 点 i先前 位 置 ，将 顶点 i

一 3移至顶 点 i--1先前位 置 ，直到重 新达 到一有 效构 象

当 C一 (zH (f)， H (f))时 ，只需 把 顶 点 i移 至

F 即完 成 此 次 局 部 移 动 ．当 C是 空 位 时 ，首 先 把 顶

点 i移 至 F，把 顶 点 i一1移 至 C，然 后 在 达 到 一 个 有

效 构 象 前 进 行 以下 移 动 ：从 顶 点 J— i一 2开 始 直 到

顶 点 1，置 (z，(t+ 1)， ，(t+ 1))一 (Xj+Z(t)，yj+2

(f))．也 就 是 说 ，达 到 一 个 新 的 有 效 构 象 前 ，所 有 的

顶 点均 沿 着链 向前 移 动 了 两 个 位 置 ．注 意 这 样 移 动

可 以确 保 构 象 的 有 效 性 ．

该 移 动 的优 点 之 一 为 ：只要 达 到 一 个 有 效 构 象 ，

就 可 以停 止 此 次移 动 ，因此 只需 改 变 尽 量 少 的 顶 点 位

维普资讯 http://www.cqvip.com



36 武汉 大学 学 报 (理 学版 ) 第 51卷

置 ．实 验 中可 以看 出大 多移 动 只 需 移动 很 少 的顶 点 ．

同样 ，可 以考 虑 另 外 一 个 方 向 的移 动 ．即从 一 个

既 是 ( (￡)， 一 (￡))的 邻 位 ，也 是 ( ，(￡)， ，(￡))的

对 角 相 邻 位 置 的 空 位 F开 始 ，过 程 类 似 ．

为 了保 证 该 移 动 可 逆 ，需 要 对 端 点 做 特 别 处 理 ．

考 虑 一 个 路 径 的端 点 ，如 果 有 两 个 空 位 ，并 且 其 中一

个 是 顶 点 Y／的 邻 位 ，只 需 把 顶 点 Y／一 1和 Y／移 至 这 两

个 空 位 ，然 后 做 以下 移 动 ：从 顶 点 —Y／一2开始 直 到

顶 点 1，置 (I7，(t+ 1)，yj(t+ 1))一 (I7，+2(t)，

，+ 。 (￡))，直 到 达 到 一 个 新 的 有 效 构 象 ．对 端 点 1的

处理类 似．文献[7]证 明 了该 移动 集是 完全 的 ，并且

是 可 逆 的 ．

本 文 中 ，每 完 成 一 个 循 环 ，就 按 照 精 英 策 略 (e—

litist strategy)选 择 一 定 数 目(蚂 蚁 数 目的 1 )的 构

象 按 上 述 原 则 实 行 局 部 搜 索 ，并 且 计 算 新 构 象 的 能

量 值 ，如 果 优 于 原 有 的构 象 则 接 受 该 解 ；否 则 放 弃 ．

2．3 信 息 素 的 更 新

每次结 束一 个循环 并完成 局部搜 索后 ，按 照精

英 策 略 选 择 一 定 数 目(蚂 蚁 数 目的 1 )的 构 象 按 下

式 进 行 信 息 素 的 更 新 ：

Ti． P ·Ti， + △ ， ，

其 中 0
蚁 的候 选 构 象 c中 第 i个 位 置 是 否 包 括 局 部 基 元 d

有 关 的 值 ，若 不 包 括 则 为 0，为 了 防 止 有 较 大 能 量 的

序列在搜 索 阶段 的 过早 停 滞 现 象 ，本 文 的 取 值 为

E(f)／E ，其 中 E 是 给 定 序 列 已 知 的 最 小 能 量 值

或 者是 和 序 列 中 H 数 目相 关 的一 个 近 似 值 ．

3 实验 结 果

为 了 评 价 算 法 性 能 ，本 文 把 改 进 后 的 蚁 群 算 法

应 用 于 表 1中 的 11个 2D HP蛋 白质 折 叠 问 题 的基

准 实 例 ，这些 实 例 在 很 多 文 献 中 已被 广 泛 采 用 ．除 非

特 别 指 出 ，本 文 中 的 实验 参 数 为 a： 1， 一2，lD一0．8．

< 48的 序 列 蚂 蚁 数 目为 500只 ，48≤ n< 85的 序

列 用 了 1 500只 蚂 蚁 ，Y／≥ 85的 序 列 蚂 蚁 数 目 为

5 000只 ．选 择 1 的 蚂 蚁 实 行 局 部 搜 索 和 信 息 素 的

更新 ．实 验 对 每个 序 列 执 行 的 循 环 数 是 独 立 的 ：对 于

较 短 的 序 列 ( ≤ 25)，如 序 列 1到 序 列 3，采 取 较 少

的循 环 数 (50次 )，每 次 循 环 后 进 行 2 000次 局 部 搜

索 即可 在 2 S内找 出最 优 解 ．n> 25的 序 列循 环 数 为

500个 ，进 行 5 000次 局 部 搜 索 ．经 过 实 验 发 现 该 算

法 对 于 序 列 5和 序 列 7不 是 很 稳 定 ，不 管 是 增 大 循

环次 数 还 是增 大 局 部 搜 索 次 数 均 不 能保 证 找 出 最 优

解 ．但 是 对 于 序 列 5在 5O s(500次 循 环 5 000次 局

部 搜 索 )的 时 间 内均 可 找 出次 优 解 (一22)，找 出最 优

解 (一23)的 概率 为 2 ，而 对 于序 列 7则 可 在 100 s

(500次循 环 5 000次 局 部 搜 索 )的 时 间 内 找 出 次 优

解 一 35．具 体运 行 时 间 和 结 果 见 表 2．图 5给 出 了

本 文算 法 找 出的 序 列 5、序 列 7以及 序 列 9、序 列

10、序 列 11的最 优 解 和 次 优 解 ．

运 行 时 间 以 CPU 时 间 测 量 ，所 有 的 实 验 运 行

环 境 为 ：2 GHz Pentium IV CPUs，512 KB cache

and 256 MB RAM．其 中 原 ACO 算 法 循 环 次 数 分 别

为 ：1OO次 ( > 64)，300次 (50< Y／≤ 64)和 500次 (Y／

≤ 50)，蚂 蚁 数 目为 ：500只 ( ≤ 48)和 1 500只 ( >

48)，运 行 环境 为 ：1 GHz Pentium Ⅲ CPUs，256 KB

cache and 1 GB RA M ．

本 文 为 了评 价 局部 搜 索 的 速度 ，对 于多 个 序 列 采

用 了不 同的局 部 搜 索 次数 ，发 现 局 部 搜 索 的 次 数 对 于

时 间 的影 响相 对 于 循 环数 的 影 响要 小 一 些 ．如 对 于 序

列 1O，局部 搜 索 次 数增 加 1O倍 (由 5 000次 到 50 000

次 )时 ，运 行 时 间 为原 来 的 3倍 ．而循 环 次 数 增 加 一 倍

时运行时间即变为原来的 2倍．各参 数对运行 时间和

结 果 的 影响 本 文 作者 将 作进 一 步 研究 ．

表 2 改进 的蚁 群算 法和 原算 法 结果 比较

(其 中 f 为算 法找 到该 解 需要 的平均 时 间 )

3．33

2．52

1O．62

11．81

405．79

4 952．92

62 471．24

5 844．93(2 h)

21 901．34(6 h)

29 707．22(9 h)

10 835．51(3 h)

O．562

O．859

O．797

11．641

43．859

52．156

95．657

159．453

487．657

1 188．828

2 086。526

c=。 捣 卯

M 捣 卯

一 一 一 一 ～ 一 一 一 一 一

M 捣 够 的 犍 一 一 一 一 一 ～ 一 一 ～ 一

加 犍 的 ∞ 踮 ∞ ∞

1 2 3 4 5 6 7 8 9 u

维普资讯 http://www.cqvip.com



第 1期 何莲 莲 等 ：改进 的蚁 群算 法 在 2D HP模 型 中的应 用 37

霹霉· 魁 塌目_嚣艘虫 船 魏 辩 礴随 麓 翟辫 鞲

(a) (b) (c) (d)

(i) 【j)

图 5 本文 算 法发现 的 序列 5、7、9、10、11的次优 解 和最 优解

(a)，(b)为序列 5的两个 次优解 (--22)；(c)为最优 解(--23)；(d)为序 列 7的次优 解(一35)；

个次优 解 (--51)；(h)，(i)为 序列 lO的次 优解 (--47)；(j)，(k)为 序列 11的两 个次 优解 (--46)

4 结 论

本文在 文献[7]的基础 上改进 了蚁群算法 ，再 次

表 明该 算 法 在求 解 2D HP模 型 方 面 的 良好 性 能 ．经

过 和 原 算 法 作 比较 ，改 进 后 算 法 的 一 个 明 显 改 进 就

是 ：在 保 证 解 的 质 量 的 前 提 下 ，运 行 时 间 大 大 缩 短 ，

尤 其 是 对 于 较 长 序 列 ．可 见 本 文 中 采 取 的 局 部 搜 索

确 实 可 以 改 善 算 法 性 能 ．

如果 考 虑 一 种 更 简 单 的 局 部 搜 索 机 制 可 能对 解

决 问题 更 有 效 ，将 蚁 群 算 法 应 用 于 生 物 学 中 的 其 他

问 题 也 将 是 一 件 很 有 意 义 工 作 ．

参 考文 献 ：

[1] Dorigo M，Maniezzo V，Colorni A．The Ant System：

[2]

An Autocatalytic Optimizing Process[R]． Technical

Report No．91—016，Italy，M ilano：Dipartimento di Elet—

tronica，Politecnico di M ilano， 1991．

Dorigo M ， M aniezzo V ，Colorni A ． The A nt System ：

Optimization by a Colony of Cooperating Agents[J]．

IEEE Transactions on Systems，M an，and Cybernet一

[3]

[4]

[5]

[6]

[7]

(k)

(e)，(f)，(g)为 序 列 9的 三

frPart B ，1996，26(1)：29—41．

Dorigo M ，Gambardella L M ． Ant Colony System ： A

Cooperative Learning Approach tO the Travelling

Salesman Problem ． IEEE Trans on Evolutionary

Cornputation，1997，1(1)：53—66．

Colorni A ，Dorigo M ，M aniezzo V 。eta1． Ant System

for Job-Shop Scheduling[J]．‘，()RBEL，1994，34(1)：

39—53．

Costa D， Hertz A． Ants Can Colour Graphs[J]．

Journal of the Operational Research Society，1997．48

(3)：295—305．

Bullnheimer B， Hartl R F， Strauss C． Applying the

Ant System tO the Vehicle Routing Problem[A]．Voss

S， M artello S，Osman I H ，et a ，eds． M eta-H euris—

tics： Advances and Trends in LocaI Search Para-

digms r Optimization[c]．Boston：Kluwer，1998，

109—12O．

Alena Shmygelska， Holger H H oos． A n Improved

A nt Colony Optim isation A lgorithm fo r the 2D HP

Protein Folding Problem [A]． Yang Xiang，Brahim

Chaib-draa，eds． Canadian Con rence 0n AI，Lecture

Notes in Computer Science[e1．Berlin：Springer Ver-

lag，2003，2671．

维普资讯 http://www.cqvip.com



38 武汉 大 学学 报 (理学 版 ) 第 51卷

[8J Shmygelska A．Hernandez R．HOOS H H．An Ant

Colony A lgorithm for the 2D H P Protein Folding

Problem[A]．Marco Dorigo，Gianni Di Caro，Michael

Sam pels，eds．A nt A lgorithms，Lecture Notes in Corn —

puter Science[C]．Berlin： Springer Verlag，2002，

2463．

[9] Anfinsen C B，Haber E，White F H．The Kinetics of

the Formation of Native Ribonuclease During O xida—

tion of the Reduced Polypetide Domain[J]．Proc Natl

Acad Sci USA ，1961，47(9)：1309—1314．

r 1 03 Backofen R． The Protein Structure Prediction Prob—

lam ：A Constraint Optimization Approach using a New

Lower Bound[J]．Constraints，2001，6：223-255．

[113 Berger B，Leighton T．Protein Folding in the Hydro—

philic-Hydrophobic(HP)Model is NP—Complete[J]．

Journal of Computational Biology，1998，5(1)：27—40．

r123 Hart W E，Istrail S．Robust Proofs of NP—Hardness

for Protein Folding General Lattices and Energy Poten—_

rials[J]．Journal of Computational Biology，1997，4

(1)：1—22．

r133 NealJ esh，Michael Mitzenmacher，Sue Whiresides．A

Com plete and Effective M ove Set for Sim plified Protein

Folding[A]． Miller W ，Vingron M，Istrail S，et a1．

Eds． Annual Conference on Research in Com putational

Molecular Biology[C]． New York： ACM Press，

2003， 188—195．

[14]Lau K F，Dill K A．A lattice Statistical Mechanics

M odel of the Conform ation and Sequence Space of Pro—

teins[J]．Macromolecules，1989，22：3986—3997．

[15] Dill K A． Theory for the Folding and Stability of

Globular Proteins[J]．Biochemistry，1985，24：1501．

[16] Anfinsen C B．Principles that Govern the Folding of

Protein Chains[J]．Science，1973，181(4096)：223—227．

[173 Krasnogor N， Hart W E，Smith J，et a1． Protein

Structure Prediction with Evolutionary Algorithm s

[A]． Banzhaf W ，Daida J，Eiben A，et a1． Eds．

GECCO-99：Proceedings of the Genetic and Evolu～

tionary Computation Conference[C]． San Mateo，

CA ： M organ Kaufmann，1999，1596—1601．

Application of Im proved Ant Colony Optim ization

Algorithm to the 2D HP M odel

HE Lian-lian ，SHI Feng ，ZHOU Huai—bei

(1．School of M athematics and Statistics，W uhan University，W uhan 430072，H ubei，China；

2．School of Com puter ，W uhan University，W uhan 430072，H ubei，China)

Abstract：A n im proved Ant Colony O ptimization (ACO ) is proposed for the 2-dimensional hydropho～

bic-polar (2D H P) protein folding problem ，we m odified the local search m echanism by using pull moves：

First one or two vertices was m oved by rule，then，pull the other vertices two spaces up the chain until a

new valid configuration is reached． The advantage is that m ost moves displace few vertices． It can quicken

the convergence rate． O ur experim ents show that our algorithm can observably decrease com puting tim e

w ith the sam e result of previous AC0 algorithm．

K ey words：protein folding；lattice m odel；ant colony optim ization (ACO ) algorithm ；bioinform atics

维普资讯 http://www.cqvip.com




改进的蚁群算法在2D HP模型中的应用.pdf