（交通信息工程及控制专业论文）基于免疫原理的优化算法及应用研究.pdf

摘要 i 基于免疫原理的优化算法及应用研究 摘要 基于免疫原理的优化算法及应用研究 摘要 作为一个复杂的生物系统，免疫系统具有强大的信息处理能力。基于免疫机理发展 起来的人工免疫系统具有噪声忍耐、自组织、自学习、记忆等优良特性；它吸取了分类 器、神经网络等系统的优点。其独特的信息处理方式，为求解复杂的优化和控制问题提 供了有益的参考。本文对基于免疫原理的优化进行了研究探讨。主要研究内容和成果如 下 ： 1. 对人工免疫系统的生物学理论基础、 免疫优化机理进行了概述， 综述了国内外在 该领域的理论及工程应用研究情况，并简单介绍了常见的免疫算法及其特点。 2. 借鉴 b 细胞的克隆选择、免疫网络及 baldwin 效应等机制，提出了一种针对多 模态函数优化的免疫算法，通过与小生境遗传算法及克隆选择算法的实验比较，结果表 明该算法优化速度快，保持模式多样性的能力强，具有较强的优化能力。 3. 借鉴免疫反应机理， 提出一种动态环境下的免疫算法。 通过与几种典型算法的比 较，仿真结果表明该算法具有较强的动态优化能力，跟踪性能及其跟踪变化的效率都较 强，优化性能较为稳定。 4. 将动态免疫算法用于城市交通信号控制， 提出一种城市交通信号免疫自适应控制 方法。通过仿真实验进一步验证算法在实际工程应用中的有效性。 关键词关键词： 人工免疫系统，免疫算法，克隆选择，函数优化，动态环境，交通信号控制 abstract ii research on optimization algorithms and its applications based on immune mechanisms abstract as a complex system of organism, immune system has strong capabilities of information processing. the artificial immune system is based on mechanisms of the immune system, which has eminent characteristics of noise tolerance, self-organization, self-learning and memory and other excellent features. it combines advantages of the classifier, neural network, and other artificial intelligence systems. its special methods of information processing provide beneficial references to solve problems of complex optimization and control. in this paper, function optimization approaches based on mechanisms of the natural immune system are researched. the main works can be summarized as follows: 1. summarized the useful mechanisms of natural immune system, and the research works on artificial immune system and its applications in the world. meanwhile, the frames and characters of some familiar immune algorithms were simply introduced. 2. a multi-modal function optimization algorithm based on the mechanisms of clonal selection, immune networks and baldwin effect of b cells is presented. comparing simulations of niching genetic algorithm and clonal selection algorithm are conducted. results show this algorithm had strong ability of function optimization and maintaining diversity. 3. an immune algorithm based on immune responsed mechanisms is presented for dynamic environmental optimization. the algorithm is applied dynamic environment mutil-modal function, and compared with some typical algorithms. results show the algorithm had strong ability of non-stationary optimization, strong ability of track and effect of track changing. it has stationary ability of optimization. 4. an immune adaptive control approach for urban traffic signal control based on immune algorithm in dynamic environment is presented. the results of simulation test show the approach is effective in engineering application. key words: artificial immune system, immune algorithm, clonal selection, function optimization, dynamic environments, traffic signal control 独创性声明独创性声明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表和撰写的研究成果，也不包含为获得华 东交通大学或其他教育机构的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢 意。 本人签名_日期_ 关于论文使用授权的说明关于论文使用授权的说明 本人完全了解华东交通大学有关保留、使用学位论文的规定，即：学 校有权保留送交论文的复印件，允许论文被查阅和借阅。学校可以公布论 文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 保密的论文在解密后遵守此规定，本论文无保密内容。保密的论文在解密后遵守此规定，本论文无保密内容。 本人签名_导师签名_日期_ 第一章 绪论 1 第一章第一章 绪论绪论 神奇的自然界一直激发着人们不断探索自身和生物的奥秘， 并推动着科学和工程技 术向前发展。从信息处理角度来看，生物体是一个性能卓越的信息处理器，其解决问题 的能力让目前最好的计算机也叹为观止。在生物体中，最复杂也最引起人们兴趣的信息 处理系统有脑神经系统(brain neural systems)、遗传系统(genetic systems)、免疫系统 (immune systems)、内分泌系统(endocrine systems)等。这些信息处理系统既相对独立， 又相互作用，共同维持人体的生存和发展。近几十年来，人们借助计算机技术，模仿这 些系统的工作原理，提出了许多智能信息处理方法，如人工智能、模糊系统、人工神经 网络及遗传算法等， 如今， 这些方法已被广泛应用于工程实践， 取得了令人瞩目的成效。 人工免疫系统(ais:artificial immune system)是借鉴生物免疫系统原理发展起来的新的 信息处理方法，它结合了分类器、神经网络和机器推理等系统优点，为复杂问题求解提 供了一种新的方法，并成功应用于机器学习、函数优化、故障诊断、智能控制等研究领 域，目前已经成为继神经网络、模糊逻辑和进化计算后人工智能的又一研究热点1。本 文在前人研究成果的基础上， 对基于免疫原理的函数优化算法及其在工程中的应用进行 了研究。 1.1 人工免疫系统研究现状人工免疫系统研究现状 人工免疫系统是借鉴生物免疫系统的工作原理和机制而发展起来的各种信息处理 技术、计算技术及其在工程和科学应用中产生的各种智能系统的统称2。以 jerne 提出 的独特型网络模型为标志，ais 研究开始于二十世纪七十年代，至今三十多年。下面从 理论和应用两个方面概况 ais 的研究情况。 1.1.1 人工免疫系统的理论研究人工免疫系统的理论研究 人工免疫系统理论研究主要集中在人工免疫网络模型、 免疫算法及免疫多样性三个 方面。 1. 人工免疫网络模型研究 人们根据应用对象不同，从不同角度模拟免疫系统，提出了不少有价值的人工免疫 网络模型。其中最为著名的是 jerne3提出的独特型网络模型(idiotypic network)。他从抗 体独特型出发，认为抗体具有抗体和抗原两重属性，在识别抗原的同时，也会被其它抗 体识别而产生免疫反应，因而整个免疫系统是一个通过抗体相互作用构成的网络结构， 并给出了免疫网络动态特性的微分方程表达式。 独特型网络理论能够较好地解释免疫初 次反应、二次反应、免疫记忆等现象。该模型作为一种非线性动力学系统，被广泛用于 自适应控制、机器学习和故障诊断等领域。 第一章 绪论 2 1989 年 perelson4在前人研究基础上，对独特型网络进行了深入研究。他从抗原形 态空间理论的角度出发，开创了用二进制编码描述抗体和研究免疫现象的方法，并给出 了独特型网络的概率模型。 1995 年 ishiguro5提出一种互联耦合人工免疫网络模型。他将一种分级递阶式免疫 网络，用于六足机器人的姿态控制，获得了满意的效果。 1997 年 tang6模拟生物免疫系统中 b 细胞和 t 细胞的相互作用，提出了多值免疫 网络模型，并用于字符识别。该模型具有分类少、记忆模式新和容量大等优点。 2000 年 de castro7等受独特型免疫网络的启发， 提出了一种名为 ainet 的免疫网络。 该网络模型忽略了 b 细胞和抗体的区别，利用统计推论技术，实现免疫网络对抗原的刺 激过程，主要包括抗体-抗原识别、免疫克隆增殖、亲和度成熟以及网络抑制。该模型 用于研究未标识数据集合的聚类和过滤问题，结果表明了免疫系统具有强大的计算能 力。 2. 免疫算法的研究 借鉴免疫系统运行机制提出学习和优化算法，是 ais 理论研究的重要内容之一。目 前提出的算法主要有：1994 年 forrest8提出一种阴性选择算法。该算法模拟免疫系统的 “自己” 、 “非己”识别方式，通过构造“t 细胞”结构，定义一组“自我集”和“监视 集” ，通过按概率检测系统异常，能够实现鲁棒的故障诊断。该算法被用于网络安全监 测，取得较好的效果；1995 年 hunt9等人提出一种基于 b 细胞网络的学习结构。该算 法以免疫系统中的 b 细胞为原型，通过 b 细胞网络的模式匹配和记忆更新，可以完成 复杂的模式学习和自组织记忆。 该算法被用于 dna 序列识别， 取得了较好的效果。 1996 年 ishida10等人借鉴免疫系统的局部记忆学说和免疫网络学说，提出免疫 agent 算法。 该算法包括多样性产生、 自忍耐建立、 记忆非己三种操作， 适合用于计算机病毒库进化、 网络防御和自适应控制等应用领域； 1997 年 chun11 等人将体细胞理论和遗传算法相结 合，提出一种免疫遗传算法。它通过在遗传算法流程中添加了个体浓度控制机制，使得 高适应度的超级个体在群体中的扩散速度被有效控制， 从而有助于解决遗传算法的早熟 问题， 具有较强的全局优化能力。 如今， 国内外已经涌现出较多这方面的应用成果； 1999 年 narauaki12借鉴免疫网络和免疫 mhc(major histocompatibility complex)原理提出一 种免疫自适应优化算法(immune adaptive algorithm)；2000 年 castro 13,14等人提出一种 克隆选择算法。该算法以 b 细胞的克隆选择理论为基础，用“抗原”表示优化解，用“b 细胞”表示解的可能模式，通过 b 细胞的高变异克隆完成全局最优解的搜索。该算法结 构新颖、性能优良，能够保持模式多样化，适用于求解复杂函数优化问题；同年，王磊 15,16等人提出了一种免疫规划算法。该算法模拟了免疫系统特有的自适应性和人工免疫 中接种疫苗这一加强免疫的手段，使算法具有快速全局收敛的良好性能。 3. 免疫多样性研究 抗体多样性产生机理的研究具有重要的理论意义和应用价值。目前，这方面的研究 第一章 绪论 3 相对薄弱。主要研究成果有：1996 年 perelson17等人提出了形状空间理论，开创了用数 学手段解释免疫系统多样性形成的研究；同年，hightower18等人以形状空间理论为基 础，对抗体基因库的形成机理做了进一步研究，并证明了“高变异操作”在免疫系统识 别多样性的产生中起着重要作用； 1998 年 opera19用二进制抗体模型研究了免疫系统多 样性原理和进化意义。 1.1.2 人工免疫系统的应用研究人工免疫系统的应用研究 人工免疫系统已经成功用于自动控制、 优化计算、 模式识别与故障诊断、 网络安全、 数据挖掘、图像和数据处理等诸多领域。下面对其进行简要介绍。 1. 自动控制 自动控制是 ais 应用的重要方向之一20。主要成果有：1995 年 mitsumoto 等人提 出分布式机器人群体数量决策方案21实现了分布式自治机器人群体的自组织；1997 年 lee 等人用 t 细胞作用下独特型网络方程描述系统动态过程，提出了分布式、自治机 器人的协作控制方案22； 1998 年 dasgupta 等人借鉴独特型网络理论和免疫系统的识别 反应机理，构造了基于人工免疫系统的多智能体决策和控制框架23； 1999 年 sasaki 等 提出一种基于免疫系统反馈机理的自适应学习的神经网络控制器24；2000 年丁永生等 针对低阶或高阶对象， 提出了一种新颖的基于生物免疫系统反馈机理的通用控制器结构 25,26； 2001 年 kim 用免疫网络算法优化 pid 控制器参数，实现了非线性对象的自适应 pid 控制27 。 2. 模式识别和故障诊断 模式识别和故障诊断是人工免疫系统应用的又一个重要方向。主要应用有：hunt28 等基于 b 细胞网络的免疫学习算法，用来进行 dna 的模式识别，取得了较好效果； castro14 等采用状态空间表示待识别的模式，研究了基于克隆选择原理的字符识别问 题； ishida29提出基于相关识别特性的免疫网络故障诊断方法，用于化工过程仪器系统 的故障诊断；tang6 将人工免疫网络模型用于交流驱动和 ups 的控制和诊断； dasgupta30等将人工免疫系统用于加工工具破损监测； 刘树林31等提出了对旋转机械在 线故障诊断的新方法；杜海峰32等将 art-人工免疫系统用于解决多级往复式压缩机故 障诊断，效果良好。 3. 优化计算33 优化计算也是人工免疫系统应用的一个重要方向。 基于 ais 的函数优化方法大致可 分为三类： (1) 利用免疫系统的抗体浓度控制机制改造遗传算法，克服遗传算法的早熟问题。 目前这方面应用较多，如：永磁同步电机参数优化；电磁设备外形优化；vlsi 印刷线 路板布线优化；函数测试；旅行商问题求解，约束优化和多判据设计等等。 (2) 根据 b 细胞的克隆选择原理提出新的优化算法。 克隆选择是免疫系统搜索抗体 的重要手段之一。其搜索机理类似 ep(evolutionary program)，借鉴克隆选择机理建立起 第一章 绪论 4 来的函数优化算法具有较强的全局优化能力，同时能够保持抗体模式的多样性。适合用 于求解复杂的函数优化问题。目前主要的应用成果有：旅行商问题求解；pid 控制器参 数优化等等。 (3) 借鉴人工免疫的思想，将先验知识表达成疫苗，持续改良抗体结构，达到加快 算法的全局收敛速度的目的。该方法用于求解旅行商问题，表现出良好的性能。 4. 网络安全 ais 在网络安全方面也有许多应用实例。基于免疫原理的计算机系统比普通操作系 统所支持的系统更具有辨别和保护能力。应用成果有计算机病毒检测等8,34,35。 1.2 本文主要内容本文主要内容 1.2.1 课题背景课题背景 种群多样性是影响进化算法优化性能的重要因素之一。遗传算法（ga:genetic algorithm）作为进化算法的代表，通过染色体基因的筛选和重组，能够获得较强的全局 优化结果。但是 ga 存在模式收敛性质，种群模式趋于单一，难以有效维持模式的多样 性，容易出现早熟现象，因而影响遗传算法的优化效果。遗传算法用于求解多模态函数 和动态函数优化问题效果不佳的主要原因在于此。免疫系统在遇到未知抗原入侵时，能 够迅速搜索到与之匹配的抗体，消除抗原，保持肌体健康，这意味着免疫系统具备强大 的优化能力。值得注意的是，免疫系统在实现快速优化的同时，通过自我调节机制调节 体内抗体的浓度有效地维持多种抗体长期并存。另外，克隆选择作为免疫系统重要搜索 手段具有较强的优化能力，同时也产生和保持免疫多样性。再者，免疫系统的补充机制 和记忆机制都具备了增强和保持免疫多样性和更有效抗击抗原的能力。 这些机理为优化 计算提供有效的参考。 因此借鉴免疫系统工作原理有助于构造出新的高性能函数优化算 法。 1.2.2 本文研究内容、结构本文研究内容、结构 鉴于以上国内外人工免疫系统研究现状，本文基于免疫原理构建出新的免疫算法， 并探讨它们在函数优化方面及其在工程中的应用。主要内容有： (1) 借鉴免疫系统的克隆选择、免疫网络调节、baldwin 效应等机制，提出一种多 模态函数优化算法。 (2) 借鉴免疫应答机理，提出一种动态环境下的多模态函数优化的免疫算法。 (3) 以动态环境下的免疫算法为核心提出一种城市交通信号的免疫自适应控制方 法。 全文共分六章，各章的主要内容如下： 第一章对人工免疫系统研究进行概述， 最后简要介绍了本文主要内容及论文的各章 节安排。 第一章 绪论 5 第二章介绍人工免疫系统的生物学理论基础、免疫优化的机理，并在叙述几种常用 的免疫学术语在 ais 中相对应含义的基础上，简要介绍了几种常见的免疫算法结构，并 对算法特点进行了分析。 第三章借鉴免疫系统的免疫网络、克隆选择、免疫记忆和 baldwin 效应等机理，针 对多模态函数优化问题，研究了改进的多模态函数优化方法，并通过仿真比较，验证算 法的有效性。 第四章借鉴免疫系统的反应机理， 提出一种动态环境下的多模态函数优化的免疫算 法。通过与其他几种典型算法的仿真比较，最后给出实验结果和分析结论。 第五章将第四章设计的动态环境下的免疫算法运用于城市交通信号控制， 提出一种 城市交通信号免疫自适应优化控制方法。 实验结果表明该方法能够有效地实现城市交通 信号的快速自适应控制。 第六章对全文进行总结。 第二章 生物免疫系统和人工免疫系统 6 第二章第二章 生物免疫系统和人工免疫系统生物免疫系统和人工免疫系统 本章从信息处理的角度介绍了有关生物免疫系统的组成结构及其功能。 着重阐述了 几种典型的免疫算法结构，并对算法特点进行了分析。为后续章节的进一步研究作理论 准备。 2.1 生物免疫学的发展史生物免疫学的发展史36,37 2.1.1 免疫的定义免疫的定义 “免疫”immune(免疫，免疫的)是从拉丁文 immunis 派生而来的，原意是免税，引 申为免除疾病。很早以前，人们就注意到传染病患者痊愈后，对该病有不同程度的免疫 力。因此，在相当长时期内，免疫在微生物学和病毒学上是指免除瘟疫；换而言之，是 指对传染因子的再次感染有抵抗力， 这是肌体在初次感染后对该传染因子产生免疫应答 的结果。 在医学上，免疫是指肌体接触抗原性异物时的一种生理反应。近代免疫的概念是指 肌体对“自己”(self)或“非己(non-self)”的识别并排除非己的功能。具体地说，免疫是 肌体识别和排除抗原性异物，以维护自身生理平衡稳定的功能。正常情况下，免疫应答 的结果对肌体有利， 起到免疫保护、 免疫稳定和免疫监视等生理保护作用。 在免疫缺陷、 功能失调或免疫应答过程不足时，则可能造成病理损伤或超敏反应。 2.1.2 免疫学的发展史免疫学的发展史 免疫学是生物领域一门相对年轻的学科，然而，人类应用免疫学方法预防传染病的 历史，可以追溯到 16 世纪中国医学家用人痘苗预防天花的伟大实践。此后，免疫学经 历了四个时期： 免疫学经验时期(11-17 世纪)； 经典免疫学时期(18 世纪末到 20 世纪中叶)； 近代免疫学时期(20 世纪中叶)； 现代免疫学时期(20 世纪 60 年代到 至今)。 1. 免疫学经验时期 我国早在南宋时期(11 世纪)，就创造性地发明了人痘苗，用人工轻度感染的方法， 达到预防天花的目的，这是医学史上的一项伟大贡献。到了 16 世纪，人痘法有了重大 进展，人们将人痘苗反复传代，连种数次，即为种苗。种苗保存了一定的抗原性，其毒 性较弱，使用时无甚危险，却有预防天花的效果。到了 17 世纪，不但我国已普遍使用 人痘苗预防天花，也很快传入俄国、朝鲜、日本等国。后又从俄国传入土耳其。1721 年，英国驻土耳其大使夫人 montagu 将人痘法传入英国，在英国进行了人体实验，把接 种人痘者移居天花流行区，结果发现接种者均获得抵抗力。 第二章 生物免疫系统和人工免疫系统 7 2. 经典免疫学时期 从 18 世纪末至 20 世纪中叶，随着微生物学的发展，人们对免疫功能的认识从人体 现象的观察进入了科学实验时期。它的发展和微生物学的发展密切相关，并成为微生物 学的一个分支。这一时期重要成就有：1796 年，英国人 jenner 发明了后牛痘苗，取代 了人痘苗；1881 年，法国人 pastuer 发明了减毒细菌疫苗；1884 年，俄国的 metchnikoff 发现吞噬细胞；1890 年，德国的 behring 发现抗体；1895 年，比利时人 bordet 发现补 体；1896 年德国学者 ehrlich 提出了抗体生成的侧链学说，精确的推测了抗原与抗体分 泌细胞相互作用的方式，奠定了受体学说的基础。 3. 近代免疫学时期 20 世纪中叶至 60 年代，由于近代免疫生物学的进展和细胞系选择学说的提出，使 免疫学发展有了重大的转折和突破。这一时期的主要成就有：1942 年，英国人 chase 揭示了特异性细胞的免疫功能；1945 年，英国人 owen 发现天然免疫耐受现象；1953 年，英国人 medawar 发现获得性免疫耐受；1956 年丹麦学者 jerne 提出了天然抗体选 择学说；1957 年澳大利亚免疫学家 burnet 提出了抗体生成的克隆选择学说（clonal selection theory） 。 4. 现代免疫学时期 20 世纪 60 年代后，免疫学进入了现代免疫学时期，近 40 年来，免疫学的研究不断 取得巨大的进展，自此，免疫学开始发展成为一门独立于微生物学之外的重要学科。 1957 年 glick 发现早期摘除鸡的法氏囊（bursa of fabricius） ，可影响抗体的产生； 1961 年 miller 及 1962 年 good 分别在哺乳动物体内进行早期胸腺摘除术，严重地影响 了动物的免疫功能；1965 年，gowan 证明了淋巴细胞是具有免疫功能的细胞；1969 年， claman、miller 和 mitchell 等人，在淋巴细胞中区分了 t 和 b 两类淋巴细胞，并证实了 t、b 细胞在抗体产生中的协同作用；cooper 等人证实了淋巴细胞在周围淋巴组织的分 布；1969 年，dumonde 等发现了淋巴因子；1974 年，jerne 提出免疫网络学说；70 年 代 unanue 等证明了巨噬细胞在免疫应答中的作用。通过这些研究，在器官、细胞和分 子水平上，揭示了肌体存在一个十分重要的功能系统免疫系统。该系统由中枢免疫 器官（胸腺、法氏囊） 、外周免疫器官（脾、淋巴结等） 、免疫细胞（t、b 细胞等）和 免疫分子（抗体、淋巴因子、补体等）细胞组成。 随着现代生物学和医学的发展，免疫学的研究内容得到极大地拓展和丰富，同时免 疫学开始向医学的各个领域进行渗透，并产生了许多免疫学的分支和交叉学科，如细胞 免疫学、分子免疫学、神经和内分泌免疫学、遗传免疫学、生殖免疫学和行为免疫学等。 近年来， 计算机科学和其它工程科学与免疫学的交叉研究逐渐成为国际研究领域内的一 个新方向，而且应用计算机对免疫系统及其各种功能与特征行为进行数学建模，则更易 于分析和解释各种免疫现象的内在机理。 第二章 生物免疫系统和人工免疫系统 8 2.2 生物免疫系统结构生物免疫系统结构 免疫功能是由免疫系统完成的。生物免疫系统包括免疫活性分子、免疫细胞、免疫 组织和器官等组成的复杂系统（如图 2-1 所示） 。免疫器官分为中枢免疫器官和外周免 图 2-1 生物免疫系统组成图 fig.2-1 composing of biological immune system 疫器官，它们是免疫细胞产生、分化和成熟的场所，对外周免疫器官的发育具有促进作 用。外周免疫器官包括免疫淋巴结、脾脏和粘膜相关的淋巴组织，它们是 t、b 淋巴细 胞定居、增殖地接受抗原刺激产生特异性免疫应答的部位，同时也是血液中淋巴细胞进 入淋巴系统完成淋巴系统再循环的场所。 免疫细胞种类繁多， 有的在免疫应答中起协助、 调节作用，有的直接发挥吞噬、杀伤等免疫作用。免疫细胞包括淋巴细胞、单核吞噬细 胞系统的细胞、各种抗原提呈细胞、各种粒细胞。现已证明红细胞也参与免疫的某些环 免疫系统 免疫器官 免疫细胞 免疫分子 中 枢 免 疫 器 官 骨髓、 法氏囊 （禽 类）胸腺 外周免疫器官 造血干细胞 淋巴细胞 胸腺 脾 粘膜相关的淋巴组织 骨髓、 法氏囊 （禽类） 淋巴结 t 淋巴细胞 b 淋巴细胞 第三群淋巴细胞 nk 细胞 lak 细胞 抗 原 呈 递 细 胞 单核吞噬细胞 树突细胞 并指细胞 朗格汉斯细胞 b 细胞 免疫细胞 中性粒细胞 嗜酸性粒细胞 肥大细胞 红细胞 抗体 补体 细胞因子 第二章 生物免疫系统和人工免疫系统 9 节。免疫分子有抗体、补体系统各成分及免疫活性的细胞因子等，这些免疫分子绝大部 分是免疫细胞的产物，合成后释放在细胞外及体液中，有调节免疫细胞活性、参与免疫 应答的作用。在免疫过程中免疫器官、免疫细胞与免疫分子相互协调、相互制约，适度 而精确地完成复杂的免疫。 2.3 免疫系统的特性及机理免疫系统的特性及机理 生物免疫系统在完成其防御功能时表现出许多优良的特性， 正是由于这些特性的启 示使得人们构造了人工免疫系统。下面介绍几种比较突出的特性。 2.3.1 抗体的多样性抗体的多样性 抗体是一种能够特异识别、结合和清除抗原的免疫球蛋白分子。b 细胞识别抗原后， 经过活化和克隆扩增之后，一部分分化成浆细 胞， 浆细胞大量的分泌具有相同特异性的抗体。 抗体的基本结构(如图 2-2 所示)， 它由两条相同 重链（h 链）和轻链（l 链）通过二硫键接成 对称四肽链结构。抗体分子上氨基酸的排列是 可变的，根据氨基酸排列的变化情况可以分为 可变区（v 区）和恒定区（c 区） 。在 v 区内三 个高变区。其结构主要由 v、d、j 三种基因片 段组成。c 区的氨基酸排列都是相同的，v 区 是高变区的氨基酸组成，排列随结合抗原的特 异性不同而异， 故氨基酸排列和种类千变万化， 可与许多不同特异性的抗原结合，并且相同特 图 2-2 抗体的结构 异性的抗体只能与具有互补特性的抗原结合。这 fig.2-2 the structure of an antibody 是抗体多样性来源的重要原因。引起抗体多样的原因主要有以下几个方面： 胚系中 存在众多的 v、d、j 基因片段。胚系中未重排的氨基酸有众多的 v 基因片段以及一定 数量的 d、j 基因片段。不同基因的组合产生不同种类的抗体； v、d、j 连接的多 样性。在 v-j 连接点以及轻链基因与重链基因重排过程中，d-j 以及 v-d-j 连接点有一 定的变异范围； 体细胞突变(somatic mutation)。体细胞在发育过程中会发生基因突 变， 这种类型突变主要发生在 v 基因。 体细胞突变扩展了原有胚系众多基因片段的多样 性； n 区的插入。在重链基因片段重排过程中，有时可能通过模板指导的机理在重 组后的 d 基因片段两侧插入称之为 n 区的几个核苷酸。由于额外插入了 n 区，可发生 移码突变，增加了抗体多样性； 轻链和重链随机配对将产生更多种类的抗体。 vh ch1 cl ch2 ch3 vl vh cl ch1 ch2 ch3 vl 第二章 生物免疫系统和人工免疫系统 10 2.3.2 免疫应答与免疫记忆免疫应答与免疫记忆 免疫应答(immune response)是指免疫细胞对抗原分子的识别、活化、分化等产生免 疫效应的全过程，是由抗原刺激免疫系统所发生的一系列复杂的变化。免疫系统有两种 免疫应答类型：一种是固有免疫应答(innate immune response)，指肌体在进化过程中逐 渐建立起来的天然防御功能，它是肌体防御外来侵袭的第一道防线。另一种是适应性免 疫应答(adaptive immune response)，指通过学习以识别特异性抗原，并对其保持记忆， 以便下次快速做出应答的过程。 免疫应答一般可分为(如图 2-3 所示)的三个阶段： 感应阶段，指抗原激活、递呈 抗原 摄取、处理 巨噬细胞 呈 递 b细胞介导的体液免疫 t细胞介导的细胞免疫 排异 或排己 免疫 保护 免疫 病理 反应阶段反应阶段 抗感染免疫 抗肿瘤免疫 变态免疫 自身免疫 效应阶段 感应阶段 效应阶段 感应阶段 淋巴细胞 图 2-3 免疫应答过程 fig.2-3 the immune response processes 的系列过程，体现了抗原分子与免疫细胞之间的相互作用； 反应阶段，指 t、b 细胞 接受相应抗原激活、增殖和分化的阶段，体现了免疫细胞的相互作用； 效应阶段， 指产生特异性或效应细胞而发挥免疫效应的阶段。 适应性免疫应答又分为两种过程：初次免疫应答（primary immune response）及二 次免疫应答(secondary immune response)。 (1) 初次免疫应答 初次免疫应答发生在某种病原体第一次入侵时， 此时免疫系统产生大量抗体清除生 物体内抗原。初次应答学习过程较慢，通常发生在身体初次感染的前几天，通常要用几 周时间才能清除抗原。 (2) 二次免疫应答 初次免疫应答后，免疫系统首次遭遇异己物质且该物质已经被清除体外，但是免疫 系统中仍保留一定数量的 b 细胞，称为免疫记忆细胞38。如图 2-4 所示的是初次与再次 免疫应答中免疫球蛋白(包含免疫球蛋白 g 和免疫球蛋白 m，即 igg , 5.12,5.12 (0.05) f x yxyx y xy =+ + 函数函数 3-3： 2( , ) sin(4)sin(4)2; 1,1fx yxxyyxy=+ ， 函数函数 3-4： 55 3 11 (cos(1)cos(1);, 10,10 ii fiixiiiyix y = = + 第三章 一种用于多模态函数优化的免疫算法 28 函数函数 3-5： 222 4 222 sin ()0.5 ( , )0.5; , 10,10 (1 0.001() xy fx yx y xy + = + 函数函数 3-2， needle-in a-haystack 问题，其中最优解近似为3600，分布在（0，0） ， 4个局部极值点；函数函数 3-3，有4个全局最优点，32个局部最优点，最优点分布密，函 数值差别大，常规算法不易获得所有的局部最优解；函数函数 3-4，shubert 测试函数，有 760个局部最优值，其中的18个是全局最优值，其值为186.73，由于该函数的局部极值 点的分布非常密集，要求算法有良好的搜索性能；函数函数 3-5，schaffer 函数，该函数在 可行域内只有一个全局最大优值为1，分布在（0，0） ，它在全局最优点附近存在无穷个 局部极值点将其包围，而且该函数振荡强烈，一般算法难以得到最优解。 考虑到与niching-ga相比，clonalg更适合求解多峰优化问题，因而在此仅以 clonalg作对比分析。将参数调至最优，将克隆选择算法和本文算法的优化结果进行 比较。算法的参数见表3-1，优化结果见图3-5和表3-2至表3-5。 表 3-1 算法参数 函数 克隆选择算法（csa） 本文算法 函数 3-2 二进制编码（30 位）种群规模=100 ,各抗体克 隆规模=10,变异概率=0.01 进化代数=100 实数编码(2 位) n1=20, =20 =2 =0.8 =4 g=5 进化代 数=100 n4=2 函数 3-3 二进制编码（30 位）种群规模=200 , 各抗体 克隆规模=10,变异概率=0.005,进化代数=100 实数编码(2 位) n1=20, =100 =2 =0.8 =0.5 g=5 进化代 数=100 n4=8 函数 3-4 二进制编码（30 位）种群规模=200 , 各抗体 克隆规模=10,变异概率=0.005,进化代数=100 实数编码(2位)n1=200, =100 =2 =0.8 =0.5 g=5 进化代 数=100 n4=40 函数 3-5 二进制编码（30 位）种群规模=200 , 各抗体 克隆规模=10,变异概率=0.015,进化代数=100 实数编码(2 位) n1=20, =10 =2 =0.8 =1 g=5 进化代数 =100 n4=4 （a） clonalg-函数 3-2 (b) 本文算法-函数 3-2 第三章 一种用于多模态函数优化的免疫算法 29 （c） clonalg -函数 3-3 (d ) 本文算法-函数 3-3 （e） clonalg -函数 3-4 (f ) 本文算法-函数 3-4 （g） clonalg -函数 3-5 (h) 本文算法-函数 3-5 图 3-5 克隆选择算法与本文算法对函数 3-2函数 3-5 的优化结果比较 fig.3-5 the comparison results between with clonalg and this papers algorithm of function (3-2)(3-5) 第三章 一种用于多模态函数优化的免疫算法 30 表 3-2 本文算法对函数 3-2 优化结果 序号 极大值点（x,y） （103）函数值（103） 发现率% 1 2 3 4 5 (0.0000 ， 0.0000) (0.0051 ， 0.0051) (-0.0051 ， 0.0051) (0.0051 ， -0.0051) (-0.0051 ， -0.0051) 3.6000 2.7488 2.7488 2.7488 2.7488 100 100 100 100 100 表 3-3 本文算法对函数 3-3 优化结果 序号 极大值点（x,y）函数值 发现率%序号极大值点（x,y）函数值 发现率% 1 (-0.6351 ,0.6348) 3.2600 100 19 (-1.0000,-0.6347)2.6300 100 2 (0.6350 , -0.6350)3.2600 100 20 (-0.6361,-1.0000)2.6300 100 3 (0.6346, 0.6351 ) 3.2600 100 21 (-0.1624,-0.1608)2.2896 100 4 (-0.6368,-0.6338)3.2600 100 22 ( 0.1610, 0.1615 )2.2896 100 5 (0.1615 , 0.6344) 2.7748 100 23 (0.1617, -0.1616)2.2896 100 6 (-0.1574, 0.6337) 2.7748 100 24 (-0.1597, 0.1606)2.2896 100 7 (-0.6353 ,-0.1606)2.7748 100 25 (1.0000, -0.1614)2.1448 100 8 (-0.6373, 0.1597) 2.7748 100 26 (-0.1612,-1.0000)2.1448 100 9 (-0.1606, -0.6350)2.7748 100 27 (-1.0000, -0.1617)2.1448 100 10 (0.1624, -0.6336) 2.7748 100 28 ( 1.0000, 0.1616 )2.1448 100 11 (0.6350, -0.1612) 2.7748 100 29 (-0.1616, 1.0000)2.1448 100 12 (0.6351,0.1616) 2.7748 100 30 (0.1608, -1.0000)2.1448 100 14 (0.6346,-1.0000)2.6300 100 32 (-1.0000, 0.1569)2.1448 100 15 (1.0000,-0.6349) 2.6300 100 33 (-1.000, 1.0000 )2.0000 100 16 (-0.6349, 1.0000) 2.6300 100 34 ( 1.0000, 1.0000)2.0000 100 17 (0.6349, 1.0000)2.6300 100 35 (-1.0000,-1.0000)2.0000 100 18 (-1.0000, 0.6355) 2.6300 100 36 (1.0000, -1.0000 )2.0000 100 表 3-4 本文算法对函数 3-4 的全局最优值结果 序 号 最大值点(x,y) 函数值 发现率 % 序 号 最大值点 (x,y) 函数值 发现率 % 1 2 3 4 5 6 7 8 9 (5.4829 ,-7.7083) (-7.0835 ,-1.4251) (4.8581 ,-7.0835) (-1.4251 ,-7.0835) (-0.8003 ,4.8581) (-0.8003 ,-7.7083) (-7.7083 ,-7.0835) (-1.4251 ,5.4829 ) (5.4829 ,-1.4251) 186.7309 186.7309 186.7309 186.7309 186.7309 186.7309 186.7309 186.7309 186.7309 100 100 100 100 100 100 100 100 100 10 11 12 13 14 15 16 17 18 (-7.7083 ,5.4829) (-7.0835 ,4.8581) (-0.8003 ,-1.4251) (4.8581 ,-0.8003) (-7.7083 ,-0.8003) (-7.0835 ,-7.7083) (5.4828 ,4.8580) (4.8581 ,5.4829) (-1.4251,-0.8003) 186.7309 186.7309 186.7309 186.7309 186.7309 186.7309 186.7309 186.7309 186.7309 100 100 100 100 100 100 100 100 100 第三章 一种用于多模态函数优化的免疫算法 31 表 3-5 运行时间比较 函数 克隆选择算法(s) 本文算法 (s) 函数 3-2 11.265 1.5630 函数 3-3 9.5940 4.000 函数 3-4 67.031 148.3750 函数 3-5 10.8120 7.4220 图3-5是 clonalg与本文算法对测试函数3-2至3-5的仿真结果。 从图中我们可 以更直观地看出以上四个二维函数的几何特征以及clonalg和本文优化性能的差异。 首先这些测试函数都是多模态函数， 都有多个局部最优值有的甚至有无穷多的局部最优 值，从图中我们发现这两种算法都能搜索到函数的全局最优值，对于搜索各个函数的局 部最优值本文算法比clonalg搜索效果要好。clonalg有时只搜索到部分的局部 最优值，而本文算法每次都能快速搜索到相应的局部极值。以函数3-5为例，此函数有 一个全局最优值f(0,0)=1,却有无穷多个局部最优解，它的局部最优值与全局最优相差甚 微，所以要搜索到全局最优值的同时又搜索到分布均匀局部极值是较困难的， clonalg与本文算法都能找到全局最优值， clonalg仅能搜索到部分的局部最优 值 (如图3-5(g)，本文算法都能快速找到分布均匀的局部最优值(如图3-5(h)；以函数 3-4为例，此函数有众多个峰值，其中有18个全局最优和760个局部最优，本文算法搜 索到所有的全局最优值和几乎所有的局部最优(如图3-5(f)，本文算法每次搜索到的局部 最优达到9