基于蚁群算法的多维0_1背包问题的研究

C o m p u t e rE n g i n e e r i n ga n dA p p l i c a t i o n s计算机工程与应用2 0 0 7,4 3(3 0) 1引言 背包问题是运筹学中一个典型的优化难题 8 , 是一个N P - 完全问题。对该问题求解方法的研究无论是在理论上, 还是在 实践中都具有一定的意义, 如资源分配、 投资决策、 装载问题、 网络资源分配等均可建模为背包问题 1 。求解背包问题的方法 主要有回溯算法、 贪婪算法、 遗传算法、 禁忌搜索算法、 模拟退 火算法等。 蚂蚁算法 (A n t C o l o n yA l g o r i t h m,A C A) 是一种源于大自然 的新型仿生类进化算法, 源于对蚂蚁觅食模型的研究。它是继 模拟退火、 遗传算法、 禁忌搜索等之后的又一启发式智能优化 算法。它由意大利学者D o r i g oM .等 7 首先提出, 在离散型组合 优化问题中表现突出, 成功地应用于求解T S P、 二次分配、 图着 色、 车辆调度、 集成电路设计及通信网络负载等问题。 蚂蚁算法 的基本思想是模仿蚂蚁依赖信息素 (p h e r o m o n e) 进行通信而显 示出的社会性行为, 在智能体 (a g e n t) 定义的基础上, 由一个贪 心法指导下的自催化 (a u t o c a t a l y t i c) 过程引导每个智能体 (a g e n t) 的行动 3 。它是一个随机的通用试探法, 是一个增强型学习系 统, 具有分布式的计算特性, 具有很强的通用性、 顽健性、 鲁棒 性, 易于与其它优化算法融合, 是基于总体优化的方法, 是解决 N P问题的有效工具。 本文提出一种基于蚁群算法求解多维0 - 1背包问题的算 法, 多维0 - 1背包问题蚁群算法。该算法对常规的蚁群算法进 行改进。它大大减少了蚁群算法的搜索时间, 有效改善了蚁群 算法易于过早地收敛于非最优解的缺陷。 仿真实验取得了较好 的效果。 2常规蚁群算法 (A S) 蚂蚁有能力在没有任何提示下找到从其巢穴到食物源的 最短路径, 并且能随环境的变化, 适应性地搜索新的路径, 产生 新的选择。根本原因是蚂蚁在寻找食物源时, 能在其走过的路 上释放一种特殊的分泌物- -信息素 (p h e r o m o n e) , 随着时间的 推移该物质会逐渐挥发, 后来的蚂蚁选择该路径的概率与当时 这条路径上该物质的强度成正比。 当一条路径上通过的蚂蚁越 来越多时, 其留下的信息素也越来越多, 后来蚂蚁选择该路径 基于蚁群算法的多维 0 - 1 背包问题的研究 汪采萍 1,2 , 胡学钢 1 , 王会颖 3 WA N GC a i - p i n g 1,2 ,H UX u e - g a n g 1 ,WA N GH u i - y i n g 3 1 .合肥工业大学 计算机与信息学院, 合肥2 3 0 0 0 9 2 .安徽职业技术学院, 合肥2 3 0 0 5 1 3 .安徽大学 计算机学院, 合肥2 3 0 0 3 9 1 . S c h o o l o f C o m p u t e rS c i e n c ea n dI n f o r m a t i o n,H e f e i U n i v e r s i t yo f T e c h n o l o g y,H e i f e i 2 3 0 0 0 9,C h i n a 2 . A n h u i V o c a t i o n a l a n dT e c h n i c a l C o l l e g e,H e i f e i 2 3 0 0 5 1,C h i n a 3 . S c h o o l o f C o m p u t e rS c i e n c e,A n h u i U n i v e r s i t y,H e f e i 2 3 0 0 3 9,C h i n a E - m a i l:w a n g c p 7 0 1 6 3 . c o m WA N G C a i - p i n g,H U X u e - g a n g,WA N G H u i - y i n g . O n mu l t i - d i me n s i o n 0 - 1k n a p s a c k p r o b l e m b a s e d o n a n tc o l o n y a l g o r i t h m. C o mp u t e rE n g i n e e r i n ga n dA p p l i c a t i o n s,2 0 0 7,4 3(3 0) :7 4 - 7 6 . A b s t r a c t:A n tc o l o n ya l g o r i t h m i sa n a l y z e da n do p t i m i z e di nt h i sa r t i c l e . A n e ws o l v i n g0 - 1k n a p s a c kp r o b l e m a l g o r i t h m,M u l t i - d i m e n s i o n0 - 1K n a p s a c kP r o b l e m A n tC o l o n yA l g o r i t h m(M K P A C A) ,i sp u tf o r w a r d . I tg r e a t l yr e d u c e st h es e a r c h i n gt i m eo fa n t c o l o n ya l g o r i t h m . I ta l s oe f f e c t i v e l ya m e l i o r a t e st h e d i s a d v a n t a g e o fe a s i l y f a l l i n g i n l o c a lb e s to fa n tc o l o n y a l g o r i t h m . T h e s i m u l a t i o nr e s u l t ss h o wt h a t t h ea l g o r i t h m i sm o r ee f f i c i e n t . K e yw o r d s:m u l t i - d i m e n s i o n0 - 1k n a p s a c kp r o b l e m;a n tc o l o n ya l g o r i t h m;M u l t i - d i m e n s i o n0 - 1K n a p s a c kP r o b l e m A n tC o l o n y A l g o r i t h m(M K P A C A) 摘要: 系统地阐述了蚁群算法, 并对它进行改进、 优化。将蚁群算法应用于求解多维0 - 1背包问题, 提出一种求解多维0 - 1背包 问题的算法多维0 - 1背包问题蚁群算法。 它大大减少了蚁群算法的搜索时间, 有效改善了蚁群算法易于过早地收敛于非最优 解的缺陷。仿真实验取得了较好的结果。 关键词: 多维0 - 1背包问题; 蚁群算法; 多维0 - 1背包问题蚁群算法 文章编号:1 0 0 2 - 8 3 3 1(2 0 0 7)3 0 - 0 0 7 4 - 0 3 文献标识码:A中图分类号:T P 3 9 1 基金项目: 安徽省自然科学基金 (t h eN a t u r a l S c i e n c eF o u n d a t i o no f A n h u i P r o v i n c eo f C h i n au n d e rG r a n t N o . 0 5 0 4 2 0 2 0 7) 。 作者简介: 汪采萍 (1 9 7 0 -) , 女, 副教授, 硕士研究生, 主要研究方向: 数据挖掘与人工智能; 胡学钢 (1 9 6 1 - ) , 男, 博士, 教授, 硕士生导师; 王会颖 (1 9 6 9 -) , 女, 硕士研究生, 主要研究方向: 智能软件、 群体智能。 7 4 2 0 0 7,4 3(3 0) 的概率也越高, 从而更增加了该路径的信息素强度。而强度大 的信息素会吸引更多的蚂蚁, 从而形成一种正反馈机制。通过 这种正反馈机制, 蚂蚁最终可以发现最短路径。 特别地, 当蚂蚁 巢穴与食物源之间出现障碍物时,蚂蚁不仅可以绕过障碍物, 而且通过蚁群信息素在不同路径上的变化, 经过一段时间的正 反馈, 最终收敛到最短路径上 4 。 T S P问题的描述为,已知n个城市及各城市间的距离, 求 一条经过各城市一次且仅一次的最短的回路。图论描述为,G = (V,A) ,V = v 1,v2, ,vn 是n个城市的顶点集,A = e i j| vi,vjV 是 V中各顶点相互连接组成的弧集,已知各城市间的距离d i j , 求 一条最短的H a m i l t o n回路。本文选用的实例是对称T S P问题, 即d i j= dj i。 以T S P为例说明常规蚁群算法 (A n t S y s t e m,A S) 。 设有n个城市,m只蚂蚁,任意两城市i,j之间的距离为 d(i,j) ,(i,j) 表示两个城市i,j之间信息素的浓度。初始时刻, 各信息素的浓度相同。蚂蚁k从一个城市i转移到另一个城市 j的转移概率的计算公式如式 (1) 。J(k) 为蚂蚁k在城市i时, 还没有访问的城市的集合。 启发函数(i,j)= 1 / d(i,j) 。、为 参数。 p k i j= (i,j) (i,j) (i,j) (i,j) s J(k) s J(k) 0其 # % % % % % $ % % % % % & 它 (1) (i,j)= (i,j)+ (i,j)(2) 信息素更新公式为式 (2) 。1 - (0 N c或当前解已稳定。 3多维0 - 1背包问题 多维0 - 1背包问题 (m u l t i - d i m e n s i o n0 - 1k n a p s a c kp r o b - l e m) 给出一套实体及它们的价值和尺寸, 选择一个或多个互不 相干的子集, 使每个子集的尺寸不超过给定边界, 而被选择的 价值总和最大。具体地, 给定m种资源 (如空间、 容积、 载量 等) , 各种资源的最大提供数量是c i,i = 1,2, ,m, 现将n种物 资装入背包,第j项物资占用第i种资源的数量是a i j,j = 1,2, ,n, 受益量 (p r o f i t s ) 是 p s j。 求一个二进制的向量X = (x 1,x2, , x n) , 使总受益最大。本质上, 这是一个整数规划: m a xf(x)= n j = 1 “xj p sj s . t . n j = 1 “xj ai jci,i = 1,2, ,m x j 0,1 ,j = 1,2, ,n 当m 2时, 称为多维0 - 1背包问题 1 。 4求解多维0 - 1背包问题的蚁群算法 在多维0 - 1背包问题蚁群算法 (M K P A C A) 中, 每种物资是 一个信息单位,信息素积累在物资上。设有n种物资,m类资 源,s只蚂蚁。一代迭代后, 每只蚂蚁形成一个可行解, 第 k只 蚂蚁形成的可行解以0、1形式存在向量 (x k 1,xk 2, ,xk n) 中,xk j= 1 表示在当前一代迭代中第k只蚂蚁选中物资j,x k j= 0表示在当 前一代迭代中第k只蚂蚁没有选中物资j。 引入一种受益量密度 j, 定义为物资单位总资源量的受益 量。 设第j项物资占用的总资源量为w j,wj= a1 j+ a2 j+ am j , 第 j项 物资的受益量为p s j, 则第j 项物资的受益量密度 j= p sj/ wj。 启发函数(j) 取为物资单位总资源量的受益量, 即受益量 密度 j, (j)= j= p sj/ wj。这样受益量越高同时消耗的总资源量越 小的物资, 启发函数(j) 的值就越大, 则该物资被选择的概率 就大,最终在相等的消耗限制下选取的物资的总受益量就越 大。物资j被蚂蚁k选择的概率, 按公式 (3) 计算。信息素的处 理方式为: 一代中仅对总受益量最大的蚂蚁所选择的物资进行 信息素的修改增加, 其余衰减, 更新公式为式 (2) 。 p j= j (t) (j) ,j = 1,2, ,n(3) 在式 (3) 中,j(t ) 为 t时刻在物资j上积累的信息素。在式 (2) 中, 当j属于一代中总受益量最大的蚂蚁所选择的物资时,(j)= Q * p s j/ l m b,l m b为这一代中最大的总受益量。 4 . 1分析及改进常规蚁群算法 上述常规蚁群算法A S中选择概率p k i j的大小主要依据两 个城市间信息素浓度(i,j) 和距离d(i,j) 。 第 (4) 步对信息素进 行全局更新, 在 (2)-(3) 步中, 信息素没有发生变化。 因此, 在第 (2) 步中, 各次按概率公式 (1) 计算转移概率p k i j, 概率大者仍然 大, 小者仍然小, 各概率的大小关系没有发生变化, 蚂蚁k按转 移概率p k i j大者选择的下一个城市j 也没有变化。 因而就没有必 要在选择下一个城市时都计算一下各城市的选择概率, 可以提 前统一计算。 上述常规蚁群算法A S中, 第 (4) 步, 信息素全局更新形成 正反馈机制, 为了增加搜索的随机性, 对第 (2) 步进行改进, 蚂 蚁k按 “轮盘赌 (r o u l e t t ew h e e l) ” 方式而不是按概率大者选择 下一个城市, 这样既兼顾了概率大小, 又增加了搜索的随机性, 有效改善了蚁群算法易于过早地收敛于非最优解的缺陷。 用蚁群算法求解多维0 - 1背包问题, 因为每种物资是一个 信息单位, 信息素积累在物资上, 蚂蚁k按转移概率选择下一 个物资, 主要是概率大小比较问题, 所以可以简化概率计算公 式, 去掉公式 (1) 中的分母, 采用公式 (3) 来计算物资的被选择 概率。这时各概率p j之和不再为1, 改变了概率之和为1的思 想。设概率之和为u, 又采用轮盘赌方法, 因此引入了概率之和 为u的轮盘赌r o u l e t t e - w h e e l(u) 。 其实现思想为: 生成一随机数 r,0 r u, 按轮盘赌方法, 根据r和各概率p j, 找到适合的物资 j, 蚂蚁k根据约束条件, 决定选择物资j或不选择物资j。多维 汪采萍, 胡学钢, 王会颖: 基于蚁群算法的多维0 - 1背包问题的研究7 5 C o m p u t e rE n g i n e e r i n ga n dA p p l i c a t i o n s计算机工程与应用2 0 0 7,4 3(3 0) 实例 w e i n g 1(m = 2,n = 2 8) w e i n g 6(m = 2,n = 2 8) w e i n g 8(m = 2,n = 1 0 5) w e i s h 0 8(m = 5,n = 4 0) w e i s h 3 0(m = 5,n = 9 0) p e t 5(m = 1 0,n = 2 8) p e t 5(m = 3 0,n = 4 0) s e n t 0 1(m = 3 0,n = 6 0) 各种资源的最大提供数量 (6 0 0,6 0 0) (5 6 2,4 9 7) (5 0 0,5 0 0) (4 8 0,7 6 0,8 0 0,1 1 8 5,1 2 0 0) (2 1 0 0,1 1 0 0,3 3 0 0,3 7 0 0,3 6 0 0) (9 3 0,1 2 1 0,2 7 2,4 6 2,5 3 2,5 7 2, 2 4 0,4 0 0,4 7 0,4 9 0) (3 3 1 7,1 8 8 0,2 7 4 0,4 3 1 0,2 6 8 1, 3 3 7 5,4 7 0 4,3 0 3 1,3 1 1 5,2 8 7 8, 2 6 0 9,3 3 2 1,4 1 4 2,4 6 7 0,2 1 3 0, 3 3 2 3,4 7 6 6,2 5 9 0,3 5 7 3,2 8 8 8, 3 5 7 8,3 4 7 8,4 1 8 9,1 7 4 8,2 0 3 9, 2 6 6 0,4 6 4 5,3 5 7 8,4 4 1 8,2 2 1 1) (6 0 0 0,6 0 0 06 0 0 0,6 0 0 0,6 0 0 0, 6 0 0 0,6 0 0 0,6 0 0 0,6 0 0 0,4 0 0 0, 6 0 0 0,6 0 0 0,6 0 0 0,6 0 0 0,6 0 0 0, 6 0 0 0,6 0 0 0,6 0 0 0,6 0 0 0,4 0 0 0, 6 0 0 0,6 0 0 0,6 0 0 0,6 0 0 0,6 0 0 0, 6 0 0 0,6 0 0 0,6 0 0 0,6 0 0 0,4 0 0 0) 最优时各类资源的总消耗 (5 9 5,5 9 4) (5 4 5,4 9 7) (4 9 4,4 9 8) (4 7 9,6 2 1,7 8 3,9 3 1,1 0 2 8) (1 7 7 7,1 1 0 0,2 2 5 9,2 2 3 2,2 4 1 8) (8 1 5,1 2 0 4,1 7 3,3 7 0,4 4 3, 4 6 9,1 4 6,3 2 3,4 5 3,4 9 0) (3 2 6 9,1 8 6 2,2 7 2 4,2 2 5 4,2 5 9 2, 2 2 4 8,3 7 6 9,1 0 7 6,2 1 8 4,8 2 2, 1 3 3 6,1 9 2 4,2 4 1 4,2 7 8 0,1 1 5 7, 2 3 8 7,1 0 4 5,2 4 5 5,2 0 2 9,1 0 0 5, 3 5 4 7,3 4 0 9,1 8 7 0,1 6 9 0,1 9 1 9, 2 0 8 5,1 7 8 3,1 0 0 3,1 6 6 5,1 4 4 2) (5 9 5 2,5 9 8 2,5 9 8 4,3 9 4 4,5 9 1 1, 4 8 7 3,5 0 6 5,4 0 4 5,5 0 6 9,1 9 4 4, 4 7 2 7,4 6 0 3,4 2 7 2,4 1 1 0,5 0 2 7, 5 0 6 4,2 2 7 9,5 8 6 5,4 4 5 6,2 1 1 7, 5 9 6 9,5 9 3 1,3 6 8 1,5 9 4 2,8 8 0, 5 4 2 5,3 1 3 8,3 4 2 5,3 2 4 7,3 2 3 1) 最优值 1 4 1 2 7 8 1 3 0 6 2 3 6 2 4 3 1 9 5 6 0 5 1 1 1 9 1 1 2 4 0 0 7 7 6 7 7 7 2 进化代数 1 0 3 1 3 7 2 3 7 7 9 表2求解多维0 - 1背包问题的蚁群算法 (M K P A C A) 求得的不同实例的结果 0 - 1背包问题蚁群算法, 在一代内, 各概率p j的计算次数为n 次, 而常规蚁群算法A S, 在一代内, 概率p k i j的计算次数为m * n * (n - 1)/ 2次。从而大大地减少计算量, 缩短了搜索时间。 4 . 2求解多维0 - 1背包问题的蚁群算法算法描述 根据上述分析、 优化, 提出多维0 - 1背包问题蚁群算法 (M K - P A C A) ,M K P A C A算法描述如下: (1) 初始化。 (2) 按概率公式 (3) 计算各物资被选择的概率p j,j = 1,2, ,n。每只蚂蚁k(k = 1,2, ,s) 随机选择一个物资h装入背包 作为初始,x k h= 1。 (3) 每只蚂蚁独立地构造一个解: 增加临时向量t e m p(j) , 1 j n, 初值和p j相同,u = u - t e m p (h) ,t e m p(h)= 0。 蚂蚁k按轮 盘赌r o u l e t t e - w h e e l(u) 选择下一个物资j,u = u - t e m p(j) ,t e m p(j)= 0, 测试物资j是否能装入背包,如果物资j装入后各类资源的总 消耗都不大于各种资源的最大提供数量c i, 则将物资j装入背 包,x k j= 1, 否则物资j 不能装入背包x k j= 0, 如此循环, 直到蚂蚁k 测试完所有的物资。 (4 ) 若 s只蚂蚁都构造完成各自的解, 则转 (5) , 否则转 (3) 。 (5) 找出这一代中总受益量最大的蚂蚁k, 按式 (2) 进行全 局信息素更新。 (6) 若满足结束条件, 则输出最优解, 否则G E N = G E N + 1, 转 ( 2) 。结束条件为G E N m a x G E N或当前解已稳定。 5仿真实验 实验采用文献 5 提供的比较经典的验证求解背包问题方 法的标准测试数据。文献 2 给出的例1,1 9 6 6年H . M a r t i nWe i n - g a r t n e r所举的成本预算问题中的一个实例, 就是w e i n g 1。实验 测试的部分结果如表2, 且对M K P A C A和A I A A C A 1 和A r 6 算 法 进 行 了 对 比 实 验 。 实 验 运 行 环 境 为 :I n t e l 4,C P U 2 . 2 6G, V B 6 . 0。 实验参数: 蚂蚁数s = 2 n, = 1, = 1, = 0 . 7,Q = 1, 最大进化代 数为5 0。对文献 5 提供的5 5个标准测试实例, 用多维0 - 1背 包问题蚁群算法 (M K P A C A) , 进行实验, 均较轻松求得其最优 值和最优解, 表2给出一些代表性实例的求解结果。 表2中, 最 优值为M K P A C A求得的最大总受益量,进化代数为求得最优 解时,算法迭代的最小次数。表1是1 0次连续试验的统计结 果, 其中:T表示获得最优解的次数,V a v e表示平均最优值, T a v 表示一代运行时间,T m i n,T m a x,T a v e分别表示获得最优解的 最少进化代数、 最大进化代数和平均进化代数。从表1可以看 出,M K P A C A的进化代数和每代的求解时间要好于 A I A A C A 实例 w e i n g 6 (1 3 0 6 2 3) m = 2 n = 2 8 w e i s h 0 8 (5 6 0 5) m = 5 n = 4 0 项目 T V a v e T a v T m i n T m a x T a v e T V a v e T a v T m i n T m a x T a v e M K P A C A 1 0 1 3 0 6 2 3 0 . 0 0 0 1 3 2 4 1 1 . 1 1 0 5 6 0 5 . 0 0 . 0 1 5 6 7 1 4 1 1 A I A A C A 1 0 1 3 0 6 2 3 0 . 0 4 2 6 1 3 4 2 1 9 . 9 1 0 5 6 0 5 . 0 0 . 0 6 3 2 1 7 2 5 2 2 A r 1 0 1 3 0 6 2 3 0 . 1 4 4 5 2 8 2 4 0 7 8 . 0 1 5 5 8 0 . 4 0 . 1 8 7 7 1 3 7 / / 实例 w e i n g 8 (6 2 4 3 1 9) m = 2 n = 1 0 5 w e i s h 3 0 (1 1 1 9 1) m = 5 n = 9 0 M K P A C A 1 0 6 2 3 4 1 9 0 . 2 1 8 7 1 3 1 8 1 5 . 6 7 1 1 1 8 9 . 3 0 . 1 2 5 0 2 3 3 2 2 6 . 5 A I A A C A 1 0 6 2 4 3 1 9 0 . 2 2 0 1 3 7 9 8 6 5 . 6 1 0 1 1 1 9 1 . 0 0 . 1 6 4 3 3 8 7 2 5 8 . 7 A r 0 6 0 8 3 6 0 0 . 2 1 5 5 / / / 0 1 0 2 8 8 . 0 0 . 1 8 7 7 / / / 项目 T V a v e T a v T m i n T m a x T a v e T V a v e T a v T m i n T m a x T a v e 表1 M K P A C A和A I A A C A、A r求解结果比较 (下转1 6 1 页) 7 6 2 0 0 7,4 3(3 0) (上接7 6 页) 和A r, 且表2中的进化代数也较小, 说明了多维0 - 1背包问题 蚁群算法 (M K P A C A) 求解的高效性。 表1和表2同样表明多维 0 - 1背包问题蚁群算法求解质量的有效性。 6结论 文章提出了多维0 - 1背包问题蚁群算法M K P A C A。将蚁 群算法应用于求解多维0 - 1背包问题, 并对常规蚁群算法进行 改进。 在M K P Q A C A中, 引入受益量密度的概念。M K P Q A C A通 过改变概率计算的时机,采用了简化形式的概率计算公式, 使 一代中概率计算的次数从m n(n - 1)/ 2次降低到n次, 大大地降 低了计算量, 大大减少了蚁群算法的搜索时间。 蚂蚁采用 “轮盘 赌” 方式根据概率p j选择下一个圆, 这样既兼顾了概率大小, 又增加了搜索的随机性, 兼顾解空间的多种情况, 有效改善了 蚁群算法易于过早地收敛于非最优解的缺陷。 仿真实验取得了 较好的结果。从理论研究蚁群算法, 将蚁群算法和其它算法融 合, 进一步改进算法, 是需要进一步研究的问题。 (收稿日期:2 0 0 7年3月) 参考文献: 1 杜海峰, 刘若辰, 焦李成, 等.求解0 - 1背包问题的人工免疫抗体修 正克隆算法 J .控制理论与应用,2 0 0 5,2 2(3) :3 4 8 - 3 5 2 . 2 姚瑞枫, 宋玉阶.多维0 - 1背包问题的混合遗传算法, 武汉科技大学 学报: 自然科学版,2 0 0 3,2 6(2) :2 1 4 - 2 1 6 . 3 忻斌健, 汪镭, 吴启迪.蚁群算法的研究现状和应用及蚂蚁智能体的 硬件实现 J .同济大学学报,2 0 0 2,6 0(1) :8 2 - 8 7 . 4 丁建立, 陈增强, 袁著祉.遗传算法与蚂蚁算法的融合 J .计算机研 究与发展,2 0 0 3,4 0(9) :1 3 5 1 - 1 3 5 6 . 5 G e o r gS . M p _ t e s t d a t a E B / O L . B e r l i n:Z u s eI n s t i t u t eB e r l i n,2 0 0 3 2 0 0 4 . h t t p:/ / e l i b . z i b . d e / p u b / P a c k a g e s / m p _ t e s t d a t a / i p / s a c 9 4 _ s u i t e / i n d e x . h t m l . 6 M i c h a l e w i c z Z . G e n e t i c a l g o r i t h m+ d a t a s t r u c t u r e = e v o l u t i o n p r o - g r a m s M . B e i j i n g:S c i e n c eP r e s s,2 0 0 0:5 9 - 6 5 . 7 D o r i g oM,G a m b a r d e l l aLM . A n t c o l o n ys y s t e m:ac o o p e r a t i v el e a r n - i n ga p p r o a c ht ot h et r a v e l i n gs a l e s m a np r o b l e m J . I E E ET r a n so n E v o l u t i o n a r yC o m p u t a t i o n,1 9 9 7,1(1) :5 3 - 6 6 . 8 S y s l oM M . D i s c r e t eo p t i m i z a t i o na l g o r i t h m s M . E n g l e w o o dC l i f f s,N e w J e r s e y:P r e n t i c e - H a l l,1 9 8 3:1 1 8 - 1 6 5 . 快速和成熟收敛, 在此基础上提出了基于免疫遗传算法的静态 环境下移动机器人全局路径规划的方法。 文章对算法进行了仿 真研究, 与遗传算法相比, 本文提出的方法在收敛速度和保证 成熟收敛上具有明显优势, 说明该方法是可行的、 有效的。 (收稿日期:2 0 0 7年4月) 参考文献: 1 K h a t i bO . R e a l - t i m eo b s t a c l ea v o i d a n c ef o rm a n i p u l a t o r sa n dm o - b i l er o b o t s J . I n t e r n a t i o n a l J o u r n a l o f R o b o t i c sR e s e a r c h,1 9 8 6,5(1) : 9 0 - 9 8 . 2 庄晓东, 孟庆春, 高云, 等.复杂环境中基于人工势场优化算法的最 优路径规划 J .机器人,2 0 0 3,2 5(6) :5 3 1 - 5 3 5 . 3 A l e x o p o u l o sC,G r i f f i nP M . P a t hp l a n n i n gf o ram o b i l er o b o t J . I E E ET r a n s a c t i o n so nS y s t e m s,M a na n dC y b e r n e t i c s,1 9 9 2,2 2(2) : 3 1 8 - 3 2 2 . 4 Wa n gC h u n - m i a o,S o hYC,Wa n gH a n,e t a l . Ah i e r a r c h i c a l g e n e t i c a l g o r i t h mf o r p a t hp l a n n i n gi nas t a t i ce n v i r o n m e n t w i t ho b s t a c l e s C / / I E E EC a n a d i a nC o n f e r e n c eo nE l e c t r i c a la n dC o m p u t e rE n g i n e e r - i n g,C a n a d a,2 0 0 2(3) :1 6 5 2 - 1 6 5 7 . 5 邢立宁, 陈英武, 蔡怀平, 等.求解全局优化问题的智能遗传算法 J . 系统仿真学报,2 0 0 6,1 8(4) :1 0 6 7 - 1 0 6 9 . 6 G o l d b e r gD E . G e n e t i ca l g o r i t h m si ns e a r c h,o p t i m i z a t i o n,a n dm a - c h i n el e a r n i n g M . B o s t o n,M A,U S A:A d d i s o n - We s l e yL o n g m a nP u b - l i s h i n gC oI n c,1 9 8 9 . 7 Z h uY o n g - j i e,C h a n gJ i a n g,Wa n gS h u - g u o . A n e w p a t h - p l a n n i n g a l g o r i t h mf o r m o b i l er o b o t b a s e do nn e u r a l n e t w o r k C / / I E E ER e g i o n T e n t h C o n f e r e n c e o n C o m p u t e r s,C o m m u n i c a t i o n s,C o n t r o l a n d P o w e rE n g i n e e r i n g . B e i j i n g,C h i n a:I E E E,2 0 0 2(3) :1 5 7 0 - 1 5 7 3 . 8 孙增沂.智能控制理论与技术 M .北京: 清华大学出版社,1 9 9 7 . 9 吕岗, 陈小平, 谭得健.免疫算法抗体浓度调节定义的改进 J .数据 采集与处理,2 0 0 3,1 8(1) :4 4 - 4 8 . 1 0 R u d o l p hG . C o n v e r g e n c ea n a l y s i so f c a n o n i c a l g e n e t i ca l g o r i t h m s J . I E E ET r a n s a c t i o n so nN e u r a l N e t w o r k s,1 9 9 4,5(1) :9 6 - 1 0 1 . 1 1 王磊, 潘进, 焦李成.免疫算法 J .电子学报,2 0 0 0,2 8(7) :7 4 - 7 8 . (上接9 3 页) 参考文献: 1 S c h e n aM,S h a l o nD,D a v i sR W,e ta l . Q u a n t i t a t i v em o n i t o r i n go f g e n ee x p r e s s i o np a t t e r n sw i t hac o m p l e m e n t a r yD N Am i c r oa r r a y J . S c i e n c e,1 9 9 5,2 7 0(5 2 3 5) :4 6 7 - 4 7 0 . 2 O l s o nCF . P a r a l l e la l g o r i t h m sf o rh i e r a r c h i c a lc l u s t e r i n g J . P a r a l l e l C o m p u t i n g,1 9 9 5,2 1:1 3 1 3 - 1 3 2 5 . 3 C h i uSL . F u z z ym o d e li d e n t i f i c a t i o nb a s e do nc l u s t e re s t i m a t i o n J . J o u r n a l o f I n t e l l i g e n t a n dF u z z yS y s t e m s,1 9 9 4,2(3) :2 6 7 - 2 7 8 . 4 陈国良.并行算法的设计与分析 M .北京: 高等教育出版社,2 0 0 2 . 5 B e z d e kJC . P a t t e r nr e c o g n i t i o nw i t hf u z z yo b j e c t i v ef u n c t i o na l g o - r i t h m s M . N e wY o r k:P l e n u m P r e s s,1 9 8 7 . 6 L iK L,L iQ H,L iR F . O p t i m a lp a r a l l e la l g o r i t h m f o rt h ek n a p - s a c kp r o b l e m w i t h o u tm e m o r yc o n f l i c t s J . J o u r n a lo fC o m p u t e rS c i - e n c ea n dT e c h n o l o g y,2 0 0 4,1 9(6) :7 6 0 - 7 6 8 . 7 L iX . P a r a l l e la l g o r i t h m sf o rh i e r a r c h i c a lc l u s t e r i n ga n dc l u s t e r i n g v a l i d i t y J . I E E ET r a n sP a t t e r nA n a l y s i sa n dM a c h i n eI n t e l l i g e n c e, 1 9 9 0,1 2:1 0 8 8 - 1 0 9 2 . 8 H e r r e r oJ . A h i e r a r c h i c a lu n s u p e r v i s e dg r o w i n gn e u r a ln e t w o r kf o r c l u s t e r i n gg e n ee x p r e s s i o np a t t e r n s J . B i o i n f o r m a t i c s,2 0 0 1,1 7(2