求解多目标概率优化问题的免疫优化算法

张仁崇　杨坤

【摘 要】探讨求解随机变量分布特征信息未知情形下多目标概率优化问题的免疫优化算法。在算法设计中，基于免疫理论的运行机理，借助快速非支配排序法，将进化种群分割为多个类型子群;利用模拟二进制交叉加强各子群间的信息交流;采用多项式变异和均匀变异展开全局探索和局部开发;设计样本采样方案使个体动态获取样本大小。比较性的数值实验表明，所提算法的搜索效果、运行效率等具有明显优势，且对求解复杂多目标概率优化具有一定应用潜力。

【关键词】多目标概率优化;免疫优化;动态采样

中图分类号：TP301.6 文献标识码： A 文章编号： 2095-2457（2019）16-0008-003

DOI：10.19694/j.cnki.issn2095-2457.2019.16.003

Immune Optimization Algorithm for Solving Multi-objective Probabilistic Optimization Problems

ZHANG Ren-chong YANG Kun

（Computer and Information Engineering College，Guizhou University of Commerce，

Guiyang Guizhou 551400，China）

【Abstract】The immune optimization algorithm for multi-objective probabilistic optimization problem with unknown distribution characteristic information of random variables is proposed. In the algorithm design， based on the operation mechanism of immune theory，the evolutionary population is divided into several sub-populations by means of fast nondominated sorting approach;information exchange among sub-populations is strengthened by simulated binary crossover; global exploration and local development are carried out by using polynomial mutation and uniform mutation;and sample sampling scheme is designed to dynamically acquire the sample size. The comparative numerical experiments show that the proposed algorithm has obvious advantages in search effect and operation efficiency， and has certain application potential for solving complex multi-objective probabilistic optimization.

【Key words】Multi-objective probabilistic optimization;Immune optimization;Immune theory;Dynamic sampling

多目标机会约束规划是多个性能指标相互冲突的随机规划问题，依据目标函数表现的形式可分为，以期望值函数为目标函数的多目标E-模型，以及目标函数为概率约束函数的多目标P-模型。大量实际工程优化问题均可经由多目标P-模型加以描述和解决，例如，水资源调度[1-2]、空降作战[3]、电网[4]、动力配煤规划、证券投资、项目管理以及医疗管理等问题[5-6]。当随机变量（简称噪声）的概率分布信息已知时，少量特殊的多目标P-模型能经过复杂变换化为确定性多目标优化模型，进而采用静态优化方法求解，但此类方法通常是难以实现。当随机变量的分布函数极为复杂或分布特征未知时，模型很难转化为确定性优化模型;针对此种情形，多目标P-模型的目标函数的估计值与随机变量的样本大小有关，因此，探讨搜索速度快、解质量高、极具应用潜力的智能优化方法是多目标P-模型求解的关键。

然而，从智能优化的角度研究求解多目标P-模型的研究成果未见报道。但针对特定领域的可描述为多目标P-模型的工程优化问题的研究已有部分成果，主要是在随机变量的样本大小固定（即静态采样）的情形下，采用单目标、多目标遗传算法进行有效求解，但由于运行效率低、計算资源开销大，致使其尚不能满足工程领域的需求，较难被广泛推广。为此，本文针对无先验噪声分布信息的多目标P-模型，借助免疫应答原理，尝试研究求解此类模型的多目标免疫优化算法（MOIOA：Multi-Objective Immune Optimization Algorithm）。

1 问题描述

考虑如下多目标概率优化问题[7]（多目标P-模型）：

在此，x为决策向量，D∈Rp为有界闭区域，ξ∈Rq为分布信息未知的随机向量，Pr{.}为概率算子，αi∈[0，1]是置信水平，fi（x，ξ）关于x的非线性随机目标函数。在点x处，当ξ的样本大小确定后，借助Monte Carlo 随机模拟确定fi（x）的估计值[7]。引入候选解的支配概念及Pareto最优解的概念[8]：

定义1对于任意候选解x，y∈D称x支配y（即x？刍y），如果

定义2 候选解x*∈D是问题（多目标P-模型）的Pareto最优解，若在D中不存在候选解x使得x？刍y。

2 算法描述

免疫应答原理[9-10]描述识别抗原能力强的免疫细胞被选择参与应答，抑制或消灭抗原受体，以至于清除入侵的抗原的过程。借助免疫应答原理，设计免疫优化算法求解多目标P-模型。为便于算法描述，将此问题本身视为抗原，候选解被视为B细胞，MOIOA可描述如下：

步1输入参数：群体规模N，最大迭代数Gmax，初始样本大小m和M，记忆集合规模N0，募集新成员比例λ;

步2置n←1，G=？覫， 随机产生规模为N的初始B细胞群A={x1，x2，…，xN};依据m、M及式（2）， 估计A中各B细胞x的目标向量值

步3采用快速非支配排序法，将种群A排序为d个不同支配等级，相对应获得d个子群B1，B2，...，Bd;其中，B1由A的所有经验非支配B细胞构成;

步4B1的B细胞繁殖3个克隆，B2的B细胞繁殖2个克隆;Bi中B细胞的变异概率pi如下：

步5G的经验非支配B细胞指导B1中克隆实施模拟二进制交叉（SBX），Bi-1的B細胞指导Bi中B细胞（或克隆）实施SBX，i=2，…，d;经SBX后，B1和B2中B细胞的克隆实施多项式变异，变异分布指数取ηmlg（1+10n/Gmax）+1，B3，…，Bd的B细胞实施均匀变异，获得交叉、变异后的群体B*;

步6依据步2，初步估计B*中B细胞的目标向量值;借助定义1，将B*划分为经验非支配子群C1和经验支配子群C2;将C1与B1的B细胞组合构成群体C;步7依据m和如下式：

将式（2）中M用Mn取代，重新估计C中B细胞的目标向量值;

步8借助定义1，将群体C分割为经验非支配子群D1和经验支配子群D2;

步9清除记忆集合G中与D1相同的个体后，加入D1的B细胞;若|G|>N0，保留N0个优质B细胞;

步10将G的经验非支配B细胞构成E，若|E|≥（1-λ）N，则基于拥挤距离采用轮盘选择法随机选取E中（1-λ）N个相异的B细胞与λN个随机生成的B细胞组合成规模为N的新群体A;若|E|<（1-λ）N，E中B细胞、N-|E|个随机生成的B细胞组合成规模为N的新群体A;此外，个体的拥挤距离越大，被选择进入下一代群体的概率也越大;

步11若满足终止条件，则结束，输出结果;否则，置n←n+1，转步3。

3 数值实验

在Windows 7系统配置为CPU/2.53 GHz、RAM/4.00GB的Visual C++平台上进行数值实验。将MOIOA与AgMOPSO[11]、MOEA/DD[12]、CMIGA[13]、NNIA[14]和NSGA-II[15]进行性能比较。算法终止准则均设置为进化代数是300，比较算法的个体样本大小设置为300[16]。为使得算法获得的解集的目标向量值逼近真实值，各算法所获解集均需重新估计目标向量值，样本大小为104。

参与比较算法的参数设置如表1：群体规模N，克隆规模NC，交叉概率pc，变异概率pm，SBX分布指数ηc，多项式变异分布指数ηm，步长参数F2，权重向量的领域集规模T，惩罚参数PBI，选择概率δ，飞行速度惯性权重w，基因片段池规模nseg，基因片段长度lseg，转换概率ptra。经调试后，MOIOA的参数设置为N=10，m=2，M=10，nm=23，λ=0.1。采用记忆集规模为50保存各算法所获结果。此外，MOIOA算法执行多项式变异参考文献[17]。

测试问题[15]：

式中，α为置信水平，N（.，.）为正态分布。该测试问题是经标准函数KUR扩展获得，目标函数具有多模态特性，且目标函数含有噪声，致使问题求解非常困难。在置信水平α=0.1、0.9下，各算法对测试问题独立运行100次获得的统计结果和平均运行时间如表1所示。注：表中ACR（.，.）、CS、CS分别表示平均覆盖率、平均覆盖范围、平均覆盖宽度[6]，PN和AR分别表示非支配解集规模均值和平均执行时间。

经由表2的CR（.，.）值可知，在置信水平α=0.1下，CMIGA平均覆盖率最高，MOIOA次之且略低于CMIGA，MOIOA高于NNIA，AgMOPSO和NSGA-II相近且高于MOEA/DD;在置信水平α=0.9下，CMIGA平均覆盖率最高，MOIOA和NNIA相近且稍低于CMIGA，MOEA/DD和AgMOPSO较低但略高于NSGA-II;以上分析表明，算法CMIGA所获解质量最好，且略优于MOIOA和NNIA，AgMOPSO、MOEA/DD和NSGA-II的解质量相对较低。

经由CD、CS的平均值、均方差可知，各算法所获非支配解的覆盖范围、覆盖宽度相近且较低，表明所有算法所获解的分布情况较好且相贴近。进一步，由PN的平均值得知，每种算法所获非支配解的数量较多，其中AgMOPSO稍低于其他算法。此外，由表中AR值获知，MOIOA的运行效率最高，是AgMOPSO的5.53倍、MOEA/DD的4.37倍、CMIGA的4.46倍、NNIA 的3.09倍、NSGA-II的2.30倍。

以上综合分析表明，MOIOA与比较算法均能有效求解具有多模态特性的多目标P-模型，所获非支配解集的分布性较好、解质量较高，但MOIOA运算速度最快，是比较算法的2.3倍以上。

4 结论

鉴于多目标P-模型频繁出现于经济、军工、水资源、工程等领域，已受到高度关注。本文从免疫应答机理出发，尝试性探讨求解多目标概率优化问题的免疫优化算法。算法设计中，设计样本分配方案使个体动态获取样本大小，利用快速非支配排序法分割进化种群为多个不同类型子群，采用SBX加强各子群间个体信息交流，设计动态变异概率、变异指数动态变化的多项式变异指导个体进化，确保进化种群具有全局搜索和局部开发能力。该算法运行初期，个体样本规模小、运行速度快、搜索范围宽;随着算法运行，个体样本规模增大，局部开发能力增强，优质非支配解逐渐突显。比较性的数值实验表明，相比较于其他算法，MOIOA的搜索效果和运行效率均有明显优势，是一种具有竞争力的优化方法。此外，算法进化模块、噪声抑制效果以及样本分配方案做下一步研究。

【参考文献】

[1]李晓娜.不确定环境下城市需水量预测及多水源联合供水调度研究[D].河北工程大学，2018.

[2]纪昌明，李克飞，张验科，等.基于机会约束的水库调度随机多目标决策模型[J].电力系统保护与控制，2012（19）：36-40.

[3]张国新，王瑜，沈田双.空降地面作战突破点决策模型[J].火力與指揮控制，2010，35（11）：54-57.

[4]谢仕炜，胡志坚，宁月.考虑最优负荷削减方向的电网多目标分层随机机会约束规划[J].电力自动化设备，2017，37（8）：35-42.

[5]ZHANG Z， WANG L， LONG F. Immune optimization approach solving multi-objective chance-constrained programming[J].Evolving Systems，2013，6（1）：41-53.

[6]YANG K， ZHANG Z， LU J. Adaptive racing ranking-based immune optimization approach solving multi-objective expected value programming[J]. Soft Computing，2017：1-20.

[7]LIU B D. Theory and Practice of Uncertain Programming[M]. 2nd ed. Berlin： Springer-Varlag，2009.

[8]ZHANG Z，TU X.Probabilistic dominance-based multi-objective immune optimization algorithm in noisy environments[J].Journal of Computational and Theoretical Nanoscience，2007，4（7）：1380-1387.

[9]于善謙，王洪海，朱乃硕，等.免疫学导论[M].北京：高等教育出版社，2006.

[10]黄席樾，张著洪，胡小兵，等.现代智能算法理论及应用[M].北京：科学出版社，2005.

[11]ZHU Q， LIN Q， CHEN W， et al. An external archive-guided multiobjective particle swarm optimization algorithm[J]. IEEE Transactions on Cybernetics，2017，47（9）：2794-2808.

[12]LI K， DEB K， ZHANG Q， et al. An evolutionary many-objective optimization algorithm based on dominance and decomposition[J].IEEE Transactions on Evolutionary Computation， 2015，19（5）：694-716.

[13]QIAN S， YE Y， JIANG B， et al. Constrained multiobjective optimization algorithm based on immune system model[J].IEEE Transactions on Cybernetics，2015，46（9）：2056-2069.

[14]GONG M， JIAO L， DU H， et al. Multiobjective immune algorithm with nondominated neighbor-based selection[J]. Evolutionary Computation，2008，16（2）：225-255.

[15]DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm：NSGA-II[J].IEEE Transactions on Evolutionary Computation，2002，6（2）：182-197.

[16]POOJARI C A， VARGHESE B. Genetic algorithm based technique for solving chance constrained problems[J].European Journal of Operational Research，2008，185（3）：1128-1154.

[17]LIN Q， CHEN J， ZHAN Z H， et al. A hybrid evolutionary immune algorithm for multiobjective optimization problems[J].IEEE Transactions on Evolutionary Computation， 2016，20（5）：711-729.