人工免疫算法ppt课件VIP

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