免疫算法.pptx

第5章 免疫算法研究背景O在在生生物物科科学学领领域域，人人们们对对进进化化、遗遗传传和和免免疫疫等等自自然然现现象象已已经经进行了广泛而深入的研究进行了广泛而深入的研究；O进进化化算算法法是是建建立立在在模模仿仿生生物物遗遗传传与与自自然然选选择择基基础础上上的的一一种种并并行优化算法，其性能优异、应用广泛；行优化算法，其性能优异、应用广泛；O进进化化算算子子在在为为每每个个个个体体提提供供了了进进化化机机会会的的同同时时，也也无无可可避避免免地产生了退化的可能；地产生了退化的可能；O大大多多数数待待求求问问题题有有可可以以利利用用的的先先验验知知识识或或特特征征信信息息，故故可可以以利用这些信息来抑制进化过程中的退化现象；利用这些信息来抑制进化过程中的退化现象；O生生物物免免疫疫理理论论为为改改进进原原有有算算法法的的性性能能，建建立立集集进进化化与与免免疫疫机机制于一体的新型全局并行算法奠定了基础制于一体的新型全局并行算法奠定了基础。免疫学习算法免疫学习算法非选择算法（非选择算法（Forrest）；）；免疫学习算法（免疫学习算法（Hunt&Cooke）；）；免疫遗传算法（免疫遗传算法（Chun）；）；免疫免疫Agent算法（算法（Ishida）；）；免疫网络调节算法（免疫网络调节算法（Wang&Cao）；）；免疫进化算法（免疫进化算法（Jiao&Wang）.AIS 的应用自动控制故障诊断模式识别图象识别优化设计机器学习网络安全AIS在控制领域中的应用PID型免疫反馈控制器（型免疫反馈控制器（Takahashi）；）；机器人控制（机器人控制（Mitsumoto,Ishiguro,Lee）；）；控制系统的设计（控制系统的设计（Ishida）；）；复杂动态行为建模和自适应控制（复杂动态行为建模和自适应控制（Kumak）；）；倒立摆的控制（倒立摆的控制（Bersini）。）。AIS在故障诊断中的应用基于相关识别特性的免疫网络模型基于相关识别特性的免疫网络模型用于故障诊断的方法（用于故障诊断的方法（Ishida）；）；通过构造大规模独特型免疫网络来通过构造大规模独特型免疫网络来建立用于在线服务的故障诊断系统建立用于在线服务的故障诊断系统（Ishiguru）。）。AIS在模式识别中的应用Hunt等人开发了一种具有学等人开发了一种具有学习能力的人工免疫系统并用于模习能力的人工免疫系统并用于模式识别。式识别。AIS在联想记忆中的应用Gilbert等人采用免疫网络模等人采用免疫网络模型设计了一种内容可访的自动联型设计了一种内容可访的自动联想记忆系统并用于图像识别。想记忆系统并用于图像识别。AIS在优化设计中的应用永磁同步电动机的参数修正的优化设计；永磁同步电动机的参数修正的优化设计；电磁设备的外形优化；电磁设备的外形优化；VLSI印刷线路板的布线优化设计；印刷线路板的布线优化设计；函数测试；函数测试；旅行商问题的求解；旅行商问题的求解；约束搜索优化问题和多判据设计问题约束搜索优化问题和多判据设计问题；AIS在网络安全的应用数据检测（数据检测（Forrest）；）；病毒检测（病毒检测（Kephart）；）；UNIX过程监控过程监控（Forrest）。免疫进化算法生物免疫的启示n在在生生物物自自然然界界中中，免免疫疫现现象象普普遍遍存存在在，并并对对物物种种的的生生存存与与繁衍繁衍发挥着重要的作用；发挥着重要的作用；n生生物物的的免免疫疫功功能能主主要要是是由由参参与与免免疫疫反反应应的的细细胞胞或或由由其其构构成成的器官来完成的；的器官来完成的；n生生物物免免疫疫系系统统是是通通过过自自我我识识别别、相相互互刺刺激激与与制制约约而而构构成成了了一个一个 动态平衡的网络结构动态平衡的网络结构。免疫生物学的基本概念 抗原是指能够刺激和诱导机体的免疫系统使其产生免疫应答，并能与相应的免疫应答产物在体内或体外发生特异性反应的物质。抗体是指免疫系统受抗原刺激后，免疫细胞转化为浆细胞并产生能与抗原发生特异性结合的免疫球蛋白，该免疫球蛋白即为抗体。免疫系统的主要特点免疫识别免疫应答免疫耐受免疫记忆免疫调节算法研究生物学概念与理论生物学概念与理论方法：方法：工程计算方法工程计算方法进化免疫 传统进化算法是在一定发生概率的条件下，随机地、没有指导地迭代搜索，因此它们在为群体中的个体提供了进化机会的同时，也无可避免地产生了退化的可能。每一个待求的实际问题都会有自身一些基本的、显而易见的特征信息或知识。然而进化算法中的交叉和变异算子在求解问题时，操作的可变程度较小。基本概念抗原所有可能错误的基因，即非最佳个体的基因。疫苗根据进化环境或待求问题的先验知识，所得到的对最佳个体基因的估计。抗体根据疫苗修正某个个体的基因所得到的新个体。免疫算子有两种类型：免疫算子有两种类型：全免疫全免疫 非特异性免疫非特异性免疫目标免疫目标免疫 特异性免疫特异性免疫免疫思想的实现 免疫算子即即：群群体体中中的的每每个个个个体体在在进进化化算算子子作作用用后后，对对其其每一环节都进行一次免疫操作的免疫类型；每一环节都进行一次免疫操作的免疫类型；即即：在在进进行行了了进进化化操操作作后后，经经过过一一定定的的判判断断，个个体仅在作用点处发生免疫反应的一种类型。体仅在作用点处发生免疫反应的一种类型。免疫操作的基本过程首首先先，对对待待求求问问题题进进行行具具体体分分析析，从从中中提提取取出出 最基本的特征信息最基本的特征信息；其其次次，对对此此特特征征信信息息进进行行处处理理，以以将将其其转转化化为为求解问题的一种方案；求解问题的一种方案；最最后后，将将此此方方案案以以适适当当的的形形式式转转化化成成免免疫疫算算子子 以实施具体的操作。以实施具体的操作。免疫算子 算法中的免疫思想主要是在合理提取疫苗算法中的免疫思想主要是在合理提取疫苗的基础上，通过免疫算子来实现的；的基础上，通过免疫算子来实现的；免疫算子由免疫算子由 接种疫苗接种疫苗 和和 免疫选择免疫选择 两个操两个操作完成的。作完成的。The Immune operator为了防止群体为了防止群体的退化。的退化。为了提高个体为了提高个体的适应度。的适应度。设设个个体体x，给给其其接接种种疫疫苗苗是是指指按按照照先先验验知知识识来来修修改改x的的某某些些基基因因位位上上的的基基因因或或其其分分量量，使使所所得得个个体体以以较较大大的的概概率率具具有有更更高高的的适适应应度度。疫疫苗苗 是是从从先先验验知知识识中中提提炼炼出出来来的的，它它所所含含的的信信息息量量及及其其准准确确性性对对算算法法性性能能的的发发挥挥起起着着重重要的作用。要的作用。免疫算子接种疫苗之这这一一操操作作一一般般分分两两步步完完成成：第第一一步步是是免免疫疫检检测测，即即对对接接种种了了疫疫苗苗的的个个体体进进行行检检测测，若若其其适适应应度度仍仍不不如如父父代代，则则该该个个体体将将被被父父代代中中所所对对应应的的个个体体所所取取代代；第第二二步步是是 退退火火选选择择，即即在在目目前前的的子子代群体中以右边所示概率代群体中以右边所示概率免疫算子免疫检测之选选择择个个体体进进入入新新的的父父代代群群体体。在在免免疫疫策策略略中中，仅仅有有免免疫疫检检测而没有退火选择。测而没有退火选择。体系结构n免疫算法免疫算法免疫算法n随机产生初始父代种群随机产生初始父代种群A1，根据先验知识抽取疫苗；根据先验知识抽取疫苗；n若若当当前前群群体体中中包包含含最最佳佳个个体体，则则算算法法停停止止运运行行并并输输出出结果；否则，继续；结果；否则，继续；n对对当当前前第第k代代父父本本种种群群Ak进进行行交交叉叉操操作作，得得到到种种群群Bk；n对对Bk进行变异操作，得到种群进行变异操作，得到种群Ck；n对对Ck进行接种疫苗操作，得到种群进行接种疫苗操作，得到种群Dk；n对对Dk进进行行免免疫疫选选择择操操作作，得得到到新新一一代代父父本本Ak+1，转转至至第二步。第二步。Immune Algorithm-IA免疫算法的收敛性状态转移过程示意图：状态转移过程示意图：定定 理：免疫算法是收敛的。理：免疫算法是收敛的。定定 义义：如果对于任意的初始分布均有如果对于任意的初始分布均有则称算法收敛。则称算法收敛。具体分析待求问题，搜集特征信息。具体分析待求问题，搜集特征信息。免疫疫苗的选取方法通用方法之一以以TSP问问题题为为例例，通通过过具具体体分分析析可可以以得得出出相相邻邻两两两两城城市市之之间间的的最最短短路路径径即即为求解该问题时可以利用的一种疫苗。为求解该问题时可以利用的一种疫苗。TSP问题的描述TSP问问题题是是旅旅行行商商问问题题的的简简称称。即即一一个个商商人人从从某某一一城城市市出出发发，要要遍遍历历所所有有目目标标城城市市，其其中中每每个个城城市市必必须须而而且且只只须须访访问问一一次次。所所要要研研究究的的问问题题是是在在所有可能的路径所有可能的路径中中寻寻找找一一条条路路程程最最短短的的路路线线。该该问问题题是是一一个个典典型型的的NP问问题题，即随着规模的增加，可行解的数目将做指数级增长。即随着规模的增加，可行解的数目将做指数级增长。TSP问题的分析设所有与城市设所有与城市Ai距离最近的城市为距离最近的城市为Aj,进行一次如虚线所示的调整后进行一次如虚线所示的调整后,多数情况下，多数情况下，l3较较aj-1+aj的减少量要大于的减少量要大于l1+l2较较ai的增加量。的增加量。故：故：Begin:while(Conditions=True)统计父代群体，确定最佳个体：统计父代群体，确定最佳个体：;分解最佳个体，抽取免疫基因：分解最佳个体，抽取免疫基因：;执行遗传和免疫算子操作执行遗传和免疫算子操作;end免疫疫苗的选取方法自适应方法之二仿真实验基于IA的TSP求解a.免疫抗体免疫抗体b.最优化路径最优化路径75城市的城市的TSP问题免疫优化仿真示意图问题免疫优化仿真示意图子代适应度值随进化过程子代适应度值随进化过程的变化曲线的变化曲线a 通用遗传算法计算曲线通用遗传算法计算曲线b 免疫算法计算曲线免疫算法计算曲线仿真实验a.免疫疫苗示意图免疫疫苗示意图 b.最优路径示意图最优路径示意图442城市的城市的TSP问题免疫优化仿真示意图问题免疫优化仿真示意图谢 谢！