（计算机应用技术专业论文）免疫网络模型优化算法研究.pdf

瓠痧 # 夸 二： o 。 。j “k ，1 蔷 。一 童氟 一 妒，莎 1 1 武汉科技大学 研究生学位论文创新性声明 本人郑重声明：所呈交的学位论文是本人在导师指导下，独立进行研 究所取得的成果。除了文中已经注明引用的内容或属合作研究共同完成的 工作外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 论文作者签名：塑雌日期： i f p 研究生学位论文版权使用授权声明 本论文的研究成果归武汉科技大学所有，其研究内容不得以其它单位 的名义发表。本人完全了解武汉科技大学有关保留、使用学位论文的规定， 同意学校保留并向有关部门( 按照武汉科技大学关于研究生学位论文收录 工作的规定执行) 送交论文的复印件和电子版本，允许论文被查阅和借阅， 同意学校将本论文的全部或部分内容编入学校认可的国家相关数据库进行 检索和对外服务。 论文作者签名： 耋丝蜱 指导教师签名：2 三婆益 日 一 武汉科技大学硕士学位论文第1 页 摘要 人工免疫系统是借鉴自然免疫系统具有的并行、分布式、自适应处理机制解决实际计 算问题的一类方法。由于人工免疫系统在学习、认知、记忆等方面的优良特性，其在网络 规划和组合优化问题求解方面具有巨大潜力。 基于人工免疫系统原理的全局优化算法中，克隆选择算法和免疫网络( a i n e t ) 算法 是最常用的两种算法，这两种算法在搜索全局最优、避免陷入局部极值等方面具有一定的 优越性，但是在保持解集的多样性方面均存在一定缺陷。 本文针对这两种算法存在的不足，提出一种新的优化算法c l o n a l g - a i n e t 。本算法旨在 找到全局最优解的同时搜索尽可能多的局部优化解。算法结合了克隆选择算法和免疫网络 算法的优点，在克隆选择算法的基础上，将免疫网络算法中的网络抑制引入到每一代免疫 进化过程中，筛选出相似的问题解，再根据亲和力大小，删除二者中的劣质解。抑制去除 了不同种群间的相似个体，较好的保持了解集的多样性。另外，新算法改进了克隆选择算 法中的选择策略，既保证最优解能被良好的继承和保留，又保持了种群规模。 本文对算法进行了仿真实验分析，比较了传统的克隆选择算法、a n e t 算法和新算法 在执行过程中的效果和性能。实验表明，该算法可以更有效的搜索到全局最优峰和局部优 化解。 关键词：人工免疫系统、免疫优化算法、克隆选择算法、a i n e t 算法 第1 i 页武汉科技大学硕士学位论文 a b s t r a c t a sap a r a l l e l ，d i s t r i b u t e da n ds e l f - a d a p t i v ei n f o r m a t i o np r o c e s s i n gs y s t e mw i t hh i g h i n t e l l i g e n c ep e r f o r m a n c e ，t h en a t u r ei m m u n es y s t e mp r o v i d e san e ww a yt od e a lw i t ha c t u a l c a l c u l a t i o np r o b l e m s b e c a u s et h ea r t i f i c i a li m m u n es y s t e mh a sf i n ec h a r a c t e r i s t i c so ns t u d y , c o g n i t i o na n dm e m o r y i th a sg r e a tp o t e n t i a li nn e t w o r kp l a n n i n g ，p r o b l e ms o l v i n gc o m b i n a t o r i a l o p t i m i z a t i o n b a s e do na r t i f i c i a li m m u n es y s t e mt h ep r i n c i p l e ，c l o n a ls e l e c t i o na l g o r i t h ma n dt h e i m m u n en e t w o r k ( a i n e t ) m e t h o da r eg l o b a lo p t i m i z a t i o na l g o r i t h m sw h i c hb eu s e dm o s t c o m m o n l y , t h e s et w oa l g o r i t h m sh a v ec e r t a i na d v a n t a g e so ns e a r c h i n gf o rt h eo p t i m u ma n d a v o i d i n gf a l l i n gi n t ol o c a lm i n i m u m ，b u ti t sa l s oh a v es o m ed e f e c t so nk e e p i n gt h ed i v e r s i t yo f s o l u t i o ns e t i nt h i s p a p e r , an e wo p t i m i z a t i o n a l g o r i t h mc l o n a l g a i n e t b e p r o p o s e df o r t h e s h o r t c o m i n g so f t h e s et w oa l g o r i t h m s ，t h ea l g o r i t h ma i m st of i n dt h eg l o b a lo p t i m u ms o l u t i o n w h i l es e a r c h i n gal o c a lo p t i m a ls o l u t i o na sm u c ha sp o s s i b l e t h i sa l g o r i t h mc o m b i n e st h e a d v a n t i a g e so fc l o n a ls e l e c t i o na l g o r i t h ma n dt h ei m m u n en e t w o r ka l g o r i t h m ，a n db a s e do nt h e c l o n a ls e l e c t i o na l g o r i t h m ，i n t r o d u c e dt h es u p p r e s s i o no fi m m u n en e t w o r ka l g o r i t h mt ot h ee v o l u t i o n o fe a c hg e n e r a t i o n ，s e l e c t e das i m i l a rp r o b l e ms o l v e d ，a n dt h e na c c o r d i n gt oa f f i n i t y , r e m o v et h e p o o rq u a l i t ys o l u t i o n t h es u p p r e s s i o nr e m o v et h es i m i l a r i t yb e t w e e nd i f f e r e n tp o p u l a t i o n so f i n d i v i d u a l sa n dk e e pt h ed i v e r s i t yo fs e tm o r eb e t t e r i na d d i t i o n ，t h en e w a l g o r i t h mi m p r o v e di n t h es e l e c t i o ns t r a t e g yo fc l o n a ls e l e c t i o na l g o r i t h m ，w h i c hi st oe n s u r et h eo p t i m a ls o l u t i o nc a n b ei n h e r i t a n c ea n dr e t e n t i o n ，w h i l em a i n t a i n i n gt h ep o p u l a t i o ns i z e i nt h i sp a p e r , t h en e wa l g o r i t h mi sa n a l y z e da n ds i m u l a t e d ，a n dd ot h ec o m p a r t i o no ft h e r e s u l t si nt h ei m p l e m e n t a t i o np r o c e s sa n dp e r f o r m a n c eo ft h et r a d i t i o n a lc l o n a ls e l e c t i o n a l g o r i t h ma n da i n e ta l g o r i t h ma n dn e wa l g o r i t h m e x p e r i m e n t ss h o wt h a tt h ea l g o r i t h mh a s m o r ee f f e c t i v e l yi n s e a r c h i n gt h eg l o b a lo p t i m a ls o l u t i o na n dt h el o c a lo p t i m a ls o l u t i o n k e yw o r d s ：a r t i f i c i a li m m u n es y s t e m ，i m m u n eo p t i m i z a t i o na l g o r i t h m ，c l o n a ls e l e c t i o n a l g o r i t h m ，a i n e t ，c l o n a l g a i n e t 武汉科技大学硕士学位论文 第1 i i 页 目录 摘要i a b s t r a c t i i 目录i i l 第一章绪论1 1 1 研究背景l 1 2 人工免疫系统发展概况1 1 3 免疫优化算法的研究现状3 1 4 本文的主要工作及结构安排4 第二章人工免疫网络相关原理及模型5 2 1 人工免疫网络理论及特性5 2 2 克隆选择算法( c s a ) 6 2 2 1 克隆选择算法流程6 2 3 免疫网络模型7 2 3 1a i n e t ( a r t i f i c i a li m m u n en e t w o r k ) 7 2 3 2o p t - a i n e t 9 2 4 本章小结1 l 第三章优化问题相关理论1 3 3 1 最优化问题1 3 3 2 免疫优化的机理1 4 3 3 本章小结1 5 第四章基于免疫网络模型的优化算法设计1 6 4 1 人工免疫网络算法分析1 6 4 2c l o n a l g a i n e t 优化算法设计1 6 4 2 1 算法主要思想1 7 4 2 2 算法主要步骤l8 4 3 本章小结1 9 第五章仿真实验及结果分析2 0 5 1 实验方案2 0 5 2 实验结果及分析2 0 5 3 本章小结2 4 第六章总结与展望2 6 6 1 工作总结2 6 6 2 展望2 6 参考文献2 7 附录i 攻读硕士学位期间成果3 0 致谢3l 武汉科技大学硕士学位论文第1 页 1 1 研究背景 第一章绪论 今天，随着科学技术的不断进步，各种学科都得到了迅猛的发展，伴随学科研究的不 断深入和扩展，单一领域的理论已经不能完全解决复杂问题，这使得多学科、多领域交叉 得到长足发展，促使了边缘学科的形成。从2 0 世纪6 0 年代开始，自然现象或生物系统特性 的理论被信息科学不断借鉴、引用，并发展出了一系列相关理论，比如人工神经网络、进 化算法、模糊系统、人工免疫系统等。这些理论的应用对计算机技术、人工智能、计算智 能的发展等诸多领域的问题起到了巨大的推进作用，例如进化算法已经在机器学习、过程 控制、工程优化、等1 6 个大领域取得成功。 免疫系统是生物体中信息处理系统不可或缺的一部分，除此之外生物体还包括脑神经 系统、遗传系统、内分泌系统。自然免疫系统的主要作用是通过识别自身细胞特性，有效 的使用自身多种机能进行细胞分类，防御非自体病原体。基于自然免疫系统的特点，人们 逐渐丌始关注、研究免疫机制，尤其是国内外信息学科的学者们。他们基于免疫系统机理 进行仿生，建立了信息学科新型的信息处理系统人工免疫系统( a r t i f i c i a li m m u n e s y s t e m a i s ) 。基于免疫学的人工免疫系统仿照神经网络拥有自适应性及学习能力，同时， 与遗传算法类似拥有进化机制，实现群体的特异性和多样性。 1 9 9 8 年之前，免疫系统还未能引起相关学者的关注，1 9 9 8 年m a na n dc y b e r n e t i c s 国际 会议第一次组织了人工免疫系统专题讨论会。在以后的几年中，国内外学者对免疫系统的 研究不断增加，这成为继神经网络、进化算法、模糊系统之后的新热点。a i s 为实际的工 程问题带来诸多的启发，这其中包括模式识别能力、学习能力、记忆能力、多样性产生能 力、噪声耐受、分布式诊断和优化等。以免疫学为基础的计算技术，除了使人们更好的理 解免疫系统本身，更重要的是为现实工程问题带来解决方法。事实证明，人工免疫系统正 在成为应用日益广泛的一个新领域。 人工免疫系统发展概况 人工免疫系统的研究内容主要包括免疫计算智能系统、免疫工程应用系统、人工免疫 系统理论研究三个方面。 首先是免疫计算智能系统，由于受到自然免疫系统并行、分布式的自适应特性的启发， 研究人员开发了大量基于免疫系统的计算技术，主要体现以下三个方面： 第一，以生物免疫系统原理为基础的新算法，即免疫算法。这其中有阴性选择算法、 克隆选择算法、免疫优化算法、免疫遗传算法、以及为了完成各种任务设计出的基于免疫 原理的特定算法。优化是免疫算法的主要应用，多种形式的免疫算法已经广泛应用于优化 及调度方面【2 3 】。其中免疫克隆算法的多样性、全局和局部优化能力得到了深入丌发【4 | 。对 第2 页武汉科技大学 硕士学位论文 于免疫算法的研究是目前发展比较活跃的部分。图1 1 为一般智能计算与免疫计算的关系： 一。1 。_ _ _ 。一一 l 自然启发的计算l ；物理、化学启发的计算】：生物启发的计算 社会启发的计算 _ 。_ _ - 。1 。，。 一 i 进化计算免疫计算群钨 l 一 4 一一一习巫 ；砭孬习厂菟嚣螽孬 _ 一- 免疫湿件l 陬羞孩存i 苔 l 一jl 1 【jl 一 j 图1 1 其他智能计算与免疫计算的关系 第二，以生物免疫系统原理为基础的人工免疫网络模型和人工免疫系统模型。目前提 出的各种免疫网络学说有独特型网络【12 1 、免疫反应网络【1 4 1 、互联耦合免疫网络【1 3 】、对称网 络等【1 5 】。其中独特型网络的应用最为广泛。 第三，结合人工神经网络和模糊系统建立的混合智能系统，例如智能计算系统就结合 了免疫、神经网络、模糊技术；改进遗传算法进行的搜索优化利用了免疫系统抗体多样性 遗传机制。这方面研究主要是以与神经网络混合应用为主，发展比较缓慢。 其次为免疫工程应用研究，这方面主要是利用生物免疫系统某一特性解决特定工程问 题，另外还可以基于免疫学原理建立各种疾病诊断系统、保安系统、网络入侵诊断和检测 系统、应用于各种工业生产的故障检测、各种工业生产的故障诊断和异常检测系统。免疫 工程应用研究不同与免疫算法研究，它主要是为了解决特定问题的架构和硬件系统。其中 免疫算法有针对性的被嵌入其中。这方面的研究成果有很多，例如利用免疫系统阴性选择 机制，f o r r e s t 最早提出并设计了u n i x 系统下的计算病毒检测系统，k e p h a r t 提出一个免疫 系统启发的结构保护计算机不受病毒侵袭【5 1 。2 0 0 1 年w i l l i a m s 等人提出了基于免疫系统方法 的计算机网络防御系统【6 】。 最后是人工免疫系统理论研究，这一方面主要借助数学模型、非线性、混沌、计算机 智能等理论对人工免疫系统进行深入研究，这方面发展相对人工免疫系统的其他研究方面 相对滞后。目前一套能够解释所有人工免疫系统方法的通用性的相关理论体系尚未建立。 在欧盟资助i m c o m p 计划的自助下免疫计算成为主要研究内容【7 】。免疫计算计划的研究目 标是建立基于自然免疫系统的数学模型【8 1 ，并将该算法应用于软件和硬件。目前，在此计 划支持下，以生物体内蛋白质和免疫网络信息处理原理为基础，一种新的免疫计算范例已 经被研究人员建立，用以解决特定复杂问题和计算机系统中入侵袭击、防护病毒、噪声和 随机误差等问题。该计划最终实现设计出免疫计算机原型及软件系统，称为免疫计算机的 新型计算机系统【9 】。 人工免疫系统研究的三个方面是相互渗透、相互联系的。根捌研究和应用情况来看又 可以分两种情况：一是为解决特殊问题进行的计算方法上的研究，比如解决光谱分析问题 武汉科技大学硕士学位论文第3 页 的免疫算法，只能用于解决光谱分析【1 6 】；二是具有普遍意义的系统和方法，例如二进制免 疫系统模型【2 1 。2 4 1 ，这个已经得到广泛应用。而计算机与网络入侵检测和计算机免疫系统作 为一种计算机安全系统已经广泛应用到多个研究组织。 人工免疫系统与其他学科和领域交叉应用如图1 2 所示。 图1 2 人工免疫系统与其他学科和领域的交叉关系及其应用 1 3 免疫优化算法的研究现状 借鉴免疫系统的诸多优点，许多新型的计算方法被发展出来运用于信息学科。目前比 较典型的算法有：克隆选择算法、免疫遗传算法、阴性选择算法等，这些算法已经被广泛 应用于实际问题的解决。 免疫算法应用于优化领域的主要分为以下几类：l 、通过对亲和力相关克隆和变异过 程进行控制的免疫优化算法【1 7 锄】，此类算法在抑制早熟的环节上具有良好的效果，算法本 身实现了优质抗体特性保持，同时也提高了种群的多样性，使优化解集具有良好的全局收 敛性；2 、以克隆选择算法为研究基础的优化算法【i6 1 ，这些算法借鉴了免疫系统克隆选择 的机制，在算法演进过程实现优秀抗体的扩展和新增，同时，基于算法具有的记忆特性保 证了全局最优解的收敛；3 、在免疫优化算法中引入疫苗接种的概念【l ，此类算法在实现 过程中，将算法中的已知问题考虑在内，按照一定规则预先定义疫苗的规则，将算法中的 已知问题考虑在内，保证了问题的有效解决，实验证明此类算法在优化问题中可以带来良 好的效果；4 、基于免疫抗体记忆的免疫优化算法【27 1 ，这类算法将这种算法将随机搜索过 第4 页武汉科技大学硕士学位论文 程中的局部搜索和全局搜索采用不同的促进和抑制策略，有效保证了算法的收敛速度。免 疫算法本身所具的学习、认知、记忆等特性，也决定了它在解决各种优化问题上具有的巨 大潜力。 本文的主要工作及结构安排 本文的主要研究目的是用免疫算法解决最优化问题。基于目前的c l o n a l g 算法，以及在 此基础上提出的a i n e t 算法，提出一种新的优化算法，解决定义域内全局最优解和局部最优 解的搜索问题，该算法有效的抑制了种群间相似个体的产生，提高了计算效率。通过仿真 实验及结果分析进一步的说明了算法的优越性。 本文分为六章，各章内容组织如下： 第一章简要的介绍了人工免疫系统的研究背景及意义、对免疫优化算法的研究现状 进行了阐述，对本文的主要研究内容及结构安排做介绍。 第二章介绍了人工免疫网络的相关理论，主要包括a i n e t 算法原理介绍、遗传选择算 法的原理介绍及o p t a i n e t 算法思想。 第三章介绍了优化问题，重点介绍了免疫优化的机理。 第四章对克隆选择算法及a i n e t 算法进行了分析，阐述了这两中算法的优点及不足， 最后结合克隆选择算法和免疫网络算法的优点，在克隆选择算法的基础上提出一种新的算 法c l o n a l g - a i n e t 。 第五章基于第四章提出的新算法，进行仿真实验，对实验结果进行分析，并同传统 的克隆选择算法及免疫网络算法进行实验对比，说明新算法的优越性。 第六章对本论文研究内容进行了总结，并对相关领域的工作进行分析列出待研究的 内容。 武汉科技大学硕士学位论文 第5 页 第二章人工免疫网络相关原理及模型 人工免疫网络理论及特性 人工免疫网络是基于免疫网络理论提出的，1 9 7 4 年美国诺贝尔奖获得者j e i i l e 提出免疫 网络理论和概念，该理论描述了淋巴细胞活动、自然抗体产生和预免疫指令系统选择、埋 首、自体非自体识别、记忆和免疫系统进化等特点。指出，免疫系统由即使没有抗原的情 况下也能相互识别的细胞分子调整的网络构成。免疫系统正式定义为大量的复杂的识别抗 原决定基的抗体决定基和抗体决定基识别的独特型集合的网络。 淋巴细胞通过抗原抗体相互作用而动态的联系。不仅抗原、由淋巴细胞产生的抗体也 起抵制其他淋巴细胞的作用，这样的作用是在产生免疫系统的抗原内影像。抗原及其内影 像都对可作用于同一类的淋巴细胞。网络理论的主要特征为：抗原、抗体的相互作用形成 均匀网络；存在内在抗原内影像【2 5 2 6 】。如图2 1 所示。 p 2 抗原 一一 抗熔决定基p1 内影像 1 2 i1 独特位 - p 3 1 3 图2 1 免疫网络 免疫网络中，抗体的产生具有随机性，即抗体被看做有机体当作抗原处理。抗原决定 基和抗体决定基为免疫识别的两个基本特性。目i j i 实验证实，抗体分子具有功能性作用， 呈现抗原决定基。 人工免疫网络遵从免疫网络特性也具有以下三个主要特性，结构、动念性、亚动力学。 结构描述免疫网络中分子和细胞内成分之间相互作用的类型，不涉及它们可能具有的功能 性后果。在免疫系统中真正起到作用的不是分子本身，而是分子间的相互作用。免疫动态 性指免疫元素问的相互作用，免疫元素相互抑制和作用是抗体v 区变化的作用结果。免疫 系统的亚动力学的性质是新抗体的连续产生。不仅存在免疫活性淋巴细胞的高流通率，也 存在通过新形成的淋巴细胞、非刺激或者自体反应细胞的死亡保持更新网络结构的过程， 系统的动态性持续变化产生新的结构。免疫网络方面的亚动力学性表示了免疫学习机制。 第6 页武汉科技大学硕士学位论文 2 2 克隆选择算法( c s a ) 在生物学中，生物免疫是指机体识别并排除非自体异物，并保持自身生理稳定和平衡 的功能。抗体和抗原是免疫系统主要的特征体。在机体受到刺激时，免疫系统引发免疫应 答产生具有免疫效应的物质，即抗原。抗体是在这种情况下，产生的与抗原结合的特异性 物质。 克隆选择学说是指生物体中的抗体以受体形式存在，并与抗原进行选择行反应的过 程。抗原和抗体问进行反应最终导致细胞产生克隆性增殖，克隆出的细胞具有特异性，这 其中一些细胞分化为抗体生成细胞，另外的一些免疫记忆细胞参加二次免疫反应。基于生 物学克隆选择机理具有的记忆、学习和进化特性，研究人员在问题优化方面受到启发，2 0 0 0 年，d ec a s t r o 等人对克隆选择机理进行了进一步概括，提出了一种更为简单的克隆选择算 法( c l o n a l 酌【2 9 1 。c l o n a l g 算法的原理是通过亲和度成熟进行操作，产生高亲和度的个体，并 从中选择改进后的后代加入抗体集。c l o n a l g 算法通过搜索周边的空间，对单个个体在局部 实现了优化，并且产生了新的个体，扩大了搜索空间，这表明算法具有贪婪搜索能力。 c l o n a l g 算法的特性非常适合多峰函数优化【3 0 1 。 2 2 1 克隆选择算法流程 模型描述：从指令系统中将功能性记忆细胞分离出来；适应度高的个体存活下来，并 进行选择和克隆；适应度低的细胞被淘汰；根据亲和力，将较高亲和力克隆的进行重新选 择；产生和保持细胞多样性；亲和力低的细胞产生高频变异； 算法工作流程图2 2 女i ：1 下 图2 2 克隆选择算法流程图 算法描述：随机生成抗体数目为n 的初始抗体集合a b 。 武汉科技大学硕士学位论文第7 页 1 根据a b ，确定其适应度f 。 2 选择出适应度最高的n 个个体，组成新的抗体集合a b n ，。 3 克隆新抗体集a b 。，形成新的抗体集c 。对于新抗体集c ，其中亲和里越大 的，克隆的次数越多。但在多峰值函数中每个个体克隆次数为n x 8 次，6 为克 隆率。 4 c 进行变异形成成熟抗体集c 木，抗体集c 中适应度低的个体产生的变异越大。 5 对于抗体集c 宰中的每个个体计算适应度向量f 宰。 6 在c 宰中选取n 个适应度高的抗体，组成抗体集a b l n 进入初始抗体集a b 。 7 产生d 个新抗体替换a b 中适应度最低的d 个抗体。 达到条件结束，返回步骤2 执行下次循环。 2 3 免疫网络模型 2 3 1a i n e t ( a r t i f i c i a li m m u n en e 铆o r k ) 是1 9 7 4 年由美国诺贝尔奖获得者j e n l e 提出，是生物学上关于淋巴细胞活动、自然抗体 免疫网络产生、预免疫指令系统选择、和自体非白体区分、记忆和免疫系统进化等观点的 新构想【i l 】。免疫网络假设免疫系统在没有抗原的情况下也可以进行细胞、分子问的相互识 别形成网络。免疫细胞对抗原或其他免疫细胞进行判断和选择。被选择的细胞进行激活、 分芽繁殖及抗体分泌。未被选择的导致抗体抑制。 a i n e t ( a n i f i c i a li m m u n en e 觚o n ) 是由d ec a s t r o 以生物免疫网络原理为基础最早提出 的【”】，此网络模型忽略了抗体与b 细胞的区别，并且拥有减少冗余、包括聚类形状、描述 数据结构等特征。数据集的聚类问题和过滤问题是该网络模型主要研究的问题，研究证实 了免疫系统强大的计算能力。 2 3 1 1a 州e t 的网络定义及描述 m n e t 可以看做为一个边界加权图，它由细胞的节点集合构成，节点相对集合称为边界。 相连的边界都具有一组连接强度，通常称之为亲和力。 a i n e t 具有两个特性，一是进化的，根据群体内遗传、变异和选择控制网络可塑性和动 态；二是连接的，由于a i n e t 为边界加权图，需要定义出连接强度的相关矩阵度量网络细胞 间的亲和力。如图2 3 ( a ) 所以示，定义网络中聚类为内映像，将数据集合中的聚类映射到网 络聚类。图2 3 ( b ) 为假设的网络结构，由a i n e t 产生。图2 3 ( b ) 显示出细胞构成和连接强度， 当权值大于某一个阈值时用虚线表示，表明该连接应被剪除，其目的是为对聚类进行检测， 并定义出最终的网络。 第8 页武汉科技大学硕士学位论文 图2 3 ( a ) 网络聚类 0 5 一一 图2 _ 3 ( b ) a i n e t 类似免疫网络，a i n e t 中通过亲和力对抗原进行识别和选择，留下来的细胞就会引导网 络进行细胞变异和扩增，即进行克隆选择。不具备条件的细胞被系统淘汰。同时，通过a b a b 识别进行网络抑制，模型中给定抑制阈值。在形状空间s 内每一对a g - a b 相互联系，通过他 们之间亲和力d j j 交互作用反映不相似性，即克隆的概率，同理，每一对a b a b 的亲和力s i j 反应相似性交互。 在多维向量空间r 中定义如下： x ：表示向量n p 的数据集合( x r p ) a b m ：有n 构成的网络细胞矩阵( a b m r m x p ) a b m i ：抗体的克隆记忆细胞矩阵。( a b m 包含a b m i ) d ：元素d i j ( a g - a b ) 的相似矩阵，d i j 为抗原和抗体间的亲和力，抗体、抗原间的距离越 小，其亲和力d 越大。可以表示为： 加瓦1 d = 毫沪船一川，m 2 1 n ：每一个选择细胞产生的克隆细胞个数 s ：关于s i i 的梢似矩阵。 一 ， ，、， ，卜6 武汉科技大学硕士学位论文第9 页 n ：选择出的进行变异和克隆的细胞个数 1 ：选择的成熟细胞的百分比 三：表示抑制阈值 a i n e t 算法描述如下： 1 对于每一个抗原a g i 执行一下步骤： 1 1 确定其与网络中所有抗体a b j 的亲和力d i j ； 1 2 根据亲和力大小进行克隆选择，选出n 个具有最高亲和力的网络细胞； 1 3 亲和力越高，则克隆的细胞个数越多，即n 越大； 1 4 根据公式对细胞n 进行控制成熟。 1 c a + = c a + o c ( a g i c ) ，0 【芘_ j k ，江1 ，朋，j = l ， d u ( 2 2 ) 1 5 根据确定的细胞n 生成d i j ( a g a b ) 的相似矩阵d ； 1 6 亲和力计算； 1 7 根据d 重新选择最高亲和力的细胞的”，建立a b m i 的记忆细胞矩阵； 1 8 x 寸于亲和力低于e 的细胞进行清除，形成a b m i 的消减矩阵； 1 9 计算a g a b 的亲和力s i j ； 1 1 0 进行克隆抑制，将s i j d , 于阈值芒的细胞清除； 1 1 1 将记忆细胞集合放入原有细胞矩阵，连接a b m i 和a b m： 2 确定s ，并清除s i j 芎的细胞( 网络抑制) ； 3 达到迭代次数，生成免疫网络； 2 3 2o p t - a i n e t 作为人工免疫系统的重要模型，a i n e t 在解决优化问题上具有优越的性能，在减少冗余 的同时可以保持局部优化解的多样性。但是，随着人们对a i n e t 模型的研究深入，也发现a i n e t 在应用中的一些问题，例如，如果目标函数定义不当，可能会导致汜忆网络无规律动态变 化，最终无法收敛到最优解；再或者，当存在噪声或样本边界不够清晰时，会引起抗体产 生导致免疫网络结构的模糊。针对存在的问题，研究人员在a i n e t 的基础上又进行了深入的 研究，以a i n e t 为基础产生了一系列的优化的算法，o p t a i n e t 是其中最著名的一种1 3 6 j 【4 。 2 3 2 1o p t - a i n e t 算法描述 免疫网络优化算法，简称o p t a i n e t ，最早是由d e c a s t r o 幂i t i m m i s ，在c l o n a l g 算法 的基础上进行拓展得出。o p t a i n e t 算法实现了个体的动态分配，同免疫系统中的细胞一样， 群体中的每个个体，用欧几罩空f n j 中一个实时向量进行表示。实验证明o p t a i n e t 在多峰 值搜索的能力上具有一定的优越性【2 8 】。 以下为此算法的描述： 第1 0 页武汉科技大学硕士学位论文 1 1 1 1 i t i a l i z ea n t i b o d i e ss e t e 卜 5 j 4 譬，a b ，= 彳6 ，) ：， 爿研” 2 w h i l en o tc o n v e r g e da n di t i t m a x n u m 初始化抗体群 评估每一个抗体的亲和力 当未达到迭代次数执行 一c l o n e 克隆 一m u t a t e 变异 一e v a l u a t ea f f i n i t ya f , ) f o re a c h 彳妒对新生成的抗体矩阵4 6 ： 进行亲和力彳f ) 计算 一f o re a c hc l o n es e l e c tt h em o s tf i ta n dr e m o v et h eo t h e r s ( c l o n a ls u p p r e s s i o n ) 克隆抑制 一i t = i 什1 d e t e r m i n e a v e r a g e e r r o r ( a v e f i t e r m o w = a b s ( m e a n ( e r r ) ) ； n o t c o n v e r g e e d = - - ( ( 1 一a v e f i t e r r n o w a v e f i t e r r o l d ) 0 1 ) ； 一s u p p r e s s i o n 网络抑制 3 c h o o s enh i l g h e s ta f f i n i t ya n t i b o d i e s选择n 个亲和力最大的抗体 i n t r o d u c eap e r c e n t a g edo f r a n d o m l yg e n e r a t e dn e t w o r kc e l l s 随机生成d 的网 络细胞 2 3 2 2c e l ll i n e 抑制 在o p t a i n e t 中利用欧氏距离间接测量细胞问的亲和力，为了更准确的设置阈值参数( 强 度a s ) ，需要预先考虑到算法实现中一些函数的优化。在某些情况下，很难确定一个适当 的阈值。在文献【柏】中对o p t a i n e t 进行了优化，采用c e l ll i n es u p p r e s s i o n 有效的进行抑制， 降低了具有相同亲和力的细胞在峰值上聚集，从而减少冗余。该细胞为抑制算法描述如下。 f u n c t i o n x _ c e l l _ l i n e s u p p r e s s ( x ，g s ) f o re a c hp a i ro f c e l l sx l ，x 2d o 只= 【x lf ( x 1 ) 】 最= x 2f ( x 2 ) 】 p = x l + o 5 ( x 2 x 1 ) f ( x l + o 5 ( x 2 - x 1 ) ) 】 v 2 罡一只 w 2p 一只 c l = w v向量w 、v 的点积 武汉科技大学硕士学位论文第11 页 c 2 = l v i 向量v 的模 b = c l c 2 i f c l = 0 ，距离点只最近的点 d = d i s t ( p ，只) e l s ei fc 2 = c l ， 距离点最近的点 d = d i s t ( p ，昱) e l s e ， 圪w h e r e p 圪上e 尸2 忍= 鼻+ b v d = d i s t ( p ，圪) e n d i f d g st h e n e l i m i n a t et h ec e l lw i t hw o r s to b j e c t i v e f u n c t i o nv a l u e e n d 点只、罡为两个抗体在空间域中的位置，表示为i x 。，厂g ，) 】和i x ：，s ( x ：) 】，e , 6 为连接只、 的缄点p 为点只冀的中点表示为尸_ 掣厂( 掣 ，胍w 删表示丽 及p 只。然后，计算点p 到舅的距离，此距离由点p 到线段的投影进行表示，如果投影 在线段外部，则点只( 当c l 0 时) 或者最( 当c 2 = e l 时) 在满足条件下被保留。随后， 计算两点间的欧氏距离，如果小于阈值( i s ，则其中一个抗体细胞被淘汰。此时阈值的设置 将更容易，由于不同于抗体细胞间距离，阈值设置不能太大，经过实验证实，建议设置阈 值为o s = 0 5 。 2 4 本章小结 本章主要介绍了人工免疫网络相关原理，在此基础上大量的免疫算法被提出，本文中 重点介绍了克隆选择算法和免疫网络算法，克隆选择算法是通过亲和度成熟进行操作，产 生高亲和度的个体，并从中选择改进后的后代加入抗体集的过程。免疫网络模型( a i n e t ) 第1 2 页武汉科技大学硕士学位论文 忽略了抗体与b 细胞的区别，并且拥有减少冗余、包括聚类形状、描述数据结构等特征。 数据集的聚类问题和过滤问题是该网络模型主要研究的问题。本文通过对这两种算法的研 究，对免疫算法解决优化问题进行了进一步的思考。 武汉科技大学硕士学位论文第1 3 页 3 1 最优化问题 第三章优化问题相关理论 变量参数、目标函数和约束条件是优化问题研究的几个因素，他们之问的函数表达式 如下： f m a x f ( x ) = f ( 1 ，x 2 ，)( 3 1 ) k t x = ( x l ，x 2 ，而) q 其中，f 【x ) 称为目标函数，x q 称为约束条件，q 称为x 的定义域。对于优化问题 通常可以归为以下四类：线性规划( l i n e a rp r o g r a m n l i n g ) 问题、二次规划( q u a d r a t i c p r o g r a n n l l i n g ) 问题、凸规划( c o n v e xp r o g r a n n l l i n g ) 问题、非凸规划( n o n c o n v e x p r o g r a n n l l i n g ) i h j 题 3 2 , 3 3 1 。 1 ) 线性规戈1 ( l i n e a rp r o g r a m n l i n g ) i n 题是当约束条件和目标函数都为线性表达式时， 对这类问题，现在有比较完善的求解方法。 2 ) 二次规划( q u a d r a t i cp r o g r a n n l l i n g ) i h 题是当目标函数为二次函数，而约束条件为线 性约束时，对二次规划问题，类似于线性规划也可以找到有限步搜索的接的优化 方法。 3 ) 凸舰划( c o n v e xp r o g r a n n l l i n g ) i 口 题是当目标函数为凸函数，约束条件确定的可行 域q 为凸空间时，牛顿法、梯度下降法、准牛顿法等方法都能有效地搜索到最优 解。 非凸舰划( n o n c o n v e xp r o g r a n n l l i n g ) l h 题，一般会收敛于局部的极值点，在全局范围内 找到最优解比较困难，对此一直没有非常有效的求解方法。 从上个世纪六十年代开始，以遗传算法为代表，发展出大量的进化计算，这些算法是 一种随机搜索机制，在大规模、多峰值优化求全局最优解问题上得到应用。 优化问题对于所有目标函数来讲不存在唯一解，也就是说没有全局最优解。但是存在 对一个或几个目标函数最优，但对其他目标函数不会劣化的解，这样的解我们称为非劣最 优解。 非劣解的定义为，在可行解中存在x 幸，使得x s t 不存在任意的x 满足f 【x ) f ( x 木) ，则 x 宰称之为非劣解。非劣解也称为p a r e t o 最优解，或有效解，非劣解不止一个，非劣解的集 合称之为非劣解集，表示为x 幸。最优化的目标就是，在满足约束条件下寻求使目标函数最 大的解的集合【