第2卷第5期 智能系统学报 Vol.2№5 2007年10月 CAAI Transactions on Intelligent Systems 0ct.2007 动态多目标免疫优化算法及性能测试研究 钱淑渠2张著洪 (1.贵州大学理学院，贵州贵阳550025：2.贵州安顺学院数学系，贵州安顺561000) 摘要：基于生物免疫系统的自适应学习、免疫记忆抗体多样性及动态平衡维持等功能，提出一种动态多目标免疫 优化算法处理动态多目标优化问题.算法设计中，依据自适应飞邻域及抗体所处位置设计抗体的亲和力，基于P r心to控制的概念，利用分层选择确定参与进化的抗体，经由克隆扩张及自适应高斯变异，提高群体的平均亲和力，利 用免疫记忆动态维持和Average linkage聚类方法，设计环境识别规则和记忆池，借助3种不同类型的动态多目标 测试问题，通过与出众的动态环境优化算法比较，数值实验表明所提出算法解决复杂动态多目标优化问题具有较大 潜力. 关键词：动态多目标优化，时变Pareto面；环境跟踪；自适应（邻域；免疫算法 中图分类号：TP301.6文献标识码：A文章编号：16734785(2007)05006810 Dyna mic multiobjective immune optimization algorithm and performance test QIAN Shurqu'2,ZHAN G Zhuhong (1.College of Science,Guizhou University,Guizhou 550025,China;2.Department of Mathematics,Anshun College,Anshun 561000,China) Abstract:A dynamic multi-objective immune optimization algorithm suitable for dynamic multi-objective optimization problems is proposed based on the functions of adaptive learning,immune memory,antibody diversity and dynamic balance maintenance,etc.In the design of the algorithm,the scheme of antibody af- finity was designed based on the locations of adaptive-neighborhood and antibody;antibodies participating in evolution were selected by Pareto dominance.In order to enhance the average affinity of the population, clonal proliferation and adaptive Gaussian mutation were adopted to evolve excellent antibodies.Further- more,the average linkage method and several functions of immune memory and dynamic balance mainte- nance were used to design environmental recognition rules and the memory pool.The proposed algorithm was compared against several popular multi-objective algorithms by means of three different kinds of dy- namic multi-objective benchmark problems.Simulations show that the algorithm has great potential in sol- ving dynamic multi-objective optimization problems. Keywords:dynamic multi-objective optimization;time-varying Pareto front;environment tracking;adap- tive -neighborhood;immune algorithm 动态多目标优化(dynamic multi-objective opti- 等.尽管大量静态多目标进化算法已相继提出) mization,DMO)是指优化问题的目标函数、定义 其中较为典型的2种进化算法为SPEAII31和NS 域、约束条件中至少有一个随时间而变化的多目标 GAIT,但寻求解决DMO的算法研究甚少).文 优化问题.在工程应用领域，大量此类问题急需解 献[1-2,6-7]报道了有关动态多目标进化算法的 决山，如：交通信号灯控制、机器人控制、故障诊断 研究进展.特别是Marco等在文献[2]中设计了几 种动态多目标测试问题，相应地，提出了一种邻域搜 收稿日期：200612-05. 基金项目：因家自然科学基金资助项目(60565002) 索算法(directiombased method,DBM),从性能测 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 2 卷第 5 期 智 能 系 统 学 报 Vol. 2 №. 5 2007 年 10 月 CAAI Transactions on Intelligent Systems Oct. 2007 动态多目标免疫优化算法及性能测试研究 钱淑渠1 ,2 ,张著洪1 (1. 贵州大学 理学院 ,贵州 贵阳 550025 ; 2. 贵州安顺学院 数学系 ,贵州 安顺 561000) 摘 要 :基于生物免疫系统的自适应学习、免疫记忆、抗体多样性及动态平衡维持等功能 , 提出一种动态多目标免疫 优化算法处理动态多目标优化问题. 算法设计中 , 依据自适应ζ邻域及抗体所处位置设计抗体的亲和力 , 基于 Pa2 reto 控制的概念 ,利用分层选择确定参与进化的抗体 , 经由克隆扩张及自适应高斯变异 ,提高群体的平均亲和力 ,利 用免疫记忆、动态维持和 Average linkage 聚类方法 , 设计环境识别规则和记忆池 , 借助 3 种不同类型的动态多目标 测试问题 ,通过与出众的动态环境优化算法比较 , 数值实验表明所提出算法解决复杂动态多目标优化问题具有较大 潜力. 关键词 :动态多目标优化 ; 时变 Pareto 面 ; 环境跟踪 ; 自适应ζ邻域 ; 免疫算法 中图分类号 : TP301. 6 文献标识码 :A 文章编号 :167324785 (2007) 0520068210 Dynamic multi2objective immune optimization algorithm and performance test QIAN Shu2qu 1 ,2 , ZHAN G Zhu2hong 1 (1. College of Science , Guizhou University , Guizhou 550025 , China ; 2. Department of Mathematics , Anshun College , Anshun 561000 , China) Abstract :A dynamic multi2objective immune optimization algorit hm suitable for dynamic multi2objective optimization problems is proposed based on the f unctions of adaptive learning , immune memory , antibody diversity and dynamic balance maintenance , etc. In t he design of t he algorithm , t he scheme of antibody af2 finity was designed based on t he locations of adaptive2neighborhood and antibody ; antibodies participating in evolution were selected by Pareto dominance. In order to enhance t he average affinity of t he pop ulation , clonal proliferation and adaptive Gaussian mutation were adopted to evolve excellent antibodies. Furt her2 more , t he average linkage method and several f unctions of immune memory and dynamic balance mainte2 nance were used to design environmental recognition rules and t he memory pool. The p roposed algorit hm was compared against several pop ular multi2objective algorit hms by means of three different kinds of dy2 namic multi2objective benchmark problems. Simulations show that t he algorit hm has great potential in sol2 ving dynamic multi2objective optimization problems. Keywords :dynamic multi2objective optimization ; time2varying Pareto front ; environment tracking ; adap2 tive 2neighborhood ; immune algorithm. 收稿日期 :2006212205. 基金项目 :国家自然科学基金资助项目(60565002) . 动态多目标优化(dynamic multi2objective opti2 mization ,DMO) 是指优化问题的目标函数、定义 域、约束条件中至少有一个随时间而变化的多目标 优化问题. 在工程应用领域 , 大量此类问题急需解 决[1 ] , 如 : 交通信号灯控制、机器人控制、故障诊断 等. 尽管大量静态多目标进化算法已相继提出[2 ] , 其中较为典型的 2 种进化算法为 SPEA II [ 3 ] 和 NS2 GAII [4 ] , 但寻求解决 DMO 的算法研究甚少[5 ] . 文 献[1 - 2 , 6 - 7 ]报道了有关动态多目标进化算法的 研究进展. 特别是 Marco 等在文献[ 2 ]中设计了几 种动态多目标测试问题 ,相应地 ,提出了一种邻域搜 索算法 ( direction2based method ,DBM) ,从性能测
第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 ·
·70· 智能系统学报 第2卷 新：外循环的主要作用在于更新记忆池，保存不同 6)经由算术交叉获N·N。个新抗体插入B 环境的统计特征值及产生相似、相同或新环境下的 中，并转入7) 初始抗体群.另外，在此图中，N为群体规模，B为 7)分层选择作用于B,获抗体群C 分层选择率0<B<1),N。为所获非控个体数， 8)计算C中抗体的亲和力，并实施免疫算子： 为第1环境下算法执行的当前时刻，T,表示当前环 ①以a为选择率在C中选取LaNJ个亲和力较 境保持不变的最大允许时间，“e=0”用于识别下 高的抗体构成群体D,其中0<a<B<1; 一环境是否为新环境：当为新环境时，e=0:当为 ②克隆算子V作用于D,获克隆群K: 相似或相同环境时，e=1. ③突变算子作用于K,获突变群E: ④组合B和E,计算抗体的亲和力，选取N个 初始抗体群 较高亲和力抗体构成群体F N 1≤T? 输出结果 9)若<T,则A-F,转3)；若否，存储当前 y 环境的统计特征，更新记忆池，置1=1+1，转10) 非控个体群 更新记忆集 10)实施环境判别规则，判断此环境是否与以前 Y N<BN 算术交叉 的某环境相似，若是，则从记忆池中此环境对应的 记忆集中抽取m(m<S)个记忆细胞，并随机产 分层选择 生N·m2个新抗体构成当前环境的初始群体A;若 计算亲和力 否，则随机生成N个抗体构成初始群体A,转2). 克隆选择、繁殖、突变 评注该算法通过分层选择确保优秀的抗体参 ,<T? 组合 与进化，加速算法的收敛速度.4)通过记忆集来保 存非控个体，使用Average linkage聚类，防止记忆 存储统计特征 史新记忆池 集无限扩大，且有助于使所获非控面的分布较均 匀；5)和6)主要是防止算法进化中参与进化的非控 Y 相似抗体群 非相似抗体样 个体过少，导致算法搜索效果差等现象，其中，6) 是为防止进化初期所获非控个体太少而设计，交叉 方式为：分别在群体B和A中随机抽取一个抗体 图1 DMIOA的流程图 经由算术交叉获新抗体，经N·N。次便获相应数目 Fig.1 Flowchart of DMIOA 新抗体，9)依据算法实际运行的时间，确定该环境是 3算法的描述与设计 否继续进行，此更能体现算法的实时性：同时，使用 存储统计特征模块来保存不同环境的统计特征，便 3.1算法描述 于分析不同环境算法的搜索效果；10)通过判别环 基于以上免疫特征、机理及算法流程图1， 境的相似性，确定初始抗体群的产生方式，目的是 DMIOA可描述为 利用免疫系统的再次应答，加快算法在相似环境的 1)随机产生规模为N的初始抗体群A,置1= 寻优速度」 1,确定选择率a,月 3.2免疫算子模块设计 2)判断t≤T?若是，置”=0及置记忆集 1)分层选择 M,=中，转入3)；否则，输出统计结果 根据群体B中抗体在群体中的受控或被控情 3)确定由A中非控个体构成的群体B,其群体 况，计算各抗体被控的个数，根据抗体的被控个数的 规模记为N. 值由小到大排序所有抗体，被控个数为0的抗体放 4)更新记忆集 在第0层，被控个数为1的放在第1层，如此，然后 ①制B中所有抗体进入M:,并清除M,中受 由低层向高层依次选择round(v)个抗体，便获抗 控个体和相同的个体 体群C,在此，round(x)是不超过x的最大整数 ②若M,的规模大于给定的值S。,则利用Av 2)亲和力 erage linkage法聚类 设A为给定环境t的抗体群，则抗体x∈A的 5)若N:<N,则转6)；若否，转7) 亲和力设计为 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.ne
新; 外循环的主要作用在于更新记忆池 ,保存不同 环境的统计特征值及产生相似、相同或新环境下的 初始抗体群. 另外 , 在此图中 , N 为群体规模 ,β为 分层选择率(0 <β< 1) , Ne 为所获非控个体数 , vt 为第 t 环境下算法执行的当前时刻 , Tt 表示当前环 境保持不变的最大允许时间 ,“e = 0 ?”用于识别下 一环境是否为新环境; 当为新环境时 , e = 0 ; 当为 相似或相同环境时 , e = 1. 图 1 DMIOA 的流程图 Fig. 1 Flowchart of DMIOA 3 算法的描述与设计 3. 1 算法描述 基于以上免疫特征、机理及算法流程图 1 , DMIOA 可描述为 1) 随机产生规模为 N 的初始抗体群 A ,置 t = 1 , 确定选择率α,β. 2) 判断 t ≤T ? 若是 , 置 vt = 0 及置记忆集 Mt = <,转入 3) ; 否则 , 输出统计结果. 3) 确定由 A 中非控个体构成的群体 B , 其群体 规模记为 Ne . 4) 更新记忆集. ①复制 B 中所有抗体进入 M t , 并清除 Mt 中受 控个体和相同的个体. ②若 Mt 的规模大于给定的值 S e , 则利用 Av2 erage linkage 法聚类[11 ] . 5) 若 Ne <βN , 则转 6) ; 若否 , 转 7) . 6) 经由算术交叉获 N - Ne 个新抗体插入 B 中 , 并转入 7) . 7) 分层选择作用于 B ,获抗体群 C. 8) 计算 C中抗体的亲和力 , 并实施免疫算子 : ①以α为选择率在 C 中选取 αN 个亲和力较 高的抗体构成群体 D , 其中 0 <α<β< 1 ; ②克隆算子[11 ]作用于 D ,获克隆群 K; ③突变算子作用于 K,获突变群 E; ④组合 B 和 E , 计算抗体的亲和力 , 选取 N 个 较高亲和力抗体构成群体 F. 9) 若 vt < Tt , 则 A ←F, 转 3) ; 若否 , 存储当前 环境的统计特征 ,更新记忆池 , 置 t = t + 1 , 转 10) . 10) 实施环境判别规则 ,判断此环境是否与以前 的某环境相似 , 若是 , 则从记忆池中此环境对应的 记忆集中抽取 m2 ( m2 < Se ) 个记忆细胞 , 并随机产 生 N - m2 个新抗体构成当前环境的初始群体 A ;若 否 ,则随机生成 N 个抗体构成初始群体 A , 转 2) . 评注 该算法通过分层选择确保优秀的抗体参 与进化 , 加速算法的收敛速度. 4) 通过记忆集来保 存非控个体 , 使用 Average linkage 聚类 , 防止记忆 集无限扩大 , 且有助于使所获非控面的分布较均 匀; 5) 和 6) 主要是防止算法进化中参与进化的非控 个体过少 , 导致算法搜索效果差等现象 , 其中 , 6) 是为防止进化初期所获非控个体太少而设计 ,交叉 方式为 : 分别在群体 B 和 A 中随机抽取一个抗体 经由算术交叉获新抗体 ,经 N - Ne 次便获相应数目 新抗体 ,9) 依据算法实际运行的时间 ,确定该环境是 否继续进行 , 此更能体现算法的实时性;同时 ,使用 存储统计特征模块来保存不同环境的统计特征 , 便 于分析不同环境算法的搜索效果; 10) 通过判别环 境的相似性 ,确定初始抗体群的产生方式 , 目的是 利用免疫系统的再次应答 , 加快算法在相似环境的 寻优速度. 3. 2 免疫算子模块设计 1) 分层选择[4 ] 根据群体 B 中抗体在群体中的受控或被控情 况 ,计算各抗体被控的个数 ,根据抗体的被控个数的 值由小到大排序所有抗体 ,被控个数为 0 的抗体放 在第 0 层 ,被控个数为 1 的放在第 1 层 ,如此 ,然后 由低层向高层依次选择 round (βN) 个抗体 ,便获抗 体群 C,在此 ,round ( x) 是不超过 x 的最大整数. 2) 亲和力 设 A 为给定环境 t 的抗体群 , 则抗体 x ∈A 的 亲和力设计为 · 07 · 智 能 系 统 学 报 第 2 卷
第5期 钱淑渠，等：动态多目标免疫优化算法及性能测试研究 ·71· aff (x.raw(x.+f(x ①算法最终获得的记忆集及记忆细胞的平均 (1) 浓度 式中：raw(x,)=1+ls(x,t 1 一为抗体x在其S ②算法执行中，相邻两代的抗体群间相互的 覆盖率 (邻域内的浓度：S(x,)为该环境下，抗体群A中 6)环境判别规则 抗体x的5()邻域内，所有抗体y(y≠x)构成的集 首先随机生成m个候选解构成集合M={x' 合，即 1函≤w},然后依据下列式子确定环境t是否有 S(x,=y:f(x,)-f(y,‖≤s(), 相似环境： y∈A∧y≠xy, 0 ，1≤n()≤m, n(t) 时fx,-fx,Ⅱ ()= e(t.k) 点，n(0>m mm阳f(x,功·fX,亚刊 x'EM 式中：、为可调参数，m为大于1的正整数， 式中：k为1与1-1之间的正整数：若￡(t,< n()为1环境的当前代数，此设计的目的在于使算 1025则确定满足此条件的第1个k值，并认为环 法在最终所获的非控面有较好的分布：式(1)中右 境t和环境k是相似环境，否则为非相似环境 边的第1项说明若某抗体的邻域内的抗体数较少， 4 性能测试准则 则其亲和力偏高，反之则偏低，此有助于被选中个 体分布均匀；第2项有助于提高算法的搜索性能. 给定算法A与算法B在环境t分别执行G次： 3)亲和突变 S、S分别是此两算法在该环境中第m次执行所 设x为参与突变的抗体，则其突变概率设计为 获非控解集. 1)平均覆盖率.定义映射S,S)一0,1]， 即 R(x)1-ks exp af f (x)-af fma 3 af f max af f min S,S)=∈↓3∈<4 1S1 式中：0<台<I,affmax、affmin分别为抗体群中最 (5 大、最小亲和力.突变方式为多项式突变4 则在环境1下，算法A对算法B的平均覆盖率为 4)更新记忆池 G 由于随环境的变化，各环境所获的最好解之间 C(A,B=人∑p(Sd,s9 G 6 不能比较优劣：相应地，相同、相似或不同抗原所 对应的记忆细胞之间不能比较各自的优劣，这导致 若C(A,B)=1,则在环境1，算法B所获非控解集 记忆池的容量将逐渐增大：为了克服此问题，降低 完全被算法A的覆盖 算法的计算复杂度，记忆池由若干类记忆集构成， 2)平均浓度、平均覆盖.平均浓度D()和平均 具体设计如下： 覆盖H()可分别用于度量算法A所获非控解集的 将环境划分成若干类，每一类由相同或相似环 整体分布状况及覆盖的范围，基于文献[9]的设计， 境构成.？由第1类环境中各环境下算法所获记忆 它们被设计为 细胞构成，特别地，若仅由一种环境下的记忆细 1 胞构成，则表示该环境属于新环境：反之，若？由 D(=1 S (dm-dum)2 GG S-1-1c 多种环境的记忆细胞构成，则这些记忆细胞的各分 量被等价转化为0,11区间上的值，进一步，中 7) 仅保存m2个记忆细胞，若超出此数，则计算各记 H(0=士∑max{I(x.: 忆细胞的浓度)，保存浓度大的m个记忆细胞 G1G1945 x',X∈Sm} (8) 5)统计特征存储 式中： 该模块用于保存算法在每一环境中获得的统计 dam min{llxx ll:xx ES, 特征，存储： 1为，1写司S1 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
af f ( x , t) = raw ( x , t) + k1 ‖f ( x , t) ‖ . (1) 式中 : raw ( x , t) = 1 1 +| S ( x , t) | 为抗体 x 在其ζ ( t) 邻域内的浓度; S ( x , t) 为该环境下 , 抗体群 A 中 抗体 x 的ζ( t) 邻域内 ,所有抗体 y( y ≠x) 构成的集 合 , 即 S ( x , t) = { y : ‖f ( x , t) - f ( y , t) ‖ ≤ζ( t) , y ∈A ∧y ≠x} , ζ( t) = k1 n( t) ,1 ≤n( t) ≤m1 , k2 m1 , n( t) > m1 . (2) 式中 : k1 、k2 为可调参数 , m1 为大于 1 的正整数 , n( t) 为 t 环境的当前代数 , 此设计的目的在于使算 法在最终所获的非控面有较好的分布; 式 (1) 中右 边的第 1 项说明若某抗体的邻域内的抗体数较少 , 则其亲和力偏高 , 反之则偏低 ,此有助于被选中个 体分布均匀; 第 2 项有助于提高算法的搜索性能. 3) 亲和突变 设 x 为参与突变的抗体 , 则其突变概率设计为 R ( x) = 1 - k3 ·exp af f ( x) - af f max af f max - af f min . (3) 式中 :0 < k3 < 1 , af f max 、af f min 分别为抗体群中最 大、最小亲和力. 突变方式为多项式突变[14 ] . 4) 更新记忆池 由于随环境的变化 , 各环境所获的最好解之间 不能比较优劣; 相应地 , 相同、相似或不同抗原所 对应的记忆细胞之间不能比较各自的优劣 , 这导致 记忆池的容量将逐渐增大; 为了克服此问题 , 降低 算法的计算复杂度 , 记忆池由若干类记忆集构成 , 具体设计如下 : 将环境划分成若干类 ,每一类由相同或相似环 境构成. τi 由第 i 类环境中各环境下算法所获记忆 细胞构成 , 特别地 , 若τi 仅由一种环境下的记忆细 胞构成 , 则表示该环境属于新环境; 反之 , 若τi 由 多种环境的记忆细胞构成 , 则这些记忆细胞的各分 量被等价转化为[0 , 1 ]区间上的值 , 进一步 , τi 中 仅保存 m2 个记忆细胞 , 若超出此数 , 则计算各记 忆细胞的浓度[13 ] , 保存浓度大的 m2 个记忆细胞. 5) 统计特征存储 该模块用于保存算法在每一环境中获得的统计 特征 , 存储 : ①算法最终获得的记忆集及记忆细胞的平均 浓度. ②算法执行中 , 相邻两代的抗体群间相互的 覆盖率. 6) 环境判别规则 首先随机生成 m0 个候选解构成集合 M = { x i , 1 ≤i ≤m0 } , 然后依据下列式子确定环境 t 是否有 相似环境 : ε( t , k) = ∑ m0 i =1 ‖f ( x i , t) - f ( x i , k) ‖ m0 max x i ∈M { ‖f ( x i , t) - f ( x i , k) ‖} . (4) 式中 : k 为 1 与 t - 1 之间的正整数; 若ε( t , k) < 10 - 215则确定满足此条件的第 1 个 k 值 , 并认为环 境 t 和环境 k 是相似环境 ,否则为非相似环境. 4 性能测试准则 给定算法 A 与算法 B 在环境 t 分别执行 G 次; S A tm 、S B tm分别是此两算法在该环境中第 m 次执行所 获非控解集. [3 ] 1) 平均覆盖率. 定义映射Φ( S A tm , S B tm ) →[0 ,1 ] , 即 Φ( S A tm , S B tm ) = | { x B ∈S B tm | ϖ x A ∈S A tm :x A < x B } | | S B tm | . (5) 则在环境 t 下 , 算法 A 对算法 B 的平均覆盖率为 C( A , B) = 1 G ∑ G k =1 Φ( S A tk , S B tk ) . (6) 若 C( A , B) = 1 , 则在环境 t , 算法 B 所获非控解集 完全被算法 A 的覆盖. 2) 平均浓度、平均覆盖. 平均浓度 D ( t) 和平均 覆盖 H ( t) 可分别用于度量算法 A 所获非控解集的 整体分布状况及覆盖的范围 ,基于文献[9 ]的设计 , 它们被设计为 D ( t) = 1 G1 ≤∑m ≤G 1 | S A tm | - 1 1 ≤i∑ ≤| S A tm | ( dtm - dtim ) 2 , (7) H ( t) = 1 G 1 ≤∑m ≤G max 1 ≤j , j ≤| S A tm | { ‖( x i - x j ) ‖: x i , x j ∈S A tm } . (8) 式中 : dtim = min i ≠j ,1 ≤j ≤| S A tm | { ‖x i - x j ‖: x i , x j ∈S A tm } , 第 5 期 钱淑渠 ,等 :动态多目标免疫优化算法及性能测试研究 · 17 ·
·72 智能系统学报 第2卷 G(t)sin(0.5t/10) 3)收敛行为 x1=(x)∈[0,11， 设X(n2)为算法A在第t环境第m次执行 xm=(x2,x3,….x0)∈「-1,11 中，第n代所得的记忆集合，则其收敛性可由下式度 量： 表2DBM对各问题在不同环境独立运行 30次所需平均时间 Pa(t)= 9) Table 2 DBM:Average run time for each environment of the given problem with respectively 30 executions /min 式中：6∈Z 环境t 1 2 34 5 67 P(i.m.0=IC()+c() 问题12.82.82.72.72.72.72.7 问题229 2.82.8 2.8 2.82.82.8 式9)表明，若lim_Pa()=0,则算法A在环境1 问题32.83.02.92.92.92.92.9 有很好的收敛性」 5数值实验 该问题的理论Pareto面满足f2=1-1.各 选取参与比较的算法为DBM,DNSGAII-A 算法在7个环境中分别独立执行30次后所获的统 及CSADMO,各算法的初始群体规模均为N=80. 计值及平均覆盖率如表3、4；此3种算法借助式 在给定环境下，指定保存此3种算法及DMIOA所 9),所获收敛行为曲线如图2，但由于DBM是一种 获非控个体的集合的规模均为80，也假定环境总个 邻域搜索算法，其结构的特殊性使得在此不能描述 数为7，即T=7.由于算法在解决给定环境优化问 出其搜索曲线，各算法在各环境中执行一次所获的 题时，其执行时间是评价动态环境优化算法的性能 非控面比较如图3.表3是各算法对各环境独立运 之一I,为此，对DNSGAII-A、CSADMO及 行30次所获非控解集的平均浓度、平均覆盖比较， DMIOA,规定其在每个环境内的执行时间T,=5s, 由此表获知：参与比较的3种算法所获非控解集的 而对于DBM,由于其结构设计的特殊性，指定每次 平均浓度较差，其中DBM最差，DNSGAⅡ-A、 执行的最大迭代数为20000，这要求DBM对每个 CSADMO稍好，而DMIOA所获效果较好；由各 测试问题在每一次执行中至少需要162s(见表2)， 环境所获非控解集平均覆盖获知：DNS GAⅡ-A、 即T.=162s.各算法对每一测试问题的各环境分 CSADMO稍差，DBM及DMIOA较好.表4是各 别独立执行30次，即G=30,获相应的统计特征值 算法对各环境所获平均覆盖率比较，其中X、 及DBM在每个环境的平均执行时间（表2），DBM XDN、XS、XM分别为算法DBM、DNSGAII·-A、 的进化策略中的突变概率为0.35，梯度搜索法中停 CSADMO DMIOA所获非控解集，由此表获知： 机精度ε=0.01：其他算法参数值的选取可参考文 DMIOA与DNSGAII-A在各环境效果较接近，而 献10-11J:对于DMIOA,除了m=10外，其他 CSADMO及DBM效果较差.图2是DNSGAII- 参数如表1. A、CSADMO DMIOA对各环境独立运行30次所 获平均收敛曲线，n是实际时刻算法所对应的代 表1 DMIOA算法参数设置 Table 1 DMIOA's Parameter settings 数，由图2可知，三算法在给定时间内运行的最大代 参数aB 数均有所不同，DMIOA在较少的代数内收敛行为 k1反m 曲线接近0，而其他两算法收敛较慢.图3是各算法 值0.40.70.210.9520 100 在各环境所获非控面的点分布比较；为便于图形直 问题1FDA1PI 观，将目标函数值f2以G=0.21平移，由图获知： minf(x)=(f1(x)f2(x)) DNSGAII-A收敛较好，但其在f1接近于1的点 较难找到，而CSADMO及DBM分布较好，但收敛 s.t.fi(x x..f2 (x)=g(1- 稍差，而DMIOA所获非控面的点分布较均匀，且 与DNSGAIⅡ-A收敛行为曲线相似，此也可由表4 g(m)=1+∑(x:-G()2 获知 1994-2008 China Academie Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
dtm = 1 | S A tm | 1 ≤i∑ ≤| S A tm | dtim . 3) 收敛行为 设 X n tm ( n ≥2) 为算法 A 在第 t 环境第 m 次执行 中,第 n代所得的记忆集合, 则其收敛性可由下式度 量: PGn ( t) = 1 Gl 0 1 ≤∑m ≤G, n+1 -∑l 0 ≤i ≤n P ( i , m , t) . (9) 式中 :l0 ∈Z + , P( i , m , t) = 1 2 [ C( X i tm , X i - 1 tm ) + C( X i - 1 tm , X i tm ) ]. 式(9) 表明 , 若 lim G, n→∞ PGn ( t) = 0 , 则算法 A 在环境 t 有很好的收敛性. 5 数值实验 选取参与比较的算法为 DBM , DNSGA II - A 及 CSADMO , 各算法的初始群体规模均为 N = 80. 在给定环境下 ,指定保存此 3 种算法及 DMIOA 所 获非控个体的集合的规模均为 80 ,也假定环境总个 数为 7 ,即 T = 7. 由于算法在解决给定环境优化问 题时 ,其执行时间是评价动态环境优化算法的性能 之 一[1 ] , 为 此 , 对 DNSGAII - A 、CSADMO 及 DMIOA ,规定其在每个环境内的执行时间 Tt = 5 s, 而对于 DBM , 由于其结构设计的特殊性 ,指定每次 执行的最大迭代数为 20 000 , 这要求 DBM 对每个 测试问题在每一次执行中至少需要 162 s(见表 2) , 即 Tt = 162 s. 各算法对每一测试问题的各环境分 别独立执行 30 次 , 即 G = 30 , 获相应的统计特征值 及 DBM 在每个环境的平均执行时间 (表 2) . DBM 的进化策略中的突变概率为 0135 , 梯度搜索法中停 机精度ε= 0101 ;其他算法参数值的选取可参考文 献[10 - 11 ];对于 DMIOA , 除了 m2 = 10 外 , 其他 参数如表 1. 表 1 DMIOA算法参数设置 Table 1 DMIOA’s Parameter settings 参数 α β k1 k2 k3 m0 m1 值 0. 4 0. 7 0. 2 1 0. 95 20 100 问题 1 FDA1 [2 ] min f ( x) = ( f 1 ( x) , f 2 ( x) ) , s. t. f 1 ( xI) = xi , f 2 ( x) = g (1 - f 1 g ) , g ( xΠ) = 1 + x i∑∈x I ( xi - G( t) ) 2 , G( t) = sin (015πt/ 10) , xI = ( x1 ) ∈[0 ,1 ] , xΠ = ( x2 , x3 , …, x30 ) ∈[ - 1 ,1 ]. 表 2 DBM 对各问题在不同环境独立运行 30 次所需平均时间 Table 2 DBM : Average run time for each environment of the given problem with respectively 30 executions / min 环境 t 1 2 3 4 5 6 7 问题 1 2. 8 2. 8 2. 7 2. 7 2. 7 2. 7 2. 7 问题 2 2. 9 2. 8 2. 8 2. 8 2. 8 2. 8 2. 8 问题 3 2. 8 3. 0 2. 9 2. 9 2. 9 2. 9 2. 9 该问题的理论 Pareto 面满足 f 2 = 1 - f 1 . 各 算法在 7 个环境中分别独立执行 30 次后所获的统 计值及平均覆盖率如表 3、4 ; 此 3 种算法借助式 (9) ,所获收敛行为曲线如图 2 ,但由于 DBM 是一种 邻域搜索算法 ,其结构的特殊性使得在此不能描述 出其搜索曲线 ; 各算法在各环境中执行一次所获的 非控面比较如图 3. 表 3 是各算法对各环境独立运 行 30 次所获非控解集的平均浓度、平均覆盖比较 , 由此表获知 :参与比较的 3 种算法所获非控解集的 平均浓度较差 , 其中 DBM 最差 , DNSGA II - A 、 CSADMO 稍好 , 而 DMIOA 所获效果较好 ; 由各 环境所获非控解集平均覆盖获知 :DNSGA II - A 、 CSADMO 稍差 , DBM 及 DMIOA 较好. 表 4 是各 算法对各环境所获平均覆盖率比较 , 其中 X DB 、 X DN 、X CS 、X DM 分别为算法 DBM、DNSGAII - A 、 CSADMO、DMIOA 所获非控解集 , 由此表获知 : DMIOA 与 DNSGA II - A 在各环境效果较接近 ,而 CSADMO 及 DBM 效果较差. 图 2 是 DNSGAII - A 、CSADMO、DMIOA 对各环境独立运行 30 次所 获平均收敛曲线 , n 是实际时刻算法所对应的代 数 ,由图 2 可知 ,三算法在给定时间内运行的最大代 数均有所不同 ,DMIOA 在较少的代数内收敛行为 曲线接近 0 ,而其他两算法收敛较慢. 图 3 是各算法 在各环境所获非控面的点分布比较 ;为便于图形直 观 , 将目标函数值 f 2 以δt = 0. 2 t 平移 ,由图获知 : DNSGA II - A 收敛较好 ,但其在 f 1 接近于 1 的点 较难找到 ,而 CSADMO 及 DBM 分布较好 ,但收敛 稍差 ,而 DMIOA 所获非控面的点分布较均匀 , 且 与 DNSGA II - A 收敛行为曲线相似 ,此也可由表 4 获知. · 27 · 智 能 系 统 学 报 第 2 卷