chapter8人工免疫算法.ppt

免疫进化理论 焦李成 免疫进化理论的研究 研究背景 AIS的研究现状之一 ? 人工免疫网络模型 免疫思想的实现 免疫算子有两种类型： 全免疫 非特异性免疫 目标免疫 特异性免疫 免疫操作的基本过程 ? 首先，对待求求问题进行具体分析，从中提取出 最基本的特征信息； ? 其次，对此特征信息进行处理，以将其转化为求解问题的一种方案； ? 最后，将此方案以适当的形式转化成 免疫算子 以实施具体的操作。 免疫算子 ? 算法中的免疫思想主要是在合理提取疫苗的基础上，通过免疫算子来实现的； ? 免疫算子由 接种疫苗 和 免疫选择 两个操作完成的。 免疫算子 设个体x，给其接种疫苗是指按照先验知识来修改x的某些基因位上的基因或其分量，使所得个体以较大的概率具有更高的适应度。疫苗 是从先验知识中提炼出来的，它所含的信息量及其准确性对算法性能的发挥起着重要的作用。 免疫算子 体系结构 免疫算法 免疫规划 免疫策略 免疫算法 随机产生初始父代种群A1 ，根据先验知识抽取疫苗； 若当前群体中包含最佳个体，则算法停止运行并输出结果；否则，继续； 对当前第k代父本种群Ak进行交叉操作，得到种群Bk； 对Bk进行变异操作，得到种群Ck； 对Ck进行接种疫苗操作，得到种群Dk； 对Dk进行免疫选择操作，得到新一代父本Ak+1，转至第二步。 免疫算法的收敛性 免疫规划 初始化：首先，根据要求确定解的精度；其次，随机产生N个个体，并由此构成初始的父代种群A0； 根据先验知识抽取疫苗H； 计算当前种群Ak的个体适应度，并进行停机条件的判断。若条件满足，则停止运行并输出结果；否则继续； 对当前的父代群体Ak进行变异操作，生成子代群体Bk； 对群体Bk进行接种疫苗操作，得到种群Ck； 对群体Ck进行免疫选择操作，得到新一代父本Ak+1，并转至第三步。 免疫规划的收敛性 免疫策略 根据要求确定解的精度，再根据先验知识抽取疫苗H； 随机产生?个个体作为初始的父本群体； 交叉：产生由父代和子代构成的规模为2?的中间群体； 变异：对每一个个体进行变异将得到一个新的个体； 免疫：首先按照对问题的先验知识修改个体(x,?)的某些分量；然后对群体中注射了疫苗的个体进行检测； 选择：从规模为2?的群体中按适应度的大小取出前?个个体作为新一代父本的群体； 停机条件检测。 免疫策略的收敛性 免疫算子的机理 在免疫选择作用下，若疫苗使抗体适应度得到提高，且高于当前群体的平均适应度，则疫苗所对应的模式将在群体中呈指数级扩散；否则，它将被遏制或呈指数级衰减。 免疫算子的执行算法 Begin: 抽取疫苗： 分析待求问题，搜集特征信息； 依据特征信息估计特定基因位上的模式: ； k = 0 and j = 0； while (Conditions = True) if {PV}=True, then j = j +1； i = 0； for (i≤n) 接种疫苗： ； 免疫检验：if , then ; else ； i = i +1； 退火选择： ； k = k+1； End 免疫疫苗的选取方法 具体分析待求问题，搜集特征信息。 TSP问题的描述 TSP问题是旅行商问题的简称。即一个商人从某一城市出发，要遍历所有目标城市，其中每个城市必须而且只须访问一次。所要研究的问题是在所有可能的路径 TSP问题的分析 免疫疫苗的选取方法 Begin: while (Conditions = True) 统计父代群体，确定最佳个体： ; 分解最佳个体，抽取免疫基因： ; 执行遗传和免疫算子操作; end 免疫疫苗的选取方法 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(Neighbor(