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

《人工免疫算法培训课件.ppt》由会员分享，可在线阅读，更多相关《人工免疫算法培训课件.ppt（43页珍藏版）》请在三一办公上搜索。

1、人工免疫算法,人工免疫算法,主要内容, 研究背景与现状； 免疫进化算法； 免疫神经网络；,2,人工免疫算法,主要内容 研究背景与现状；2人工免疫算法,研究背景,在生物科学领域，人们对进化、遗传和免疫等自然 现象已经进行了广泛而深入的研究 ；进化算法是建立在模仿生物遗传与自然选择基础上的一种并行优化算法，其性能优异、应用广泛；进化算子在为每个个体提供了进化机会的同时，也无可避免地产生了退化的可能；大多数待求问题有可以利用的先验知识或特征信息，故可以利用这些信息来抑制进化过程中的退化现象；生物免疫理论为改进原有算法的性能，建立集进化与免疫机制于一体的新型全局并行算法奠定了基础。,3,人工免疫算法,

2、研究背景在生物科学领域，人们对进化、遗传和免疫等自然 现象已,Artificial Immune SystemAIS,人工智能信息处理系统的研究,脑神经系统（神经网络）；遗传系统（进化计算）；免疫系统（人工免疫系统）。,4,人工免疫算法,Artificial Immune SystemAIS人工,一门新兴的研究领域。,AIS的研究历史,Farmer等人在1986年首先在工程领域提出免疫概念；Varela等人受免疫网络学说的启发，提出并进而完善免疫网络模型。,5,人工免疫算法,一门新兴的研究领域。AIS的研究历史Farmer等人在1,人工免疫网络模型,AIS的研究现状之一,独特型免疫网络（Jer

3、ne）；互联耦合免疫网络（Ishiguro）；免疫反应网络（Mitsumoto）；对称网络（Hoffmann）；多值免疫网络（Tang）.,6,人工免疫算法,人工免疫网络模型AIS的研究现状之一独特型免疫网络（Je, 免疫学习算法,AIS的研究现状之二,反面选择算法（Forrest）；免疫学习算法（Hunt&Cooke）；免疫遗传算法（Chun）；免疫Agent算法（Ishida）；免疫网络调节算法（Wang&Cao）；免疫进化算法（Jiao&Wang）.,7,人工免疫算法, 免疫学习算法AIS的研究现状之二反面选择算法（Forr, 国际研究,AIS的研究现状之三,1996年，日本，基于免疫性

4、系统的国际专题讨论会，提出并确认人工免疫系统（AIS）的概念；1997年，IEEE的SMC组织专门成立了人工免疫系统及应用的分会组织；目前，几乎所有有关人工智能领域的学术会议都收录AIS方面的论文。,8,人工免疫算法, 国际研究AIS的研究现状之三1996年，日本，基于免疫,免疫进化算法的研究,9,人工免疫算法,免疫进化算法的研究9人工免疫算法,生物免疫的启示,在生物自然界中，免疫现象普遍存在，并对物种的 生存与繁衍 发挥着重要的作用；生物的免疫功能主要是由参与免疫反应的细胞或由其构成的器官来完成的；生物免疫主要有两种类型： 特异性免疫（Specific Immunity）， 非特异性免疫反应

5、（Nonspecific Immunity）；生物免疫系统是通过自我识别、相互刺激与制约而构成了一个 动态平衡的网络结构 。,10,人工免疫算法,生物免疫的启示在生物自然界中，免疫现象普遍存在，并对物种的,免疫生物学的基本概念, 抗原是指能够刺激和诱导机体的免疫系统使其产生免疫应答，并能与相应的免疫应答产物在体内或体外发生特异性反应的物质。 抗体是指免疫系统受抗原刺激后，免疫细胞转化为浆细胞并产生能与抗原发生特异性结合的免疫球蛋白，该免疫球蛋白即为抗体。,11,人工免疫算法,免疫生物学的基本概念 抗原11人工免疫算法,免疫系统的主要功能, 免疫防御即机体防御病原微生物的感染； 免疫（自身）稳定

6、即机体通过免疫功能经常消除那些损伤和衰老的细胞以维持机体的生理平衡； 免疫监视即机体通过免疫功能防止或消除体内细胞在新陈代谢过程中发生突变的和异常的细胞。,12,人工免疫算法,免疫系统的主要功能 免疫防御12人工免疫算法,免疫系统的主要特点,免疫识别免疫应答免疫耐受免疫记忆免疫调节,13,人工免疫算法,免疫系统的主要特点免疫识别13人工免疫算法,算法研究,生物学概念与理论,方法：,工程计算方法,14,人工免疫算法,算法研究生物学概念与理论方法：工程计算方法14人工免疫算法,进化免疫,传统进化算法是在一定发生概率的条件下，随机地、没有指导地迭代搜索，因此它们在为群体中的个体提供了进化机会的同时，

7、也无可避免地产生了退化的可能。 每一个待求的实际问题都会有自身一些基本的、显而易见的特征信息或知识。然而进化算法中的交叉和变异算子在求解问题时，操作的可变程度较小。,15,人工免疫算法,进化免疫传统进化算法是在一定发生概率的条件下，随机地、,基本概念,染色体表示待求问题的解的形式的一种数据结构。基因构成染色体的最基本的数据单位。个体具有某类染色体结构的一种特例。,16,人工免疫算法,基本概念染色体16人工免疫算法,基本概念,抗原 所有可能错误的基因，即非最佳个体的基因。疫苗根据进化环境或待求问题的先验知识，所得到的对最佳个体基因的估计。抗体根据疫苗修正某个个体的基因所得到的新个体。,17,人工

8、免疫算法,基本概念抗原17人工免疫算法,免疫算子有两种类型：全免疫 非特异性免疫目标免疫 特异性免疫,免疫思想的实现, 免疫算子,即：群体中的每个个体在进化算子作用后，对其每一环节都进行一次免疫操作的免疫类型；,即：在进行了进化操作后，经过一定的判断，个体仅在作用点处发生免疫反应的一种类型。,18,人工免疫算法,免疫算子有两种类型：免疫思想的实现 免疫算子即：群体中的每,免疫操作的基本过程,首先，对待求求问题进行具体分析，从中提取出 最基本的特征信息； 其次，对此特征信息进行处理，以将其转化为求解问题的一种方案；最后，将此方案以适当的形式转化成 免疫算子 以实施具体的操作。,19,人工免疫算法

9、,免疫操作的基本过程首先，对待求求问题进行具体分析，从中提,免疫算子,算法中的免疫思想主要是在合理提取疫苗的基础上，通过免疫算子来实现的；免疫算子由 接种疫苗 和 免疫选择 两个操作完成的。,The Immune operator,为了防止群体的退化。,为了提高个体的适应度。,20,人工免疫算法,免疫算子 算法中的免疫思想主要是在合理提取疫苗的基础上，,设个体x，给其接种疫苗是指按照先验知识来修改x的某些基因位上的基因或其分量，使所得个体以较大的概率具有更高的适应度。疫苗 是从先验知识中提炼出来的，它所含的信息量及其准确性对算法性能的发挥起着重要的作用。,免疫算子,接种疫苗,之,21,人工免疫

10、算法,设个体x，给其接种疫苗是指按照先验知识来修改x的某些基因位上,这一操作一般分两步完成：第一步是 免疫检测 ，即对接种了疫苗的个体进行检测，若其适应度仍不如父代，则该个体将被父代中所对应的个体所取代；第二步是 退火选择 ，即在目前的子代群体中以右边所示概率,免疫算子,免疫检测,之,选择个体进入新的父代群体。在免疫策略中，仅有免疫检测而没有退火选择。,22,人工免疫算法,这一操作一般分两步完成：第一步是 免疫检测 ，即对接种了疫苗,体系结构,免疫算法免疫规划免疫策略,23,人工免疫算法,体系结构免疫算法23人工免疫算法,免疫算法,随机产生初始父代种群A1 ，根据先验知识抽取疫苗；若当前群体中

11、包含最佳个体，则算法停止运行并输出结果；否则，继续；对当前第k代父本种群Ak进行交叉操作，得到种群Bk；对Bk进行变异操作，得到种群Ck；对Ck进行接种疫苗操作，得到种群Dk；对Dk进行免疫选择操作，得到新一代父本Ak+1，转至第二步。,Immune Algorithm-IA,24,人工免疫算法,免疫算法随机产生初始父代种群A1 ，根据先验知识抽取疫苗；I,免疫算法的收敛性,状态转移过程示意图：,定 理：免疫算法是收敛的。,定 义：如果对于任意的初始分布均有,则称算法收敛。,25,人工免疫算法,免疫算法的收敛性状态转移过程示意图：定 理：免疫算法是收,人工免疫算法培训课件,免疫规划的收敛性,状

12、态转移过程示意图：,定 理：免疫规划是收敛的。,定 义：如果对于任意的初始分布均有,则称算法收敛。,27,人工免疫算法,免疫规划的收敛性状态转移过程示意图：定 理：免疫规划是收,免疫策略,根据要求确定解的精度，再根据先验知识抽取疫苗H；随机产生个个体作为初始的父本群体；交叉：产生由父代和子代构成的规模为2的中间群体；变异：对每一个个体进行变异将得到一个新的个体；免疫：首先按照对问题的先验知识修改个体(x,)的某些分量；然后对群体中注射了疫苗的个体进行检测；选择：从规模为2的群体中按适应度的大小取出前个个体作为新一代父本的群体；停机条件检测。,Immune Strategy-IS,28,人工免疫

13、算法,免疫策略根据要求确定解的精度，再根据先验知识抽取疫苗H；Im,免疫策略的收敛性,状态转移过程示意图：,定 理：免疫策略是收敛的。,定 义：如果对于任意的初始分布均有,则称算法收敛。,29,人工免疫算法,免疫策略的收敛性状态转移过程示意图：定 理：免疫策略是收,免疫算子的机理,在免疫选择作用下，若疫苗使抗体适应度得到提高，且高于当前群体的平均适应度，则疫苗所对应的模式将在群体中呈指数级扩散；否则，它将被遏制或呈指数级衰减。,定 理：,30,人工免疫算法,免疫算子的机理在免疫选择作用下，若疫苗使抗体适应度得到提高，,Begin:抽取疫苗： 分析待求问题，搜集特征信息； 依据特征信息估计特定基

14、因位上的模式: ；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；End,免疫算子的执行算法,31,人工免疫算法,Begin:免疫算子的执行算法31人工免疫算法,具体分析待求问题，搜集特征信息。,免疫疫苗的选取方法,通用方法,之一,以TSP问题为例，通过具体分析可以得出相邻两两城市之间的最短路径即为求解该问题时可以利用的一种疫苗。,32,人工免疫算法,具体分析

15、待求问题，搜集特征信息。免疫疫苗的选取方法通用方法之,TSP问题的描述,TSP问题是旅行商问题的简称。即一个商人从某一城市出发，要遍历所有目标城市，其中每个城市必须而且只须访问一次。所要研究的问题是在所有可能的路径,中寻找一条路程最短的路线。该问题是一个典型的NP问题，即随着规模的增加，可行解的数目将做指数级增长。,33,人工免疫算法,TSP问题的描述TSP问题是旅行商问题的简称。即一个商人从某,TSP问题的分析,设所有与城市Ai距离最近的城市为Aj,进行一次如虚线所示的调整后,多数情况下， l3较aj-1 + aj的减少量要大于l1 + l2较ai的增加量。,故：,34,人工免疫算法,TSP

16、问题的分析设所有与城市Ai距离最近的城市为Aj,进行一,Begin:while (Conditions = True) 统计父代群体，确定最佳个体：; 分解最佳个体，抽取免疫基因：; 执行遗传和免疫算子操作;end,免疫疫苗的选取方法,自适应方法,之二,35,人工免疫算法,Begin:免疫疫苗的选取方法自适应方法之二35人工免疫算法,Begin:邻近城市序列初始化：Neighbor(i) = random(1, n) , i =1, , n;最短子路径的初始化：Sub_path(i) i =1, n;while (Conditions = True) for i = 1 to n 变异： Ne

17、ighbor(i) = Floor(Gauss(Neighbor(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 endend,免疫疫苗的选取方法,进化规划方法,之三,36,人工免疫算法,Begin:免疫疫苗的选取方法进化规划方法之三36人工免疫算,仿真实验,基于IA的TSP求解,之一,a. 免疫抗体b. 最优化路径75城市的TSP问题免疫优化仿真

18、示意图,37,人工免疫算法,仿真实验基于IA的TSP求解之一a. 免疫抗体b.,子代适应度值随进化过程的变化曲线,a 通用遗传算法计算曲线b 免疫算法计算曲线,38,人工免疫算法,子代适应度值随进化过程的变化曲线a 通用遗传算法计算曲线,仿真实验,基于IS的TSP求解,之二,a. 免疫疫苗示意图 b. 最优路径示意图442城市的TSP问题免疫优化仿真示意图,39,人工免疫算法,仿真实验基于IS的TSP求解之二a. 免疫疫苗示意图,子代适应度值随进化过程的变化曲线,a (,2 )-ES计算曲线 b ( ,2 )-IS 计算曲线,40,人工免疫算法,子代适应度值随进化过程的变化曲线a (,2 )-

19、ES计,仿真实验,基于IE的函数优化,之三,问题: 在(0,1)内寻找 xmax使下式成立:,41,人工免疫算法,仿真实验基于IE的函数优化之三问题: 41人工免疫算法,接受正常免疫疫苗时的计算曲线,(a) 基于EP的进化过程中个体分布图;(b) 基于IP的进化过程中个体分布图(c) EP和IP所求得的最佳适应度对比图(d) EP和IP所求得的平均适应度对比图,42,人工免疫算法,接受正常免疫疫苗时的计算曲线(a) 基于EP的进化过程中个,免疫疫苗为 时的计算曲线,(a) 基于EP的进化过程中个体分布图;(b) 基于IP的进化过程中个体分布图(c) EP和IP所求得的最佳适应度对比图(d) EP和IP所求得的平均适应度对比图,43,人工免疫算法,免疫疫苗为 时的计算曲线(a) 基于EP的进化过程,