基于免疫优化的单目标多模态期望值规划

杨 凯， 张著洪，2

（1.贵州大学计算机科学与技术学院，贵州贵阳550025；2.贵州大学电子信息学院，贵州贵阳550025）

基于免疫优化的单目标多模态期望值规划

杨 凯1， 张著洪1，2

（1.贵州大学计算机科学与技术学院，贵州贵阳550025；2.贵州大学电子信息学院，贵州贵阳550025）

为了求解未知随机变量分布下单目标多模态期望值规划，通过引入检测候选解是否为局部最优解的随机函数，将该期望值规划问题转化为多目标期望值规划问题，并进一步探寻问题的转化关系，获得在一定条件下有效解是最优解的结论；根据样本平均近似化思想，将多目标规划转化为非恒定样本采样的近似化模型，并基于克隆选择和免疫记忆的机理，通过设计递归非支配分层、样本自适应采样和自适应繁殖与变异方案，引导进化种群往优质个体所在区域转移，提出了求解该近似化模型的免疫优化算法.仿真结果表明：与参与比较的多目标优化算法相比，该算法搜索多个最优解方面有明显优势，搜索效果稳定，噪声抑制能力强；求解低、高维标准测试问题获得最优解的数量分别平均提高了20%和70%.

随机规划；多模态期望值规划；多目标优化；免疫优化；自适应采样

多模态期望值规划（multi-modal expected value programming，MEVP）是一类含随机变量和多个局部最优解的期望值规划.如何在未知随机变量分布下，探讨高效且具有强进化能力的优化算法，寻找噪声环境下局部、全局最优解（简称最优解），是智能优化研究要解决的难题［1-3］.关于一般期望值规划的算法求解研究，主要集中在首先利用神经网络或样本平均近似化处理方法，对优化模型作近似化处理，然后借助已有静态优化方法寻找问题的近似解.例如，文献［4］基于差分进化，获得静态采样下的智能优化算法.样本平均逼近法作为一种近似化处理方法，其采样次数不受维数的影响，但难点是确定合适的样本大小［5-6］.研究表明，自适应采样较适用于处理期望值规划中的随机变量［5］，可有效回避因样本数过大导致算法寻优效率低的问题.另一方面，多模态函数优化是一类具有多个局部最优解的静态优化问题，其作为极为困难的优化对象已有较多进化算法研究成果［7］，主要集中在探讨能规避早熟现象，以及快速发现全局最优解且具有足够多样性和强进化能力的进化算法.特别是将多模态优化转化成两目标优化，然后设计多目标优化算法求解是一种较好的尝试［8-9］.

免疫优化作为人工免疫系统的重要研究分支已取得优于其它主要智能优化算法的众多研究成果［10-12］.例如，文献［10］提出求解静态多模态函数优化的人工免疫网络算法，该算法的突出特点是进化种群中每个抗体均需繁殖，变异后的克隆群的平均亲和力要求不低于当前种群的平均亲和力，以及利用网络抑制清除冗余抗体.文献［5］针对一般期望值规划问题，探讨自适应采样和噪声抑制方案，获得了免疫优化算法.

综上可知，尽管智能优化在期望值规划和静态多模态函数优化方面均已有大量研究，但仍然存在很多问题亟需解决，特别是未见探讨二者结合的多模态期望值规划的研究报道.因此，本文通过引入局部检测随机函数，将MEVP转化为多目标期望值规划，探讨问题转化的理论基础，借助克隆选择和免疫记忆原理，设计具有自适应采样的多目标免疫优化算法（multi-objective immune optimization algorithm，MIOA）.该算法在以下4个方面不同于已有智能优化算法：

（1）通过引入候选解的局部检测随机函数，将问题转化为多目标期望值规划，并证明二者的等价关系；

（2）自适应采样有效抑制了随机变量对寻优质量的影响；

（3）递归非支配分层提高了个体优劣辨别速度；

（4）候选解的方向检测方案增强了群体局部探测能力.

1 问题描述及转化

考虑如下多模态期望值规划问题

式中：D是Rp中有界闭区域；

x为决策向量；

ξ∈Rq为随机向量；

E［·］是期望值算子；

f（x，ξ）关于x是多模态随机函数.

称x*∈D为MEVP的局部最优解，若存在x*的邻域O（x*）⊆D，使得对于任意的x∈O（x*），均有E［f（x*，ξ）］≤E［f（x，ξ）］；若x*在D上使该不等式成立，则称为全局最优解.鉴于f（x，ξ）具有多模态和不确定的特性，在此用随机函数g（x，ξ）作为局部检测函数来检测x在期望值意义下是否为局部最优解，它满足在x的邻域内E［g（x*，ξ）］≥0，且等号成立的充要条件是x*为MEVP的局部最优解.将MEVP转化为如下期望值多目标规划问题（expectedvaluemulti-objective programming，EMP）：

定义1 称x*∈D为EMP的局部有效解，若存在x*的一个邻域O（x*），使得不存在y∈O（x*）满足y支配x*，在此，y支配x*是指

且至少有一个不等式的等号不成立.

以下理论研究中，不妨设MEVP有唯一最优解，即MEVP仅有一个局部最优解且为全局最优解.

定理1x*∈D是MEVP的最优解的充要条件是x*是EMP的有效解.

以上表明，在g（x，ξ）的定义下，问题MEVP与EMP具有相同的解.根据该定义，检测x是否为局部最优解，不仅需要考虑x的邻域O（x）中的所有点，而且需要考虑随机向量ξ的样本大小，这必然会增大检测x是否为最优解的计算量.在实际应用中，仅需选择x的邻域中部分点进行比较即可.为此，给定随机向量的样本ξ，定义

式中：μj（ξ）＝min｛f（x－δ，j，ξ），f（x＋δ，j，ξ）｝，x＋δ，j和x－δ，j分别为x中第j个分量xj变为xj＋δ和xjδ，而其它分量不变时获得的两个向量；δ为预先设定的邻域阈值.

利用式（2），通过Ij（x，ξ）检测f（x，ξ）沿着x的第j个方向的两个点是否比x更优越.因此，用g（x，ξ）检测中心为x、半径为δ的超球面上2p个点中是否有优于x的点.可获得如下结论：

定理2若x*∈D是MEVP的最优解，且满足对于∀x∈D和∀ξ∈Rq，均有f（x*，ξ）≤f（x，ξ），则x*∈D是EMP的有效解且满足E［g（x*，ξ）］＝0.

证明设x*∈D是MEVP的最优解，则对于∀x∈D，有E［f（x*，ξ）］≤E［f（x，ξ）］.若x*不是EMP的有效解，则存在¯x∈D，使得¯x支配x*，即，

进一步，由式（2）知，

又对于∀x∈D，有f（x*，ξ）≤f（x，ξ），所以得

此导致矛盾，故结论成立.

2 样本平均近似化

假定ξ1，ξ2，…，ξm为随机向量ξ的样本，m为样本大小，则由大数定律知，当m充分大后，下列多目标规划问题（sample approximation multiobjective programming，SMP），

的有效解必为EMP的有效解.为了克服计算代价过大和寻优速度慢的困难，在每个候选解x处指派随机向量的样本大小为n（x），于是SMP被修改为为自适应采样多目标规划问题（adaptive sampling multi-objective programming，AMP），

式中：

显然，若对于∀x∈D，n（x）均等于同一常数，则AMP即为SMP.以下设计具有自适应采样特性的免疫优化算法求解AMP，使得最终获得的有效解能尽可能逼近MEVP的最优解.

3 算法原理与描述

3.1 算法原理

MIOA由递归非支配分层、群体样本分配、记忆集更新、自适应繁殖与变异、群体更新构成，其算法流程如图1所示.

图1中，n表示迭代次数，M表示记忆集，Gmax表示最大迭代，递归非支配分层是基于递归和群体随机划分思想，将群体划分为若干互不支配的子群；群体样本分配借助与迭代数有关的群体样本规模和各抗体的重要程度，确定各抗体的样本大小，目的在于提高估算优质抗体的准确率；记忆集更新将当前群体中优质抗体复制入记忆集，并清除受支配、相同或相似的记忆细胞；自适应繁殖依据群体中各抗体的重要程度，按照特定的规则确定抗体的繁殖规模，重要程度越高的抗体将得到较大的克隆规模；克隆变异依据与抗体重要程度有关的变异概率执行均匀变异；抗体群更新借助已变异的克隆群，对当前群体中的抗体进行取代或有指导性转变，产生下一代群体.

图1 MIOA流程图Fig.1 Flowchart of MIOA

3.2 算法描述

对应于以上AMP，抗体由p个长度均为l的二进制基因块构成，每个基因块对应AMP中决策向量的一个分量，记忆细胞视为算法进化到当前代获得的较好抗体，抗原被视为问题AMP本身.抗体x的目标向量值为给定时刻n的抗体群

式中：N为群体规模.

假定xi在该群体中的优先等级为r（xi），1≤i≤N，r（xi）越小，xi越好.该群体在时刻n的采样大小为

式中：m0为给定的正整数.

在抗体x处的随机变量的样本大小为

式中：m（x）＝rmax－r（x）＋1，

式（7）用于确保群体A中不同等级的抗体获得不同数目的样本，鼓励优质抗体参与进化，较差抗体逐渐被淘汰.因此，抗体x的等级r（x）越小，则获样本越多；反之，则越少.式（6）和（7）构成群体A的样本分配方案.递归的思想最初由文献［13］将其引入到群体中来寻找一个子群，使得该子群中任何个体均不受群体中任何个体支配.在此基础上，本文通过引入随机抽取的思想，将群体A划分为若干子集（此方法简记为递归非支配分层），并对A的抗体确定优先级，等级越低的抗体，其重要程度越高.假定A中各抗体的目标值已确定，首先在A中随机选择一个抗体x，将A＼｛x｝分为被x支配的抗体构成的群体A1和不被x支配的抗体构成的群体，获得有序集合序列A1，｛x｝，；然后，分别对A1，采用同样方式进行划分，如此继续，最终获得有序的抗体集合序列.

依据此序列，抗体的优先等级确定规则是，若抗体x处于此序列中最后位置或不被其后面的所有抗体支配，则记其等级为1；否则，排在抗体x后面且支配该抗体的所有抗体中，距离此抗体最近的抗体的等级加1后定义为抗体x的等级.基于此设计和图1，MIOA的具体描述如下：

步骤1输入：种群规模N，抗体的各基因块长度l，初始采样数m0，局部检测阈值δ，记忆集规模Mmax，抑制半径σth，最大迭代次数Gmax.

步骤2置迭代数n＝0，记忆集M＝Ø.

步骤3随机生成N个采样次数均为m0的抗体构成初始种群An＝｛x1，x2，…，xN｝，计算各抗体的目标值

步骤4对An实施递归非支配分层，确定各抗体的优先等级r（xi），1≤i≤N.

步骤5依据式（7）确定An中各抗体的样本大小，重新计算各抗体的目标值1≤i≤N；执行抗体方向检测，即对于给定抗体x∈An，若沿着x的第k基因块对应的分量方向xk，的偏差值是抗体x沿着各方向获得的偏差值中的最大值，不妨设沿着x到xk＋δ的偏差最大，则记x的最大变化方向为Dk（x）.

步骤6对An再次实施递归非支配分层，确定各抗体的优先等级r（x），x∈An.

步骤7复制An中等级为1的抗体作为记忆细胞加入M中，清除受支配的记忆细胞；若则以σth为抑制半径，清除M中相似的抗体.

步骤8An中各抗体进行繁殖，即x繁殖mx个克隆构成克隆群Bn（x），其中

式中：rmax为所有抗体的等级中的最高等级.

步骤9对每个克隆子群，Bn（x）中的克隆依据其变异概率px实施均匀变异，即该抗体的每一基因按概率进行变异，

获群体Cn（x），每个变异后的克隆被指派样本大小为m0，计算Cn（x）中各克隆的目标值

步骤10执行群体更新：对于每个克隆群，首先找到Cn（x）中使在此子群中取最小值的所有克隆，这些克隆构成群体在 E（x）中取最小的克隆；若或者，则An中x被y取代；否则，x沿着最大变化方向Dk（x）的抗体取代x；如此继续，对An中每个抗体更新后，获得新群体An＋1.

步骤11若n＜Gmax，则n←n＋1，转步骤4；否则，转下一步.

步骤12输出：M中满足的所有记忆细胞.

4 计算复杂度与评价准则

由算法描述可知，MIOA的计算复杂度由步骤4～5、步骤7及步骤9～10确定.在最坏情形下，步骤4、步骤5和步骤7的计算复杂度依次为O（Nlb N）、O（Np＋Mn）和O（（N＋Mmax）2）；通常m0取较小值，所以，步骤9的计算复杂度为O（Np）；另外，随着n的增大，An中的抗体将互不支配，于是步骤10的计算复杂度为O（N）.故MIOA在最坏情形的复杂度为

特别当Mmax≪N时，

Oc＝O（N（N＋p＋lb（1＋n／10）））.

假定某算法求解MEVP获的最好解集为A，理论最优解集为A*.给出如下解集平均逼近度准则：

式中：d（x，A）为x到集合A的距离；

D（A，A*）为A中所有成员逼近局部或全局最优解的程度；

D（A*，A）度量A*逼近A的程度.

5 数值实验与分析

选择5种可求解期望值规划的智能优化算法，在CPU／3.3 GHZ、RMB／4 GB的PC机和VC＋＋6.0环境下进行比较分析，即3种单目标优化算法（PSO、DE［4］、CPSO［6］）和两种多目标算法（NSGA-Ⅱ［14］、PDMIOA［15］）.PSO、DE和CPSO求解MEVP的样本平均近似化模型；NSGA-II和PDMIOA求解SMP；本文算法求解AMP.各算法对每个测试问题分别独立运行30次，且设定群体规模N均为80，终止准则指定为个体的总评价次数.

具体设置描述如下：参与比较的算法的单个个体的采样大小均指定为300；DE和CPSO的其他参数设置与文献［4，6］相同；NSGA-Ⅱ的交叉概率为0.6，变异概率为0.06；PDMIOA的变异概率为0.2，生命期为3，记忆集规模Mmax为200；设MIOA的初始采样数m0为50，局部检测阈值δ为0.05，记忆集规模Mmax为200，抑制半径σth为0.05.

问题1 MMP（p）

式中：0≤xi≤1，1≤i≤p.

问题1是通过修改文献［8］的测试函数为随机函数获得的，其中，ξ为随机变量，ki为给定常数.该问题在静态情形下，当ki取特定值时，其所有最优解已有报道［8］，因此，本实验中假定ξ是服从方差为σ正态分布的随机变量，即ξ～N（0，σ2），此有助于检测算法是否获得最优解.在此，仅考虑维数取p＝2和8的情形，相应的优化问题记为MMP（2）和MMP（8）.

以上每种算法求解这两问题的总评价次数分别为2.4×104和2.4×106.MMP（2）有12个解，其全局最优解的理论目标值为0.290 8；MMP（8）有48个解，其全局最优解理论目标值为2.768 2.取σ＝1，结合式（10）和（11），得到的统计结果见表1.

表1第3、4列表明，当以上算法求解MMP（2）时，MIOA始终能获所有最优解，其它算法仅能获得少量的最优解；当求解MMP（8）时，MIOA平均每次能获得约45个最优解，获所有最优解的次数占3.33%，而其它算法每次独立运行均不能获得所有最优解，特别是因算法设计不同，PSO、DE和CPSO每次仅能获得1个最优解.

表1第7、10列表明，MIOA获得的解集质量最好，它每次获得的解集与理论上的最优解集非常接近，NSGA-Ⅱ和PDMIOA获得的解集质量次之，其它算法获得的解质量较差.这说明将多模态期望值优化问题转化成多目标问题求解，有利于求解全局最优解.

由表1第8、11列可知，MIOA搜索效果较为稳定，PDMIOA次之；因PSO、DE和CPSO在每次运行中仅获1个最优解，而求解的问题包含多个最优解，所以它们获得的D（A*，A）值较大，得到D（A，A*）的标准差为0.

表1中最后1列表明，MIOA的执行效率比NSGA-Ⅱ和PDMIOA的效率均高，这说明自适应采样和递归非支配分层能极大提高MIOA的执行效率，而固定采样和常规的非支配分层方法会导致算法搜索效率低；另一方面，PSO、DE和CPSO作为单目标优化算法，其设计模块比多目标优化算法的要简单，因此效率较高是自然的，但在搜索多个解方面要比多目标优化算法差.

表1 逼近程度统计结果比较Tab.1 Statistical comparison of approximation degrees

问题2硬盘随机控制系统参数辨识［5］磁头臂控制系统的数学模型如下：

式中：uc为参考信号；

y为输出信号；

Nd服从正态分布N（0，σ2）；

a、b、Kv、K、J为待定参数.

取采样步数为L，采样周期为T，将系统（式（12））离散化可得

式中：yd为参考输出，

θ为决策向量，

θ＝（a，b，Kv，K，J）；

ξ为随机向量，

ξ＝（ξ1，ξ2，…，ξL），ξi与Nd具有相同的分布.

设置a，b∈［0.1，10］，Kv，K∈［－10，10］，J∈［0.01，2］，

各算法的终止评价次数均设为2.4×104.类似于问题1的实验，各算法独立运行30次后，获得的统计结果见表2.

由表2可知，NSGA-Ⅱ和PDMIOA获得的目标函数值的均值和标准差均较大，说明这两种算法的解质量已受到噪声的严重干扰，搜索效果不稳定；PSO、DE和CPSO的目标均值和标准差比NSGA-Ⅱ和PDMIOA均较小，它们的搜索效果比后两种多目标优化算法更为稳定；MIOA获得的目标值的均值和标准差均最小；因此，获得的效果最好且最稳定.

表2 解的目标值统计结果比较Tab.2 Comparison of statistical results for objective values of solutions acquired

6 结束语

通过引入局部检测随机函数，将求解问题转化为多目标期望值规划，并根据向量支配的概念，获得一定的理论结果.在此基础上，基于克隆选择原理的简化运行机制，设计了多目标免疫优化算法.为克服随机变量和群体中抗体的比较影响算法搜索效率的现象，设计递归非支配分层、样本自适应采样方案和自适应繁殖与变异方案，有引导性地使进化群体沿着优质抗体所在区域转移.实验结果表明，该算法求解理论测试问题时，能获得满意效果，且解的质量基本不受随机因素的干扰；在求解应用测试问题时，能获得最佳参数值.

［1］ JIN Y，BRANKEJ.Evolutionaryoptimizationin uncertain environments-a survey［J］.IEEE Transactions on Evolutionary Computation，2005，9（3）：303-317.

［2］ LIUB.Theoryandpracticeofuncertain programming［M］.Berlin：Springer，2009：25-53.

［3］ SHAPIRO A，DENTCHEVA D，RUSZCZYNSKI A.Lectures onstochasticprogramming：modelingand theory［M］.Philadelphia：SIAM，2009：157-195.

［4］ 孙滢，高岳林.一种求解随机期望值模型的改进差分进化算法［J］.微电子学与计算机，2012，29（4）：23-25.SUN Ying，GAO Yuelin.An improved differential evolutionalgorithmofstochasticexpectedvalue models［J］.Microelectronics＆Computer，2012，29（4）：23-25.

［5］ ZHANG Z H，TU X.Immune algorithm with adaptive sampling in noisy environments and its application to stochastic optimization problems［J］.IEEE Computational Intelligence Magazine，2007，2（4）：29-40.

［6］ MENDEL E，KROHLING R A，CAMPOS M.Swarm algorithmswithchaoticjumpsappliedtonoisy optimization problems［J］.Information Sciences，2011，181（20）：4494-4514.

［7］ DAS S，MAITY S，QU B Y，et al.Real-parameter evolutionary multimodal optimization：a survey of the state-of-the-art［J］.Swarm and Evolutionary Computation，2011，1（2）：71-88.

［8］ DEB K，SAHA A.Finding multiple solutions for multimodal optimization problems using a multi-objective evolutionary approach［C］∥Proceedings of the 12th AnnualConferenceonGeneticandEvolutionary Computation.New York：ACM，2010：447-454.

［9］ YAO J，KHARMA N，GROGONO P.Bi-objective multipopulationgeneticalgorithmformultimodal functionoptimization［J］.IEEETransactionson Evolutionary Computation，2010，14（1）：80-102.

［10］ TIMMIS J，EDMONDS C.A comment on opt-ainet：an immune network algorithm for optimization［C］∥Genetic and Evolutionary Computation-GECCO 2004.Berlin：Springer，2004：308-317.

［11］ DASGUPTA D，YU S，NINO F.Recent advances in artificial immune systems：models and applications［J］.Applied Soft Computing，2011，11（2）：1574-1587.

［12］ CHANG W W，YEH W C，HUANG P C.A hybrid immune-estimation distribution of algorithm for mining thyroidglanddata［J］.ExpertSystemswith Applications，2010，37（3）：2066-2071.

［13］ ZHENG J H，LING C，SHI Z，et al.A multi-objective genetic algorithm based on quick sort［C］∥Advances in Artificial Intelligence.Berlin：Springer，2004：175-186.

［14］ DEB K，PRATAP A，AGARWAL S，et al.A fast and elitist multiobjective genetic algorithm：NSGA-Ⅱ［J］.IEEETransactionsonEvolutionaryComputation，2002，6（2）：182-197.

［15］ ZHANG Z H，TU X.Probabilistic dominance based multi-objective immune optimization algorithm in noisy environments［J］.JournalofComputationaland Theoretical Nanoscience，2007，4（7／8）：1380-1387.

（中文编辑：秦萍玲 英文编辑：兰俊思）

Single-Objective Multi-modal Expected Value Programming Based on Immune Optimization

YANG Kai1， ZHANG Zhuhong1，2
（1.College of Computer Science and Technology，Guizhou University，Guiyang 550025，China；2.College of Electronics and Information，Guizhou University，Guiyang 550025，China）

To solve the problem of single-objective multi-modal expected value programming with unknown noisy distribution，a multi-objective immune optimization algorithm based on immune response principles was proposed.By means of a random function used for checking whether a candidate solution was a locally optimal solution，the expected value problem was converted into a multi-objective expected value programming problem.Moreover，some relations between the original problem and the transformed problem were studied，and a conclusion that an efficient solution must be an optimal solution under certain conditions was developed.Relying upon the idea of sample average approximation，the multi-objective programming was further transformed into an approximate model with variable sampling sizes.Based on the metaphors of clonal selection and immune memory，one such optimization approach was obtained to deal with the approximation model.It searched high-quality individuals toward some regions which the optimal solutions existed，depending on several main modules：recursive non-dominated sorting，adaptive sampling，adaptive proliferation，and adaptive mutation.By comparison with the multi-objective optimization algorithms，the simulation results show that the proposed algorithm with strong noise suppression can achieve averagely about a seventy percent increase in the number of optimal solutions found for the high-dimensional benchmark problem and atwenty percent increase for the low-dimensional benchmark problem；it can gain the stable search effect and has the prominent advantage in solving multiple optimal solutions.

stochastic programming；multi-modal expected value programming；multi-objective optimization；immune optimization；adaptive sampling

TP301.6

：A

0258-2724（2014）06-1061-07

10.3969／j.issn.0258-2724.2014.06.018

2013-10-12

国家自然科学基金资助项目（61065010）；教育部博士点基金资助项目（20125201110003）

杨凯（1975－），男，博士研究生，研究方向为免疫优化理论与应用，E-mail：csc.kyang＠gzu.edu.cn

张著洪（1966－），男，教授，博士，博士生导师，研究方向为控制理论与计算智能，E-mail：sci.zhzhang＠gzu.edu.cn

杨凯，张著洪.基于免疫优化的单目标多模态期望值规划［J］.西南交通大学学报，2014，49（6）：1061-1067.