智能信息处理导论PPT第7章--免疫算法

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人工免疫系统的定义人工免疫系统的几种定义：DeCastro为人工免疫系统下的第一个定义认为：“人工免疫系统是遵循可信的生物学范例—人类免疫系统原理的数据处理、分类、表示和推理策略系统”。Timmis为人工免疫系统给出的第一个定义则认为：“人工免疫系统是基于自然免疫系统方法的计算系统”。Dasgupta给出的定义是：“人工免疫系统是由生物免疫系统启发而来的智能策略所组成，主要用于信息处理和问题解决”。7.2.1人工免疫系统的定义DeCastro后来为人工免疫系统给出了第二个定义：“人工免疫系统是受生物免疫系统启发而来的用于求解问题的适应性系统”。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中状态的数量ijss表示si，sj作为X的子集时的包含关系ikV表示随机变量V在第k代时处于状态si7.2.5免疫算法的收敛性定义1如果对于任意的初始分布均有*lim{}1ikksSPA，则称算法收敛。设f是X上的适应度函数，令*{()max()}iSxXfxfx7.2.6免疫算法与免疫系统的对应7.2.7常见免疫算法否定选择算法具体步骤:定义一个自体字符串集合Ｓ，例如，Ｓ可以是一个程序，数据文件（任何软件）或一般的行为模式.随机产生一个检测器集合Ｒ，其中每一个字符串都不能与集合Ｓ中的字符串相匹配。该算法中的匹配不是完全匹配，而是部分匹配，只要有连续ｒ位相同就称为匹配，此ｒ为一个可选择的参数。通过与Ｒ集的匹配不断检测Ｓ的变化，一旦发生任何匹配，就说明Ｓ集合发生了变化，即有外来元素的侵入。7.2.7常见免疫算法肯定选择算法具体步骤：初始化：产生一个Ｔ细胞候选集合Ｐ。假设所有的分子都用长度为l的二进制串表示，则可能产生27个不同的细胞；亲和力计算：通过集合Ｓ，计算Ｐ中所有元素与自体Ｓ的亲和力；可用集合的产生：如果Ｐ中某个元素与Ｓ中某个元素的亲和力大于或等于一个给定的阈值，即这个Ｔ细胞能识别这个自体，则它肯定被系统选用，放入Ａ；否则删除它。7.2.7常见免疫算法克隆选择算法具体步骤：生成候选方案的一个集合（P）（初始群体），它由记忆细胞（M）的子集合加上剩余群体（Pr）（P＝Pr＋M）；选择n个具有较高亲和力的个体；克隆这ｎ个最好的个体，组成一个临时的克隆群体（C）。与抗原亲和力越高，个体在克隆时的规模也就越大；把克隆群体提交到高频变异，根据亲和力的大小决定变异。产生一个成熟的抗体群体(Ｃ*)；对Ｃ*进行再选择，组成记忆细胞集合Ｍ。Ｐ中的一些成员可以被Ｃ*中的其它一些改进的成员替换掉；生成ｄ个新的抗体取代Ｐ中ｄ个低亲和力的抗体，保持多样性。7.2.7常见免疫算法克隆选择算法在克隆选择算法表现出的重要特征中，高频变异(hypermutation)、受体编辑（receptorediting）是其重要的组成部分，它们是实现多样性的基本保障。高频变异机制的目的是为了使免疫应答能够快速地成熟。整数形态空间可以被看成是字母表大小缩小了的海明形态空间。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装