（计算机软件与理论专业论文）免疫克隆智能优化算法的研究与应用.pdf

摘要 摘要 生物免疫系统是一个分布式的，具有高度自适应性的系统，具有学习、记 忆和模式识别的能力。人工免疫系统通过模拟和应用生物免疫系统的信息处理能 力，己成为智能计算领域一个新豹磷究方翻。 本文的研究工作受陕西省自然科学基金和陕诬省教育厅重点科研计划项目 资助，就人工免疫系统中的免疫算法研究展开工作，围绕免疫算法、克隆选择学 说等理论，对免疫克隆算法进行研究，并将其应用到函数优化和数据挖掘中。本 文的主要王作如下： ( 1 ) 概述了生物免疫系统的组织结构及生物免疫系统的仿生机理，对模拟其 机理而产生的人工免疫系统中的算法作了详细讨论。 ( 2 ) _ 以免疫克隆算法为基础，提出种改进鲶鸯适应克隆算法莉一季孛改进 的免疫克隆智能算法，并将其用于函数优化，仿真实验证明了文中算法的有效性 和可行性。 ( 3 ) 将免疫克隆算法应用于关联规则挖掘，提出了基于免疫克隆理论的关联 规则挖掘算法，并将文中提出的算法与传统的a p 矗o r i 算法进行了比较，仿真实 验证明了文中算法的有效性和可行性。 关键词：免疫算法克隆算法自适应克隆算法免疫克隆算法 关联规则挖 a b s t r a c t k e y w o r d s ：i l n m u n ea l g o r i t c 1 0 n i n ga l g o n t l m l sa d a p t i v ec l o n i n ga l g o r j t c l o n i n g 融m u n ea l g o r i t h 】mm i n i n ga s s o c i a t i o nr u l e s 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：丝亟霪。 指导教师签名： z 即芬年石月f ( 7 日g 年多月j 罗日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，本论文不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西北大学或其它教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名：张潮艮 2 佃子 年月l 9 日 第章绪论 第一章绪论 生物学是人正智能研究灵感的重要来源，由生物学原理仿生的信息处理系统 中的神经网络和进化计算已被广泛地应用予各个领域，而人工免疫系统由于其复 杂性，应用相对较少。随着免疫学理论研究的不断发展，人们对生物免疫系统的 认识不断深入。免疫系统独特的工作机理和如色的工作性能在机器学习、函数优 化、模式识别、智能控制等研究领域展示出巨大的能力，引起了国内外研究人员 的极大兴趣。本文在认真研究前人工作的基础上，对基本克隆算法进行了研究和 探索，并将其应用于函数优化和数据挖掘。在本章中主要介绍了生物免疫理论的 发展状况以及人工免疫系统理论，阐述了本论文的研究目标和研究内容。 1 1 课题背景 生物体是一个复杂的大系统，英信息处理系统可分为脑神经系统、遗传系 统、免疫系统和内分泌系统。近年来，人们不断从生物系统中获得灵感，提出了 若干采用计算途径实现的学习系统。人工免疫系统( a n i f i c i a li m m u n es y s t e m ) 是 继人工幸睾经网络、遗佟算法、蚁群算法等根据生物相关特性丽发展的进化计算之 后新的智能计算研究方向，是生命科学和计算机科学交叉形成的研究热点。 人工免疫系统是模仿自然免疫系统功能的一种智能方法，它受生物免疫系统 的高度并行、分布、自适应和自组织性等特点启发，通过学习生物免疫系统的学 习、识别、记忆和特征提取的能力f ，提供噪声忍耐、无教师学习、自组织、记 忆等进化学习机理，具有提供新颖的解决问题方法的能力。人工免疫系统除了具 有群体并行搜索的优点之外，它还借助克隆选择、免疫记忆、疫苗接种等特殊的 免疫机理，从恧具有独特的概率收敛、反映种群多样性、对个体多样性进季亍自我 调节等优势。 近年来，人工免疫系统引起了国际上许多学者的极大兴趣，1 9 9 6 年在网本 首次举行了基于免疫系统的国际专题讨论会，雨1 9 9 7 和1 9 9 8 年l e e es y s t e m ，m 雒 a n dc y b e m e t i c 圈际会议还组织了有关人工免疫系统的专题讨论，成为了智能系 统中继神经网络、模糊系统和进化计算等研究之后又一个研究热点【2 1 。 1 第章绻论 1 。2 生物免疫系统理论 自然界中的免疫是指机体对感染具有抵抗能力丽不患疫病或传染病。免疫 性是生物体的一种保护性生理反应，它在生物体接触抗原性异物后，能产生种 特异性排除这些异物。近代免疫的概念是指机体对“自我( s e l f ) 抑和“非我( n o n s e l f ) 的识别并排除非我的能力。免疫学作为一门医学科学是在人类与传染 病斗争过程中发展起来的，分为了经验免疫时期，科学免疫时期和现代免疫学三 个阶段。从1 7 9 6 年e d w a r dj 咖e r 发现牛痘疫苗并用于治疗天花开始，在3 0 0 多 年的时间里，人们对免疫学的认识逐步加深，从对其生物学机制一无所知，到如 今多种理论相继形成，并不断取得突破。最近，免疫学研究的主要王作包括：抗 原提呈、细胞凋亡、细胞裂解、免疫调节、记忆、自身免疫性疾病、d n a 疫苗、 细胞间发生信号、免疫应答成熟等。在医学上，免疫学也是一门独立的学科，它 已经发展盘许多分支，包括基础免疫学、临床免疫学、分子和细胞免疫学等。 自然免疫系统是一个复杂的自适应系统，其复杂程度不弧于大脑，它可保 护人体不受外部病原体侵害，并把体内所有的细胞或分子分成两类：属于自己的 种类( 自体细胞) 或者属于外部来源的非自体分子种类。免疫系统不依靠任何中心 控制，具有分布式任务处理熊力，具有在局部采取行动的智能，也通过起交流作 用的化学信息构成网络，进而形成全局观念。免疫系统多种多样，具有独特性。 这就和入一样，同样是人，一个人和另外一个人的免疫系统除了本质构成样外， 具体靛状态和功麓则千差万剐。免疫系统是生物，特别是脊椎动物和人类所舆有 且必备的防御机制。人的免疫系统最为复杂，它由免疫效应分子和有关的基因及 具有免疫功能的细胞、组织、器官等组成，可以保护机体，抗御病原体。有害异 物等致病因素的侵害。免疫系统的主要功能是：免疫防御，免疫稳定，免疫监督。 免疫系统基本元素包括巨噬细胞、淋巴细胞及其抗体，抗体识别特定抗原并将其 清除。生物系统具有大量发达的抗体系统，能够处理不断变化的环境。 免疫系统可分为先天性免疫系统和适应性免疫系统。先天性免疫系统是生 物在稀系发育和进化过程中逐渐建立起来的一系列天然防御功能，其特点是与生 俱有，能传给下一代，无特异性，对各种病原体都有一定的防御功能。适应性免 疫系统具有两种应答方法：初次应答和二次应答。初次应答发生在系统第一次遭 第一章绪论 遇到抗原并与其反应的时候。免疫系统能够学习抗原，该机拳l 产生免疫记忆，这 样为身体再次遇到同样的抗原时产生二次应答。当抗体结合一个抗原时，b 细胞 受刺激产生自体克隆，克隆过程中的变异机制使免疫系统具有适应性。 生物进化和免疫系统进化之间在时闻范围翻霉的上有着显著的差别：在生 物进化系统中，进化需要长时间进行才能改善一个物种种群的性能：在免疫系统 中，寻找合适的抗体种群成员所用的时间可以短到几天。免疫系统的进化可分为 两个不同模式：缓慢进化模式，体现在d n a 分子的进能( 全局优化) ，快速进化 模式，体现在免疫系统在与外部抗原斗争时的自适应性( 局部优化) 。 随着社会的演变和科学的发展，人们已经从许多角度开创不同的学科来研 究生物体系，其中一个重要领域就是生物信息处理系统。生物信息系统可看成一 个分布式自治系统，且能提供给科学和工程领域各种的技术和方法，许多磅究人 员已经在工程领域应用生物系统的信息处理能力。 科学蓬勃发展的今天，作为生物信息系统的一个重要部分，生物免疫系统 突穗的性能，使入工免疫的研究蓬勃发震。所谓人工免疫系统正是在研究借鉴、 利用生物免疫系统( 主要是人类免疫系统) 信息处理机制的基础上发展而来的各 类信息处理技术、计算技术及其在工程学科中应用而产生的各种智能系统的统 称。人工免疫系统是一个跨越多个学科的研究领域，是生物免疫系统相对应的工 程概念。 。 1 3 免疫算法发展概况 冒前，人工免疫系统的具体研究内容和范围主要包括免疫计算智能系统、 免疫工程应用和人工免疫系统理论的研究。免疫计算智能系统的研究主要包括各 种免疫原理及算法，人工免疫网络和免疫计算系统等内容。免疫工程应用研究包 括各种免疫计算智能技术在工程中的应用研究。人工免疫系统理论研究深入研究 人工免疫系统的机制，发展樱对滞意。人工免疫系统的研究手段和内容涉及了医 学免疫学，计算机科学，人工智能，控制理论等多个领域，是一个交叉学科。不 同学科的研究人员在各自的领域取得了许多的研究成果。其中，w a t k i n s 利用人 工免疫算法实现了一个资源受限的分类器，得到令入满意的结果疆】，李海峰等人 第一章绪论 化算法以及为完成特定任务两设计的基于免疫原理的算法；另外一项研究是根据 生物免疫系统原理建立人工模型，包括人工免疫网络模型和人工免疫系统模型； 此外的研究还包括建立混合智能系统。 由于对免疫枫理的认识还不是十分系统深入，掰以，有关免疫算法约研究 主要集中在利用免疫机理改进其他的算法以构成新的算法，如免疫一遗传算法， 免疫一神经网络等等，而关予人工免疫系统本身的算法研究成果并不多。j n a g s 豫gc h h 于1 9 9 8 年分绍了免疫算法的数学模鍪和基本步骤吲，瓣述了它不圈于 其他优化算法的优点。最后将免疫算法，遗传算法和进化策略同时应用于求解 s i n c 函数的最优值，以进行比较研究。指出免疫算法在求解某些特定优化问题方 面优于其他优化算法，有广阔的应用前景。 在目翦的人工免疫系统的研究和应用中，多数仍以发展基于免疫原理的计 算方法为主，包括各种算法，人工免疫网络和免疫计算系统及模型。研究者借助 于免疫原理中的学习，识别，记忆等特性，发展出了一些有效的新的算法，比如 d ec a s 韵【1 8 】在算法中弓| 入记忆集合，将进化群体中较好的个体记录予记忆集合 中，而且不断更新该记忆集合，以此形成了用于多目标优化的多目标人工免疫算 法。b e r s i n i 等对克隆选择算法中的算子进行研究，提出了具有更优性能的克隆 和交叉算予。a d n 锺a e 鑫n 提盘多样孪生算子，改善了算法的收敛性能。刘著尘 就免疫单克隆机制和免疫多克隆机制进行了分析讨论，将免疫记忆和克隆消除引 入克隆算法，提出免疫记忆克隆算法和免疫记忆动态克隆算法【2 1 1 。孙宁就人工 免疫算法的改进进行了研究，提出了增强变异人工免疫算法和弓l 导型人工免疫算 法【2 2 】。 1 4 本文的研究内容 本文概述了生物免疫系统的组成、性质、原理和机制，深入研究了生物免 疫系统所蕴含的进化学习，记忆等机制，探索了人工免疫系统的应用原理以及工 作机制，对克隆选择算法进行了深入的研究探讨，在分析现有基于克隆选择原理 的免疫算法的基础上，提出了两种改进的基于克隆选择原理的免疫优化算法。本 文还将免疫克隆算法瘦焉到数据挖搦中的关联规则挖掘，分析了已有的经典关联 第二牵免疫理论及人一免疫算法概述 第二章免疫理论及人工免疫算法概述 2 。1 生物免疫系统 f 免疫器官 中枢免疫器官：骨髓、鼹腺 。l 阱周免疫器官：脾脏、淋巴结和黏膜免疫系统 兰|f 淋巴细胞 薹免煮细胞 墓蓦盖星细胞 ， 统l【其它参与免疫应答和效应的细胞 免疫分子：效应分子、膜分子等 图2 ，l 生物免疫系统 在免疫系统中，最重要的是淋巴系统和补体系统。 组成免疫系统的组织和器官分布于人体各处，以完成各种免疫防歪功能。 它们就是人们熟知的淋巴细胞和淋巴组织。淋巴器官按照功能分为：中枢淋巴器 官，由骨髓和胸腺组成，执行生成免疫细胞的功能，多能造血干细胞在这些部位 发育成熟为免疫细胞：外周淋巴器官，由淋巴结、脾、赢桃体组成，成熟的免疫 缨施在这些部位执行应答功能。单核细胞和淋巴细胞经血液循环及淋巴循环，进 出外周淋巴组织和器官，构成免疫系统的完整网络，既能及时将免疫细胞动员起 来，聚集于体表及内脏各处病原体入侵部位，又能及时地将这些部位的抗原成分 经吞噬细胞携带到相应的港巴组织和器宫，活化零和b 缨麓，执行特异免疫应 答功能。淋巴器官及其主要功能包括： ( 1 ) 淋巴管：组成一个管道网络传送淋巴液到免疫器官和血液中去，淋巴管 中的淋巴液包含了淋巴细胞和外源性抗原的液体。 ( 2 ) 淋巴结：作为淋巴管的聚集地，每个淋巴结都存储免疫细胞，包括b 和 t 细胞，淋巴结是适应性免疫发生的位置。 第二瑟免疫理论及人一免疫算法慨述 ( 1 ) 物理屏障：物理屏障多数在皮肤中，皮肤，粘膜具有物理阻挡作用，局 部细胞可以分泌抑菌杀菌物质，此外，呼吸系统和消化道也可以起到防范的作用。 ( 2 ) 生理屏障：唾液、汗液、眼泪这类液体含有生物酶，能够有效的分化和 破坏微生物，焉胃酸麓够杀死多数存活于消化道中的微生物，体温和p 疆酸度值 也不适于某些“入侵微生物”的生存。 ( 3 ) 免疫系统：可分为固有免疫系统和自适应免疫系统，能有效地识别入侵 的微生物，并采取相应的措施将其清除。 图2 2 给出了免疫系统的多层次结构发挥免疫保护作用的过程。 熊 + - 素一 跳髓叫毒 图2 2 免疫系统的层次结构 淋巴细胞是免疫系统中越主要作用的微小的自缨胞，它有两种主要类型：b 细胞和t 细胞。 b 细胞是免疫系统的本质部分，是b 淋巴细胞的简称。b 细胞首先证明是 在鸟类淋巴样器官法氐囊内发育成熟的，故称之为b 细胞。哺乳动物的b 细胞， 在胚胎早期存在于胚肝，胚胎晚期至出生詹则在骨髓内分化成熟。成熟的8 细 胞定居于周围淋巴组织，如淋巴结、脾、扁桃体等组织和器官当中。 b 细胞是体内唯一能够产生抗体( 免疫球蛋白分子) 的细胞，它的表面含有 可以识别特异性抗原的多静抗体分子。b 缨胞有三个主要的功麓：产生抗体、提 呈抗原和分泌细胞因子参与免疫调节。 t 细胞在胸腺中成熟，他们的功能包括调节其他细胞的活动以及直接袭击 宿主感染细胞。t 细胞按功畿不同分为两类：即毒性t 细施和调节f 细胞。毒 第二常免疫理论及人丫免疫算法概述 性t 细胞能够清除微生物入侵者、病毒或者癌细胞，它对于保持免疫应答十分重 要，可以继承其他免疫细胞的行为，没有它们的活动，免疫会失去控制，导致过 敏反应和自身免疫性疾病。调节t 缁胞叉分为辅助性t 细胞和抑制性f 细胞，辅 助性t 细胞可以在与抗原结合时分泌作用于b 细胞，并帮助刺激b 细细胞的分子， 其本质作用是激活b 细胞。 不同淋巴细胞的特异性给免疫系统提供更快的适应性应答能力和非自体反 应能力。墨辅助纲胞的责任是非叁体耐受，8 细胞自由的高频变异适应特异病原 体；t 细胞一般执行非特异检测，对特异检测效率不高，b 细胞则适应更特异抗 原，对检测特殊病原体更有效率。 抗体是b 细胞识别抗原薏克隆扩增分化为浆细胞新产生的一种蛋自质分子， 也称为免疫球蛋白分子。抗体结合由外部入侵的感染微组织或者有毒物等抗原， 然后依靠自己或者借助免疫系统其他元素( 如t 细胞等) 帮助破坏这些抗原，除对 人体的威胁。从功能上来看，抗体分子具有两种不同的功能。一部分是保持褶对 静态状态的稳定区，称为稳定区，简称e 区，c 区变化有限；另一部分则是负责 与不同的多种感染抗原结合的分子变化区，称为可变区，简称v 区，v 区的变化 使免疫系统在自适应处理中具有一定的能力和速度。对免疫应答期间产生的抗体 多样性的研究已经证明v 区的体细胞变异随时间增栩，正是可变区为免疫系统提 供了大部分鲁棒性和自适应能力。从组成上来看，抗体由抗体决定基和独特型组 成，抗体决定基是抗体上识别抗原决定基的部分，而独特型是抗体上可供自身免 疫细胞识别的拭原决定基。 。 抗原在免疫学中指任何能够被抗体或者t 细胞受体识别出的分子。抗原被 抗体识别的部分成为抗原决定基。根据现代免疫学抗原的概念，抗原必须具备两 种特性，即免疫原性和抗原性。抗原的免疫原性是指抗原分子能诱导免疫应答的 特性。抗原的抗原性是指抗原分子能与免疫应答产物，即抗体或效应重细胞发生 特异反应的特性，故称之为抗原的反应原性。 抗体与抗原结合的时候并不是和整个入侵抗原结合，而是与抗原表面的许 多分子中的一个结合。抗体通过抗体的抗体决定基秘抗原的抗原决定基之闻模 x 第二二章免疫联论及人一免疫算 轰概述 补，结合就越可能发生，结合豹力度也就越紧密，这种结合的力度与强度被称为 抗体与抗原之间的亲和力。 2 2 免疫系统机制及性质 免疫系统具有两种应答类，鸯有性免疫应答和适应性免疫应答。固有性免 疫应答遇到病原体后，首先起到防卫作用，它在感染早期执行防卫功能，具有固 有性免疫功能的有皮肤和黏膜的物理阻挡及局部细胞分泌的抑菌、杀菌物质的化 学作焉。适应性免疫应答的执行者是零及8 淋巴细胞。按照免疫学家的说法，我 们体内有大量循环的免疫细胞，淋巴细胞是参与免疫响应的最主要的免疫细胞。 淋巴细胞具有专一性，多样性，记忆和自适应等特点。有两种淋巴细胞，t 细胞 和b 细胞。b 细胞能产生抗体以消灭入侵的抗原，t 细胞具有促进和抑翻8 纲胞 反应的作用。这些细胞在免疫过程中帮助识别和破坏一些特定物质。能被t 细胞 及b 细胞识别并刺激t 及b 细胞进行特异性免疫应答的瘸原体成分称为抗原。任 何能使免疫系统产生这样的应答和反应的物质都是抗原或免疫原。t 及b 细胞与 被免疫系统认为是异物的物质结合惹开始活化，即识别瘸原体成分蜃活化，活化 后并不即刻表现防卫功能，而是经免疫应答过程，约4 5 天后才生成效应细胞， 对已被识别的病原体施加杀伤清除作用。适应性免疫应答是继固有性免疫应答之 后发挥效应的，再最终清除病原体，促进疾病治愈及防止再感染中起主导作用。 适应性免疫应答又分为两种类型：初次以及二次免疫应答。 初次免疫应答发生在免疫系统遭遇某种病原体第一次入侵时，此时免疫系 统对感染产生大量抗体，帮助清除体内抗体。几天后，抗体浓度水平开始下降， 直到再次遇到抗原。自适应免疫系统能够学习和记忆特异种类的病原体。初次应 答是对以前未见过的病原体的应答过程。初次应答学习过程很慢，发生在初次感 染前几天，要用几周时间清除感染。初次免疫应答时，免疫系统首次遭遇抗原并 将其清除盘体外，但免疫系统中仍保留一定数量的8 细胞作为免疫记忆细胞，这 使得免疫系统能够在再次遭遇异物盾仍能快速识别并清除抗原，这个过程称为二 次免疫应答。二次应答更迅速，无须重新学习。二次免疫应答对引起初始免疫反 应及造成免疫系统8 细胞和抗体数量迅速增加的抗原是特异的。这种二次免疫应 第一二帮免疫理论及人t 免疫算法概述 答要归功予免疫系统内存警的b 缨胞，这样警抗原或类似抗原孬次入侵时，不用 再重新生成抗体，因为已经有抗体存在了，这意味着身体准备抗击一切再感染。 图中显示了免疫应答的过程。 挠体 细胞 牛痘 辫次应爸 答 。下i 1 疋数 天花 图2 3 二次应答 由于前面所述二次免疫应答是在初次免疫应答分化遗留下来的记忆细胞的 基戳上实现的，当初次免疫应答遭遇过的相同抗原或类似抗原出现时，免疫记忆 细胞迅速从休眠状态活化，并通过克隆增生过程产生大量的b 细胞和抗体，中和 入侵的抗原，因此应答的反应速度非常快，省去了学习的时间，这就是免疫系统 的实现鲁适应应答的一耱重要概制，印免疫记忆。 1 9 5 8 年奥地利免疫学家n k b r l l l l e t 首先提比了克隆选择学说【2 3 l ，该学说 认为，免疫细胞是随机形成的多样性的细胞克隆，每一克隆的细胞表达同一特异 性豹受体，当受到抗原的刺激，细胞表葱受体特异识别并结合挠原，导致细艴进 行克隆扩增，产生的大量后代细胞，合成大量相同的特异性抗体。当一种抗原侵 入生物机体后，在无数种淋巴细胞中，只有表面本来就带有和这种抗原互补的抗 体的少数b 细胞才能与其结合。而且这种b 细胞一旦和抗原结合，就会在介导细 胞，如辅助t 细胞的二次信号作用下被激活并具有分裂能力，并且连续分裂产生 大量带有该种抗体的b 淋巴细胞群。由于这群b 淋巴细胞同源，它们都携带有同 一种抗体，所有我们称该过程为细胞克隆( c l o n e ) 。这些b 淋巴细胞最终停止 分裂成为成熟( 不再分裂 的细胞，这时的8 细胞分裂为两类缨胞，酃长寿浆细 胞和长寿免疫记忆b 细胞。其中浆细胞是最活跃的抗体分泌器，可以分泌大量的 抗体。但是，这时的抗体与抗原的结合力( 或称抗体和抗原的亲和力) 比较低。 记忆细胞不能分泌抗体，它翻通过血液、淋巴、组织在生物体的全身循环，并且 第二章免疫理论及人一免疫算法概述 特型( 郾抗原决定基) ，同样善细胞上也含有抗原决定基。因此无论是b 细胞或t 细胞都有可能被淋巴细胞所识别，并被当作非自体细胞，成为免疫系统的攻击目 标。这对免疫系统来说是致命的，因此免疫系统提供了阴性选择机制来消除或抑 制那些识别皇体特异抗原的淋巴细胞。 t 细胞在胸腺的成熟过程中发生了阴 生选择。当不成熟的t 细胞在胸腺中时 它将完全暴露给免疫系统的淋巴细胞，当该t 细胞能够识别某个自体的特异抗 原时，它将被清除，不会脱离胸腺进入免疫系统。只有那些不识别自体特异抗原 的t 细胞才能成熟，并从胸腺迁出进入免疫系统。b 细胞在骨髓中也是经过了类 似的阴性选择过程。但阴性选择并不是非常完善的，还是会有一部分能够识别自 体特异抗原的淋巴细胞逃脱了阴性选择进入到了免疫系统，增加了自身免疫性疾 病的威胁。为了解决此问题，免疫系统提供了免疫耐受机制。 所谓耐受，是指免疫系统对自体抗原的不应答。也称为错误耐受。b 细胞 和t 细胞分别在骨髓和胸腺中进行了阴性选择，实质上就是进行了耐受化。但还 是有少量识别自体抗原的细麓进入了免疫系统。面且，淋巴缨麓在识别箢来抗原 的过程中发生了变异和受体编辑，使得产生了一定数量的新淋巴细胞，这些新的 淋巴细胞上的抗体决定基并没有经过骨髓和胸腺的耐受化。因此免疫系统提供了 协同刺激使其耐受纯。 t 细胞要想与抗原决定基反应，必须接受两个信号：必须超过了亲和力阐值； 必须由固有免疫细胞提供协同刺激信号进行协助。而固有免疫系统只有在组织被 破坏时才发出第二种信号，所以一个自体反应t 细胞只能在组织被破坏区域才能 存活，离开这个区域，t 细胞如果只接受第一种信号焉没有第二种信号它将会死 亡。 当b 细胞识别到抗原决定基时，t 细胞就会检测这个抗原是不是囱体抗原， 如果不是，t 细胞将发懑协蜃刺激信号激活8 缨胞，使其克隆增生分化。如果罩 细胞发现这个抗原是自体抗原，它将不会发出刺激信号，这将导致该b 细胞的死 亡。 免疫系统内部存在反馈机制，可以同时实现两个不同的任务：是迅速对 外部物质的出现进行应答；二是稳定免疫系统。 第一二带免疫理论及人 二免疫算滤慨述 免疫系统显示两种类型的应答：种是体液应答：另一种是细胞应答。在体 液应答中，抗体由b 细胞产生，并去中和抗原：在细胞应答中，杀伤t 细胞捕捉 微生物细胞或者被病毒感染的细胞，然后杀死它们。由于t 细胞在两种应答中都 起萋要作用，所以该机制称为善细胞调节免疫循环。在外部物质被抗原提呈细胞 消化后，抗原提呈细胞把抗原的有关信息传递给辅助t 细胞，激活辅助t 细胞， 然后辅助t 细胞刺激b 细胞、杀伤t 细胞和抑制t 细胞。激活b 细胞和杀伤t 细胞的调节机制是免疫系统的最重要的反馈机制。 辅助t 细胞和外部物质激活抑制t 细胞，而抑制t 细胞禁止其他细胞的活 动，如辅助t 细胞、b 细胞和杀伤t 细胞等。结果免疫系统的反应平静下来。这 是免疫系统中的另一种反馈机制。禁止机制和主反馈机制之闻的合作使免疫反馈 枫制对辨部物质迅速反应，并使免疫系统迅速稳定。 免疫系统具有分布式、自适应性、鲁棒性等特性。 免疫系统由分布在机体各个部分的细胞、组织和器官等组成。免疫系统的 分布式特性首先取决于病原体的分布式特征，郎瘸原体是分教在机体内部各处 的，对遍布全身的病原体的检测和清除由遍布全身的效应细胞完成。其次免疫系 统的分布式特性有利子加强系统的鲁棒性，从而使得免疫系统不会因为局部组织 损伤而使整体功能受到很大影嗡，也不会匿为在应答妻冬过程中苇个免疫协同发生 错误而导致灾难性后果。分散予机体备部分的淋巴细胞采用学习的方式实现对特 定抗原的识别，完成识别的抗体以正常细胞变异概率的1 0 倍进行变异，使得其 亲合度提高的概率大大增加，并通过分纯为效应细胞和记忆细胞分别实现对抗原 的有效清除和记忆信息保留，这个过程实际上是一个适应性的应答过程。由于免 疫应答机制是通过局部细胞的交互起作用而不存在集中控制，所以系统的分布式 进一步强化了其自适应特性。 2 3 人工免疫算法 人工免疫系统是借鉴、利用生物免疫系统( 主要是人类免疫系统) 各种原理 和机制而发展的各类信息处理技术、计算技术及其在工程和科学中应用而产生的 各种智能系统的统称1 2 熨。免疫系统具备的强大的学习、识别和注忆的能力以及 第_ 二露免疫腥论及人t 免疫算法瞧述 分布式、逸组织狂多样性特性等显著的特性，不断地吸引着研究人员跌中获得启 发，从而开发相应的人工免疫系统模型和算法用于信息处理和问题求解。 人工免疫算法是根据生物免疫系统原理发展的新的算法，主要包括克隆选 择算法，阴性选择算法，免疫遗传算法及其他的为完成特定任务蔼设计的基于免 疫原理的算法。 在免疫系统机制及性质一节中介绍了克隆选择的原理，克隆选择算法是 2 0 0 0 年p ec a s t r o 和v o nz 曲e n 根据克隆选择原理丽提出的算法哆克隆选择原 理中包含着免疫细胞应答抗原的几种机理，即： 克隆选择：应答抗原能力强的免疫细胞被确定性地选择进行应答。 细胞克隆：被选择进行应答的免疫细胞依据其应答抗原能力的强弱，繁殖一 定数目的克隆细胞，免疫细胞繁殖克隆的数霹与其亲和力成正比。记忆细胞获取： 部分克隆细胞变为记忆细胞或长寿细胞，被保存于免疫系统中并更新已有的低亲 和力的记忆细胞，记忆细胞产生免疫记忆。 亲和成熟：部分细胞成熟为浆缨胞并分泌抗体分子。在细胞成熟过程孛，克 隆细胞在其母体的亲和力影响下，按照与母体亲和力成反比的概率对抗体的基因 多次重复随机突变及基因块重组，进而产生种类繁多的免疫细胞，并获得大量识 别抗原能力比母体强的8 细胞。这些识别能力较强的细胞能有效缠住入侵抗原， 这种现象称为亲和成熟。 亲和成熟的过程主要由抗体的突变完成，称为亲和突变，而突变受其母体 的亲和力制约，因此亲和成熟过程本质上是克隆细胞不断重复遭受变异的过程。 突变的方式主要有：单点突变、超突变及基因块重组、基因块反序、基因块替换( 酃 用随机产生的基因取代基因块中所有基因) 等。 生物抗体克隆选择学说中的概念和克隆算法算法中的相关概念的关系如表 2 量。 在克隆选择算法中，有两种向量串，类是抗原( 用a g 表示) ，另一类是抗 体( 用a b 表示) ，l 是抗原抗体的向量的维数。 克隆选择算法如下： 第二举免疫理论及人t 免疫算法慨述 表2 ，l 尧隆选择学说拳l 毙隆算法粳关概念对应 生物抗体克隆选择学说中的概念克隆选择算法中的概念 抗体 问题所求的解 撬魇闯题的优仡鹜标( 露标函数) 及箕约紊条绺 抗体一抗体亲合在解空间中，砥个解之间的距离 抗体一抗原亲合 解所对应的目标函数值 ( 戏设定的亲合发函数值) s t e p l ：从待识别的抗原群中随机选择一个抗原a g ( a 舀a 疹著且将其提呈 给抗体群a b ； s t 印2 ：计算a b 中所有的n 个抗体对予抗原a 蜀的亲和力向量与： s 蹭3 ：从舳中选择与抗原a 裁的亲和力最高的n 个抗体组成她 珏； s t e p 4 ：将a b j n ) 中的这n 个抗体根据它们的亲和力大小进行克隆扩张得到 抗体群c i ；亲和力越高的抗体，可以复制出越多的相同的个体； s l 铎5 ：对q 进行高频变异得到抗体群c j + ；c j 孛抗体的亲稿力越低，变异 率越高；反之，变异率越低； s t 印6 ：计算c j + 中的抗体对抗原a g j 的亲和力向量弓； s t e p 7 ：从q + 中选波对抗原a 岛的亲和力最高的抗体a b j + ，如果挑+ 对抗原 a 鞠的亲和力高予记忆细胞群a b m ，中某一抗体a b 与抗原a 羁的亲和力，则用 a b i + 代替该a b 放入记忆细胞群a b m ) ； s t 印8 ：产生替代抗体群a b d ，代替a b r ) 中对于抗原a 翁亲和力最低的d 个抗原。 当抗原集合中的每个抗原都提呈给抗体群，并按如上算法步骤进行后，这 样就完成了一次迭代的计算。经过n g e n 次迭代或者算法得到的解满足终止条件 时，算法结束，记忆缨胞群即为优化解。 在克隆选择算法中选择亲和力最大的细胞进行克隆；淘汰没被激活的细胞； 对克隆的细胞进行变异并且根据亲和力进行重新选择。该算法已经成功应用到了 模式识别、多峰函数优化和组合优化中等，并取褥了良好效采。但是此算法要在 一个相对静止的状态下进行，当环境剧烈变化的时候，算法的效率降低。 第二章免疫理论及人t 免疫算法概述 阴性选择算法借助免疫系统机制及性质一节中介绍的阴性选择原理的自己 和非己识别的原理来设计。它先随机产生检测器，然后删除其中与自身对抗的， 并保留能检测到非己的细胞。阴性选择算法思想分为两个阶段，即检测器生成阶 段和检测器监控阶段，前一阶段保证成熟的检测器不与自己匹配，后一阶段利用 检测器监控被保护数据集。其算法如下： s t e p l ：定义自己( s e l f ) 为一个字符串集合s ，每个字符串由字母表中n 个字 母组成，字符串可以是一个网络数据包，电子邮件特征向量或程序的一般行为模 式。 s t 印2 ：产生一个初始监测器集合r 。 s t 印3 ：监测器集合中每个监测器经历阴性选择过程。其中每一个监测器都不 能与集合s 中的任何一个字符串相匹配，否则就从监测器集合中删去对应的检测 器。 s t 印4 ：通过与r 集合的匹配不断监测s 的变化，一旦发生任何匹配，则说明 s 集发生了变化，即有外来抗原侵入。 在最初的算法描述中，候选的监测器是随机产生的，然后测试以删除与自 身字串相匹配的监测器，算法中采用的匹配规则是r 一连续位匹配，即当两个字 符串至少存在连续r 位相同是才发生匹配。该过程重复进行，直到所需数量的监 测器被产生出来。通常用概率分析方法来估算为了满足一定的可靠性所应有的监 测器的数目。采用随机产生的方法最主要的限制就是产生有效监测器的计算难度 随自身集的规模的增加而呈指数增加。于是更为有效的监测器产生方法被提出。 这种方法与自身集的规模成正比。还有另外一些产生方法，它们的计算复杂性都 有所不同。 阴性选择算法以对系统的侵害检测、保护为目的，在变化检测领域有许多 的应用。该算法所依赖的3 个重要原则是眩们：每种监测算法是唯一的；监测是 概率性的；一个鲁棒性的系统应能随机性地监测外来的活动而不是搜索已知的模 式。该算法在变化监测领域有许多应用。实际上，阴性选择算法被应用于计算机 网络安全保障，解决了许多过去在同类问题中难以解决的难题，成效显著。 基于免疫原理的免疫算法具有较强的搜索优化能力，所以免疫算法可以看 成是搜索方法的一个新的方向。基于免疫原理利用不同的模型，免疫算法已经演 第一二章免疫理论及人1 = 免疫算法溉述 变出7 多种改进算法，免疫遗传算法就是其中典型的算法。免疫遗传算法是一种 新型融合算法，是具有免疫功能的遗传算法。免疫遗传算法与免疫算法在形式上 看，就是在免疫算法中加入了遗传算子，与遗传算法相比，增加了抗原识别、记 忆功能和调节功能，没有附粕复杂的操作，没有降低遗传算法的鲁捧性，兼顾了 搜索速度，全局和局部搜索能力。比较典型的是用于b p 网络设计的免疫遗传算 法和自体免疫遗传算法，前者是利用一种引入免疫功能的遗传算法设计b p 神经 网络，后者则在t s p 问题求解中表现出较傀的特性。 此外，不同的研究人员出于不同的研究目的，开发出用于不同闯题的免疫 算法，如：s h y hj i e rh u a n g 子1 9 9 9 年提出的解决电容布置问题的免疫算法【2 7 】， j e e m 讯h o n g 于2 0 年提出免疫生产计划算法，用于解决多头表面装配器的最小 化p c b 装配时闻的问题【捌。戤mj 予2 0 0 2 年提出了用于应对连续变化的环境， 预测非自体新模式的动态克隆算法【2 9 】t 。 根据免疫算法的研究经验，外来侵害的检测和内部学习机制的优化成为两 大难点f 捌。重前使用的外来侵害检测算法还十分简单低能，与生物体的机施差 距很大，远不能满足实际优化问题应用的需要。现在的免疫算法一般建立在精确 的数学模型公式的基础上。数学模型固然简单、易于实现，但功能不强，结果 往往失真，智能度不高，也不便于改进。在免疫算法中加入问题的启发性信息， 优化了算法的效率。 免疫算法与般的确定性优化算法相比，有以下显著特点1 3 1 】： ( 1 ) 同时援索解空间中的一系列点，而不只是一个点； ( 2 ) 处理的对象是表示带求解参数的编码数串，丽不是参数本身； ( 3 ) 用的是目标函数本身，而不是其导数或其它附加信息： ( 4 ) 变化规则是随机的，而不是确定的。 今后免疫优化算法研究重点大致集中在：免疫优化算法的有效性；异邑智 能化识别能力；免疫优化算法的智能化等几个方蕊。今后的发展的趋势是向通用 型的免疫算法发展，应用在不同的领域，尽可能少的修改算法。提高学习机制的 效率，与其它算法混合使用。 第二帮免疫理论及人t 免疫算法概述 2 ，4 小结 生物免疫系统是一个高度进化、分布式、强鲁棒性的复杂动力系统，能有 效识别外来侵入者，维持机体本身的平衡，保证生物体自身的生存和发展，它很 大程度地保护人体免受各种外界入侵的有机体的侵害，它的许多作用原理和功能 特点对于很多工程应用问题有着良好的启示。本章概述了生物免疫系统的组成和 结构以及生物免疫系统的机制和性质，并探讨了由生物免疫系统仿生两来的入工 免疫系统中的免疫算法，对免疫算法在工程中的应用作了介绍，介绍了免疫算法 中的两个重要的算法( 克隆选择算法及阴性选择算法) ，总结了免疫算法的优缺 点及其发展趋势。本论文的接下来主要的工俸将模拟免疫的克隆选择机理，将免 疫记忆，二次应答等免疫特性引入克隆选择机理，改进克隆算法，并将免疫克隆 算法应用到数据挖掘中。 第三章改进的嵬隆算法 3 。_ l 引言 第三章改进的克隆算法 工程中魏许多实际问题可以抽象为戬函数优化与缀合优化为代表的复杂优 化闯题，丽这些优化问题通常难以用常规的数学方法进行求解。人工免疫算法作 为一种新兴的生物启发式算法，提供了一种求解复杂优化问题的新的途径，在解 决复杂的优化问题方面具有明显的优势。与遗传算法、人工神经网络等其他智能 优化方法相比，它的优势体现在减轻算法的退化、加速算法收敛、提高复杂优化 问题的求解质量等方面。 在第二章中介绍了基本的克隆选择算法，该算法借鉴了生物免疫系统中的 克隆原理，算法具有高度的并行性，通过控制高频变异率，可以实现对最一般特 征的初始搜索，提高了收敛速度，较好的保持了种群多样性。但和其它智能优化 算法一样，基本克隆算法也存在不足之处，如在迭代后期容易出现停滞现象，导 致搜索精度不高；对初始解有较强的依赖性，容易陷入局部最优。因此许多研究 人员对基本克隆算法作了深入的研究，并作了许多改进，使得改进后的克隆选择 算法在多用户检测、函数优化、数据挖掘等方面得到了广泛的康用。 基本的克隆算法包含的生物梳理包括亲和力成熟，克隆，克隆选择，基因 突变等，但是诸如记忆、遗忘，以及自适应等免疫机理没有考虑或者涉及很少， 因此很多研究者将不同的免疫机理引入克隆算法，研究出新的免疫克隆算法。其 中，文献i 2 l j 将免疫记忆机理和耐受的克隆消亡引入克隆选择算法，提出了新的 免疫克隆算法，邸免疫记忆动态壳隆算法和免疫记忆克隆算法，并证明了其收敛 性。文献【2 2 】提出了增强变异免疫算法和引导型免疫算法。 3 。2 免疫克隆算法 克隆选择的主要特征是免疫缨胞在抗原刺激下产生克隆增殖，随后通过遗 传变异分化为多样性效应细胞( 如抗体细胞) 和记忆细胞。克隆选择对应着一个亲 合度成熟的过程，即对抗原亲合度较低的个体在克隆选择机制的作用下，经历增 第三章改进的兜隆算法 ( 2 ) 基于欧氏距离的抗体一抗体亲和度计算方法 对于实数编码的算法，抗体一抗体亲和度通常可以通过抗体向量之间的欧氏 距离来计算： a f f ( a b i ，a b j ) 2晒 3 2 式中a b i ，k 和a b j ，k 分别为抗体i 的第k 维和抗体j 的第k 维，l 为抗体编码总 维数。这是实数编码算法中最常见的抗体一抗体亲和度的计算方法。 ( 3 ) 基于海明距离的抗体一抗体亲和度计算方法 对于基于离散编码的算法，衡量抗体一抗体亲和度最直接的方法就是利用抗 体串的海明距离鳓： l l a 避癜i ，如) 一氐 争3 度。 其中 a k = 擞裁羔 3 4 式中a b i ，l ( 和a b j 玉分别为抗体i 的第k 位和抗体j 的第k 位，l 为抗体编码长 ( 4 ) 基于信息熵的抗体一抗体杀和度计算方法 在离教编码的算法中，利用信息熵的概念实现抗体一抗体亲和度的计算也是 一种常见的方法。此方法中抗体一抗体亲和度的定义为【3 4 】： a 仃( a b p a b j ) 。再茜而 3 其中，h i j ( 2 ) 为抗体a b i 和a b j 组成的抗体群的平均信息熵，定义为： h 叫( 2 ) = 。( 2 ) 3 6 。k 群o 其中l 为抗体编码长度，h i j ，k ( n ) 为抗体a b i 和a b j 组成的抗体群第k 个基因 座上信息熵，计算方法为： h i j k ( 2 ) = - p 扯b g p 扯 3 7 其中，p 。为抗体a b j 和a b j 组成的抗体群中第k 维为第n 个等位基因的概率。 第三章改进的兜照算法 基于抗体一抗原亲和度的计算方法将抗体一撬原亲和度较近的抗体视为近戗 抗体，因此具有相近的抗体一抗原亲和度的抗体之间将具有较高的抗体一抗体亲和 度。然而，在许多应用中，抗体一抗原亲和度的定义可能是一个多峰函数，具有 相近抗体一抗原亲和度的两个抗体可能满予搜索空闻孛不圈的区域，抑刹这样的 抗体将导致不能很好的寻得最优解，对算法寻优过程有害无益。基于欧式距离的 计算方法适用于十进制数编码的编码方式。基于海明距离的计算方法和基于信息 熵阁的计算方法适用于基于离散编码的算法。在本文算法中由于采用二进制编 码，故采用基于海明距离的计算方法，当采用二进制编码的时候，海明距离的计 算方法如下： l - 重 a 域a b i ，a b j ) = fa b i k a b j ki k = o 3 8 其中，式中a b i k 和a b m 分别为抗体i 的第k 位和抗体j 的第k 位，l 为抗体 编码长度。 可见采用基于海明距离的抗体抗体亲和度计算方法，相同位数越多的抗体 之间亲和度越高。 在免疫系统中，当一种抗体受到抗原刺激或其它抗体刺激或抑制的时候， 这种抗体昭数量将发生变化。般亲和力大靛抗体的数量将得到提高，当其提高 到一定值的时候就要受到抑制，否则将导致抗体种群多样性差的问题。在人工免 疫系统中抗体浓度表征抗体种群的多样性好坏，抗体浓度过高意味着种群中非常 类似的个体大量存在，则寻优搜索会集中予可行解区间的一个区域，不利于全局 优化。因此优化算法中应对浓度过高的个体进行抑制，保证个体的多样性。 抗体浓度通常定义为【3 4 】： 出n ( 剐2 吉荟a 趣a _ b i ，蝴 3 棚 其中n 为种群规模；a b i 为种群中的第i 个抗体；a 趣a b i ，a b l ) 为抗体i 与抗体 的亲和度。 籀三章改进的兜隆算法 3 。2 。3 克隆扩增和克隆变异 在克隆算法中，非常重要的一个环节是克隆扩增和克隆变异，一般统称为 克隆算子。克隆扩增算予将亲和度大的抗体个体进行复制。克隆扩增算子可以描 述为【3 6 】： t c ( a b i ) = c l o n e ( a b i ) 式中c l 鼹e 曲i ) 为嫩i 个与曲i 相网的克隆构成的集合；爨i 势抗体竞隆数西， 可以事先确定，也可以动态自适应计算。进行动态自适应计算的时候，克隆扩增 的规模是抗原亲和力测量的递增函数，亲和力越大，克隆规模越大。一般克隆规 模按照下式来进行： q i = i n tn c 掣 a f f ( a j ) j = l 3 1 0 n e 是抗体群的总的壳隆规模，i n ) 为上取整涵数，i 燃( x ) 表示取大予x 的最 小的整数。由公式可以看出，反映抗体个体克隆规模的量是依赖抗原亲和度并可 自适应地调整，亲合度大的个体其克隆规模也大。 在克隆算法牢，克隆变异是指对克隆扩增得到的抗体克隆结果进行变异操 作，以产生亲和度突变，实现局部搜索，是克隆算法中产生有潜力的毅抗体、实 现区域搜索的重要算子，对算法的性能有很大影响。 一般每个抗体的克隆变异概率按照下式进行计算： 碱细，长：掣印m 3 哪 其中a b i j ，m 是抗体a b i 的第m 个克隆体的第j 维；! a b i j ，m 为a b i j ，m 取反的结果： 凇琏) 是产生( 0 ，1 ) 范圈内随机数的鼹数，通常采用基于均匀分布鹩隧机数发生 器；p m 为变异概率。由于变异概率p m 一般较小，海明距离d ( a ，b ) 越小，p a 峥b 越大，从而变异使得抗体在其领域内变化，扩大了搜索范围。 在文献1 3 7 1 中，提出了多克隆算子，多克隆与单克隆算子主要的区别在于在 克隆复制之后不但有克隆变异，还有克隆重组。多克隆为多种重组策略的共同作 用提供了条件，可以实现对于闶一抗体的不同克隆个体按一定概率采用不