智能信息处理导论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描述描述问题描述：有个结点需要提供装货或卸货服务，表示为，可使用车辆数为（条物流配送路径），每条路径都有自己的装货点和送货点。已知：要求在结点的装货量为，卸货量为。这些任务由车场发出的车辆来完成，假设车辆容量为，已知、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、比较免疫算法与遗传算法。