（计算机应用技术专业论文）进化非选择算法的分析和应用.pdf

中国科学技术火学硕士学位论文 摘要 人工免疫系统是继人工神经网络和进化计算之后又一种新型的智能计算方 法，是生命科学和计算机科学的交叉学科研究领域。生物免疫系统是一个自适应、 自组织、自学习的分布式并行复杂系统。人工免疫系统的研究旨在抽取生物免疫 系统所蕴涵的丰富的信息处理机制，设计相应的模型和算法，并用于解决各种复 杂问题。 生物免疫系统具有很强的自我保护功能。从信息处理的角度看，非选择机制 和进化学习机制是生物免疫系统自我保护机制中的两个重要组成部分。进化非选 择算法是将生物免疫系统的非选择机制和进化学习机制相结合设计而成的算法。 本文重点研究了针对逻辑电路自动设计、软硬件划分问题的进化非选择算法，并 以函数优化问题为背景分析了进化非选择算法的求解能力。 具体而言，本文的研究内容主要包括以下几个方面： ( 1 ) 设计了一种用于逻辑电路自动设计的进化非选择算法。该算法对迭代 生成的电路进行评估，将最差的电路加入自我集。在进化过程中，和自我集中个 体相匹配的电路被淘汰，不参与基于个体适应度的选择。本文设计了针对逻辑电 路设计问题的匹配规则和自我集更新策略。和传统进化算法的对比试验结果表 明，该算法具有较好的性能。 ( 2 ) 提出将了基于进化非选择算法的软硬件划分求解策略。软硬件划分是 软硬件协同设计的关键步骤之一。针对这一问题，本文采用先进先出方法更新自 我集，设计了相应的自我个体和候选解之间的匹配策略，并通过和进化算法的实 验对比结果表明了算法的有效性。 ( 3 ) 以函数优化问题为例，从实验和理论两个方面分析了进化非选择算法 的性能和参数。文中重点分析了非选择算子的特点，指出非选择算子使得进化非 选择算法能够较好地跳出局部最优解，具有较为稳定的求解性能。与此同时，本 文还给出了在使用非选择算子时需考虑的两个基本参数，即自我集大小和自我集 更新速度，并给出了针对函数优化问题的参考取值。 总的来说，本文主要研究和分析了基于免疫原理的进化非选择算法作为一类 摘要中国科学技术大学硕= 匕学位论文 新的通用且高效的启发式搜索算法的求解能力。本文从理论上证明了进化非选择 算法的收敛性，分析了进化非选择算法跳出局部最优解的原理，并以逻辑电路自 动生成和软硬件划分问题为应用背景，通过实验表明该算法不仅可以应用于网络 安全和异常检测，而且可以作为一种通用的启发式搜索算法。 关键词：人工免疫系统；硬件进化：进化非选择；逻辑电路自动设计；软硬件划 分 1 1 a b s t r a c t 中国科学技术大学硕十学位论文 a b s t r a c t a r t i f i c i a li m m u n es y s t e m ( a i s ) i san o v e li n t e l l i g e n tc o m p u t i n gr e s e a r c hf i e l d a f t e ra r t i f i c i a ln e u r a ln e t w o r ka n d e v o l u t i o n a r yc o m p u t a t i o n ，a n d i ti sa n i n t e r d i s c i p l i n a r y f i e l dd e r i v e df r o ml i f es c i e n c ea n dc o m p u t e rs c i e n c e a i si sa c o m p l e xs e l f - a d a p t i v e ，s e l f - l e a r n i n g ，s e l f - o r g a n i z a t i o n ，d i s t r i b u t e dp a r a l l e ls y s t e m t h ep u r p o s eo fa r t i f i c i a li m m u n es y s t e mi st oe x t r a c ts p e c i a li n f o r m a t i o np r o c e s s i n g m e c h a n i s m sc o n t a i n e di nb i o l o g i c a li m m u n es y s t e m ，a n dt h e nt os t u d ya n dd e s i g nt h e c o r r e s p o n d i n gm o d e l sa n da l g o r i t h m s ，w h i c hc o u l db eu s e dt os o l v em a n yk i n d so f c o m p l e xp r o b l e m s o no n eh a n d ，b i o l o g i c a li m m u n es y s t e mh a ss t r o n ga b i l i t yt od i s t i n g u i s hs e l fa n d n o n - s e l f , o nt h eo t h e rh a n d ，i ti sac o m p l e xs e l f - a d a p t i v es y s t e mf o ri t sv e r yg o o d i m m u n el e a r n i n gm e c h a n i s mb a s e do ne v o l u t i o n b yc o m b i n i n gt w oi m p o r t a n t f e a t u r e so fi m m u n es y s t e m ，an e wa l g o r i t h m - e v o l u t i o n a r yn e g a t i v es e l e c t i o n a l g o r i t h m ( e n s a ) i sp r o p o s e d i nt h i sp a p e lo u rr e s e a r c hw o r k sf o c u s e so n e v o l u t i o n a r yn e g a t i v es e l e c t i o na l g o r i t h m ( e n s a ) o na u t o m a t i cd e s i g n i n go fl o g i c c i r c u i t sa n dh a r d w a r e s o f t w a r ep a r t i t i o n i n g i nt h i sp a p e r , o u rr e s e a r c hw o r kf o c u s e so nf o l l o w i n ga s p e c t s ： ( 1 ) a na l g o r i t h mb a s e do ne n s a f o ra u t o m a t i cd e s i g n i n go fl o g i c a lc i r c u i t si s p r o p o s e d i ne v e r yc y c l eo f t h ei t e r a t i o n ，t h eb a di n d i v i d u a li sa d d e dt os e l f s e t ，a n da l l t h en e wi m m a t u r ei n d i v i d u a l sa r ef i l t e r e db yn e g a t i v es e l e c t i o n ，t h eo n em a t c ht h es e l f s e tw i l lb ed e l e t e d f o c u s i n go nt h es p e c i a la p p l i c a t i o n ，n o v e lm a t c h i n gr u l e sa n d u p d a t i n gr u l e so fp o p u l a t i o na r ed e s i g n e d c o m p a r e dw i t hs t a n d a r de v o l u t i o n a r y a l g o r i t h m ，r e s u l t so f t h ee x p e r i m e n t ss h o wt h a te n s a i sm o r ee f f i c i e n t ( 2 ) a ne n s a - b a s e dp a r t i t i o n i n ga l g o r i t h mf o rh a r d w a r e s o f t w a r ep a r t i t i o n i n gi s p u tf o r w a r d h a r d w a r e s o f t w a r ep a r t i t i o n i n gi so n eo f t h ek e ys t e p so fs o cc o d e i g n s an o v e lm a t c hr u l e sa n df i t n e s sf u n c t i o ni sp r o p o s e d e x p e r i m e n t ss h o wt h a tt h e p r o p o s e da l g o r i t h mi sm o r ee f f e c t i v et h a ne a 1 1 1 a b s t r a c t 中国科学技术大学硕士学位论文 ( 3 ) b a s e do nf u n c t i o no p t i m i z a t i o n ，as e r i e so fr e s e a r c h e sa r ed o n eo ne n s a f r o mb o t he x p e r i m e n t a la n dt h e o r e t i c a la s p e c t s t h er e s e a r c h e sa r ef o c u s e do nt h e n e g a t i v es e l e c t i o no p e r a t o r , i n d i c a t i n gt h a tt h en e g a t i v es e l e c t i o no p e r a t o rc a na v o i d t h ea l g o r i t h mb e i n gt r a p p e di nl o c a lo p t i m i z a t i o n t h er e s u l t so fe x p e r i m e n t ss h o w t h a te n s ai sm o r ee f f e c t i v ef o rm u l t i m o d a lf u n c t i o n t h ee x p e r i m e n t sa l s og i v et h e o p t i m a lp a r a m e t e r so f t h en e g a t i v es e l e c t i o no p e r m o l t h i sp a p e rd o e sm u c he x p e r i m e n t a la n dt h e o r e t i c a le x p l o r a t i o nt od i s c u s st h e p e r f o r m a n c eo fe n s aa sah e u r i s t i cs e a r c ha l g o r i t h m t h ec o n v e r g e n c ea n a l y s i so f e n s ai sd e m o n s t r a t e d ，a n da n a l y z eo nh o wt oj u m pf r o ml o c a lo p t i m i z a t i o ni sa l s o g i v e n a p p l i c a t i o n s o fe n s ao na u t o m a t i c d e s i g n i n g o fl o g i c a lc i r c u i t sa n d h a r d w a r e s o f t w a r ep a r t i t i o n i n gs h o wt h a te n s ai sn o to n l ys u i t a b l ef o rn e t w o r k s e c u r i t ya n da n o m a l yd e t e c t i o n ，b u t a l s oa n g e n e r a l ，e f f e c t i v e h e u r i s t i cs e a r c h a l g o r i t h m k e y w o r d s ：a r t i f i c i a li m m u n es y s t e m ；e v o l v a b l eh a r d w a r e ；e v o l u t i o n a r yn e g m i v e s e l e c t i o na l g o r i t h m s ；l o g i cc i r c u i t sd e s i g n ；h a r d w a r e - s o f t w a r ep a r t i t i o n i n g 目录 中国科学技术大学硕士学位论文 表2 - 1 表2 - 2 表2 3 表3 1 表4 1 表4 2 表4 3 表4 4 表4 5 表4 6 表格目录 匹配操作规则，1 8 e a 和e n s a 的性能比较2 0 进化得到正确解的代数分布2 1 试验结果3 4 函数一一3 8 函数二一3 8 函数三3 9 不同步长的测试结果一3 9 平均进化代数( 每个个体产生一个新个体) 4 1 最优解随s 变化的分布4 2 目录中国科学技术大学硕士学位论文 图1 1 ： 图1 2 ： 图1 3 ： 图1 - 4 ： 图2 1 ： 图2 2 ： 图2 3 ： 图2 - 4 ： 图2 5 ： 图2 - 6 ： 图3 1 ： 图3 2 ： 图3 3 ： 图3 - 4 ： 图3 5 ： 图4 1 ： 图4 2 ： 图4 3 ： 图4 - 4 ： 图4 5 ： 插图目录 克隆选择学说示意图 j e m e 免疫网络模型 克隆选择算法流程 s f o r r e s t 提出的非选择模型 门级f p g a 结构模型 个体编码方案 用于电路进化设计的e n s a 流程 匹配示例 用e n s a 进化所得电路 适应度变化曲线 软硬件协同设计流程 成本一延迟关系 体系结构模型 2 0 个节点c d f g 实例 适应度变化曲线 函数一 函数二 函数三 函数四 进化代数随a s 变化曲线 “ “ j m m 侈 加 舱 巧 ” 凹 孙 ” 拍 ” 鸵 第l 章绪论中国科学技术大学硕士学位论文 第1 章绪论 人工免疫系统( a r t i f i c i a li m m u n es y s t e m ：a i s ) 是继神经网络、进化计算之 后新的智能计算领域。人工免疫系统的研究旨在从生物免疫系统中提取其蕴涵的 丰富的信息处理机制，设计相应的模型和算法，并用来解决各种复杂问题。 生物免疫系统是一个具有很强自我保护功能的系统，能够抵御外界入侵，有 效识别已知和未知抗原，并将抗原分类清除。生物免疫系统的基本功能是识别自 我和非我，然后去除非我，它是一个自适应、自组织、自学习的复杂系统。 本章重点介绍了人工免疫系统的概念，生物免疫系统的相关背景，人工免疫 系统的研究进展以及本文的主要研究内容。 1 1 什么是人工免疫系统 目前，人工免疫系统的定义有几种。j t i m m i s 指出“人工免疫系统是自然 免疫系统的抽象计算系统 1 n 而后又改为“人工免疫系统是受己知的免疫功 能、原理和模型以及理论免疫学启发而提出的用于解决实际问题的自适应系统”： d a s g u p t a 指出“人工免疫系统是受免疫系统激发而提出的用于解决实际问题的智 能方法【2 1 ”。 一般认为，人工免疫系统是一类基于生物免疫系统的功能、原理、基本特征 以及相关理论免疫学说而建立起来的用于解决各种复杂问题的计算系统 1 。 生物免疫系统的基本功能是识别自我和非我，并将非我分类清除，是具有免 疫识别、免疫记忆、免疫调节和免疫宽容等功能特征的系统，能有效的识别外来 侵入者，维持机体本身的平衡，保证生物体自身的生存和发展【4 】 5 。 最先提出用免疫学来实现计算系统的是f a r m e r 等，他们在1 9 8 6 年提出了基 于个性基因网络理论( i d i o t y p i cn e t w o r kt h e o r y ) 的模式识别模型 3 ，该模型提出了 免疫系统可以看作是一个基于免疫记忆的学习系统，后来被改进用于数据缩减和 聚类。 此后，日本的i s h i d a 和欧洲的b e r s i n i 在1 9 9 0 借鉴免疫原理分别建立了人工 免疫算法并用于解决计算问题【6 7 。s f o r r e s t 等人则在1 9 9 4 年首先提出了可应 第1 章绪论中国科学技术大学硕士学位论文 用于网络安全领域的变化检测算法，即非选择算法 8 。 第一个以人工免疫系统为主题的国际会议于1 9 9 6 年在日本召开，即 “i n t e r n a t i o n a lw o r k s h o po ni m m u n e b a s e ds y s t e m ”。随后，人工免疫系统开始引 起世界各国研究人员的注意。作为计算智能的一个崭新分支，a i s 己成为许多 国际期刊的重要议题，如e v o l u t i o n a r yc o m p u t a t i o n ，i e e et r a n s a c t i o no n e v o l u t i o n a r yc o m p u t a t i o n 等，后者在2 0 0 1 年和2 0 0 2 年还相继出版了a i s 专辑。 在国际会议方面，从1 9 9 7 年开始，i e e es y s t e m ，m a na n dc y b e r n e t i c s 国际会议 每年均组织专门的a i s 研讨会( w o r k s h o p ) 。2 0 0 2 年第一届人工免疫国际会议 ( i c a r i s 2 0 0 2 ) 在英国举行，会议主要探讨人工免疫系统理论和应用的最新进 展。该会议每年举行一次，今年将在葡萄牙举行第五届人工免疫国际会议。目前， 人工免疫系统已经发展成为一个相对独立的研究领域，吸引了越来越多的研究者 的参与。 1 2 生物免疫系统简介和基本免疫学说 1 2 1 生物免疫系统的组成和功能 自然界生物的免疫系统是一个高度复杂的分布式协调自适应系统。生物免疫 系统能够抵抗外界病菌的侵入和感染，维持机体自身生理活动的稳定和平衡。下 面从免疫系统的组成、基本概念和基本功能三方面对生物免疫系统进行简单介 绍。 ( 1 ) 免疫系统的组成。 免疫系统由免疫器官、免疫细胞、免疫分子和淋巴循环网络组成 9 】。 免疫器官分为中枢免疫和外周免疫器官，中枢免疫器官是免疫细胞发育成熟 的场所，包括胸腺和骨髓。外周免疫器官是成熟淋巴细胞定居和产生免疫响应的 场所，包括淋巴结、肿脏和乳膜免疫系统。 免疫细胞泛指执行免疫功能的各种细胞，包括t 细胞、b 细胞、吞噬细胞、 自然杀伤州k ) 细胞等与免疫响应有关的细胞。免疫细胞都来源于造血干细胞， 免疫细胞的成熟过程实际上是造血干细胞的发育分化过程。 免疫分子是免疫细胞合成和分泌的执行免疫功能的各种分子的统称，包括抗 第1 章绪论 中国科学技术大学硕士学位论文 体、补体、细胞因子、主要组织相容性复合体等。 淋巴循环网络为免疫细胞和分子进行免疫响应和免疫补充提供了一个流动 的环境，它与血液循环系统相联系。 ( 2 ) 基本概念 接下来介绍生物免疫应答过程中的几个基本概念，这对正确地理解免疫学的 基本内容是必要的。 抗原( a n t i g e n ) ：抗原是一组能被淋巴细胞识别的有机物质，包括多肤、寡糖、 脂质酸等小分子，其化学成分不同于宿主细胞自身物质的化学组成。抗原由载体 和半抗原组成。半抗原又称作抗原决定簇或表位( e p i t o p e ) 。抗原决定簇的成分、 数目和空间构型决定了抗原的特异性。抗原决定簇是被免疫细胞识别的标志和免 疫反应具有特异性的物质基础，它与相应淋巴细胞表面的抗原受体结合，激活淋 巴细胞引起免疫响应。它也可以与游离的抗体等分子发生特异性结合，导致抗原 被清除。 抗体( a n t i b o d y ) ：抗体是一种能特异识别、结合和清除抗原的免疫球蛋白分 子。b 细胞识别抗原后，经过活化和克隆扩增之后，一部分分化成为浆细胞，浆 细胞大量地分泌具有相同特异性的抗体。 由于抗体是结构复杂的大分子糖蛋白，故也具有抗原性，将抗体作为免疫原， 可以引发机体的免疫响应，抗体的抗原性是j e m e 提出免疫网络理沦的基础。 b 淋巴细胞( bl y m p h o c y t ec e l l ) ：b 淋巴细胞( 简称b 细胞) 是介导体液免疫 的主要免疫细胞，它是淋巴系干细胞在骨髓中形成的，经过活化增殖后成熟的b 细胞称为浆细胞( p l a s m ac e l l ) ，能够分泌抗体。b 细胞表面有各种受体，以接受 外界的化学信号，如b 细胞受体( bc e l lr e c e p t o r ，简称b c r ) 、细胞因子受体、 补体受体、丝裂原受体等。b c r 是与抗体结构相同的免疫球蛋白，是b 细胞识 别和结合抗原的主要受体。其它受体主要是起到调节作用。 t 淋巴细胞( tl y m p h o c y t ec e l l ) ：t 淋巴细胞( 简称t 细胞) 是介导机体细胞免 疫的主要免疫细胞，淋巴系干细胞在胸腺的微环境下逐渐发育成熟成为t 细胞。 t 细胞受体( tc e l lr e c e p t o r ：t c r ) 由四条肤链组成，根据氨基酸变化程度也分为 v 区和c 区，v 区是t c r 识别抗原肤的部分，直接决定了t c r 抗原结合的特异 性。除了t c r 外，t 细胞表面还有细胞因子受体等其它受体，接受其它细胞和 第1 章绪论中国科学技术大学硕二b 学位论文 组织发送的化学信号。从功能上看，t 细胞可以分为不同的亚群，有细胞毒性t 细胞、能够杀伤受感染的宿主细胞和肿瘤细胞、辅助性t 细胞( h e l p e rtc e l l ：t h1 和抑制性t 细胞( s u p p r e s s o rtc e l l ：t s ) 等。t h 分泌的细胞因子正反馈调节各种 免疫细胞功能；而t s 抑制其它免疫细胞功能，负反馈调节免疫细胞的功能。 其它免疫细胞：其它参与免疫响应的重要免疫细胞有n k 细胞和抗原提呈细 胞( a n t i g e np r e s e n t a t i o nc e l l ：a p e ) 等等。n k 细胞是一种效应细胞，它是在骨髓 产生的，上面有激励和抑制两种受体，一旦被激活后，n k 细胞可以杀伤肿瘤和 被病原体感染的细胞。a p c 的作用是能够摄取抗原，并在细胞内加工处理抗原 成多肤片段，然后与m h c 分子形成复合物，并提呈到细胞表面供t 细胞识别， 能够起到a p c 作用的免疫细胞有巨噬细胞，树突状细胞和b 细胞等。 最后需要提一下淋巴循环。淋巴循环在免疫系统中具有重要的作用，它使淋 巴细胞在淋巴组织和器官中的分布更为合理。淋巴组织不断地从循环池中补充新 的淋巴细胞，有利于增强整个机体的免疫功能，有利于淋巴细胞和抗原及抗原提 呈细胞接触，有利于动员效应细胞迁往炎症部位，有利于记忆细胞参与再循环， 产生二次免疫响应。 f 3 ) 生物免疫系统的功能 如果把人体看作一个国家，免疫系统则可以看作是保卫这个“国家”安全的 “警察”和“军队”。人类和其他生物的免疫系统是一个由许多执行免疫功能的 器官、组织、细胞、分子以及淋巴循环等组成的复杂系统，其基本作用是保护自 身，抵抗外来病原体和自身癌变细胞威胁。文献【1 1 中指出：免疫是指机体接触 抗原性异物( 如各种微生物) 后，能产生一种特异性的生理反应，通过这种生理反 应可排除这些异物，从而保护机体的生存。也就是说，免疫系统的主要功能是响 应识别并清除从外界环境中入侵的病原体及其产生的毒素和内环境中基因突变 产生的肿瘤细胞，实现免疫防卫功能，维持内环境的稳定。这一过程称之为免疫 应答。从本质意义上说，免疫系统的基本功能是识别和排除“异己”，维持自身 的一致性。它具有免疫识别、免疫记忆、免疫宽容、免疫调节等特点 1 0 】。 从信息处理的角度来看，生物免疫系统中的识别和清除异己的应答过程实质 上是一个识别、效应和记忆的过程，该过程中所包含的隐喻机制正是研究人员所 需要认识提取的，而a i s 仿生机理所对应的，正是免疫系统中的应答过程。 第1 章绪论 中国科学技术大学硕： 学位论文 综合来说，人工免疫系统和人工神经网络、进化算法有相同之处，也有不同 之处。相比较而言，人工免疫系统与进化算法之间要具有更多的相似之处。从它 们各自的生物基础来看，与神经系统和遗传进化系统相比，生物免疫系统最根本 的功能特征就在于它是生物体的自我保护系统，能够识别和清除非我抗原，生物 免疫系统的一切进化学习机制都是为体现这一根本功能特征而运转的。这正是大 量过去从事人工神经网络和进化算法研究工作的专家学者转而对基于生物免疫 机制的人工免疫系统进行深入探索和研究的根本原因之一。 1 2 2 生物免疫学说 生物学家对免疫现象研究早在1 9 世纪就开始了，她们提出了若干理论和模 型，来解释生物免疫的过程，其中最著名的也最为大部分免疫学家所接受的理论 模型主要是b u m e t 提出了的克隆选择学说 1 2 和n k j e m e 提出的独特型网络调 节学说 1 3 】 ( 1 ) 克隆选择学说 自从澳大利亚人fm b e m e t 于1 9 5 4 年提出克隆选择学说后，免疫学产生了 飞跃性的发展，到现在为止，克隆选择理论已经成为免疫学界普遍接受的基本理 论，近三十多年的发现充分证实了克隆选择学说的正确性，而且进一步从更深和 更广的方面丰富了克隆选择学说的内容。 克隆选择学说认为免疫细胞在胚胎的发育阶段先广泛的生成，再接受自身抗 原的刺激，使得自身反应性细胞克隆在早期就被淘汰杀死。所以发育成熟的免疫 系统不会对自身抗原产生应答，却保留对异物抗原的应答能力。外界抗原入侵后， 机体根据免疫细胞表面受体和抗原表位间的耦合的紧密程度来选择较高匹配度 的那部分免疫细胞，使之激活并增殖。产生专门针对该抗原的抗体，引起免疫应 答，最终将其清除。图1 1 是克隆选择学说的示意图。 第1 章绪论中国科学技术大学顶： 学位论立 图i l ：克隆选择学说示意图 ( 2 ) 独特型网络调节学说 为了解释免疫系统的各种现象，在克隆选择学说的基础之上，n k 1 e m e 提 出了独特型免疫网络理论13 1 ，对免疫系统进行定量的数学描述并且提出了免疫 网络的微分方程描述 1 4 1 。 如1 21 所说，不仅抗原具有能够被抗体识别并结台的抗原决定簇( 表位) ， 抗体本身也是大分子糖蛋白也具有抗原性，具有能够被其它抗体识别并结合的 抗原决定簇。抗体上能够被其它抗体识别的抗原决定簇称为独特型( i d i o t y p e ) 抗原 决定簇，或称独特位( i d i o t o p e ：i d ) 。能够识别并结合抗体上独特型抗原决定簇的 抗体称为抗独特型( a n t i - i d i o t y p e ：a i d ) 抗体，a i d 上能够识别其它抗体或抗原上 的表位的部分称为对位( p a r a t o p e 、。a i d 上的抗体进一步又能够被抗一抗独特型 抗体识别并结合。如此类推，构成一个网络结构，如图1 - 2 所示。 i 0 二 a “女o o 厂 厂 广 彳f 一 图l - 2 ：j e r n e 免疫网主并模型 第1 章绪论中国科学技术大学硕j 一学位论文 j e m e 独特型网络调节学说强调了免疫系统中各个细胞克隆不是处于一种孤 立状态，而是通过相互刺激和抑制形成一个动态平衡的网络。构成相互刺激和制 约的物质基础是独特型和抗独特型。 j e m e 的网络学说奠定了整体的、联系的、发展的观点来解释免疫调节等免 疫现象的基本思想。以此免疫学说为基础，很多人提出了新的模型。 1 3 人工免疫系统的研究现状 本节先简要了人工免疫系统的研究现状，然后介绍了人工免疫系统中的两个 重要算法，即克隆选择算法和非选择算法。最后介绍了本文重点研究的算法，即 进化非选择算法的研究现状。 1 3 1 人工免疫的研究现状 人工免疫系统是一个全新的智能计算领域。目前已经有大量的研究人员对生 物免疫机制进行了建模、算法殴计和应用领域研究，并且在理论模型、算法研究 和应用领域均取得了一定的进展。下面介绍其中具有代表性的一些工作。 a t a r a k a n o v 等建立了一个比较系统的人工免疫系统模型，并指出该模型 经过改进后用于评价加里宁格勒( k a l i n i n g r a d ) 生态学地图集的复杂计 算 2 。 jt i m m i s 等提出了一种资源受限的人工免疫系统方法，该算法基于自然 免疫系统的种群控制机制，控制种群的增长和算法终止的条件，并成功用 于f i s h e r 花瓣等问题 1 5 1 。 j k i m 的人工免疫模型。j k i m 提出了基于非选择的人工免疫模型，并 将其应用在i d s ( 网络入侵检测系统) 的研究中 1 7 1 8 1 9 1 。该模型结 合了非选择、基因库进化和免疫记忆。采用主i d s 和从i d s 的结构来 构成分布式的入侵检测系统：同时利用基因库进化来自适应生成检测 器，使得该模型具有对未知入侵模式的识别能力。 s a h o f m e y r 提出基于非选择算法的分布式检测免疫模型 2 1 1 。其主要 贡献是，对非选择算法进行了较为详细的分析并加以扩展，将模型应用 到网络入侵中，监视广播网上的t c p 数据包。 第1 章绪论 中国科学技术大学硕士学位论文 d d a s g u p t 领导的项目组则主要基于免疫a g e n t 对入侵检测问题进行研 究，提出了基于免疫a g e n t 的入侵检测系统框架 2 2 1 。他们的设想是通 过一些基于免疫机制的a g e n t 在计算机网络上各个机器之间流动，相互 协作，监视网络的状态并发现己知和未知入侵。 s f o r r r e s t 的非选择算法。s f o r r e s t 等人将非选择算法用在u n i x 系统 下的进程行为的异常检测，来检测网络入侵【8 。其基本思想是，对系 统调用序列使用滑动窗口分片，在此基础上应用非选择算法。试验证明， 该算法得到的正常模式比较稳定，并可以对正常进程和被入侵的进程做 出一定程度的区分。 目前国内对人工免疫系统的研究也已经成为热点。比如，基于人工免疫 的入侵检测算法、模型和系统设计 2 3 2 5 】，人工免疫中检测器生成问 题研究 2 6 2 7 】，免疫接种机制研究 2 8 2 9 3 1 。 以上介绍了基于人工免疫的计算机网络安全现状。人工免疫系统的独特机制 引起了计算机科学家们的高度关注，越来越多的研究者正在加入其中。 1 3 2 克隆选择算法 d ec a s t r o 和fj v o nz u b e n 于2 0 0 1 年提出了克隆选择算法 3 0 1 ，此算法考 虑了免疫应答中亲和度成熟，主要用来解决优化问题。 根据克隆选择理论，免疫b 细胞遇到抗原后会发生克隆增殖。克隆过程中 同时出现高概率基因变异造成子细胞与母细胞不完全相同，其中亲和度更高的 后代拥有更强的繁殖能力，反之则逐步死亡，使得生存下来的细胞的亲和度能够 快速提高，并保存下来。根据这现象，d ec a s t r o 等对免疫系统的优化机理进行 深入研究，通过浓缩和概括，提出了基于克隆选择的启发式优化算法框架【3 0 】。 其基本流程见图1 - 3 。 第1 章绪论中国科学技术大学顶一：学位论文 否 图1 - 3 ：克隆选择算法流程 克隆选择算法是模拟自然免疫系统功能的一种新的智能方法，具有学习记忆 功能，为信息处理提供了新的方法它在传统进化算法的基础上，引入了亲合度 成熟、克隆和记忆机理，并利用相应的算子保证了该算法能快速地收敛到全局最 优解。 克隆选择算法的搜索手段是克隆选择算子，它实质上是一种自适应变异算 子，没有交叉算子的模式收敛效应，不易破坏种群多样性，因而不易出现早熟现 象。克隆选择算法被用于求解模式识别、多目标和多模态函数以及旅行商等优化。 1 3 3 非选择算法 免疫系统自身耐受表明免疫系统具有识别“自我”和“非我”的功能，实现 这种功能的关键是在免疫细胞形成过程中的非选择作用。受此启发，s f o r r e s t 等在1 9 9 4 年提出了一种检测变化和非正常情况的非选择算法( n e g a t i v es e l e c t i o n a l g o r i t h m ：n s a ) 8 。它将整个搜索空间分为自我和非我两部分，这两部分之 间没有交集。系统有一个检测器集合和初始的自我集合。与检测器集合匹配的个 体为分我个体；所有的自我个体和检测器集合的个体不匹配。它在基于人工免疫 的网络安全、模式识异常检测等领域中具有较大的影响。 第1 章绪论 中国科学技术大学硕士学位论文 非选择算法的流程如下，如图1 4 ： 定义自我集：有限字符表上，定义一组长度为l 的字符串集合s 来代表自 我。 产生检测器：随机产生检测器，根据非选择算法对每个检测器进行过滤，与 自我集匹配的检测器被删除。 通过连续将检测器集合中的检测器与自我s 比较来监测s 的改变。 这里所说的“匹配”可以根据不同的需要采取不同的匹配规则，如海明距离 匹配和连续r 位匹配两种部分匹配规则。本文在研究非选择算法的应用时，针对 不同的应用领域，采用了不同的匹配规则。 囱 ( a 1 产! 卜榆洲器蜒 ( b 】蚧讹璺徘护敝榭 图1 4 ：sf o r r e s t 提出的非选择模型 1 3 4 进化非选择算法 克隆选择机制具有较好的学习进化能力，而非选择算法则具有优秀的区分自 我和非我的能力。因此不少学者在研究如何将这两种优点结合起来。进化非选择 算法( e v o l u t i o n a r y n e g a t i v es e l e c t i o n a l g o r i t h m ：e n s a ) 2 4 和自适应非选择算 法( a d a p t i v e n e g a t i v es e l e c t i o n a l g o r i t h m ) 3 2 被提了出来。 进化非选择算法将免疫非选择机制和学习机制相结合 2 4 ，常用于网络安全 卤 第l 章绪论中国科学技术大学硕士学位论文 和异常检测。算法将受保护的数据和进化生成的检测器集合进行匹配，匹配成功 的检测器作为自我集合删除，否则作为成熟检测器。采用这种算法生成的检测 器集合作为异常检测的成熟检测器集来进行异常检测。 l u i sj g o n z a l e z 提出的自适应非选择算法主要是采用自适应变异技术来调 节检测器集合进化生成中的变异概率【3 2 】。算法在变异生成新的检测器的过程 中，根据检测器的亲和度来确定其变异概率。文中将该算法应用于异常检测，并 和具有变异的非选择算法进行比较。 此外，j k i m 等将静态克隆选择、动态克隆选择、基因库进化和非选择结 合在一起进行了大量的研究工作 3 3 1 1 3 4 1 1 3 5 。 目前，进化非选择算法的研究目前还处于相对初始阶段，它的主要应用也集 中于网络安全和异常检测。 与本节所讨论进化非选择算法不同，本文主要将进化非选择算法应用于优化 领域，分析探讨将进化非选择算法作为一种启发式搜索算法的可行性和潜在应 用。 1 4 本文主要研究内容和章节安排 本文主要从实验和理论方面证明进化非选择散发在不同优化领域的性能。我 们选取了两个比较有代表性的优化应用领域：逻辑电路自动生成和软硬件划分。 实验分析了进化非选择算法相对传统进化算法的求解能力的优势。本文还以函数 优化为背景，从实验上分析进化非选择箅子在函数优化中的性能和几个重要参数 的设定。在理论方面，本文分析了进化非选择算法的收敛性，并给出算法跳出局 部最优解原理。 本文其余的章节的结构如下。第二章提出基于e n s a 的逻辑电路的自动化 设计算法，针对电路自动化设计，提出了特定的编码规则和匹配规则，并和传统 进化算法进行对比试验。第三章提出用于软硬件划分问题的进化非选择算法，采 用先进先出策略结合，设计了自我集匹配规则和个体适应度函数。第四章通过函 数优化问题分析进化非选择的非选择算子的求解能力和参数设定，并对算法理论 分析。第五章是总结和展望。 第2 章用于逻辑电路设计的进化非选择算法 中国科学技术大学硕士学位论文 第2 章用于逻辑电路自动设计的进化非选 择算法 进化型硬件( e v o l v a b l eh a r d w a r e ：e h w ) 是2 0 世纪9 0 年代兴起的- 1 3 新 兴学科。进化型硬件能够根据环境改变自身结构和行为。电路进化设计是进化型 硬件研究的重要内容，即利用进化计算技术来配置电路的内部结构以获得所需功 能的电路，目前主要的采用进化算法来实现。本章用进化非选择算法作为电路自 动设计方法，设计了相应的匹配规则和自我集更新策略。实验结果显示，该方法 相对传统进化算法具有更高的进化效率。 本章先介绍了电路进化设计的背景和研究现状，然后给出逻辑电路进化设计 的进化非选择算法的流程，设计了具体的匹配规则和自我集更新策略，最后是实 验结果分析和本章小节。 2 1 1 研究背景 2 1 电路自动设计 进化型硬件是上个世纪9 0 年代初逐步兴起的交叉学科研究领域。进化型硬 件是指在变化的运行环境中，硬件本身能够自动地改变结构以适应环境的变化， 或者说具有某种功能的硬件能够随着环境的变化而变化。 概括地说，e h w 研究是以进化算法( e v o l u t i o n a r y a l g o r i t h m ：e a ) 作为组 合优化和全局搜索的主要工具，将可编程器件作为主要的评估手段和实现载体， 试图在不依赖先验知识和外力推动( 如人工干预) 的条件下，通过进化来寻求满 足给定要求的电路和系统结构，进而使系统能自动地、实时地调整( 重新配置) 其内部结构，以适应内部条件( 如局部故障) 和外部环境( 功能要求或物理条件) 的变化 3 6 3 7 3 8 。 追根溯源，有关e h w 的最早的思想起源是上个世纪五十年代5 0 年代冯诺 依曼提出的研制具有自繁殖与自修复能力的机器的设想。在此后很长的一段时期 内，由于相关理论和技术条件的限制一直未能实现。随着相关技术条件的成熟， 第2 章用于逻辑电路设计的进化非选择算法中国科学技术大学硕：卜学位论文 1 9 9 5 年1 0 月，进化型硬件研讨会( w o r k s h o pt o w a r d se v o l v a b l eh a r d w a r e ) 在瑞 士召开。随后e h w 进入了较快的发展期。1 9 9 6 年1 0 月，第一届进化型硬件国 际会议( 1 s ti n t e r n a t i o n a lc o n f e r e n c eo ne v o l v a b l es y s t e m s ：i c e s 9 6 ) 在日本召开， 该会议除2 0 0 0 年和2 0 0 1 年连续开了两次会议之外，每两年开一次。美国 n a s a d o d 于1 9 9 9 年召开了第一届进化型硬件专题研讨会( t h ef i r s t n a s a d o dw o r k s h o po ne v o l v a b l eh a r d w a r e ) ，随后浚会议每年召开一次，专门 探讨e h w 的相关理论和应用的最新进展。目前，e h w 已发展成为多学科交叉、 应用前景广阔的新兴研究领域，在电路设计、自动控制、容错系统、模式识别与 人工智能、机器人等领域展现了广阔的应用前景和潜在的巨大商业价值。 e h w 的产生和发展旨在为复杂电路设计提供一种全新的方法，