基于人工免疫算法和蚁群算法求解旅行商问题
基于人工免疫算法和蚁群算法求解旅行商问题
胡纯德 祝 延军 高随祥
(中国科 学院研 究生院 ，北 京 lO0039)
E—mail：huchunde@ 126．COrn
摘 要 人 工免疫 算法 具有 快速随机 的全局搜 索能力 ，但 对 于 系统 中的反 馈 信 息利 用不足 ，往往 做 大量 无 为 的冗余 迭
代 ，求解 效 率低 。蚁 群算 法具 有分布 式 并行全局 搜 索能 力 ，通过信 息 素的积 累和 更新 收敛 于最优路 径 上 ，但初 期信 息 素匮
乏 ，求 解速 度慢 。该 文提 出一 种基 于人 工免疫 算 法和 蚁 群算 法的 混合算 法 ，采 用人 工免疫 算法 生成信 息素 分布 ，利用蚁 群
算法 求优 化解 。将 该算 法 用于求解旅 行 商 问题 进行 计算机 仿 真 ，结果表 明 ，该 算法是 一种 收 敛速度 和 寻优 能 力都 比较 好
的 优 化 方 法 。
关键 词 人 工免疫 算法 蚁群 算法 旅行 商问题
文章 编号 10o2—8331一(2004)34—00l6o—04 文 献标识 码 A 中图分 类号 I'P301．6
A Hybrid Algorithm Based on Artificial Imm une Algorithm and Ant
Colony Algorithm for Solving Traveling Salesman Problem
Hu Chunde Zhu Yanjun Gao Suixiang
(Graduate School of tIle Chinese Academy of Sciences，Beijing lO0039)
Abstract： Artificial Imm une Algorithm has the ability of doing a global searching quickly and stochas tically．But it can't
make use of enough system output information，and hence has to do a large redundan cy repeat searching for the opti-
ma l solution，which reduces the efficiency of algorithm．Ant Colony Algorithm converges on the optimal path through
pheromone accumulation and renewal，and has the ability of parallel processing and global searching．But its convergence
speed is slow because of pOOr pheromone on the path early．In this pape r we propose a hybrid algorithm based on Arti-
ficial Immune Algorithm and Ant Colony Algorithm．It adopts Artificial Imm une Algorithm to give pheromone to dis-
tribute and makes Use of Ant Colony Algorithm to give the optimal solution．The computer simulation results show that
the proposed algorithm is better than the previous two algorithms on the convergence spe ed an d ab ility of searching for
approximate global optimal solution for solving Traveling Salesman Problem．
Keywords：Artificial Immune Algorithm(AIA)，Ant Colony Algorithm(ACA)，Traveling Salesman Problem(TSP)
l 引言
旅 行 商 问题 (Traveling Salesman Problem，TSP)是 具 有 重
要 意 义的组 合 优化 难题 ，已被 证 明属 于 NPC问题 。 它 可简述
为 ：给 定 一 个边 赋 权 图 G---(V，E)，寻 找 G 的 Hamilton圈 C，使
得 C的总权 ‘|，(C)最小 。TSP问题 描述 简单 却难 以求 解 ，因而一
直作 为衡量 各种 优化 算法 性能 的标 准。 近年来 ，人们 从仿 生学
的机 理 中受 到启 发 ，提 出 了许 多 用 于求 解 TSP问题 的新 方 法 ，
如 ：禁忌 搜 索算 法 、遗 传算 法 、摸拟 退火 算 法 、人工 免疫 算 法 和
蚁 群算 法 等 。然 而 ，面对 TSP问题 的复杂 性 ，每种 算 法都 表 现
出各 自的优 势和 缺陷 。
人 工 免 疫 算 法 (Artificial Immune Algorithm．AIA)是 近 几
年才 提 出 的一 种随 机 优化 方 法 ，它 模拟 生 物免 疫 系统 ，用 亲 和
力 来 描述抗 体 与抗原 之间 的 匹配程 度 ，用排斥 力 来描 述 两个抗
体 之间 的相 似程 度 ，依据 抗体 与抗原 之 间 的亲和 力 以及抗 体 与
抗 体之 间 的排斥 力来 选择 抗体 。在 用 AIA求 解优 化 问题 时 ，一
个抗 体用 一 个字 符 串表示 ，满足 约束 条件 的最 优解 即是 抗原 ，
候选 解即是 抗体 。抗 体 与抗原 之间 的亲 和力反 映 了候选 解与最
优解 的接 近程度 ，也 即反映候 选解 对 目标 函数 和约束 条 件 的满
足程度 ；抗体 与抗 体之 间 的排 斥力 反映 了不 同候 选解 之 间 的异
同 ，也 即反映 了抗 体 的多样性 。保 持抗 体 的多样 性 可 以防止 算
法陷 入局 部最 优解 。AIA具 有快 速 随机 的全 局搜 索 能力 ，但 对
于 系统 中的反馈 信 息利用 不 足 ，当求解 到一 定 范 围时往 往做 大
量无 为 的冗余 迭代 ，求 解效 率低 。
蚁 群 算 法 (Ant Colony Algorithm，ACA)是 由 意 大 利 学 者
M．Dorigo，A．Colorni，V．Manizzo等 在 9o年代 初 提 出来 的一 类 新
的模拟进化算法 ，它通过信息素的积累和更新来寻求最优解。
它 的特点 是模拟 自然界 中蚂 蚁的群 体行 为 。科学 家们 发 现 ，蚂
蚁有 能力 在没 有任 何提示 下 找到从 巢穴 到食 物源 的最 短路 径 ，
并 且能 随 环境 的变化 而 变化 ，适 应性 地 搜索 新 的路 径 ，产 生新
的选 择 。经研究 发 现 ，其根 本原 因是 蚂蚁在 寻 找食物 源 时 ，在 其
走过 的路 上释放 一 种特 殊 的分泌 物一 信 息素 ，后 来 的蚂蚁 选择
该路 径的 概率 与当 时这条 路 径上该 物质 的强 度成 正 比。当一定
基 金项 目 ：国 家 自然科学 基金 项 目(编号 ：10171095)；国家 863计划 重大专 项 (编号 ：2002AA103061)资助
作 者简 介 ：胡纯 德 (1973一)，男 ，硕 士研 究 生 ，主要 研 究 方 向为 算法 设 计 。祝 延 军 (1973一)，男 ，硕 士研 究 生 ．主 要研 究 方 向 为算 法 设 计 。高 随 祥
(1962-)，男 ，数学 系教授 ，主要研 究 方 向为组合 最优 化。
60 2O04．34 计 算 机工程 与应 用
维普资讯 http://www.cqvip.com
路 径上 通过 的蚂 蚁越 来越 多 时 ，其 留下 的信 息 素轨 迹也 越来 越
多 ，后 来 的蚂 蚁 选择 该 路径 的概 率也 越 高 ，从 而 更增 加 了该 路
径 的信 息 素强 度 。而强 度大 的信 息素会 吸 引更 多 的蚂蚁 ，从 而
形成 一种 正反 馈机 制 。通 过这种 正反 馈机 制 ，蚂 蚁最 终 可 以发
现最 短路 径 。特别 是 ，当蚂蚁 巢穴 与食物 源 之间 出现 障碍物 时 ，
蚂 蚁不仅 可 以绕 过障 碍物 ，而且通 过蚁 群信 息素 轨迹 在 不 同路
径 上的 变化 ，经 过一 定时 间的正 反 馈 ，最 终收 敛 到最 短路 径 。
ACA具 有分 布 式并 行全 局搜 索 能力 ，但 由于 初 期信 息 素 匮乏 ，
致 使求 解速 度缓 慢 。
该 文提 出的算法 汲取 了人 工免 疫算 法和 蚁群 算法 的优 点 ，
采用人 工 免疫算 法生 成信 息素 分 布 ，利用 蚁 群算 法求 优 化解 ，
优 势互 补 ，在 收敛 速度 和寻 优能 力两 方面较 原 有算 法都 有 明显
改善 。当用 于求解 P问题时 ，该算法在 收敛速 度上优 于 ACA，
在 寻优 能 力上 优 于 AIA，是一 种收 敛速 度 和寻 优能 力都 比较好
的优 化方 法 。
2 基 于人工免疫算 法和蚁群算法 的混合算 法
2．1 算法 的设计 思想
基 于人工 免疫 算法 和蚁 群算 法 的混 合算 法 ，其 基本 思 想是
算 法前 过 程采 用 AIA，充分 利 用 AIA的 快速 性 、随机 性 、全 局
收 敛性 ，寻找 较 优 的可 行 解 ，算法 后 过 程 采 用 ACA，利用 前 过
程 中 AIA获得 的 较优 可行 解 ，产 生 初始 信 息素 分 布 ，然 后 充分
利用 ACA的 并行性 、正反 馈性 ，提 高求 解效 率 。
2．2 算 法中人工免疫算子 的构 造
人 工免 疫 算 子有 字 符换 位 算子 、字 符 串移 位算 子 、字符 串
逆转 算子 和 优质 字符 串的 保 留等几种 。对 于 TSP问题 ，AIA 的
人工 免疫 算 子的构 造如 下 ：
2．2．1 字 符 换位算 子 ，可 分为 单对字 符换 位算 子和 多对 字 符换
位算 子
单对 字 符换 位 操作 是 随 机取 两个 正 整数 i， (1
)，以一 定 的概率 P 交换 抗体 A：(c。，c ，? ，c )中的一对字符 c ，
cj的位 置 ；多 对 字 符换 位 操 作 是 预先 确 定一 个 正 整数 u ，在 抗
体 A：(c-，c2，? ，c )中 随机 取 r(1
操 作 。
2．2．2 字 符 串移位 算子 ，可 分 为单个 字符 串移 位算 子 和 多个字
符 串移 位 算子
单 个 字符 串移 位操 作 是 随机取 两个 正整 数 ， (1< ,j<-n，
i )，在 抗 体 A=(c-，c2，? ，c )中取 一 个 字 符 子 串 Al：(c ，c ，
?
， cJ．·，c，)，以一 定 的概 率 P；依 次 往右 移动 A。中的 各个 字 符 ，
最 右边 的一 个 字符则 移 动到最左 边 的位 置 ；多个 字 符 串移位 操
作 是预 先确 定一 个正 整数 u，，在 抗体 A=(c。，c ，? ，c )中随机 取
r(1
2．2_3 字 符 串逆转 算子 ，可分 为单 个字 符串逆 转 算子 和 多个 字
符 串逆转 算子
单 个 字符 串 逆转操 作 是 随机 取 两个正 整 数 i， (1< ， ≤n，
i≠ )，在 抗 体 A=(c一，c2，? ，c )中取 一 个 字 符 子 串 A1：(cf’c ，
?
， cj--，Cj)，以一 定 的概 率 P 使 A。中的 各 个字 符 首尾 倒 置 ；多
个 字 符 串逆 转操 作 是 预 先确 定一 个 正 整数 u ，在 抗 体 A：(c。，
C2，? ，c )中随机 取 r(1
2．2．4 优质 字符 串 的保 留。
如果 若 干个抗 体 与抗 原之 间 的亲和 力都很 大 ，且这 些抗 体
中包含 了一个 相 同的 字符 子 串 ，则 称这 个字 符 子串 为优 质 字符
串 。如果抗 体 中存 在优 质字符 串 ，则 在抗 体产 生过 程 中 以概 率
P。使该 优质 字符 串不 受破 坏 ，即把 该 优质 字符 串 当成 一个 字 符
看待 ，称 为优 质 字符 串的保 留。
2．3 算法基本 步骤
根据 该 文算法 的设 计思 想 ，其基 本 步骤 可描述 如下 ：
步骤 l输入 问题 和确 定抗 体 的编码 表示 。
输 入 问题 的 目标 函数 和约束 条 件 ，作 为 An 的抗 原 。AIA
的抗 体 采用 自然 数编码 方 式 ，一个 字符 串代 表一 个候 选解 。对
于 n个 城 市 的 TSP问题 ，设其 城 市编码 分别 为 l，2，? ，n，并 且
把 商人 出发 城市 编为第 l号 ，其 它城市 可随 意编 号 。把 这 n个
城 市 的编 号 任意 排 列成 一 个 长度 为 n的字符 串都 可 以形 成 一
个 抗体 ，因此抗 体空 间包 含 n!个抗 体 。为 了缩小 抗 体空 间 ，提
高搜索 效率 ，将 每个 人 工抗体 (字符 串 )的第 一个 字符 固定为 出
发城 市 的 编号 l。这 样 ，每个 抗 体 只 有 (n—1)个 字符 可 任 意 排
列 ，抗 体空 间就 只包 含 (n—1)!个抗 体 。
步 骤 2 产 生初 始抗体 并进 行 预处理 。
在 一 般 情况 下 ，可按 上 述抗 体 编码 方 式 ，在解 空 间 中随 机
产 生 Ⅳ个 抗 体作 为初 始 抗体 ，构成初 始 抗 体群 ，其 中 Ⅳ 为抗 体
群 中抗 体 的数 目。考 虑 到 TSP问题 的任 何一条 路径 都是 闭合 路
径 ，从 任一 城 市 出发 ，要 到达 的下 一 个 城市 选择 为 未 到过 的 城
市 中距 该城 市最 近 的一 个 。为 了提 高搜索 效率 ，先对 每 一个初
始抗体 进行 预处 理 ，然后 才开 始算 法的迭 代计 算 。 设 初始 抗
体 A=(cl’c2，? ，c )，其 中 cl：l(即 c。代 表 商 人 出发 城 市 的 编
号 )，对 A 进行 预处 理 的步骤 是 ：
(1)随机取 正整 数 r(1sr n)。若 I"--．--47l：l，则令 A ：(c l，c 2，
?
，
C t
n) ，转 (3)；若 ／'---．．．．47I≠1(1
(2)对初 始 抗 体 A 中 的 各 个 字 符 依 次 循 环 左 移 位 (J}一1)
次 ，每 次移 位 时 ，使 c 移 到 Ci(扛l，2，? ， —1)的 位置 ，且使 cI
移 到 c。的 位 置 。设 移 位 以后 初 始抗 体 A 变为 A ，则 A ：(cI，
c“ 一，c ，cl，c2，? ，c 1)。令 A -(c 1，c 2，? ，c )，其 中 C r1．=CI，余
类推 。
(3)随机 取 c ='-'----c 。，令 C：{c 2，c 一，c l，若对 C 中任一 个
元 素 c I，都 有 d(c ，c j)<-d(c ，c I)，c jEC，则 把 c f置 于 A 中
c m+-的位置 ，此 时 A 变 为 A ，令 A，，_(c 。，c ，? ，c )。然 后从 C
中删 除 元 素 c 再 取 c” ”。，重 复 上述 步 骤 ，直到 C 中 的元 素
全 部被 删除 为止 。设 这一 步完 成 以后 初始 抗体 A 变为 曰。
(4)对 初 始抗 体 B中 的各 个 字符依 次循环 右 移 位若 干 次 ，
直 到抗体 中第 一个 字 符为 l为止 ，移位 方法 与 (2)中 的类似 ，但
方 向相反 。
步 骤 3 计算 亲 和力 和排斥 力 。
对 于 TSP问 题 ，可 定 义 抗 体 B与 抗 原 G之 间 的 亲 和 力
App(曰)：l／( )。其 中 ， 分 别为抗 体 曰与抗 原 G对应 的
旅行 路线 的总 长度 ， 也 是所 求 的最 短路 线 的总长 度 。因在计
算 结束 之前 并不 知 道 的大 小 ，可用 一适 当大 的正 数 (
)代替 。又 因计算 App(曰)需 作 除法运 算 ，可定 义 App(曰)：
。 其 中 为较 大 的正 数 ，且要 求 大于 任意抗 体 对应 的
旅行 路线 的总 长度 ，则 可避 免 在计算 App(曰)时 作除 法运 算 。因
此 ，构造抗 体 曰与抗 原 G之 间 的 亲和力 App(曰)： 并 计 算
App(B)。抗 体 与抗 原 之 间的 亲和 力反 映抗 体 与抗 原 之 间的 匹
配程度 ，App(曰)越大 ，说 明抗体 曰与 抗原 G之 间的匹 配 越好 。
对 于 TSP问题 ，可 定 义抗 体 曰。与 抗 体 曰：之 间 的 排 斥 力
Re P(B-，B2)：I 一 『并计算 Re P(B。，B2)。其 中 ， 分别 为
计 算 机工程 与应 用 2004．34 61
维普资讯 http://www.cqvip.com
抗体 日。与抗 体 日 对应 的旅 行 路线 的总 长度 。抗 体 与抗体 之 间
的排 斥 力反 映抗 体 与抗 体之 间 的差 距 ，Re P(B。，B2)越 大 ，说 明
抗 体 日。与抗 体 之 间 的差距 越大 。计算 抗体 群 中所有抗 体 与
当前最 佳抗 体之 间的 排斥力 。
步 骤 4 产 生新抗 体并 计算 其 亲和力 和排 斥力 。
构 造适 当的人工 免疫 算子 ，通过 人工免 疫算 子 的作 用概 率
P ，p。，p ，P。和 预先确 定 的正 整数 ，Us，u 产生 新抗 体 ；同 时 ，计
算 各 个 新抗 体 的亲 和力 App (日)和 新抗 体 间 的排 斥 力 Re P
(日。， )。若 新抗 体 中有与抗 原 相 匹配 的抗 体 ，或 已满 足预定 的
停机 条件 则停 机 ，从 而获得 较优 的可 行解 。否 则转 步骤 5。
步骤 5抗 体 选择 。
按照 “优胜劣 汰 ”的 自然 选择 机制 ，在 新产 生 的若干 个抗 体
中 ，选 择 出 Ⅳ个 与抗 原 匹配 得 较好 的抗 体 构成 新 的抗 体 群 ，转
步骤 4。
步 骤 6初 始 化 参数 T T m、P、d、13、Q，根据 步 骤 4获得
的较 优 可行 解 ，生 成信 息 素初 始分 布 ，将 m 只蚂 蚁 置于 n个结
点 。
这 里 ， 是一 个 根 据具 体 求 解规 模 给 定 的 信息 素 常 数 ，T。
是 AIA求 解 结 果 转 换 的 信 息 素值 ，m 是蚁 群 中蚂 蚁 的 数量 ，P
(O~p<1)为信 息 素轨迹 的残 留系 数 ，a(ct->0)为边 (i )信 息 素
轨 迹 强度 的 相 对重 要 性 ，13(P->0)为边 (iJ)能 见度 的相
对重要性 ， 为边 (i√)长度 喀的倒数 ，Q为蚂蚁循环一周所释
放 的总 信息 量 。在 初 始时 刻 ，根据 下式设 置 信息 素 的初 值 ：
)={ ’若 步骤 的较锕行路径上。
步 骤 7计 算 每 只蚂蚁 的选 择 概 率 ，根 据选 择 概 率移 动 每
只蚂蚁 到下 一结 点 。
设蚂蚁k在t时刻的转移概率为P：(t)，可行顶点集为 ，
则 按下 式 的概率 转移规 则决 定 t时刻 蚂蚁 k由位置 i转移 到 位
置J：
f』也血 ，若
P：(￡)={∑【T (￡)】 【 (￡)】 l
f
【 0， 否则
步骤 8 经过 n个时 刻 ，m 只蚂蚁 遍 历个 结 点 ，完 成一 次 循
环 。
设△T：为蚂蚁k在本次循环中在边(i√)上留下的单位长
度 轨迹 信息 量 ， 为蚂 蚁 k在本 次循 环 中所 走路 径 的长度 。此
时 ，根据 下式 对各个 路径 信 息素 更新 ：
(f+1)=p (￡)+△
其中，△T ∑△t，
．
f ，若蚂蚁k在本次循环中经过边( √) △ l l
- ,k
l0。 否则
步 骤 9 进 行递归 循 环 ，直 到满 足算法 的停 止条 件 为止 。
蚂蚁 完成 一 个搜 索 周期 ，进入 下一 个循 环 。反 复进行 递 归
循 环 ，直到 周 游计 数 器 (总循 环 次数 )NC达 到 预设 值 或所 有 蚂
蚁都 走 同一周 游路 径便 停止 计 算 ，输 出近似最 优解 。
3 仿真实验 ．
为 了验证 该算 法 的效 果 ，从 下面 两 个 TSP问题进 行 了仿
62 2004．34 计 算机 工 程与应 用
真 实验 ，都 取得 了 比较满 意 的结果 。
3．1 小规模 P问题 的实验 比较
以 9个 城市 的 TsP问题 为 例 ：设 9个城 市 为 1，2，3，4，5，
6，7，8，9。它们 之间 的距 离如 表 1所示 ：
表 1 9个城 市 之 间的距 离
AIA 中 ，有关 参数 取 为 ：p =0．2，P。=0．3，pi=O．4，p~--O．5，Uc=Us=
ui=[nl／4】，【·】表示 取 整 运 算 ，每 次抗 体 选 择 时保 留 与抗 原 匹配
得最 好 的抗 体 ，并 对 随机 产生 的初 始抗 体进 行 预处 理 ，递 归 迭
代 20次。ACA 中 ，有 关参 数取 为 ：xc~20，Tc=1，m=3，p=O．7，Or=
0．5，B=0．9，Q=100，蚁群总循环次数 NC=20。分别采用 AIA、
ACA和 该 算 法对 上 述 TSP问题 进 行 实 验 比较 ，重 复 运 行 10
次 ，计 算结 果如 表 2所 示 ：
表 2 小规模 P问曩 的 比较 结果
3．2 大规模 TSP问题的实验 比较
为 了更好 地 验证 、比较文 章 所提 出 的算 法 的效 果 ，选 用 通
用 的 TSPLIB(www．iwr．uniheideiberg．de／groups／comopt／software／
TSPLIB95)中 的 eil51TSP问题 为例 进行 仿真 实验 。
AIA 中，有关 参数 取 值 同上 ，每 次 抗 体选 择 时保 留与 抗 原
匹配得 最好 的抗 体 ，并 对 随机产 生 的初 始抗 体 进行 预 处理 ，递
归迭代 10000次 。ACA 中 ，Tc=100，T产4，其它 参数取 自文献【6】，
蚁 群总 循环 次数 ⅣC=510o00。分 别采 用 AIA、ACA和该 文算 法
对 e／／51TSP问题进 行实 验 比较 ，重 复运 行 20次 ，部 分搜 索结 果
取 自文 献【5】，计算 结果 如表 3所 示 ：
表 3 大规 模 TSP问题 的 比较结 果
从 表 2和 表 3中的实 验数 据 ，可 以清 楚地 看 到 ：该文 算 法
在 收敛 速度 上 明显优 于 ACA，在寻 优能 力上 明显优 于 AIA。
4 结 论
该 文 对于 TSP问题 的 求解 ，提 出 了一 种新 的 算法 一 基 于
人 工免疫 算法 和 蚁群算 法 的混 合算 法 ，经过 仿真 实 验 获得 以下
结 论 ：
该 算法 前过 程采用 人工 免疫 算 法生 成信 息 素分 布 ，算 法后
过 程 利用 蚁 群算 法 求 优化 解 ，汲取 了两 种算 法 的优 点 ，在 收敛
速 度 上 优 于蚁群 算 法 ，在 寻优 能力 上 优 于人 工 免疫 算 法 ，是 收
敛 速度 和 寻优能 力都 比较 好 的一种 新 的优化 方法 。
O
9 4 3 l 6 l 9 8 5 O
8 3 2 9 5 l 2 l O 4
7 6 ● 4 9 5 5 O 6
3
6 5 8 6 8 l O l l 9
5 7 l l 7 O 2 7 7 l
4 4 3 O l 3 8 8 5
3 l 7 O 9 6 7 8 3 6
2 3 O 5 l 6 4 7 l 3
2
l O 5 3 7 8 l 9 l 5
l 2 3 4 5 6 7 8 9
维普资讯 http://www.cqvip.com
(收稿 日期 ：2004年 7月 )
参考文献
1．Dorigo M ．Bonabeau E，Theraulaz G．Ant algorithm and stigmery[J]．
Future Generation Computer Systems，2OOO；16(8)：851-871
2．Tsai CF．Tsai CW ．A new approach for solving large traveling sales—
man problem using evolution ant rules[C]．In：Proc of the 20O2 Int．1
Joint Cod on Neural Networks．IJCNN 2002 Honolulu：IEEE Press，
V0l 2．20o2：1540-1545
3．Parpinelli RS，Lopes HS，Freitas AA．Data mining with an ant colony
optimization algorithm[J]．IEEE Trans on Evolutionary Computation，
20o2；6(4)：321-328
4．丁建立 ，陈增强 ，袁著祉．遗传算法与蚂蚁算法的融合叨．计算机研究
与发 展 ．2OO3；40 (9)：1351-1356
5．【日】Drik Slama，【美lJason Garbis，【澳]Perry Russel1．CORBA企业 解决
方 案【M】．北 京 ：机械 工业 出版社 ，200l
6．詹士昌，徐婕 ，吴俊．蚁群算法 中有关算法参数的最优选择叨．科技通
报 ，20o3；19(5)：381-386
7．丁永生，任立红．人工免疫系统：理论与应用叨．模式识别与人工智能，
2O00；l3(1)：52—59
8．李茂军，舒宜 ，童调生．旅行商问题的人工免疫算法[J]．计算机科学 ，
20o3：30(30)：8O一82
9．朱 燕 飞 ，蔡永 昶 ，李 中华 等 ．人 工免 疫算 法 在过 程 数据 分 析 中的 应 用
叨．计算机工程与应用。2004；40 (6)：205—2o7
lO．韩健 ，张乐，蔡瑞英．基于人工免疫算法的入侵检测系统叨．南京工业
大学 学报 (自然科 学 版 )，2004；26(1)：48-51
l1．郑 日荣 ，毛 宗 源．一 种 改进 的人 工 免疫 算 法【J】_计 算机 工 程与 应 用 ，
2003；39(33)：55-57
l2．王磊 ，肖人彬．基于免疫记忆的人工免疫算法模型及其应用【J】．模式
识 别与人 工智 能 ，2002；15(4)：385-391
(上 接 35页 )
s．t：A q．
1+GFSi+G 1+△ ， i=1，? ，T，q=l，? ，Q (9)
q厂 q． ．A q
．F一( ． )i=1，? ，T，q=l，? ，Q (10)
≥ W q
,
~-I+A口
． ‘
W q
,
r-~t·rq
．i--< 0
q厂( q 1+A q_厂 )+ ·rq．j≤ i=1，? ，T，q=l，? ，Q (11)
Gi∈z+，A ∈z+，Wq．i∈z+， ，‘∈z+，rq． ，1 (12)
初始 条件 Go=Gr+l--0，Wq．o=W口．r+|=O，k=l，? ，K；g=1，? ，Q
仍 成立 。
5 结 语
基 于需求 随机 的随 机样本 处理 方法 ，该 文 给 出了需 求随 机
型 单机 场 地 面等 待 问题 的具 体描 述 ，并 建 立 了 问题 的数 学模
型 ，而 且对该 模 型进行 了改 进 。相关定 理表 明 了该 文所 建模 型
的合 理性 和 正确性 。文 章的研 究结 果对 求解 空 中交 通 流量管 理
问题 有一 定参 考价值 。 (收稿 日期 ：2004年 8月 )
参考文献
1．Androatta G et a1．Aircraft Flow Management under Conges~on[J]．
Transportation Science，1987；(21)：2．19—253
2．Hoffman R．BaU M．A Comparison of Formulations for the Single-
Airport Ground Holding Problem with Banking Constraints[R]．Techni-
cal v~search repo rt。T R 98—44．Http：／／www．isr．umd．od u。1997
3．S Antonio Alonso。Laureano F Escudero ．Maria Teresa 01~01-no．A
Stochastic O—lPrngram Based Approach for the Air Traffic Flow
Management Problmn[J]．European Joumal of Operational Research，
2O00；l2O：47一Ir2
&Giovanni Andreatta，Lorenzo Bronetta，Gu#elmo Guastalla．From ground
holding to free flight：An exact approach[J]．Transportation Science。
2O00；34(4)：394— l
5．Hoffman R．Integer Programming Models for Groun d—Holding in Air
嘲 c Flow Manageme nt[D]．America：University of Maryland．1997
‘ ‘
(上 接 46页 )
其 中节点 可靠度 R~ -TAff／'BF，这里 为节 点工 作 周期 。计算
16取 12集群 系统 可靠 度 。M 在不 同工 作 周 期 内的 可靠 性 变
化 曲线如 图 4所 示 。
5 10 20 ×千小时
图 4 R 6／0 6时间 曲线圈
在 维修 周期 为 96小时 的情 况 下 ，维 修 周 期 内节点 可
靠度 为 — 栅 ，系统 可信度 D^ 为 ：
n
Dk／
n
=
i
n T
" (1 )
16取 12集群 系统 不问 断运 行 的可信度 D 为 ：
Dl2 6=0．999999998588
从可信度计算公式可以看到 ，D^ 仅仅和系统维修周期相
关 ，和 系统 工作 周期 无关 ，在 可维 护性 成立 的条 件 下 ，系统 在 整
个 生命周 期 内具备 不衰 退 的 、十 分可 观 的不间 断运 行 可信度 。
对 D。 的计算结 果 说 明 ，这 一系 统 在工 作过 程 中的 不 间断运
行 能力是 值得 信赖 的 。单 纯采 取可 靠性 措施 。很 难 达 到这一 指
标 。这就 是文 章基 于可信 度设 计 系统 的 目的。
7 结 论
事实上 ，单纯依赖多重冗余的高可靠设备构建关键实时计
算 系统 ，成 本 十 分 昂贵 。 以可 信度 理论 为指 导 ，综 合 采取 技 术
(故 障 沉默 和 恢 复等 )、后 勤保 障 (可 靠迅 速 的 备件 支援 )、人 员
(经过 培 训 的现 场 维 修人 员 )等 方 面 的措 施 ，用 一 般 商 业 化
(COTS)设备以低廉成本构建起来的实时集群系统 ，能够实现
关 键计 算应 用要 求 的苛刻 不问 断工作 能力 。除 了地面 系统 外 ，
这一技 术也适 应 于有后 勤储 备 的船载 实 时计算 系统 。
(收稿 日期 ：2004年 5月 )
参 考文献
1．Algirdas AvizVienis．LDs Angeles．Fundamental Concepts of Depend—
ability．http：／／www．celt．org／resoarch／isw／isw2000／papem／56．pdf
2．M girdas Avizqenis。Los Angeles．Fundamental Concepts of Co mputer
System Dependability．http：／／www．CS．vi~nia．edu／-jck／cs651／papers／
laprie．taxonomy．1~
3james L Peterson．Petri Net Theory and the Modeling of Systems．http：
／／www．cis．ulIIassd．edu／-hxu／courses／cis6ff2／papers／petrinel／
计 算机 工程 与应 用 2O04．34 63
维普资讯 http://www.cqvip.com
基于人工免疫算法和蚁群算法求解旅行商问题.pdf
