人工免疫算法课件

人工免疫算法人工免疫算法人工免疫算法人工免疫算法 人工智能信息处理系1 人工智能信息处理系统的研究人工智能信息处理系统的研究脑神经系统（神经网络）；脑神经系统（神经网络）；遗传系统（进化计算）；遗传系统（进化计算）；免疫系统（人工免疫系统）。免疫系统（人工免疫系统）。人工智能信息处理系统的研究脑神经系统（神经网络）；2一门新兴的研究领域。一门新兴的研究领域。的研究历史的研究历史等人在等人在1986年首先在工程领域提出免疫概念；年首先在工程领域提出免疫概念；等人受免疫网络学说的启发，提出并进而完善免疫网络模型。等人受免疫网络学说的启发，提出并进而完善免疫网络模型。一门新兴的研究领域。的研究历史等人在1986年首先在工程3人工免疫网络模型人工免疫网络模型的研究现状之一的研究现状之一独特型免疫网络（）；独特型免疫网络（）；互联耦合免疫网络（）；互联耦合免疫网络（）；免疫反应网络（）；免疫反应网络（）；对称网络（）；对称网络（）；多值免疫网络（）多值免疫网络（）.人工免疫网络模型的研究现状之一独特型免疫网络（）；4 免疫学习算法免疫学习算法的研究现状之二的研究现状之二反面选择算法（）；反面选择算法（）；免疫学习算法（）；免疫学习算法（）；免疫遗传算法（）；免疫遗传算法（）；免疫算法（）；免疫算法（）；免疫网络调节算法（）；免疫网络调节算法（）；免疫进化算法（）免疫进化算法（）.免疫学习算法的研究现状之二反面选择算法（）；5 国际研究国际研究的研究现状之三的研究现状之三1996年，日本，基于免疫性系统的国际专题讨论会，提出并确认人工免疫系统（）的概念；年，日本，基于免疫性系统的国际专题讨论会，提出并确认人工免疫系统（）的概念；1997年，的组织专门成立了人工免疫系统及应用的分会组织；年，的组织专门成立了人工免疫系统及应用的分会组织；目前，几乎所有有关人工智能领域的学术会议都收录方面的论文。目前，几乎所有有关人工智能领域的学术会议都收录方面的论文。国际研究的研究现状之三1996年，日本，基于免疫性系统6免疫进化算法的研究免疫进化算法的研究免疫进化算法的研究7生物免疫的启示生物免疫的启示在生物自然界中，免疫现象普遍存在，并对物种的在生物自然界中，免疫现象普遍存在，并对物种的 生存与繁衍生存与繁衍 发挥着重要的作用；发挥着重要的作用；生物的免疫功能主要是由参与免疫反应的细胞或由其构成的器官来完成的；生物的免疫功能主要是由参与免疫反应的细胞或由其构成的器官来完成的；生物免疫主要有两种类型：生物免疫主要有两种类型：特异性免疫（特异性免疫（），），非特异性免疫反应（非特异性免疫反应（）；）；生物免疫系统是通过自我识别、相互刺激与制约而构成了一个生物免疫系统是通过自我识别、相互刺激与制约而构成了一个 动态平衡的网络结构动态平衡的网络结构。生物免疫的启示在生物自然界中，免疫现象普遍存在，并对物种的 8免疫生物学的基本概念免疫生物学的基本概念 抗原抗原是是指指能能够够刺刺激激和和诱诱导导机机体体的的免免疫疫系系统统使使其其产产生生免免疫疫应应答答，并并能能与与相相应应的的免免疫疫应应答答产产物物在在体体内内或或体体外外发发生生特特异异性性反反应应的物质。的物质。抗体抗体是是指指免免疫疫系系统统受受抗抗原原刺刺激激后后，免免疫疫细细胞胞转转化化为为浆浆细细胞胞并并产产生生能能与与抗抗原原发发生生特特异异性性结结合合的的免免疫疫球球蛋蛋白白，该该免免疫疫球球蛋蛋白白即为抗体。即为抗体。免疫生物学的基本概念 抗原9免疫系统的主要功能免疫系统的主要功能 免疫防御免疫防御即机体防御病原微生物的感染；即机体防御病原微生物的感染；免疫（自身）稳定免疫（自身）稳定即机体通过免疫功能经常消除那些损伤和衰老的细胞以维持机体的生理平衡；即机体通过免疫功能经常消除那些损伤和衰老的细胞以维持机体的生理平衡；免疫监视免疫监视即机体通过免疫功能防止或消除体内细胞在新陈代谢过程中发生突变的和异常的细胞。即机体通过免疫功能防止或消除体内细胞在新陈代谢过程中发生突变的和异常的细胞。免疫系统的主要功能 免疫防御10免疫系统的主要特点免疫系统的主要特点免疫识别免疫识别免疫应答免疫应答免疫耐受免疫耐受免疫记忆免疫记忆免疫调节免疫调节免疫系统的主要特点免疫识别11算法研究算法研究生物学概念与理论生物学概念与理论生物学概念与理论生物学概念与理论方法：方法：工程计算方法工程计算方法工程计算方法工程计算方法算法研究生物学概念与理论方法：工程计算方法12进化免疫进化免疫传传统统进进化化算算法法是是在在一一定定发发生生概概率率的的条条件件下下，随随机机地地、没没有有指指导导地地迭迭代代搜搜索索，因因此此它它们们在在为为群群体体中中的的个个体体提提供供了进化机会的同时，也无可避免地产生了退化的可能。了进化机会的同时，也无可避免地产生了退化的可能。每每一一个个待待求求的的实实际际问问题题都都会会有有自自身身一一些些基基本本的的、显显而而易易见见的的特特征征信信息息或或知知识识。然然而而进进化化算算法法中中的的交交叉叉和和变变异异算算子子在求解问题时，操作的可变程度较小。在求解问题时，操作的可变程度较小。进化免疫传统进化算法是在一定发生概率的条件下，随机地、13基本概念基本概念染色体染色体表示待求问题的解的形式的一种数据结构。表示待求问题的解的形式的一种数据结构。基因基因构成染色体的最基本的数据单位。构成染色体的最基本的数据单位。个体个体具有某类染色体结构的一种特例。具有某类染色体结构的一种特例。基本概念染色体14基本概念基本概念抗原抗原 所有可能错误的基因，即非最佳个体的基因。所有可能错误的基因，即非最佳个体的基因。疫苗疫苗根据进化环境或待求问题的先验知识，所得到的对最佳个体基因的估计。根据进化环境或待求问题的先验知识，所得到的对最佳个体基因的估计。抗体抗体根据疫苗修正某个个体的基因所得到的新个体。根据疫苗修正某个个体的基因所得到的新个体。基本概念抗原15免疫算子有两种类型：免疫算子有两种类型：全免疫全免疫 非特异性免疫非特异性免疫目标免疫目标免疫 特异性免疫特异性免疫免疫思想的实现免疫思想的实现 免疫算子免疫算子即：群体中的每个个体在进化算子作用后，对其每一环节都进行一次免疫操作的免疫类型；即：群体中的每个个体在进化算子作用后，对其每一环节都进行一次免疫操作的免疫类型；即：在进行了进化操作后，经过一定的判断，个体仅在作用点处发生免疫反应的一种类型。即：在进行了进化操作后，经过一定的判断，个体仅在作用点处发生免疫反应的一种类型。免疫算子有两种类型：免疫思想的实现 免疫算子即：群体中的每16免疫操作的基本过程免疫操作的基本过程首先，对待求求问题进行具体分析，从中提取出首先，对待求求问题进行具体分析，从中提取出 最基本的特征信息；最基本的特征信息；其次，对此特征信息进行处理，以将其转化为求解问题的一种方案；其次，对此特征信息进行处理，以将其转化为求解问题的一种方案；最后，将此方案以适当的形式转化成最后，将此方案以适当的形式转化成 免疫算子免疫算子 以实施具体的操作。以实施具体的操作。免疫操作的基本过程首先，对待求求问题进行具体分析，从中提17免疫算子免疫算子 算法中的免疫思想主要是在合理提取疫苗的基础上，通过免疫算子来实现的；算法中的免疫思想主要是在合理提取疫苗的基础上，通过免疫算子来实现的；免疫算子由免疫算子由 接种疫苗接种疫苗 和和 免疫选择免疫选择 两个操作完成的。两个操作完成的。为了防止群体的退化。为了防止群体的退化。为了提高个体的适应度。为了提高个体的适应度。免疫算子 算法中的免疫思想主要是在合理提取疫苗的基础上，18设设个个体体x，给给其其接接种种疫疫苗苗是是指指按按照照先先验验知知识识来来修修改改x的的某某些些基基因因位位上上的的基基因因或或其其分分量量，使使所所得得个个体体以以较较大大的的概概率率具具有有更更高高的的适适应应度度。疫疫苗苗 是是从从先先验验知知识识中中提提炼炼出出来来的的，它它所所含含的的信信息息量量及及其其准准确确性性对对算算法法性性能能的的发发挥起着重要的作用。挥起着重要的作用。免疫算子免疫算子接种疫苗接种疫苗之之设个体x，给其接种疫苗是指按照先验知识来修改x的某些基因位上19这这一一操操作作一一般般分分两两步步完完成成：第第一一步步是是 免免疫疫检检测测，即即对对接接种种了了疫疫苗苗的的个个体体进进行行检检测测，若若其其适适应应度度仍仍不不如如父父代代，则则该该个个体体将将被被父父代代中中所所对对应应的的个个体体所所取取代代；第第二二步步是是 退退火火选选择择，即即在在目目前前的的子子代代群群体体中中以右边所示概率以右边所示概率免疫算子免疫算子免疫检测免疫检测之之选选择择个个体体进进入入新新的的父父代代群群体体。在在免免疫疫策策略略中中，仅仅有有免免疫疫检检测测而没有退火选择。而没有退火选择。这一操作一般分两步完成：第一步是 免疫检测，即对接种了疫苗20体系结构体系结构免疫算法免疫算法免疫规划免疫规划免疫策略免疫策略 体系结构免疫算法21免疫算法免疫算法随机产生初始父代种群随机产生初始父代种群A1，根据先验知识抽取疫苗；，根据先验知识抽取疫苗；若当前群体中包含最佳个体，则算法停止运行并输出结果；否则，继续；若当前群体中包含最佳个体，则算法停止运行并输出结果；否则，继续；对当前第对当前第k代父本种群进行交叉操作，得到种群；代父本种群进行交叉操作，得到种群；对进行变异操作，得到种群；对进行变异操作，得到种群；对进行接种疫苗操作，得到种群；对进行接种疫苗操作，得到种群；对进行免疫选择操作，得到新一代父本对进行免疫选择操作，得到新一代父本1，转至第二步。，转至第二步。免疫算法随机产生初始父代种群A1，根据先验知识抽取疫苗；22免疫算法的收敛性免疫算法的收敛性状态转移过程示意图：状态转移过程示意图：定定 理：免疫算法是收敛的。理：免疫算法是收敛的。定定 义：如果对于任意的初始分布均有义：如果对于任意的初始分布均有则称算法收敛。则称算法收敛。免疫算法的收敛性状态转移过程示意图：定 理：免疫算法是收23初始化：首先，根据要求确定解的精度；其次，随机产生初始化：首先，根据要求确定解的精度；其次，随机产生N个个体，并由此构成初始的父代种群个个体，并由此构成初始的父代种群A0；根据先验知识抽取疫苗根据先验知识抽取疫苗H；计算当前种群的个体适应度，并进行停机条件的判断。若条件满足，则停止运行并输出结果；否则继续；计算当前种群的个体适应度，并进行停机条件的判断。若条件满足，则停止运行并输出结果；否则继续；对当前的父代群体进行变异操作，生成子代群体；对当前的父代群体进行变异操作，生成子代群体；对群体进行接种疫苗操作，得到种群；对群体进行接种疫苗操作，得到种群；对群体进行免疫选择操作，得到新一代父本对群体进行免疫选择操作，得到新一代父本1，并转至第三步。，并转至第三步。免疫规划免疫规划 初始化：首先，根据要求确定解的精度；其次，随机产生N个个体，24免疫规划的收敛性免疫规划的收敛性状态转移过程示意图：状态转移过程示意图：定定 理：免疫规划是收敛的。理：免疫规划是收敛的。定定 义：如果对于任意的初始分布均有义：如果对于任意的初始分布均有则称算法收敛。则称算法收敛。免疫规划的收敛性状态转移过程示意图：定 理：免疫规划是收25免疫策略免疫策略根据要求确定解的精度，再根据先验知识抽取疫苗根据要求确定解的精度，再根据先验知识抽取疫苗H；随机产生随机产生 个个体作为初始的父本群体；个个体作为初始的父本群体；交叉：产生由父代和子代构成的规模为交叉：产生由父代和子代构成的规模为2 的中间群体；的中间群体；变异：对每一个个体进行变异将得到一个新的个体；变异：对每一个个体进行变异将得到一个新的个体；免疫：首先按照对问题的先验知识修改个体免疫：首先按照对问题的先验知识修改个体(x,)的某些分量；然后对群体中注射了疫苗的个体进行检测；的某些分量；然后对群体中注射了疫苗的个体进行检测；选择：从规模为选择：从规模为2 的群体中按适应度的大小取出前的群体中按适应度的大小取出前 个个体作为新一代父本的群体；个个体作为新一代父本的群体；停机条件检测。停机条件检测。免疫策略根据要求确定解的精度，再根据先验知识抽取疫苗H；26免疫策略的收敛性免疫策略的收敛性状态转移过程示意图：状态转移过程示意图：定定 理：免疫策略是收敛的。理：免疫策略是收敛的。定定 义：如果对于任意的初始分布均有义：如果对于任意的初始分布均有则称算法收敛。则称算法收敛。免疫策略的收敛性状态转移过程示意图：定 理：免疫策略是收27免疫算子的机理免疫算子的机理在在免免疫疫选选择择作作用用下下，若若疫疫苗苗使使抗抗体体适适应应度度得得到到提提高高，且且高高于于当当前前群群体体的的平平均均适适应应度度，则则疫苗所对应的模式将在群体中呈指数级扩散；否则，它将被遏制或呈指数级衰减。疫苗所对应的模式将在群体中呈指数级扩散；否则，它将被遏制或呈指数级衰减。定定定定 理：理：理：理：免疫算子的机理在免疫选择作用下，若疫苗使抗体适应度得到提高，28:抽取疫苗：抽取疫苗：分析待求问题，搜集特征信息；分析待求问题，搜集特征信息；依据特征信息估计特定基因位上的模式依据特征信息估计特定基因位上的模式:；k=0 j=0；(=),j=j+1；i=0；(in)接种疫苗：接种疫苗：；免疫检验：免疫检验：,;；i=i+1；退火选择：退火选择：；k=1；免疫算子的执行算法免疫算子的执行算法:免疫算子的执行算法29具体分析待求问题，搜集特征信息。具体分析待求问题，搜集特征信息。免疫疫苗的选取方法免疫疫苗的选取方法通用方法通用方法之一之一以以问问题题为为例例，通通过过具具体体分分析析可可以以得得出出相相邻邻两两两两城城市市之之间间的的最最短短路路径径即即为为求求解解该问题时可以利用的一种疫苗。该问题时可以利用的一种疫苗。具体分析待求问题，搜集特征信息。免疫疫苗的选取方法通用方法之30问题的描述问题的描述问题的描述问题的描述问问题题是是旅旅行行商商问问题题的的简简称称。即即一一个个商商人人从从某某一一城城市市出出发发，要要遍遍历历所所有有目目标标城城市市，其其中中每每个个城城市市必必须须而而且且只只须须访访问问一一次次。所所要要研研究究的的问问题题是是在在所所有可能的路径有可能的路径中寻找一条路程最短的路线。该问题是一个典型的问题，即随着规模的增加，可行解的数目将做指数级增长。中寻找一条路程最短的路线。该问题是一个典型的问题，即随着规模的增加，可行解的数目将做指数级增长。问题的描述问题是旅行商问题的简称。即一个商人从某一城市出发，31问题的分析问题的分析问题的分析问题的分析设所有与城市距离最近的城市为设所有与城市距离最近的城市为,进行一次如虚线所示的调整后进行一次如虚线所示的调整后,多数情况下，多数情况下，l3较较1+的减少量要大于的减少量要大于l1+l2较的增加量。较的增加量。故：故：问题的分析设所有与城市距离最近的城市为,进行一次如虚线所示的32:(=)统计父代群体，确定最佳个体：统计父代群体，确定最佳个体：;分解最佳个体，抽取免疫基因：分解最佳个体，抽取免疫基因：;执行遗传和免疫算子操作执行遗传和免疫算子操作;免疫疫苗的选取方法免疫疫苗的选取方法自适应方法自适应方法之二之二:免疫疫苗的选取方法自适应方法之二33:邻近城市序列初始化：邻近城市序列初始化：(i)=(1,n),i=1,n;最短子路径的初始化：最短子路径的初始化：(i)i=1,n;(=)i=1 n 变异：变异：(i)=(i),1);选择：选择：(i,(i)(i)(i)=(i);(i)=(i,(i);免疫疫苗的选取方法免疫疫苗的选取方法进化规划方法进化规划方法之三之三:免疫疫苗的选取方法进化规划方法之三34仿真实验仿真实验基于的求解基于的求解之一之一a.免疫抗体免疫抗体b.最优化路径最优化路径75城市的问题免疫优化仿真示意图城市的问题免疫优化仿真示意图仿真实验基于的求解之一a.免疫抗体b.最优化路35子代适应度值随进化过程的变化曲线子代适应度值随进化过程的变化曲线子代适应度值随进化过程的变化曲线子代适应度值随进化过程的变化曲线a 通用遗传算法计算曲线通用遗传算法计算曲线b 免疫算法计算曲线免疫算法计算曲线子代适应度值随进化过程的变化曲线a 通用遗传算法计算曲线36仿真实验仿真实验基于的求解基于的求解之二之二a.免疫疫苗示意图免疫疫苗示意图 b.最优路径示意图最优路径示意图442城市的问题免疫优化仿真示意图城市的问题免疫优化仿真示意图仿真实验基于的求解之二a.免疫疫苗示意图 b.37子代适应度值随进化过程的变化曲线子代适应度值随进化过程的变化曲线子代适应度值随进化过程的变化曲线子代适应度值随进化过程的变化曲线a (,2 )-ES计算曲线计算曲线 b (,2 )-IS 计算曲线计算曲线子代适应度值随进化过程的变化曲线a (,2)-ES计38谢谢谢谢39