智能信息处理导论ppt第7章免疫算法课件.ppt

第七章 免疫算法,7.1 免疫算法的生物学基础,7.1.1 免疫系统的形态空问7.1.2 免疫应答7.1.3 多样性7.1.4 克隆选择和扩增,7.1.1 免疫系统的形态空问,基本概念和技术术语：(1)免疫：指机体免疫系统识别自身与异己物质，并通过免疫应答排除抗原性异物，以维持机体生理平衡的功能。(2)免疫应答：是指抗原进入机体后，免疫细胞对抗原分子的识别、激活、分化、增殖和效应的过程。(3)抗原与抗体：诱导免疫系统产生免疫应答的物质称为抗原(antigen)；能与抗原进行特异性结合的免疫细胞称为抗体(antibody)。(4)亲和力(affinity)：免疫细胞的表面受体和抗原决定基都是复杂的含有电荷的三维结构，二者的结构和电荷越互补，就越有可能相互结合，结合的强度即是亲和力。,7.1.1 免疫系统的形态空问,(5)变异(mutation)：在生物免疫系统中，细胞与抗原结合后被激活，然后产生高频变异。这种克隆扩增期间产生的变异形式，使得免疫系统能够适应不断变化的外来入侵。(6)细胞：即淋巴细胞，它在胸腺中成熟，功能包括调节其他细胞的活动和直接袭击宿主感染细胞。(7)细胞：即淋巴细胞，来源于骨髓淋巴样前体细胞，成熟的细胞存在于淋巴结、血液、脾、扁桃体等组织和器官中，细胞是体内产生抗体的细胞，在清除病原体过程中受到刺激，分泌抗体结合抗原，但其发挥免疫作用要受辅助细胞的帮助。,7.1.1 免疫系统的形态空问,如图所示，在形态空间内有一个体积为V的区域，其中含有抗体（用 来表示）和抗原（用表示）的形状互补区域。假设一个抗体能识别所有在其周围体积 范围内的互补的抗原。,7.1.2 免疫应答,免疫系统的两种免疫应答类型：固有性免疫应答；适应性免疫应答。免疫算法主要是利用适应性免疫应答的应答原理，适应性免疫应答又分为两种类型，初次免疫应答和二次免疫应答。,7.1.3 多样性,免疫系统的多样性，本质就是抗体的多样性，即产生尽可能多的抗体对抗千变万化的抗原。免疫系统的多样性的实现： 体细胞高频变异 受体编辑 随机生成新抗体,7.1.4 克隆选择和扩增,基本思想：只有那些能够识别抗原的细胞才进行扩增，只有这些细胞才能被免疫系统选择并保留下来，而那些不能识别抗原的细胞则不被选择，也不能进行扩增。扩增过程：抗体C分化成许多克隆细胞，每一个克隆细胞受到刺激后又开始克隆，这样，增加了免疫系统中清除异物的抗体的数量。,7.2 免疫优化算法概述,7.2.1 人工免疫系统的定义7.2.2 免疫算法的提出7.2.3 免疫算法中涉及的术语简介7.2.4 免疫算法的算法思想7.2.5 免疫算法的收敛性7.2.6 免疫算法与免疫系统的对应7.2.7 常见免疫算法7.2.8 免疫算子说明,7.2.1 人工免疫系统的定义,人工免疫系统的几种定义：De Castro为人工免疫系统下的第一个定义认为：“人工免疫系统是遵循可信的生物学范例人类免疫系统原理的数据处理、分类、表示和推理策略系统”。Timmis为人工免疫系统给出的第一个定义则认为：“人工免疫系统是基于自然免疫系统方法的计算系统”。Dasgupta给出的定义是：“人工免疫系统是由生物免疫系统启发而来的智能策略所组成，主要用于信息处理和问题解决”。,7.2.1 人工免疫系统的定义,De Castro后来为人工免疫系统给出了第二个定义：“人工免疫系统是受生物免疫系统启发而来的用于求解问题的适应性系统”。Timmis后来也为人工免疫系统给出了第二个定义，即：“人工免疫系统是一种由理论生物学启发而来的计算范式，借鉴了一些免疫系统的功能、原理和模型并用于复杂问题的解决”。莫宏伟给出的人工免疫系统的定义为：“人工免疫系统是基于免疫系统机制和理论免疫学而发展的各种人工范例的特称。,7.2.3 免疫算法中涉及的术语简介,抗原：在生命科学中，是指能够刺激和诱导机体的免疫系统使其产生免疫应答，并能与相应的免疫应答产物在体内或体外发生特异性反应的物质。在我们的算法中，是指所有可能错误的基因，即非最佳个体的基因。抗体：在生命科学中，是指免疫系统受抗原刺激后，免疫细胞转化为浆细胞并产生能与抗原发生特异性结合的免疫球蛋白，该免疫球蛋白即为抗体。在本文中是指根据疫苗修正某个个体的基因所得到的新个体。,7.2.3 免疫算法中涉及的术语简介,免疫疫苗：根据进化环境或带球问题，所得到的对最佳个体基因的估计。免疫算子：全免疫和目标免疫，全免疫是指群体中每个个体在变异操作后，对其每一环节都进行一次免疫操作的免疫类型；目标免疫则指个体在进行变异操作后，经过一定判断，个体仅在作用点处发生免疫反应的一种类型。免疫调节：在免疫反应过程中，大量的抗体的产生降低了抗原对免疫细胞的刺激，从而抑制抗体的分化和增殖，同时产生的抗体之间也存在着相互刺激和抑制的关系，这种抗原与抗体、抗体与抗体之间的相互制约关系使抗体免疫反应维持一定的强度，保证机体的免疫平衡。,7.2.3 免疫算法中涉及的术语简介,免疫记忆：指免疫系统将能与抗原发生反应的抗体作为记忆细胞保存记忆下来，当同类抗原再次侵入时，相应的记忆细胞被激活而产生大量的抗体，缩短免疫反应时间。抗原识别：通过表达在抗原表面的表位和抗体分子表面的对位的化学基进行相互匹配选择完成识别，这种匹配过程也是一个不断对抗原学习的过程，最终能选择产生最适当的抗体与抗原结合而排除抗原。,7.2.4 免疫算法的算法思想,7.2.4 免疫算法的算法思想,根据流程图具体过程为：随机产生初始父代种群A1；根据先验知识抽取疫苗； 若当前群体中包含最佳个体,则算法停止运行并输出结果;否则继续；对于目前的第k代父本种群Ak进行交叉操作，得到种群Bk； 对Bk进行变异操作，得到种群Ck； 对Ck进行接种疫苗操作，得到种群Dk；对Dk进行免疫选择操作，得到新一代父本Ak+1,转至。,7.2.5 免疫算法的收敛性,算法的状态转移情况：X为搜索空间 n0的群体认为是状态空间S=Xn0中的一个点 |S|表示S中状态的数量,7.2.5 免疫算法的收敛性,7.2.6 免疫算法与免疫系统的对应,7.2.7 常见免疫算法,否定选择算法具体步骤:定义一个自体字符串集合，例如，可以是一个程序，数据文件（任何软件）或一般的行为模式.随机产生一个检测器集合，其中每一个字符串都不能与集合中的字符串相匹配。该算法中的匹配不是完全匹配，而是部分匹配，只要有连续位相同就称为匹配，此为一个可选择的参数。通过与集的匹配不断检测的变化，一旦发生任何匹配，就说明集合发生了变化，即有外来元素的侵入。,7.2.7 常见免疫算法,肯定选择算法具体步骤：初始化：产生一个细胞候选集合。假设所有的分子都用长度为l的二进制串表示，则可能产生27个不同的细胞；亲和力计算：通过集合，计算中所有元素与自体的亲和力；可用集合的产生：如果中某个元素与中某个元素的亲和力大于或等于一个给定的阈值，即这个细胞能识别这个自体，则它肯定被系统选用，放入；否则删除它。,7.2.7 常见免疫算法,克隆选择算法具体步骤：生成候选方案的一个集合（P）（初始群体），它由记忆细胞（M）的子集合加上剩余群体（Pr）（PPrM）；选择n个具有较高亲和力的个体；克隆这个最好的个体，组成一个临时的克隆群体（C）。与抗原亲和力越高，个体在克隆时的规模也就越大；把克隆群体提交到高频变异，根据亲和力的大小决定变异。产生一个成熟的抗体群体(*)；对*进行再选择，组成记忆细胞集合。中的一些成员可以被*中的其它一些改进的成员替换掉；生成个新的抗体取代中个低亲和力的抗体，保持多样性。,7.2.7 常见免疫算法,克隆选择算法在克隆选择算法表现出的重要特征中，高频变异(hypermutation)、受体编辑（receptor editing）是其重要的组成部分，它们是实现多样性的基本保障。高频变异机制的目的是为了使免疫应答能够快速地成熟。整数形态空间可以被看成是字母表大小缩小了的海明形态空间。,7.2.8 免疫算子说明,多样化抗体抑制和促进抗体抗原编码方式亲和力结合强度,7.3 免疫算法与遗传算法的比较,7.3.1 两者关系7.3.2 遗传算法的原理及缺陷7.3.3 免疫算法的原理及优势,7.3.1 两者关系,关联：免疫算法也作为一种进化算法，所用的遗传结构与遗传算法所用的类似，采用重组、变异等算子操作解决抗体优化等问题。区别：免疫算法起源于抗原和抗体之间的内部竞争，其相互作用的环境既包括外部也包括内部的环境；而遗传算法起源于个体和自私基因之间的外部竞争；免疫算法假设免疫元素互相作用，即每一个免疫细胞等个体可以互相作用，而遗传算法不考虑个体之间的作用；免疫算法中，基因可以由个体自己选择，而在遗传算法中基因由环境选择；,7.3.1 两者关系,区别：免疫算法中，基因组合是为了获得多样性，一般不用交叉算子，因为免疫算法中基因是在同一代个体进行进化，这种情况下，设交叉（杂交）概率为；而遗传算法后代个体基因通常是父代交叉的结果，交叉用于混合基因。免疫算法选择和变异阶段明显不同，而遗传算法中他们是交替进行的。,7.3.2 遗传算法的原理及缺陷,原理：利用遗传算法解决最优化问题，首先应对可行域中的点进行编码，然后在可行域中随机挑选一些编码作为进化起点的第一代编码组，并计算每个解的目标函数值。缺陷：早熟收敛、随机漫游、控制参数的选择等,7.3.3 免疫算法的原理及优势,核心思想：在合理提取疫苗的基础上，通过接种疫苗和免疫选择两个操作步骤来提高群体适应度，加速迭代过程并防止群体的退化。优势：改进的疫苗提取算法疫苗的自我识别分区域提取疫苗疫苗提取算法疫苗的构造,7.3.3 免疫算法的原理及优势,优势：改进的注射疫苗算法随机从疫苗库中选取一个疫苗利用该疫苗所含位置信息，寻找疫苗注射的合理位置找到个体中与将要注射的疫苗相冲突部分，并将冲突部分删除在找到的注射位注射疫苗,改进的免疫算法流程利用浓度概念计算记忆细胞和抑制细胞分化利用期望值计算抗体产生的促进和抑制通过随机决定基因产生新抗体，取代在前面被消除的抗体,7.4 免疫优化算法在VRP中的应用,7.4.1 装卸一体化的物流配送VRP描述7.4.2 抗体编码7.4.3 初始抗体的产生7.4.4 抗体亲和力计算7.4.5 产生记忆/抑制细胞7.4.6 选择、交叉、变异,7.4.1 装卸一体化的物流配送VRP描述,问题描述：有个结点需要提供装货或卸货服务，表示为，可使用车辆数为（条物流配送路径），每条路径都有自己的装货点和送货点。已知：要求在结点的装货量为 ，卸货量为 。这些任务由车场发出的车辆来完成，假设车辆容量为 ，已知 、 。求解：如何确定车辆行驶线路，使得总费用最小或者总行车路线最短。,7.4.1 装卸一体化的物流配送VRP描述,数学模型假设：每一车辆的都有一定的装载能力限制，配送路径上各结点的供货量和需求量均不超过汽车的核定载重量；每辆车只有一条行驶路线。期间可以为多个结点服务；每个结点的集送货服务只能由一辆车提供；封闭式配送，即每辆车的路线的开始和结束位置都在配送中心；结点的供货薰和需求量为一定值；配送中心使用的车型相同，即所有车辆的装载能力相同，且车辆参数相同；受混合时间窗限制。,7.4.1 装卸一体化的物流配送VRP描述,具体例题 某物流配送中心向周围个结点提供集送货服务，在结点（=，）的装货量为 ，卸货量为 （单位为吨）。配送中心共有两辆车用于配送，每辆汽车的载重量为t，每次配送的最大行驶距离为，配送中心与各需求点之间、各需求点相互之间的距离及各结点的装卸货物量见下表（其中需求点表示配送中心）。假设车辆的行驶时间与距离成正比，每辆车的平均行驶速度为50km/h。,7.4.1 装卸一体化的物流配送VRP描述,7.4.1 装卸一体化的物流配送VRP描述,7.4.1 装卸一体化的物流配送VRP描述,免疫优化程序设计步骤：抗原识别产生初始抗体初始化抗体群Ab，随机产生N个抗体，假设10。在第一次迭代时，抗体通常是在解空间中用随机的方法产生的，计算亲和性分别计算抗原和抗体之间的亲和性 及抗体和抗体之间的亲和性 。对Ab中的抗体按照亲和力由大至小按降序排列，再将这个抗体进行克隆，得到规模为Nc的抗体群Abc。,7.4.1 装卸一体化的物流配送VRP描述,克隆删除对Abc中的抗体按照基因重组概率进行基因重组后，进行克隆删除操作，得到规模为Nc的抗体群Abe：对Abe中的抗体按照突变概率进行突变操作后，进行克隆删除操作，得到规模为Nc的抗体群Abm。合并抗体群Ab和Abm，选出亲和力最高且互不相同的N个抗体组成抗体群Ab。记忆单元更新将与抗原的亲和性高的抗体加入到记忆单元中。由于记忆单元数目有限，所以在记忆单元中用新加入的抗体取代与其亲和性最高的原有抗体。促进和抑制抗体的产生,7.4.1 装卸一体化的物流配送VRP描述,式中，ci是抗体的密度（即数目）。为了有利于优化过程的进行，在步骤中，某些与抗原有较高亲和性的抗体也必须受到抑制。从上式中可以看出，与抗原亲和性高的抗体和低密度的抗体生存机率较大。由于高亲和性的抗体得到促进，而高密度的抗体受到抑制，所以上式体现了控制机制的多样性。经过这一步后幸存下来的抗体可以进入下一步。产生抗体通过变异和交叉，产生进入下一代的抗体。随机挑选的两个抗体按照事先设定的变异概率进行变异后，相互之间再进行交叉。重复执行步骤至步骤，直到终止条件（收敛判据）满足为止。（在一般免疫系统中，变异率为0.005）。终止条件判断是否满足终止条件，不满足则转至步骤继续执行，满足则结束计算。,7.4.2 抗体编码,简单直观的自然数编码（序数编码），用表示配送中心，用，表示各结点。因为共有辆车，最好存在条配送路径，每条配送路径都始于配送中心，也终于配送中心。为了在编码中反应车辆配送的路径，采用了增加2-1=1个虚拟配送中心的方法，分别自然数来表示。这样，（其中表示物流配送中心）这个互不重复的自然数的全排列就构成了!个抗体，表示着相应的物流配送方案。例如：抗体126398547表示配送路径的方案为：路径：0-1-2-6-39(0)；路径2：9(0)-8-5-4-7-0。,7.4.3 初始抗体的产生,按照上述的编码方式，随机产生（先假设=10）个编码长度为l的抗体，l=结点数车辆数-1=8+2-1=9。在第一次迭代时，抗体通常是在解空间中用随机的方法产生的，以下为随机产生的10个抗体：,7.4.4 抗体亲和力计算,分别计算抗体v和抗原间的亲和性axv。及抗体和抗体间的亲和axv,w。 抗原与抗体之间的亲和力axv，由于目标函数为求最小值，因此亲和力函数可以由目标函数的变换得到目标函数的倒数，即：,7.4.4 抗体亲和力计算,将上述随机产生的10个初始抗体以Ab1，Ab10。分别计算亲和力，按照亲和力由大至小按降序排列：Ab2，Ab8 ，Ab9 ，Ab7，Ab3，Ab4，Ab1，Ab10，Ab6，Ab5。可见，在这10个初始抗体中，抗体Ab2与抗原之间的亲和性最大（其亲和力等于0。00139860），抗体Ab5与抗原之间的亲和性最小（亲和力等于0。00103093）。例如：以上述10个初始抗体为例来说明抗体与抗体之间的亲和力计算。群体规模是10，抗体基因长度i=，符号集=，对于初始群体Ab1，Ab10。计算出第一个符号出现在基因座上的概率计算这10个初始抗体信息座j的信息熵j(10)计算出抗体Ab1，Ab2的平均信息熵H1,2(2)计算抗体Ab1，Ab2的相似度（亲和力）,7.4.6 选择、交叉、变异,这一步骤与通常应用于车辆路径优化调度（VRP）的遗传算法差别不大。对群体中的抗体按照各自的生存力进行选择，采用的是轮盘赌选择的方式，按照一定的淘汰率淘汰一部分生存力低的抗体，用随机产生的新抗体代替。选择生存下来的抗体再按一定的交叉概率进行随机配对交叉，交叉方法是顺序交叉（OX）法。然后，以一定的变异概率进行变异，采用的是对换变异的方法。,7.5 用免疫算法求解TSP问题,7.5.1 TSP问题描述7.5.2 免疫算子的构造方法7.5.3 免疫疫苗的选取的具体步骤7.5.4 免疫算法的程序,7.5.1 TSP问题描述,TSP问题是优化搜索算法尝试求解的经典问题之一，属于NP完全问题。TSP问题是旅行商问题的简称，即一个商人从某一城市出发，要遍历所有目标城市，其中每个城市必须而且只须访问一次。TSP问题是寻找一条最短的遍历n个城市的路径，或者说搜索整数子集X=1，2，n(X的元素表示对n个城市的编号)的一个排列V1，V2，.Vn)，使 取最小值，式中的 表示城市 到城市 的距离。,7.5.3 免疫疫苗的选取的具体步骤,分析待求问题,搜集特征信息根据特征信息制作免疫疫苗接种疫苗,7.5.4 免疫算法的程序,求解框图,7.5.4 免疫算法的程序,具体过程：个体编码和适应度函数交叉与变异算子免疫算子,习题 1、请描述免疫系统的生物学基础。 2、免疫系统有哪些特点？ 3、免疫系统有哪些特点。 4、简述免疫算法的步骤。 5、比较免疫算法与遗传算法。,