（计算机软件与理论专业论文）免疫进化算法在函数优化中的应用.pdf

摘要 函数优化问题( f u n c t i o no p t i m i z a t i o np r o b l e m s ，f o p s ) 是 科学和工程应用领域经常会遇到的一类数学规划问题，因而对其研究 具有十分重要的理论和实际意义。免疫算法( i m m u m ea l o g i t h m s ) 是基 于近年来新兴的计算智能一一人工免疫系统( a r t i f i c i a li m m u n e s y s t e m s ) 平台而发展起来的一类仿生算法。进化算法( e v o l u t i o n a r y a l g o r i t h m s ，e a s ) 是一类模拟自然进化机制而发展起来的随机搜索 算法。近年来免疫进化算法已被广泛地应用于函数优化问题，并提出 了大量的函数优化方法。 本文首先介绍了免疫算法的生物背景、相关理论及其应用。接着 描述了进化计算的起源、发展、三个主要分支( 即遗传算法、进化规 划和进化策略) 及其应用领域，然后提出了两种不同的免疫进化算法。 本文主要工作如下： 1 ) 提出了一种新的免疫进化算法，该算法针对克隆选择算法在 求解高维函数优化问题时，易陷入局部最优以及收敛速度较慢的弱 点，提出了基于生物免疫系统内部学习优化机制以及进化算法的免疫 进化算法。它包括：正交交叉、单形交叉、克隆、多极变异、选择。 新算法将进化计算的思想融入到克隆选择中，提出了一种新的变异算 子，在保证种群多样性的同时提高了算法的全局寻优能力。理论分析 证明了算法的收敛性，并将算法应用于不同的测试函数进行仿真实 验，结果表明该算法是有效的。 2 ) 基于免疫算法与差异进化算法，提出了一种新的基于局部搜 索机制的免疫进化算法。该算法首先初始化种群；接着采用单形交叉 算子来对当前群体进行交叉操作；为了提高算法的局部搜索能力，提 高其收敛速度，提出了一种新的差异进化算法，然后结合新的差异进 化策略设计了局部搜索算子，最后借鉴免疫算法的更新策略更新种 群，理论分析证明了算法的收敛性，并通过不同的测试函数验证了算 法的可行性和有效性。 关键词免疫进化算法，函数优化，全局搜索，局部搜索 a b s t r a c t f u n c t i o n o p t i m i z a t i o np r o b l e m s ( f o p s ) b e l o n gt o ak i n do f m a t h e m a t i c a lp r o g r a m m i n gp r o b l e m s ，w h i c ha r ef r e q u e n t l ye n c o u n t e r e d i nt h ed i s c i p l i n e so fs c i e n c ea n de n g i n e e r i n ga p p l i c a t i o n s ot h es e a r c ho n i ti si m p o r t a n ti nt h e o r e t i c sa n dp r a c t i c e i m m u n ea l g o r i t h m s ( i 触) a r ea k i n do fs i m u l a t e dn a t u r e a l g o r i t h m s ( s n a s ) ，w h i c hd e v e l o p e db y a r t i f i c i a li m m u n es y s t e m s - 一ak i n do fc o m p u t a t i o ni n t e l l i g e n c et h a t r e c e n t l yn e wd e v e l o p e d e v o l u t i o n a r ya l g o r i t h m s ( e a s ) a r eak i n do f r a n d o m l ys e a r c ha l g o r i t h m ，w h i c hs i m u l a t e st h ep r o c e s so fn a t u r a l e v o l u t i o n d u r i n gt h ep a s td e c a d e ，i m m u ee v o l u t i o n a r ya l g o r i t h m s ( i e a s ) h a v eb e e nb r o a d l ya p p l i e dt os o l v ef o p s ，a n dc o n s i d e r a b l ef u n c t i o n o p t i m i z a t i o na l g o r i t h m s ( f o a s ) h a v e b e e np r o p o s e d f i r s t l y , t h i sd i s s e r t a t i o ni n t r o d u c e st h eb i o l o g yb a c k g r o u n d ，r e l a t i v e t h e o r ya n da p p l i c a t i o n so fi a s t h e n ，t h i sd e s c r i p t i o no ft h eo r i g i n ， a d v a n c e ，t h r e em a i nb r a n c h e s ( i e g e n e t i ca l g o r i t h m s ，e v o l u t i o n a r y p r o g r a m m i n ga n de v o l u t i o n a r ys t r a t e g i e s ) a n da p p l i c a t i o n so fe a si s g i v e n a f t e r w a r d s ，t w oi m m u n ee v o l u t i o n a r ya l g o r i t h m sp r o p o s e db y a u t h o r t h em a i nc o n t r i b u t i o na n dw o r ka r ed e s c r i b e da sf o l l o w i n g ： 1 ) t h ea l g o r i t h m ，w h i c hc o n s i d e r i n gt h ed r a w b a c ko fe a s i l yb e i n g t r a p p e di n al o c a lo p t i m a ls o l u t i o na n ds l o wc o n v e r g e n c ev e l o c i t yo f c l o n es e l e c t i o no fi m m u n e a l g o r i t h m ，w a s n a m e dn e wi m m u n e e v o l u t i o n a r ya l g o r i t h m ( n i e a ) w h i c hp r o p o s e db yt h eb a s e m e n to nt h e i n t e r i o rs t u d ym e c h a n i s mo fb i o l o g i c a li m m u n es y s t e ma n de v o l u t i o n a r y a l g o r i t h m t h en e wa l g o r i t h mi n c l u d e do r t h o g o n a lc r o s s o v e r , s i m p l e x c r o s s o v e r , c l o n e ，m u l t i p o l a r - m u t a t i o n a n ds e l e c t i o n t h ei d e a o f e v o l u t i o n a r yc o m p u t a t i o nw a si n t e g r a t e di n t oc l o n es e l e c t i o na n dan e w m u t a t i o no p e r a t o rw a sp r o p o s e d t h i sn e wa l g o r i t h mc a ng u a r a n t e et h e d i v e r s i t y o ft h ep o p u l a t i o na n d i m p r o v et h eg l o b a l s e a r c h a b i l i t y t h e o r e t i c a la n a l y s i sp r o v e dt h a tn i e a c o n v e r g e st ot h e # o b a lo p t i m u m d i f f e r e n tf u n c t i o n sw e r eu t i l i z e dt ot e s tt h i sm e t h o da n dt h es i m u l a t i o n r e s u l t ss u g g e s tt h a tt h i sa l g o r i t h mh a sg o o dp e r f o r m a n c e 2 1 ) p r o p o s e dn o v e l i m m u n ee v o l u t i o n a r ya l g o r i t h mb a s e do nl o c a l s e a r c hm e c h a n i s m ( i e a l s n ) b a s e do ni m m u n ea l g o r i t h ma n dd i f f e r e n t i a l e v o l u t i o na l g o r i t h m f i r s t l y , i n i t i a lp o p u l a t i o ni s r a n d o m l yg e n e r a t e d s e c o n d l y , s i m p l e xc r o s s o v e ro p e r a t o ri s u s e dt op o p u l a t i o nt og e n e r a t e o f f s p r i n g a f t e rt h a tal o c a ls e a r c hm e c h a n i s mi sd e s i g n e dt oi m p r o v et h e a b i l i t yo fl o c a ls e a r c h a n dt h e s p e e do fc o n v e r g e ，w h i c h c o n t a i n s c l u s t e r i n g a n dan e wd i f f e r e n t i a l e v o l u t i o n a r y ( n d e ) t h e o r e t i c a l a n a l y s i sp r o v e dt h a ti e a l s nc o n v e r g e st ot h eg l o b a lo p t i m u m t h e n ，t h e u p d a t i n gm e t h o do fi m m u n ea l g o r i t h mi su s e dt ou p d a t ep o p u l a t i o n d i f f e r e n tf u n c t i o n sw e r eu t i l i z e dt ot e s tt h i sm e t h o da n dt h es i m u l a t i o n r e s u l t ss u g g e s tt h a tt h i sa l g o r i t h mh a sg o o df e a s i b i l i t ya n d p e r f o r m a n c e k e yw o r d si m m u n ee v o l u t i o n a r ya l g o r i t h m ，f u n c t i o no p t i m i z a t i o n ， g l o b a ls e a r c h ，l o c a ls e a r c h m 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。 作者签名：望二墨日期：塑盟年互月丝日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：盟导师签名兰殛日期：丛年互月盟日 硕+ 学位论文 第一章前言 第一章前言 1 1 课题研究背景 1 1 1 全局优化问题的概述 优化技术是一种以数学为基础，用于求解各种实际问题的应用技术。它广泛 应用于工业、农业、国防、工程、交通、金融、化工、能源、通信等许多领域。 优化作为人们一个强有力的思想方法，迅速发展成为- f q 重要的应用数学学科， 并且与分析、几何、代数、概率及计算机科学、系统科学、自动化等有密切联系， 同时相互促进。在经济、金融、工程技术、分子生物、现代化管理、信息与控制 等领域经常会遇到复杂的全局优化问题这些问题的数学模型可描述为 m i n f o ) 锄 其中x 称为决策变量，d c 掣称为可行域，称为目标函数，构成d 的条件 g f o ) s0 ，f = 1 ，2 ，m 称为约束条件。当d1r “时称为无约束优化问题。对于 x d 如果j 6 0 ，使得y x d n u o ，6 ) 都成立f ( x ) sf ( x ) ，称x 为，在d 上 的局部最优解，相应地f ( x _ ) 称为局部最优值。对于z e d ，如果对v x e d 都成立 厂o ) sf ( x ) 称为x 。为，在d 上的全局最优解，相应地f ( x ) 称为全局最优值。 寻找目标函数全局最优解的问题称为全局优化问题。当，o ) 和& o ) ，f 一1 ，2 ，m 都是凸函数时，问题称为凸规划问题，此时只需通过求解其k i t 系统即可获得问 题的全局最优解，问题相对简单。但只要厂o ) 或o ) ，f - 1 ，2 ，m 中至少有一个 非凸，问题即成为非凸规划问题，此时k t t 系统的解只是优化问题的一个稳定点， 一般情况下它未必是全局最优解，甚至连局部最优解都不是。当f ( x 、或 g i ) ，f = l 2 ，m 中至少有一个不可微分时，问题称为非光滑优化问题。 许多工程实践中遇到的问题可能更加复杂，它们通常具有精确建模困难、数 据有噪声、时变等特征，即使建立出相应的数学模型，其目标函数仍具有多峰、 非凸、非光滑等特点。传统的优化方法通常需要求解目标函数的梯度( 甚至h e s s e n 矩阵) ，因而很难处理。如何有效地求解这些全局优化问题己经成为影响这些领 域发展的关键因素之一。寻求一种适合此类问题的算法已成为最优化方法的一个 主要研究目标和引人注目的研究方向。 本文主要研究连续变量的全局优化问题 吨，0 ) 矩西。、 其中d 满足边界约束，d 一缸e r “i z sx s h ) ，x 一瓴，x 2 ，毛) ，zi “，2 ，厶) r ， 硕十学位论文 第一章前言 跖； ，“：，u 。) ，厂为目标函数，并且总假定厂在d 上存在有限的全局最优解。 传统的优化方法大多数属于局部优化方法，一般只能得到问题的一个局部最 优解，甚至只是一个稳定点，因而并不能使工程实践中遇到的问题得到满意的解 决。从上世纪6 0 年代，人们便开始了对全局优化问题的专门研究。尤其是近些年 来，计算机技术的飞速发展，使得全局优化方法成为人们研究实际问题时进行建 模和分析的重要手段之一。经过几十年的努力，在理论和算法方面都取得了很大 的发展，使全局优化发展成为最优化学科领域中的一个重要分支。 全局优化方法可以分为两大类确定性方法和随机性方法常见的确定性全局 优化方法包括区间分析法( i n t e r v a la n a y l s i s ) 、分支定界法( h o m o t o p ym e t h o d s ) 、填 充函数法( f i l l e df u n c t i o nm e t h o d ) 、同伦方法( h o m o t o p ym e t h o d s ) 、轨道法( t r a j e c t o r y m e t h o d s ) 等等。这些方法通常将句题转换为一系列的子问题，然后反复调用传统 的局部优化算法来求解这些子问题，以实现向全局优化目标的逼近，这些方法通 常有比较好的理论结果( 收敛性及收敛阶) ，但由于它们对子问题求解的结果依 赖性较强，仍然需要使用目标函数的梯度，算法设计复杂，求解代价也比较高， 容易陷入局部最优。尤其当问题规模增大，极小点数目增多时，这些方法仍然难 以找到问题的全局最优解，实际求解效果有时并不理想。常见的随机性全局优化 方法包括进化算法( e v o l u t i o n a r ya l g o r i t h m ，e a ) 、蚁群算法( a n tc o l o n yo p t i m i z a t i o n ) i t 】、人工神经网络算法( a r t i f i c i a ln e u r a ln e t w o r ) 、模拟退火算法( s i m u l a t e d a n n e a l i n g ) 、改进的击跑配合算法( i m p r o v i n gh i t a n d r u n ) 】、禁忌搜索算法( t a b u s e a r c h ) 等等，这些方法经过不断改进，逐渐成为解决复杂优化问题的一类有效方 法【2 1 。 其中，进化计算饵a ) 是一类以自组织、自适应、自学习、并行性为主要特征 的仿生随机算法，是一种现代优化方法【3 j 。e a 自2 0 世纪6 0 年代产生以来，在近几 十年里取得了辉煌的成就，涌现出一批卓有成效的进化算法。e a 的主要分支有 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 演化策略( e v o l u t i o ns t r a t e g y , e s ) 进化规划 ( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 和遗传程序设计( g e n e t i cp r o g r a m m i n g ，g p ) 等等。 编码方式是研究e a 的基础，也是影响其算法性能的关键因素之一。e a 的编 码方式有多种形式，如二进制编码、格雷编码、符号编码、实数编码等等许多研 究结果都表明离散问题( 如：组合优化问题) 比较适合采用二进制编码、符号编 码等方式进行编码，而连续空间问题( 如：连续变量优化问题) 比较适合采用实 数编码方式进行编码。由于本文主要研究连续变量的全局优化问题，因而本文主 要研究实编码进化算法( r e a l c o d e de v o l u t i o n a r ya l g o r i t h m s ，r e a s ) 。r e a s 由于其运 算简单( 不需要编码和解码过程) 、稳定性好、便于高精度计算、便于与传统算法 融合，因而在科学研究和工程技术中得到了广泛应用。 2 硕士学位论文第一章前言 不同的编码方案、繁殖算子和选择算子相结合构成不同的进化算法。r e a s 的编码方式已确定( 实数编码) ，因而不同r e a s 的主要区别在于它们的进化算子 ( 包括繁殖算子和选择算子) 。不同r e a s 的进化算子可能有很大差别，但它们算法 结构都比较简单，可以统一在一个算法框架下：首先，随机产生初始种群为x ( 0 ) ， ( 随机选取若干个点构成初始点集合) ，然后对当前种群x o ) ( f 苫0 ) 应用进化算子 ( 对当前点集中的点进行某种启发式变换) g z 成中间种群x o ) ，随后对x o ) ，x o ) 中的个体进行评价，根据评价结果( 通常较好的个体有较大的生存机会) 实施选 择，生成下一代种群x ( t + 1 1 ，直到满足一定的算法停止条件。 设待优化问题为m i n 厂伍) ，实编码进化算法( r e a ) 可简单描述如下： p r o c e d u r er e a ： s t e p1 ：i n p u te v o l u t i o n a r yp a r a m e t e r s ：p o p u l a t i o ns i z en i n i t i a l b o u n d so fv a r i a b l e sz ，u ，s e tt = 0 ；i n i t i a l i z ep o p u l a t i o n x ( o ) = 五( o ) ，x ：( 0 ) ，以( o ) 】，w h e r e 置( o ) 一“1 ，而，毛一) ； s t e p2 ：r e p e a t - - r e p r o d u c t i o n ：g e n e r a t ean e wp o p u l a t i o nx 。( t ) b a s e do nx ( t ) ，i e ，f o r e v e r yi n d e xi e q 2 ，n ) i nt h ep o p u l a t i o n ， z o ) = g ( 置o ) ，o ) o ) ，z _ o ) ) ； 一 _ e v a l u a t i o n ：e v a l u a t ep o p u l a t i o n sx ( t ) a n dx 。o ) ，i e ， c o m p u t ei ( x fo ”，( x ：o ) ) f o re a c hi n d i v i d u a l ； s e l e c t i o n ：s e l e c tt h ep o p u l a t i o nf o rn e x tg e n e r a t i o nx ( t + 1 ) ，i e ， s e l e c tni n d i v i d u a l sa m o n g x ( t ) a n dx ( f ) ； 坠望垡! 苎q 里皇兰! q 巳巳! 里g 堡堕! 璺堕旦里! 墨兰璺垡苎旦呈堕： 图1 1 实编码进化算法 1 1 2 免疫算法 生物免疫系统是一种复杂的自适应系统，有效地使用多种机制防御外部病原 体。生物免疫系统的主要作用是识别所有生物体内的细胞，并将其分类为自体和 非自体。为了诱导合适形式的防御机制，非自体细胞进一步分类。通过进化学习， 免疫系统在外部病原体和生物体自己的细胞之间进行辨别【4 】。生物免疫系统的重 要生理功能就是对“自己 和“非己 的抗原的识别和应答，它有着自身的运行 机制，并可与其它系统相互配合、相互制约，共同维持机体在生命过程中总的生 理平衡，具体表现为免疫防御、免疫监视、免疫自稳等生理功能。生物免疫系统 在运行中表现出很多智能特性，如对各种抗原的识别和应答过程实际是就是一个 进化学习的过程。通过研究生物免疫系统识别“自己 和“非己一以及产生抗体 3 硕七学位论文 第一章前言 对抗外界抗原的过程，研究人员提出了基于免疫原理的人工智能方法，如人工免 疫算法( a i a , a r t i f i c i a l l m m u n ea l g o r i t h m ) 等。人工免疫算法中的克隆选择算法 给了我们很大的启示。 克隆选择算法是f l 了d ec a s t r o 以及k i m 等提出的1 5 1 ，其灵感来自生物获得性免 疫的克隆选择原理。克隆选择算法模拟生物免疫系统的克隆选择原理，在生物免 疫系统中，一旦病原体侵入肌体就被分解为抗原片段，b 淋巴细胞能够为产生相 应的抗体与抗原结合，同时活化、增殖和分化，产生浆细胞，通过中和、溶解和 调理等作用，最终使抗原从体内消除。另有一些b 淋巴细胞变成了长期存活的记忆 细胞，它通过血液、淋巴和组织液循环，为下一次快速、高效地消除相同或者类 似抗原引起的感染奠定了基础。 人工免疫算法保留了生物免疫系统的若干特点，如多样性好、鲁棒性强、隐 含并行性等，同其他启发式优化算法相比具有自身的特点和优势，在近几年引起 相关研究人员的普遍关注，并在模式识别、故障诊断、计算机安全等领域得到实 际应用。然而，同其他新型智能算法类似，人工免疫算法也存在一些不足，如存 在早熟收敛、局部搜索能力不足等，对人工免疫算法的深入研究和改进研究，已 经成为优化计算领域的一个重要研究课题。 1 1 3 进化算法 进化算法e a ：( e v o l u t i o n a r ya l g o r i t h m ) 的起源可追溯到5 0 年代末7 0 年代以 来产生了几种进化方法如：遗传算法g a ( g e n e t i ca l g o r i t h m ) 、进化规划e p ( e v o l u t i o n a r yp r o g r a m m i n g ) 、和进化策略e s ( e v o l u t i o ns t r a t e g y ) e a s 是一 类模拟生物进化过程与机制求解问题的自组织、自适应人工智能技术，是一种具 有“生成+ 检测 的迭代搜索算法。进化算法是模拟由个体组成的群体的集体学 习过程，其中每个个体表示给定问题搜索空间中的一点，进化算法从任一初始的 群体出发，通过随机选择( 在某些算法中是确定的) 变异和交叉( 有时被完全省 去) 过程使群体进化到搜索空间中越来越好的区域【6 1 。该算法中的交叉和变异算 子，体现了群体搜索和个体之间信息交换的两大策略，为每个个体提供了优化的 机会，从而使整个群体在优胜劣汰的选择机制下保证进化的趋势。进化算法常用 的遗传操作有交叉、变异和选择等，其中交叉是模拟有性生殖过程中的染色体交 换过程，变异是模拟自然界中生物遗传物质的变异，选择则是模拟自然界的优胜 劣汰过程。 1 2 研究现状 1 2 1 免疫优化算法的研究现状 4 硕士学位论文第一章前言 目前，优化领域中应用的免疫优化算法主要有以下几种：( 1 ) 基于克隆选择 原理的免疫优化算法，这种算法利用免疫系统克隆选择的机制来实现优秀抗体的 扩展和增生，并利用了免疫系统中的记忆机制保证了算法能够最终收敛到全局最 优解；( 2 ) 基于免疫系统的抗体浓度调节原理的免疫优化算法一这种算法利用抗 体多样性保持机制，改进传统的遗传算法，提高了算法的群体多样性，能有效地 抑制早熟现象，使免疫遗传算法具有较好的全局收敛性；( 3 ) 基于免疫响应的免 疫优化算法【8 j ，这种算法引入了免疫记忆和抗体多样性等免疫特性；( 4 ) 基于免疫 疫苗接种的免疫优化算法，该算法引入疫苗接种的概念，能充分利用问题的先验 知识，改善算法的性能，在优化问题中获得了良好的效果；( 5 ) 基于免疫抗体记 忆的免疫优化算法【9 j ，这种算法将随机搜索过程中的局部搜索和全局搜索采用不 同的促进和抑制策略，有效保证了算法的收敛速度。 1 2 2 进化算法的研究现状 目前，有关进化计算的理论研究基础主要研究以下问题： ( 1 ) 进化计算的数学模型和理论基础，如算法的收敛性、收敛速度及复杂性 析。 ( 2 ) 确定特别适合采用进化计算求解的问题类型，以及采用进化计算求解效 果不太明显的问题类型。 ( 3 ) 从理论上和实际计算效果两方面比较进化计算方法与其它优化算法的计 算效果。 ( 4 ) 进化计算与其它优化算法的结合，提出新的混合算法。 ( 5 ) 探索在非优化类问题中如何使用进化计算方法。 ( 6 ) 从生物进化或自然界的各种现象中获得新的启发，提出新的方法或对现 有进化计算的改进。 针对标准遗传算法存在的缺陷，人们提出了很多改进方法，例如锦标赛选择和 并行遗传算法，免疫算法【1 0 j ，基于协调勘探和开采的遗传算法【1 1 l 等。这些方法都取 得了较好的效果。 1 2 3 免疫进化算法的研究现状 免疫进化算法( i m m u n e e v o l u t i o n a r yc o m p u t a t i o n ) 是受生物免疫系统信息处 理方式的启发构造的一类新智能优化算法。生物免疫机制有一些与进化计算有互 补作用的性能，因此，将生物免疫机制融入进化计算就提高了进化计算的性能。 焦李成和王磊等1 1 2 】基于疫苗接种理论提出基于疫苗的免疫遗传算法、免疫策 略和免疫规划：s a t o s h i 和n a m a l ( i 等【9 】基于主要组织相溶性复合体( m h c ) 和免疫网 络理论提出一种自适应优化的免疫算、法【1 3 】：王煦法和曹先彬掣1 4 j 基于抗体间相 5 硕士学位论文 第一章前言 互作用的浓度变化和抗体多样性理论提出了免疫遗传算法、免疫进化策略和免疫 进化规划；李士勇等基于生物适应性免疫应答中的进化机理提出了一类自适应免 疫进化算法【l 引。 免疫进化算法和免疫算法等融入免疫机制的算法具各许多优点【1 6 】，如全局优 化能力强、鲁棒性好、易于并行处理、智能度高等。但基本上是运用生物免疫机 制中的某一个环节或者一种机制构造出相应的免疫进化算法，生物免疫机制在他 们的算法中所起的作用或者是全局搜索、或者是局部搜索。能否将基于生物免疫 机制的全局搜索和局部搜索能力同时发挥，构造一些融入了免疫机制和领域知识 诱导的启发式规则的新型进化算法，具有很大的研究价值。 1 3 本文研究内容 本章对免疫算法、进化计算处理函数优化问题进行了简要的叙述，并简要的 介绍了免疫优化算法、进化算法、免疫进化算法的研究现状。本论文的研究内容 主要围绕如何设计有高效的进化算法展开，各章节的具体安排如下： 本文第二章首先介绍了生物免疫学的基本概念及背景；详细介绍了人工免疫 系统的背景和免疫特性，人工免疫算法的基本原理和框架，以及当前主要的人工 免疫算法类型；最后说明了人工免疫系统的主要应用领域。 第三章对进化计算的起源、发展作了简要回顾。详细阐述了进化算法的三个 主要分支，进化计算是一个多学科相融合、具有很高实用价值的研究领域。其它 学科研究的深入为进化计算的发展也带来了新的动力，分化出了许多新的研究分 支，如概率进化计算、免疫进化计算、克隆进化计算、协同进化计算等；最后说 明了进化计算的应用领域。 第四章提出了一种基于生物免疫系统内部学习优化机制以及进化算法的免 疫进化算法n i e a 。同时对该算法产生机理、算法中各个算子进行了讨论。该算 法利用正交交叉算子，使初始种群均匀化；随机生成新个体，维持种群多样性； 运用单形交叉算子，提高种群的收敛速度；使用精英群体引导整个种群的进化方 向；并且提出一种新的变异方法一多极变异，此变异方法使得不同变异算子按 照不同的概率作用到个体分量或者保持不变。对三种b e n c h m a r k 函数 、，2 、，3 的测试结果与o g q 【1 7 ：和h t g a 1 8 】进行比较，结果证明该算法是有效的，它不 仅可以跳出局部最优而且能够以较快的速度收敛于或更接近函数全局最优解。 第五章提出了一种新的基于局部搜索机制的免疫进化算法。该算法基于生物 免疫系统内部学习优化机制以及差异进化算法，首先随机初始化种群；接着采用 单形交叉算子产生新的子代个体；为了提高算法的局部搜索能力，提高其收敛速 度，引入了一种基于种群分割和新的差异进化算法的局部搜索机制；利用免疫更 新方法在每一代随机生成新个体，维持种群多样性；使用免疫记忆群体引导整个 6 硕士学位论文第一章前言 种群的进化方向。理论分析证明了算法的收敛性，并通过不同的测试函数验证了 算法的有效性。 最后，在第六章我们对本论文进行了总结并对将来的研究工作进行了分析与 展望。 7 硕士学位论文 第二章免疫算法 第二章免疫算法 本章首先介绍了生物免疫技术的基本特点，然后阐述了利用生物免疫系统的 思想产生的人工免疫系统相关理论、算法和结构，包括阴性选择算法、克隆选择 算法、免疫a g e n t 算法以及免疫g a 算法，接着说明了人工免疫系统的应用领域。 2 1 生物免疫技术 生物系统十分复杂，它是一个高度分布、并行和自适应的计算系统。生物系 统的很多机制己为人们所了解，这些大自然的杰作给我们提供了很好的体系模 型，生物模拟技术得到了广泛的应用。面对计算机病毒日趋严重的今天，基于生 物免疫系统( b i o l o g i c a li m m u n es y s t e m ，b i s ) 的研究给我们提供了一种新型求解 优化问题的新方法。生物免疫系统具有学习、记忆、大规模分布式并行处理等特 性，通过淋巴细胞( 包括胸腺的t 细胞和骨髓b 细胞) 的负选择( n e g a t i v es e l e c t i o n ) 过程和二次响应来实现对本体( s e l f ) 与非本体( n o n s e l f ) 的自适应判别，从工程应 用的角度来说，生物免疫系统可以看成是通过从不同种类的抗体构造自己非己 的一个非线性自适应复杂系统，一般在处理动态环境时发挥作用的1 1 9 。图2 - 1 为 免疫原理示意图( 此图引用免疫的非线性模型，作者：漆安慎，杜婵英) 。 抗原 滞 1 ：免疫细胞； ：j 一。： 图2 - 1 免疫原理示意图 “免疫 的英文为i m m u n i t y ，意为抗感染不生病。生物体保护自身免受外 来病菌的感染和侵害，是通过免疫系统完成的。免疫系统能够识别、消灭和清除 8 硕士学位论文第二章免疫算法 侵入机体的外部抗原( 即来自外部的病毒、细菌或寄生虫等) ，这一过程被称为免 疫应答。免疫系统( i m m u n es y s t e m ) 是由具有免疫功能的器官、组织、细胞和分 子组成，是机体免疫机制发生的物质基础。 免疫防御( i m m u n o l o g i c a ld e f e n s e ，i d ) 是指机体排斥外来抗原性异物的一种 免疫保护功能。免疫防御的关键是辨别“自身细胞 ( 机体内的无害分子) 和“非 自身细胞( 有害的病原体和外源性异物) 。由于蛋白质是生命物质的基本成分， 细胞不同，蛋白质也不同，因此它具有很好的识别性。当一个外部抗原袭击身体 时，抗原体细胞把外部分子分解到抗原决定基层次，产生与抗原决定基结合的抗 体。一旦抗原决定基发现匹配，一个特定信号就会发给免疫细胞，产生更多的抗 体，淹没抗原威胁或感染。只有那些能够识别抗原的细胞才进行扩增，才会被免 疫系统保留下来。 免疫细胞是随机形成的多样性细胞的克隆，每一克隆的细胞表达同一特异性 的受体，当受a 刺激，细胞表面受特异识别并结合a ，导致细胞大量克隆扩增， 产生大量后代细胞，合成大量相同的特异性抗体，淹没a 。与达尔文变异和自然 选择过程类似：克隆竞争结合病原体，亲和力最高的是最适应的，因此复制最多。 免疫系统使用分子的大量多样性是识别能力的关键，基础是克隆选择。克隆选择 与达尔文自然选择理论有关，主要应用在免疫系统内的细胞群体。 b i s 具有下列特征： ( 1 ) b i s 对外来侵害提供多层保护。 ( 2 ) 每个生物体的免疫系统都是独一无二的，同一机体内对不同抗原也会产 生不同的抗体。而在计算机或网络系统中，受保护的常常是多个软件副本或多个 计算机站点，如果其中一个副本或站点受到攻击，则其它的副本或站点均在所难 免。 ( 3 ) b i s 具有先天免疫功能，可识别检测首次遇到的新入侵未知病毒，并做 出应答。 ( 4 ) b i s 的检测和记忆是高度分布、非集中控制的分布检测。 ( 5 ) 免疫记忆具有联想特性。在检测中，抗体不仅对再次遇到的相应抗原做 出快速反应，而且对相似的抗原也可做出反应，抗原和抗体的匹配也是不精确的。 这种特性是当前的抗病毒技术所不具备的。 这些特点无疑都为人工智能借鉴的机理提供了重要线索。其机理可简单阐述 如下： ( 1 ) 抗体多样性：通过细胞的分裂和分化作用、体细胞超变异、抗体的可变 区与不变区的基因重组等方式，免疫系统可产生大量的抗体来抵御各种抗原，从 而使免疫抗体库具有丰富的多样性。 9 硕七学位论文 第二章免疫算法 ( 2 ) 自我调节：免疫系统具有维持免疫平衡的机制，能将免疫应答的强度限 定在一定水平上。通过对抗体的抑制和促进作用，能自我调节产生适当数量的必 要抗体。 ( 3 ) 记忆特性：产生抗体的部分细胞会作为记忆细胞而被保存下来，对于今 后侵入的同类抗原，相应的记忆细胞会迅速激发而产生大量的抗体，同时与该抗 原的亲和力也提高了。免疫系统具有识别各种抗原并将特定抗原排斥掉的学习记 忆机制，这是与神经网络不同的记忆机制。 ( 4 ) 克隆选择机理：当抗原侵入生物体内时，其免疫系统能在机体内选择出 识别和消灭相应抗原的抗体，主要借助克隆( 无性繁殖) 使之激活、分化和增殖， 以增加该抗体的数量，通过进行免疫应答最终清除抗原。可以利用克隆选择机理 来实现并行的局部搜索算法。 ( 5 ) 动态适应性：免疫系统是在与病原体不断竞争的过程中逐渐进化，这种 免疫系统与病原体的相互适应的过程具有明显的动态特性，两者相互竞争共同进 化。 ( 6 ) 其它机理：免疫系统所具的无中心控制的分布自治机理、自组织存储机 理、免疫耐受诱导和维持机理以及非线性机理均可用于建立人工免疫系统。 2 2 人工免疫系统 生物免疫系统是一个高度分布、并行和自适应的系统，在维护机体健康、排 除病菌入侵方面具有众多优良特性，它具有高度的信息处理能力，具备识别、记 忆、调节、学习等特性。这些特性决定了生物免疫系统在信息处理领域的良好应 用前景。这自然启发我们利用生物免疫系统的思想来解决优化问题，从生物免疫 系统中提取原理、结构和算法并将其运用到优化问题中去。 2 2 1 免疫系统中的几个基本概念 在人工免疫系统中完全套用生物学定义，照搬生物学过程，是不可能也不必 要的。为了更好地描述算法，以下将简要阐述几个常用的免疫学术语及其在本文 算法中的含义。 ( 1 ) 抗原 在人工免疫系统中，一般指问题及其约束，与进化算法中适应度函数类似。 具体地，它是问题目标函数厂o ) 的函数，记为g ( x ) 一g ( f 0 ”，是人工免疫系统 算法的始动因子以及算法性能的重要度量标准。但是，抗原g 的确定一般需要考 虑问题本身的特点，即需要结合问题的先验知识；一般情况下，为处理问题简单， 在未指明的情况下，取g o ) 一f ( x ) 。 ( 2 ) 抗体 1 0 硕士学位论文第二章免疫算法 与进化算法中的个体相似，抗体在人工免疫系统中一般指问题的侯选解。称 具有有限长度的字符串aa 巳口：a 。是变量x 的抗体编码，记为a e ( x ) ；而x 称 为抗体a 的解码，记为：x e - 1a ) 。依生物学术语，抗体a 中，a ，被视为遗传基 因，其可能取值与编码方式有关，被称为等位基因：一般将抗体位串分为m 段， 每段长为，z 。yt ，每段分别对应变量墨的编码。 集i 称为抗体空间，即a e l ；抗体群a = 口。，口：，口。) 为抗体口的n 元组， 是抗体种群空间，“的一个点，即，“；似：彳= 1 ，口2 ，a 。) ，a t ，1s ks ，l ，其中， 正整数n 称为抗体种群规模。 在实践中，常用的抗体编码形式有二进制和十进制。例如，一个抗体结构为 八位二进制数，则位串“0 1 1 101 0 0 即代表该抗体。 ( 3 ) 抗体抗原的亲合度 反映整个分子抗体与抗原之问的总的结合力。在人工免疫系统中，一般指侯 选解所对应的目标函数值或侯选解对问题的适应性度量。 ( 4 ) 抗体抗体亲合度 反映抗体与抗体间的结合能力。在人工免疫系统中，一般指抗体a 间的距 离，对于二进制编码一般采用海明距离，而实数编码一般采用范数，而且多数为 欧氏距离。 ( 5 ) 记忆单元 在人工免疫系统中，记忆单元是由特定抗体组成的抗体群，用于保持种群多 样性，以及求解过程中的最优解。 ( 6 ) 克隆 生物的增生过程。在人工免疫系统中的克隆算子是基于克隆选择学说，充分 结合了选择、扩展、变异和交叉的综合算子。 2 2 2 阴性选择算法 生物免疫系统通过组织淋巴细胞来识别“自体和“非体”抗原，消灭并清 除异物。在生物免疫系统中，淋巴细胞分为t 淋巴细胞和b 淋巴细胞。在抵御病 菌入侵时，t 淋巴细胞执行特异性免疫反应和调节功能。b 淋巴细胞则在其表面 产生抗体，探测对应的抗原并记录下该抗原的结构和特征，它执行识别、记忆、 学习等功能。美国n e wm e x i c o 大学的f o r r e s t 教授模拟淋巴细胞的产生过程，提 出阴性选择算法。 阴性选择算法采用基于免疫系统中的自体和异体识别的原理来进行变化监 测，先随机产生监测器，然后删除与自身对抗的，并保留