人工免疫算法课件.ppt

1、 研究背景与现状;免疫进化算法;免疫神经网络;2021/5/41O在生物科学领域在生物科学领域,人们对进化、遗传和免疫等自然人们对进化、遗传和免疫等自然 现象已经进行了广泛而深入的研究现象已经进行了广泛而深入的研究;O进化算法是建立在模仿生物遗传与自然选择基础上进化算法是建立在模仿生物遗传与自然选择基础上的一种并行优化算法的一种并行优化算法,其性能优异、应用广泛其性能优异、应用广泛;O进化算子在为每个个体提供了进化机会的同时进化算子在为每个个体提供了进化机会的同时,也也无可避免地产生了退化的可能无可避免地产生了退化的可能;O大多数待求问题有可以利用的先验知识或特征信息大多数待求问题有可以利用的

2、先验知识或特征信息,故可以利用这些信息来抑制进化过程中的退化现象故可以利用这些信息来抑制进化过程中的退化现象;O生物免疫理论为改进原有算法的性能生物免疫理论为改进原有算法的性能,建立集进化建立集进化与免疫机制于一体的新型全局并行算法奠定了基础与免疫机制于一体的新型全局并行算法奠定了基础。2021/5/42脑神经系统（神经网络）脑神经系统（神经网络）;遗传系统（进化计算）遗传系统（进化计算）;免疫系统（人工免疫系统）。免疫系统（人工免疫系统）。2021/5/43OO一门新兴的研究领域。一门新兴的研究领域。Farmer等人在等人在1986年首先在工程领年首先在工程领域提出域提出免疫免疫概念概念;V

3、arela等人受免疫网络学说的启发等人受免疫网络学说的启发,提出并进而完善免疫网络模型。提出并进而完善免疫网络模型。2021/5/44OO人工免疫网络模型人工免疫网络模型独特型免疫网络（独特型免疫网络（Jerne）;互联耦合免疫网络（互联耦合免疫网络（Ishiguro）;免疫反应网络（免疫反应网络（Mitsumoto）;对称网络（对称网络（Hoffmann）;多值免疫网络（多值免疫网络（Tang）.2021/5/45OO 免疫学习算法免疫学习算法反面选择算法（反面选择算法（Forrest）;免疫学习算法（免疫学习算法（Hunt&Cooke）;免疫遗传算法（免疫遗传算法（Chun）;免疫免疫Ag

4、ent算法（算法（Ishida）;免疫网络调节算法（免疫网络调节算法（Wang&Cao）;免疫进化算法（免疫进化算法（Jiao&Wang）.2021/5/46OO 国际研究国际研究1996年年,日本日本,基于免疫性系统的国际基于免疫性系统的国际专题讨论会专题讨论会,提出并确认提出并确认人工免疫系统人工免疫系统（AIS）的概念的概念;1997年年,IEEE的的SMC组织专门成立了组织专门成立了人工免疫系统及应用人工免疫系统及应用的分会组织的分会组织;目前目前,几乎所有有关人工智能领域的学几乎所有有关人工智能领域的学术会议都收录术会议都收录AIS方面的论文。方面的论文。2021/5/472021/

5、5/48 在生物自然界中在生物自然界中,免疫现象普遍存在免疫现象普遍存在,并对物种的并对物种的 生生存与繁衍存与繁衍 发挥着重要的作用发挥着重要的作用;生物的免疫功能主要是由参与免疫反应的细胞或由生物的免疫功能主要是由参与免疫反应的细胞或由其构成的器官来完成的其构成的器官来完成的;生物免疫主要有两种类型生物免疫主要有两种类型:特异性免疫特异性免疫（Specific Immunity）,非非特异性免疫反应特异性免疫反应（Nonspecific Immunity）;生物免疫系统是通过自我识别、相互刺激与制约而生物免疫系统是通过自我识别、相互刺激与制约而构成了一个构成了一个 动态平衡的网络结构动态平

6、衡的网络结构。2021/5/49OO 抗原是指能够刺激和诱导机体的免疫系统使其产生免疫应答,并能与相应的免疫应答产物在体内或体外发生特异性反应的物质。OO 抗体是指免疫系统受抗原刺激后,免疫细胞转化为浆细胞并产生能与抗原发生特异性结合的免疫球蛋白,该免疫球蛋白即为抗体。2021/5/410OO 免疫防御即机体防御病原微生物的感染;OO 免疫（自身）稳定即机体通过免疫功能经常消除那些损伤和衰老的细胞以维持机体的生理平衡;OO 免疫监视即机体通过免疫功能防止或消除体内细胞在新陈代谢过程中发生突变的和异常的细胞。2021/5/411OO免疫识别OO免疫应答OO免疫耐受OO免疫记忆OO免疫调节2021

7、/5/412方法方法:2021/5/413OO 传统进化算法是在一定发生概率的条件下,随机地、没有指导地迭代搜索,因此它们在为群体中的个体提供了进化机会的同时,也无可避免地产生了退化的可能。OO 每一个待求的实际问题都会有自身一些基本的、显而易见的特征信息或知识。然而进化算法中的交叉和变异算子在求解问题时,操作的可变程度较小。2021/5/414OO 染色体表示待求问题的解的形式的一种数据结构。OO 基因构成染色体的最基本的数据单位。OO 个体具有某类染色体结构的一种特例。2021/5/415OO 抗原 所有可能错误的基因,即非最佳个体的基因。OO 疫苗根据进化环境或待求问题的先验知识,所得到

8、的对最佳个体基因的估计。OO 抗体根据疫苗修正某个个体的基因所得到的新个体。2021/5/416免疫算子有两种类型免疫算子有两种类型:全免疫全免疫 非特异性免疫非特异性免疫目标免疫目标免疫 特异性免疫特异性免疫即即:群体中的每个个体在进化算子作用后群体中的每个个体在进化算子作用后,对其每对其每一环节都进行一次免疫操作的免疫类型一环节都进行一次免疫操作的免疫类型;即即:在进行了进化操作后在进行了进化操作后,经过一定的判断经过一定的判断,个体仅个体仅在作用点处发生免疫反应的一种类型。在作用点处发生免疫反应的一种类型。2021/5/417OO首先首先,对待求求问题进行具体分析对待求求问题进行具体分析

9、,从中提取出从中提取出 最基本的特征信息最基本的特征信息;OO 其次其次,对此特征信息进行处理对此特征信息进行处理,以将其转化为求解以将其转化为求解问题的一种方案问题的一种方案;OO最后最后,将此方案以适当的形式转化成将此方案以适当的形式转化成 免疫算子免疫算子 以实施具体的操作。以实施具体的操作。2021/5/418OO 算法中的免疫思想主要是在合理提取疫苗算法中的免疫思想主要是在合理提取疫苗的基础上的基础上,通过免疫算子来实现的通过免疫算子来实现的;OO 免疫算子由免疫算子由 接种疫苗接种疫苗 和和 免疫选择免疫选择 两个操两个操作完成的。作完成的。为了防止群体为了防止群体的退化。的退化。

10、为了提高个体为了提高个体的适应度。的适应度。了提高适应度2021/5/419设个体设个体x,给其接种疫苗是指按照先验知给其接种疫苗是指按照先验知识来修改识来修改x的某些基因位上的的某些基因位上的基因或其分量基因或其分量,使所得个体使所得个体以较大的概率具有更高的适应度以较大的概率具有更高的适应度。疫苗疫苗 是从先验知识中提炼出来的是从先验知识中提炼出来的,它所含的信它所含的信息量及其准确性对算法性能的发挥起着重要息量及其准确性对算法性能的发挥起着重要的作用。的作用。2021/5/420这一操作一般分两步完成这一操作一般分两步完成:第一步是第一步是 免疫检免疫检测测,即对接种了疫苗的个体进行检测

11、即对接种了疫苗的个体进行检测,若其适应度若其适应度仍不如父代仍不如父代,则该个体将被父代中所对应的个体则该个体将被父代中所对应的个体所取代所取代;第二步是第二步是 退火选择退火选择,即在目前的子代群体即在目前的子代群体中以右边所示概率中以右边所示概率P xeeif xTf xTinikik()()()10选择个体进入新的父代群体。选择个体进入新的父代群体。在免疫策略中在免疫策略中,仅有免疫检测仅有免疫检测而没有退火选择。而没有退火选择。2021/5/421免疫算法免疫算法免疫规划免疫规划免疫策略免疫策略 2021/5/422 随机产生初始父代种群随机产生初始父代种群A1,根据先验知识抽取疫苗根

12、据先验知识抽取疫苗;若当前群体中包含最佳个体若当前群体中包含最佳个体,则算法停止运行并输出结则算法停止运行并输出结果果;否则否则,继续继续;对当前第对当前第k代父本种群代父本种群Ak进行交叉操作进行交叉操作,得到种群得到种群Bk;对对Bk进行变异操作进行变异操作,得到种群得到种群Ck;对对Ck进行接种疫苗操作进行接种疫苗操作,得到种群得到种群Dk;对对Dk进行免疫选择操作进行免疫选择操作,得到新一代父本得到新一代父本Ak+1,转至第二转至第二步。步。2021/5/423ABCDAkkkkk交 叉变 异接 种 疫 苗免 疫 选 择 1状态转移过程示意图状态转移过程示意图:定定 理理:免疫算法是收

13、敛的。免疫算法是收敛的。定定 义义:如果对于任意的初始分布均有如果对于任意的初始分布均有则称算法收敛。则称算法收敛。lim*kkisSP Ai12021/5/424 初始化初始化:首先首先,根据要求确定解的精度根据要求确定解的精度;其次其次,随机产生随机产生N个个体个个体,并由此构成初始的父代种群并由此构成初始的父代种群A0;根据先验知识抽取疫苗根据先验知识抽取疫苗H;计算当前种群计算当前种群Ak的个体适应度的个体适应度,并进行停机条件的判断。并进行停机条件的判断。若条件满足若条件满足,则停止运行并输出结果则停止运行并输出结果;否则继续否则继续;对当前的父代群体对当前的父代群体Ak进行变异操作

14、进行变异操作,生成子代群体生成子代群体Bk;对群体对群体Bk进行接种疫苗操作进行接种疫苗操作,得到种群得到种群Ck;对群体对群体Ck进行免疫选择操作进行免疫选择操作,得到新一代父本得到新一代父本Ak+1,并转并转至至第三步第三步。2021/5/425状态转移过程示意图状态转移过程示意图:定定 理理:免疫规划是收敛的。免疫规划是收敛的。定定 义义:如果对于任意的初始分布均有如果对于任意的初始分布均有则称算法收敛。则称算法收敛。ABCAkkkk高斯变异接种疫苗免疫选择1lim*kkisXP Ai12021/5/426 根据要求确定解的精度根据要求确定解的精度,再根据先验知识抽取疫苗再根据先验知识抽

15、取疫苗H;随机产生随机产生 个个体作为初始的父本群体个个体作为初始的父本群体;交叉交叉:产生由父代和子代构成的规模为产生由父代和子代构成的规模为2 的中间群体的中间群体;变异变异:对每一个个体进行变异将得到一个新的个体对每一个个体进行变异将得到一个新的个体;免疫免疫:首先按照对问题的先验知识修改个体首先按照对问题的先验知识修改个体(x,)的某些的某些分量分量;然后对群体中注射了疫苗的个体进行检测然后对群体中注射了疫苗的个体进行检测;选择选择:从规模为从规模为2 的群体中按适应度的大小取出前的群体中按适应度的大小取出前 个个个体作为新一代父本的群体个体作为新一代父本的群体;停机条件检测。停机条件

16、检测。2021/5/427状态转移过程示意图状态转移过程示意图:定定 理理:免疫策略是收敛的。免疫策略是收敛的。定定 义义:如果对于任意的初始分布均有如果对于任意的初始分布均有则称算法收敛。则称算法收敛。ABCDAkkkkk交叉变异免疫选择 1lim*kkisXP Ai12021/5/428在免疫选择作用下在免疫选择作用下,若疫苗使抗体适若疫苗使抗体适应度得到提高应度得到提高,且高于当前群体的平均适且高于当前群体的平均适应度应度,则疫苗所对应的模式将在群体中呈则疫苗所对应的模式将在群体中呈指数级扩散指数级扩散;否则否则,它将被遏制或呈指数它将被遏制或呈指数级衰减。级衰减。2021/5/429B

17、egin:抽取疫苗抽取疫苗:分析待求问题分析待求问题,搜集特征信息搜集特征信息;依据特征信息估计特定基因位上的模式依据特征信息估计特定基因位上的模式:;k=0 and j=0;while(Conditions=True)if PV=True,then j=j+1;i=0;for(in)接种疫苗接种疫苗:;免疫检验免疫检验:if ,then ;else ;i=i+1;退火选择退火选择:;k=k+1;EndHhjmj,12 aVahH kiPkijI,aaH kiki,1aakiki1aakiH ki,aakiH ki,AS Akk1()2021/5/430具体分析待求问题具体分析待求问题,搜集特

18、征信息。搜集特征信息。以以TSP问题为例问题为例,通过具体分析可以通过具体分析可以得出相邻两两城市之间的最短路径即为得出相邻两两城市之间的最短路径即为求解该问题时可以利用的一种疫苗。求解该问题时可以利用的一种疫苗。2021/5/431TSP问题是旅问题是旅行商问题的简称。行商问题的简称。即一个商人从某即一个商人从某一城市出发一城市出发,要要遍历所有目标城遍历所有目标城市市,其中每个城其中每个城市必须而且只须市必须而且只须访问一次。所要访问一次。所要研究的问题是在研究的问题是在所有可能的路径所有可能的路径中寻找一条路程最短的路线。该问题是一个典型的中寻找一条路程最短的路线。该问题是一个典型的NP

19、问题问题,即即随着规模的增加随着规模的增加,可行解的数目将做指数级增长。可行解的数目将做指数级增长。2021/5/432NjkkjjjikkiikkaaaaaaD112111NjkkjikkikkalallaDc13212111设所有与城市设所有与城市Ai距离最近的城市为距离最近的城市为Aj,进行一次如虚线所示的调整后进行一次如虚线所示的调整后,多数情况下多数情况下,l3较较aj-1+aj的减少量要大于的减少量要大于l1+l2较较ai的增加量。的增加量。DDPDDPcc故故:2021/5/433Begin:while(Conditions=True)统计父代群体统计父代群体,确定最佳个体确定最

20、佳个体:;分解最佳个体分解最佳个体,抽取免疫基因抽取免疫基因:;执行遗传和免疫算子操作执行遗传和免疫算子操作;endaStatistics a inkoptimalki(|,)1Hhajmjkjoptimal,1 2 2021/5/434Begin:邻近城市序列初始化邻近城市序列初始化:Neighbor(i)=random(1,n),i=1,n;最短子路径的初始化最短子路径的初始化:Sub_path(i)i=1,n;while(Conditions=True)for i=1 to n 变异变异:Neighbor(i)=Floor(Gauss(Neighbor(i),1);选择选择:if Dis

21、tance(City_ i,Neighbor(i)Min_distance(i)then Sub_path(i)=Neighbor(i);Min_distance(i)=Distance(City_ i,Neighbor(i);end endend2021/5/435020406080020406080a.免疫抗体免疫抗体b.最优化路径最优化路径75城市的城市的TSP问题免疫优化仿真示意图问题免疫优化仿真示意图2021/5/43601000200030004000020406080100当前最佳适应度当前平均适应度适应度进 化 子 代0200400600800100020406080100当前

22、最佳适应度当前平均适应度适应度进 化 子 代a 通用遗传算法计算曲线通用遗传算法计算曲线b 免疫算法计算曲线免疫算法计算曲线2021/5/437050100150200250300050100150200250300350400050100150200250300050100150200250300350400a.免疫疫苗示意图免疫疫苗示意图 b.最优路径示意图最优路径示意图442城市的城市的TSP问题免疫优化仿真示意图问题免疫优化仿真示意图2021/5/43800.511.522.53x 104020406080100120140最佳适应度曲线平均适应度曲线0500100015002000250030003500400020406080100120140最佳适应度曲线平均适应度曲线a (,2 )-ES计算曲线计算曲线 b (,2 )-IS 计算曲线计算曲线2021/5/439