第5期 钱淑渠，等：动态多目标免疫优化算法及性能测试研究 。69= 试的角度，获得了该算法对环境的跟踪行为，但由于 衡等特点，它具有学习、记忆、识别等功能，可用于开 DMO是一类极为困难的动态优化问题，加之该算 发免疫算法，实现智能信息处理.所引用的免疫特 法属邻域搜索方法，致使其实时性需要重大改进 征和原理如下： 2006年K.Deb修改了静态的NSGAII,获得适用 )自适应性：自然界中存在的抗原类型远远多 于动态环境多目标问题求解的DNSGAIⅡ-A1,该 于生物体内的抗体种类，因此入侵生物体的抗原具 算法的自适应能力强，是一种很好的动态优化算法 有随机性和不可预测性，但免疫系统会对不同的抗 但如何利用合理的生物机理，设计有效的优化方法 原，通过免疫细胞的增殖和分化，不断地产生新的 解决DMO,仍是一个全新的课题.近来，基于免疫 抗体，最终生成亲和力较高的抗体消灭入侵抗原 机理的静态多目标免疫优化算法己有一些优越的多 2动态平衡：在应答过程中，抗原的对位与抗 目标进化算法的研究成果，，但探讨解决DMO问 体的表位以及抗体之间的表位与对位进行识别与被 题的免疫算法的研究几乎尚未启动.尚荣华等] 识别，抗体不仅识别抗原，同时又识别其他抗体和 基于克隆选择算法，利用非均匀变异抗体间距离等 被其他抗体识别，因此抗体具有识别和被识别的特 方法获得了一种克隆选择动态多目标算法(CSAD 性（二重性）。通过抗体表面的受体，抗体识别抗原， MO),并将其与DBM用于2个测试问题比较其性 抗体与抗体之间相互识别和被识别，并形成了独特 能.尽管如此，DMO免疫算法的研究仍然处于起 型免疫网络：在此网络中，被识别的抗体受到抑 步阶段，如何充分挖掘免疫系统的内在机理，选择 制，识别抗原及其他抗体的抗体得到促进和增殖 合适的免疫学原理提出更有效的算法解决DMO问 这种机制便构成了独特型免疫网络调节。网络调节 题，仍需不断努力.基于此，借鉴免疫系统的自适 能使网络中抗体的总数目获得控制，并调节各种类 应性、多样性及动态平衡维持、免疫记忆等功能，提 型的抗体在免疫系统中的数目，使所有抗体的数目 出一种新的动态多目标免疫优化算法(dynamic 达到总体上平衡。当抗原入侵免疫系统时，这种平 multiobjective immune optimization algorithm, 衡遭到破坏，应答抗原能力强的B细胞进行增殖， DMIOA),并将其与DBM,DNSGAII-A及 并导致免疫应答，待抗原被清除后，依赖于免疫网 CSADMO用于不同类型的测试问题展开比较分 络调节使抗体数目达到新的平衡。 析，数值实验结果说明了本文算法在跟踪速度和执 3)抗体多样性：免疫系统在进化过程中通过细 行效果上呈现出了一定的优越性 胞分裂、分化，抗体的二官能性，可对多种病原体产 1 问题描述 生相应的抗体.抗体的高可变区的超突变及免疫系 统浓度抑制机理，促使抗体库保存多样的抗体 考虑如下动态多目标优化问题(DMOP) 4)免疫记忆：免疫记忆是特异性免疫应答所 min f (x.(=(f(x.v .f2(x.0...fm (x.v). 特有的重要特征.当免疫系统初次遇到抗原时，淋 式中：x=(x1,x2,…,x)∈D为决策向量，DCR 巴细胞需要一定的时间进行调整，免疫应答结束后， 为定义域，：(x,)为与时间有关的子目标函数. 保留该抗原的记忆信息；当免疫系统再次遇到相同 注：本文中时间1∈1,2，，T取离散值，每一个1 或结构相似的抗原时，在联想记忆下，免疫系统提 下的优化问题就是一个环境，为环境总个数 取记忆细胞，应答速度大大提高」 定义1对于给定环境1∈T,称向量x控制向 基于以上所述，抗体动态跟踪抗原、自组织学 量记为：x<y或向量y受控于向量x,如果 习、自适应记忆的动态特性，为设计DMIOA求解 f(x,≤f(y,)∧3k,s.t.fk(x,)<fxy,), DMOP提供了新思路.在此，将问题DMOP视为 1≤i,k≤m」 环境，环境变化意指该问题随时间发生了改变.对 定义2对给定环境t∈T及有限子集XCD, 应于免疫学的术语，抗原视为环境，抗体对应给定 x`∈D,若不存在任何向量y∈X,使得x`<y,则 环境下的候选解，记亿细胞为给定环境下的抗体群 称x为1环境的非控个体.特别，若X三D,则称 中非控个体，抗体和记忆细胞均使用实数编码.在 x`为t环境的Pareto最优解 这些约定下，借助以上涉及的免疫系统特性，获得 DMOA的流程图（图1）.此图由内循环和外循环 2 免疫特征及算法运行机制 2部分构成，通过环境判别规则进行切换：内循环 生物免疫系统具有分布性、自适应性和动态平 解决给定环境下的优化问题，同时对记忆集进行更 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net试的角度 ,获得了该算法对环境的跟踪行为 ,但由于 DMO 是一类极为困难的动态优化问题 ,加之该算 法属邻域搜索方法 ,致使其实时性需要重大改进. 2006 年 K. Deb 修改了静态的 NSGA II ,获得适用 于动态环境多目标问题求解的 DNSGAII - A [ 8 ] ,该 算法的自适应能力强 ,是一种很好的动态优化算法. 但如何利用合理的生物机理 , 设计有效的优化方法 解决 DMO , 仍是一个全新的课题. 近来 , 基于免疫 机理的静态多目标免疫优化算法已有一些优越的多 目标进化算法的研究成果[9 ] , 但探讨解决 DMO 问 题的免疫算法的研究几乎尚未启动. 尚荣华等[ 10 ] 基于克隆选择算法 ,利用非均匀变异、抗体间距离等 方法获得了一种克隆选择动态多目标算法 (CSAD2 MO) ,并将其与 DBM 用于 2 个测试问题比较其性 能. 尽管如此 , DMO 免疫算法的研究仍然处于起 步阶段 , 如何充分挖掘免疫系统的内在机理 , 选择 合适的免疫学原理提出更有效的算法解决 DMO 问 题 , 仍需不断努力. 基于此 , 借鉴免疫系统的自适 应性、多样性及动态平衡维持、免疫记忆等功能 ,提 出一种新的动态多目标免疫优化算法 ( dynamic multiobjective immune optimization algorit hm , DMIOA) , 并 将 其 与 DBM , DNSGA II - A 及 CSADMO 用于不同类型的测试问题展开比较分 析 , 数值实验结果说明了本文算法在跟踪速度和执 行效果上呈现出了一定的优越性. 1 问题描述 考虑如下动态多目标优化问题 (DMOP) min x ∈D ∈R n f ( x , t) = ( f 1 ( x , t) , f 2 ( x , t) , …, f m ( x , t) ) . 式中 : x = ( x1 , x2 , …, x p ) ∈D 为决策向量 , D < R n 为定义域 , f i ( x , t) 为与时间有关的子目标函数. 注 : 本文中时间 t ∈{ 1 ,2 , …, T}取离散值 , 每一个 t 下的优化问题就是一个环境 ,为环境总个数. 定义 1 对于给定环境 t ∈T , 称向量 x 控制向 量 (记为 : x < y) 或向量 y 受控于向量 x , 如果 f i ( x , t) ≤f i ( y , t) ∧ ϖ k ,s. t. f k ( x , t) < f k ( y , t) , 1 ≤i , k ≤m. 定义 2 对给定环境 t ∈T 及有限子集 X < D , x 3 ∈D , 若不存在任何向量 y ∈X , 使得 x 3 < y , 则 称 x 3 为 t 环境的非控个体. 特别 ,若 X ≡D ,则称 x 3 为 t 环境的 Pareto 最优解. 2 免疫特征及算法运行机制 生物免疫系统具有分布性、自适应性和动态平 衡等特点 ,它具有学习、记忆、识别等功能 ,可用于开 发免疫算法 ,实现智能信息处理. 所引用的免疫特 征和原理如下 : 1) 自适应性 : 自然界中存在的抗原类型远远多 于生物体内的抗体种类 ,因此入侵生物体的抗原具 有随机性和不可预测性 ,但免疫系统会对不同的抗 原 , 通过免疫细胞的增殖和分化 ,不断地产生新的 抗体 ,最终生成亲和力较高的抗体消灭入侵抗原. 2) 动态平衡 : 在应答过程中 ,抗原的对位与抗 体的表位以及抗体之间的表位与对位进行识别与被 识别 ,抗体不仅识别抗原 , 同时又识别其他抗体和 被其他抗体识别 , 因此抗体具有识别和被识别的特 性(二重性) 。通过抗体表面的受体 ,抗体识别抗原 , 抗体与抗体之间相互识别和被识别 ,并形成了独特 型免疫网络; 在此网络中 , 被识别的抗体受到抑 制 ,识别抗原及其他抗体的抗体得到促进和增殖 , 这种机制便构成了独特型免疫网络调节。网络调节 能使网络中抗体的总数目获得控制 , 并调节各种类 型的抗体在免疫系统中的数目 , 使所有抗体的数目 达到总体上平衡。当抗原入侵免疫系统时 , 这种平 衡遭到破坏 , 应答抗原能力强的 B 细胞进行增殖 , 并导致免疫应答 , 待抗原被清除后 , 依赖于免疫网 络调节使抗体数目达到新的平衡。 3) 抗体多样性 : 免疫系统在进化过程中通过细 胞分裂、分化 ,抗体的二官能性 , 可对多种病原体产 生相应的抗体. 抗体的高可变区的超突变及免疫系 统浓度抑制机理 ,促使抗体库保存多样的抗体. 4) 免疫记忆 : 免疫记忆是特异性免疫应答所 特有的重要特征. 当免疫系统初次遇到抗原时 ,淋 巴细胞需要一定的时间进行调整;免疫应答结束后 , 保留该抗原的记忆信息; 当免疫系统再次遇到相同 或结构相似的抗原时 , 在联想记忆下 , 免疫系统提 取记忆细胞 , 应答速度大大提高. 基于以上所述 , 抗体动态跟踪抗原、自组织学 习、自适应记忆的动态特性 , 为设计 DMIOA 求解 DMOP 提供了新思路. 在此 , 将问题 DMOP 视为 环境 , 环境变化意指该问题随时间发生了改变. 对 应于免疫学的术语 , 抗原视为环境 , 抗体对应给定 环境下的候选解 , 记忆细胞为给定环境下的抗体群 中非控个体 , 抗体和记忆细胞均使用实数编码. 在 这些约定下 , 借助以上涉及的免疫系统特性 , 获得 DMIOA 的流程图 (图 1) . 此图由内循环和外循环 2 部分构成 , 通过环境判别规则进行切换; 内循环 解决给定环境下的优化问题 , 同时对记忆集进行更 第 5 期 钱淑渠 ,等 :动态多目标免疫优化算法及性能测试研究 · 96 ·