人工免疫算法培训课件.ppt

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

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

3、域提出域提出免疫免疫概念概念；Varela等人受免疫网络学说的启发，等人受免疫网络学说的启发，提出并进而完善免疫网络模型。提出并进而完善免疫网络模型。5人工免疫算法OO人工免疫网络模型人工免疫网络模型独特型免疫网络（独特型免疫网络（Jerne）；）；互联耦合免疫网络（互联耦合免疫网络（Ishiguro）；）；免疫反应网络（免疫反应网络（Mitsumoto）；）；对称网络（对称网络（Hoffmann）；）；多值免疫网络（多值免疫网络（Tang）.6人工免疫算法OO 免疫学习算法免疫学习算法反面选择算法（反面选择算法（Forrest）；）；免疫学习算法（免疫学习算法（Hunt&Cooke）；）；免

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

5、学术会议都收录AIS方面的论文。方面的论文。8人工免疫算法9人工免疫算法 在生物自然界中，免疫现象普遍存在，并对物种的在生物自然界中，免疫现象普遍存在，并对物种的 生存与繁衍生存与繁衍 发挥着重要的作用；发挥着重要的作用；生物的免疫功能主要是由参与免疫反应的细胞或由生物的免疫功能主要是由参与免疫反应的细胞或由其构成的器官来完成的；其构成的器官来完成的；生物免疫主要有两种类型：生物免疫主要有两种类型：特异性免疫特异性免疫（Specific Immunity），），非非特异性免疫反应特异性免疫反应（Nonspecific Immunity）；）；生物免疫系统是通过自我识别、相互刺激与制约而生物免疫

6、系统是通过自我识别、相互刺激与制约而构成了一个构成了一个 动态平衡的网络结构动态平衡的网络结构。10人工免疫算法OO 抗原是指能够刺激和诱导机体的免疫系统使其产生免疫应答，并能与相应的免疫应答产物在体内或体外发生特异性反应的物质。OO 抗体是指免疫系统受抗原刺激后，免疫细胞转化为浆细胞并产生能与抗原发生特异性结合的免疫球蛋白，该免疫球蛋白即为抗体。11人工免疫算法OO 免疫防御即机体防御病原微生物的感染；OO 免疫（自身）稳定即机体通过免疫功能经常消除那些损伤和衰老的细胞以维持机体的生理平衡；OO 免疫监视即机体通过免疫功能防止或消除体内细胞在新陈代谢过程中发生突变的和异常的细胞。12人工免疫

7、算法OO免疫识别OO免疫应答OO免疫耐受OO免疫记忆OO免疫调节13人工免疫算法方法：方法：14人工免疫算法OO 传统进化算法是在一定发生概率的条件下，随机地、没有指导地迭代搜索，因此它们在为群体中的个体提供了进化机会的同时，也无可避免地产生了退化的可能。OO 每一个待求的实际问题都会有自身一些基本的、显而易见的特征信息或知识。然而进化算法中的交叉和变异算子在求解问题时，操作的可变程度较小。15人工免疫算法OO 染色体表示待求问题的解的形式的一种数据结构。OO 基因构成染色体的最基本的数据单位。OO 个体具有某类染色体结构的一种特例。16人工免疫算法OO 抗原 所有可能错误的基因，即非最佳个体

8、的基因。OO 疫苗根据进化环境或待求问题的先验知识，所得到的对最佳个体基因的估计。OO 抗体根据疫苗修正某个个体的基因所得到的新个体。17人工免疫算法免疫算子有两种类型：免疫算子有两种类型：全免疫全免疫 非特异性免疫非特异性免疫目标免疫目标免疫 特异性免疫特异性免疫即：群体中的每个个体在进化算子作用后，对其即：群体中的每个个体在进化算子作用后，对其每一环节都进行一次免疫操作的免疫类型；每一环节都进行一次免疫操作的免疫类型；即：在进行了进化操作后，经过一定的判断，个即：在进行了进化操作后，经过一定的判断，个体仅在作用点处发生免疫反应的一种类型。体仅在作用点处发生免疫反应的一种类型。18人工免疫算

9、法OO首先，对待求求问题进行具体分析，从中提取首先，对待求求问题进行具体分析，从中提取出出 最基本的特征信息最基本的特征信息；OO 其次，对此特征信息进行处理，以将其转化为其次，对此特征信息进行处理，以将其转化为求解问题的一种方案；求解问题的一种方案；OO最后，将此方案以适当的形式转化成最后，将此方案以适当的形式转化成 免疫算子免疫算子 以实施具体的操作。以实施具体的操作。19人工免疫算法OO 算法中的免疫思想主要是在合理提取疫苗算法中的免疫思想主要是在合理提取疫苗的基础上，通过免疫算子来实现的；的基础上，通过免疫算子来实现的；OO 免疫算子由免疫算子由 接种疫苗接种疫苗 和和 免疫选择免疫选

10、择 两个操两个操作完成的。作完成的。为了防止群体为了防止群体的退化。的退化。为了提高个体为了提高个体的适应度。的适应度。了提高适应度20人工免疫算法设个体设个体x，给其接种疫苗是指按照先验知给其接种疫苗是指按照先验知识来修改识来修改x的某些基因位上的的某些基因位上的基因或其分量基因或其分量，使所得个体使所得个体以较大的概率具有更高的适应度以较大的概率具有更高的适应度。疫苗疫苗 是从先验知识中提炼出来的，它所含的是从先验知识中提炼出来的，它所含的信息量及其准确性对算法性能的发挥起着重信息量及其准确性对算法性能的发挥起着重要的作用。要的作用。21人工免疫算法这一操作一般分两步完成：第一步是这一操作

11、一般分两步完成：第一步是 免疫免疫检测检测，即对接种了疫苗的个体进行检测，若其，即对接种了疫苗的个体进行检测，若其适应度仍不如父代，则该个体将被父代中所对应适应度仍不如父代，则该个体将被父代中所对应的个体所取代；第二步是的个体所取代；第二步是 退火选择退火选择，即在目前，即在目前的子代群体中以右边所示概率的子代群体中以右边所示概率P xeeif xTf xTinikik()()()10选择个体进入新的父代群体。选择个体进入新的父代群体。在免疫策略中，仅有免疫检在免疫策略中，仅有免疫检测而没有退火选择。测而没有退火选择。22人工免疫算法免疫算法免疫算法免疫规划免疫规划免疫策略免疫策略 23人工免

12、疫算法 随机产生初始父代种群随机产生初始父代种群A1，根据先验知识抽取疫苗；根据先验知识抽取疫苗；若当前群体中包含最佳个体，则算法停止运行并输出若当前群体中包含最佳个体，则算法停止运行并输出结果；否则，继续；结果；否则，继续；对当前第对当前第k代父本种群代父本种群Ak进行交叉操作，得到种群进行交叉操作，得到种群Bk；对对Bk进行变异操作，得到种群进行变异操作，得到种群Ck；对对Ck进行接种疫苗操作，得到种群进行接种疫苗操作，得到种群Dk；对对Dk进行免疫选择操作，得到新一代父本进行免疫选择操作，得到新一代父本Ak+1，转至转至第二步。第二步。24人工免疫算法ABCDAkkkkk交 叉变 异接

13、种 疫 苗免 疫 选 择 1状态转移过程示意图：状态转移过程示意图：定定 理：免疫算法是收敛的。理：免疫算法是收敛的。定定 义义：如果对于任意的初始分布均有如果对于任意的初始分布均有则称算法收敛。则称算法收敛。lim*kkisSP Ai125人工免疫算法状态转移过程示意图：状态转移过程示意图：定定 理：免疫规划是收敛的。理：免疫规划是收敛的。定定 义义：如果对于任意的初始分布均有如果对于任意的初始分布均有则称算法收敛。则称算法收敛。ABCAkkkk高斯变异接种疫苗免疫选择1lim*kkisXP Ai127人工免疫算法 根据要求确定解的精度，再根据先验知识抽取疫苗根据要求确定解的精度，再根据先验

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

15、体；停机条件检测。停机条件检测。28人工免疫算法状态转移过程示意图：状态转移过程示意图：定定 理：免疫策略是收敛的。理：免疫策略是收敛的。定定 义义：如果对于任意的初始分布均有如果对于任意的初始分布均有则称算法收敛。则称算法收敛。ABCDAkkkkk交叉变异免疫选择 1lim*kkisXP Ai129人工免疫算法在免疫选择作用下，若疫苗使抗体在免疫选择作用下，若疫苗使抗体适应度得到提高，且高于当前群体的平适应度得到提高，且高于当前群体的平均适应度，则疫苗所对应的模式将在群均适应度，则疫苗所对应的模式将在群体中呈指数级扩散；否则，它将被遏制体中呈指数级扩散；否则，它将被遏制或呈指数级衰减。或呈指

16、数级衰减。30人工免疫算法Begin:抽取疫苗：抽取疫苗：分析待求问题，搜集特征信息；分析待求问题，搜集特征信息；依据特征信息估计特定基因位上的模式依据特征信息估计特定基因位上的模式:；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()31人工免疫算法具体

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

18、条路程最短的路线。该问题是一个典型的NP问题，问题，即随着规模的增加，可行解的数目将做指数级增长。即随着规模的增加，可行解的数目将做指数级增长。33人工免疫算法NjkkjjjikkiikkaaaaaaD112111NjkkjikkikkalallaDc13212111设所有与城市设所有与城市Ai距离最近的城市为距离最近的城市为Aj,进行一次如虚线所示的调整后进行一次如虚线所示的调整后,多数情况下，多数情况下，l3较较aj-1+aj的减少量要大于的减少量要大于l1+l2较较ai的增加量。的增加量。DDPDDPcc故：故：34人工免疫算法Begin:while(Conditions=True)统计

19、父代群体，确定最佳个体：统计父代群体，确定最佳个体：;分解最佳个体，抽取免疫基因：分解最佳个体，抽取免疫基因：;执行遗传和免疫算子操作执行遗传和免疫算子操作;endaStatistics a inkoptimalki(|,)1Hhajmjkjoptimal,1 2 35人工免疫算法Begin:邻近城市序列初始化：邻近城市序列初始化：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(N

20、eighbor(i),1);选择：选择：if Distance(City_ i,Neighbor(i)Min_distance(i)then Sub_path(i)=Neighbor(i);Min_distance(i)=Distance(City_ i,Neighbor(i);end endend36人工免疫算法020406080020406080a.免疫抗体免疫抗体b.最优化路径最优化路径75城市的城市的TSP问题免疫优化仿真示意图问题免疫优化仿真示意图37人工免疫算法01000200030004000020406080100当前最佳适应度当前平均适应度适应度进 化 子 代02004006

21、00800100020406080100当前最佳适应度当前平均适应度适应度进 化 子 代a 通用遗传算法计算曲线通用遗传算法计算曲线b 免疫算法计算曲线免疫算法计算曲线38人工免疫算法050100150200250300050100150200250300350400050100150200250300050100150200250300350400a.免疫疫苗示意图免疫疫苗示意图 b.最优路径示意图最优路径示意图442城市的城市的TSP问题免疫优化仿真示意图问题免疫优化仿真示意图39人工免疫算法00.511.522.53x 104020406080100120140最佳适应度曲线平均适应度曲

22、线0500100015002000250030003500400020406080100120140最佳适应度曲线平均适应度曲线a (,2 )-ES计算曲线计算曲线 b (,2 )-IS 计算曲线计算曲线40人工免疫算法f xxx()sin.10101601200.10.20.30.40.50.60.70.80.9102468101214161820问题问题:在在(0,1)内寻找内寻找 xmax使下式成立使下式成立:f xf xx()(),(,)max 0 141人工免疫算法05010000.51050100141618200501000510152005010000.51(a)(b)(c)(

23、d)(a)基于基于EP的进化过程的进化过程中个体分布图中个体分布图;(b)基于基于IP的进化过程的进化过程中个体分布图中个体分布图(c)EP和和IP所求得的所求得的最佳适应度对比图最佳适应度对比图(d)EP和和IP所求得的平所求得的平均适应度对比图均适应度对比图42人工免疫算法xk1505010000.51050100141618200501000510152005010000.51(a)(b)(c)(d)(a)基于基于EP的进化过程的进化过程中个体分布图中个体分布图;(b)基于基于IP的进化过程的进化过程中个体分布图中个体分布图(c)EP和和IP所求得的所求得的最佳适应度对比图最佳适应度对比图(d)EP和和IP所求得的平所求得的平均适应度对比图均适应度对比图43人工免疫算法