最坏情况下的鲁棒优化问题研究﹡

宫 韬

0 引言

由于实际中存在噪声等不确定干扰，解的实际性能会受到很大影响，此时解的鲁棒性决定了解的实用性。例如：在电路设计[1-2]中，电路性能应能承受温度变化带来的影响；在通信领域的多用户分集优化[3]、复杂网络社区划分[4]中，设计方案应具有抗干扰能力。可见质量好而抗干扰能力不好的解在实际中往往难有好的表现，因此鲁棒优化问题日渐成为国内外学者研究的一个热点。

由于鲁棒优化问题需要进行大量的抽样计算，因而具有着计算量大、难收敛等特点。而演化算法具有自组织、自适应、鲁棒性强、易于全局搜索等优点，因此鲁棒优化问题自然也成为了演化算法研究的重要方面之一[5]。其中，协同演化算法能够利用少数起演化导向作用的个体，减少了不必要的计算量，使收敛的速度加快[6]。因此协同演化算法在求解鲁棒优化问题的过程中会有更好的表现。

根据应用场景不同，对解的鲁棒性评价分为均值评价和最坏情况评价等。当前国内外学者主要关注均值评价下的鲁棒优化问题，对最坏情况下的问题求解研究不多[7]。通过研究最坏情况下的鲁棒优化问题，提出一种将最坏情况下鲁棒优化问题转化为极小化极大问题（minimax problem）[8]，进而利用协同演化算法进行求解的思路，最后实验证明了该方法的有效性。

1 最坏情况下的鲁棒优化问题

在介绍最坏情况下鲁棒优化问题前，我们先引入鲁棒优化问题及解的鲁棒性概念。

定义1 鲁棒优化问题

与一般最优化问题不同，鲁棒优化问题考虑了决策向量中存在干扰的情况，即：

式中， X = ( x1, x2,⋅⋅⋅,xn)是决策向量，Ω 是可行解空间， Δ = ( δ1, δ2,⋅ ⋅⋅,δn)为一干扰向量，n为决策变量的维数。

由式（1）可见，当决策向量X存在干扰向量Δ时，目标函数向量同时也会产生一个波动，这个波动越小，解的鲁棒性就越好。由图1可见，虽然该函数的全局最优解为A，但其鲁棒最优解为B。在鲁棒优化问题中，鲁棒最优解与原函数全局最优解是不一样的。

图1 鲁棒最优解示意

定义2 最坏情况下鲁棒优化问题

要求使得变量在干扰范围内最坏情况下的目标函数值最优。即：

利用式（2）已经可以进行优化求解，由于要使用协同演化算法思想来求解，这里进一步将式（2）转换为更一般的minimax问题，即：

2 基于协同演化算法的优化求解

采用两个种群进行演化，种群间交叉、变异的过程各自独立，在适应度评价的环节中相互紧密关联，种群间个体的适应度计算取决于它和另一个种群中个体的结合情况[9]。

对于式（3）描述的问题，在算法设计中我们将其划分为XP与PΔ两个种群。

种群XP中个体目标函数如下：

相应的，种群PΔ中的个体目标函数如下：

该目标函数 ()Gδ需要最大化，即函数值越大的个体，其适应度越大。

2.1 交替式协同演化算法

图2 交替式协同演化算法流程

2.2 并行式协同演化算法

图3 并行式协同演化算法流程

2.3 随机群体采样演化算法

在随机群体采样算法（RSGA）中，种群PΔ用随机种群取代了协同演化种群，整个过程中只对种群PX进行演化操作，其适应度评价由式（4）给出。该算法可作为对照算法。

3 测试函数计算结果

下面对具体的测试函数进行实验验证，测试函数为

函数图象如图4所示。

图4 测试函数

可看出该函数具有多个局部最优解，同时每个局部最优解处的鲁棒性情况也不同。图中虚线为取干扰向量 Δ =[-0.2,0.2]的情况下描绘出的最坏情况下目标函数曲线。

算法参数为种群XP大小为10，交叉概率为0.6，变异概率为 0.001，迭代次数为 100代，抽样次数100，种群PΔ大小为100。重复实验30次，实验结果如表1所示。

表1 算法实验结果

从实验结果可看出，协同演化算法可以有效的求解最坏情况下鲁棒优化问题。

4 结语

由此可见，最坏情况下鲁棒优化问题与传统优化问题在问题模型及求解思路上有着不同，该问题是一个值得研究的课题。将最坏情况下鲁棒优化问题转化为极小化极大问题，并利用协同演化算法进行求解的算法思路，能够有效的寻找到鲁棒最优解。

[1] SMITH M W.Worst Case Circuit Analysis-an Overview[C]//Proc. 1996 IEEE AnnReliabil.Maintainabil.Symp： 326-334.

[2] 胡红明. 2M电路切换器对提升电路可靠性的应用研究[J].通信技术,2010,43(06)：051.

[3] 唐冬,刘扳浩等.多用户空间分集合并系统的鲁棒性研究[J].通信技术,2010,43(06)：014.

[4] 季青松,赵郁忻,等.有效改善标签传播算法鲁棒性的途径[J].信息安全与通信保密,2012(09)：058.

[5] TSUTSUI S, GHOSH A. Genetic Algorithms with a Robust Solution Searching Scheme[J]. Evolutionary Computation, IEEE Transactions on,1997,1(03)：201-208.

[6] BÄCK T, SCHWEFEL H P. An Overview of Evolutionary Algorithms for Parameter Optimization[J].Evolutionary computation, 1993, 1(01)： 1-23.

[7] JIN Y, BRANKE J. Evolutionary Optimization in Uncertain Environments-a Survey[J]. Evolutionary Computation, IEEE Transactions on, 2005, 9(03)：303-317.

[8] CHARALAMBOUS C, Conn A R. An Efficient Method to Solve the Minimax Problem Directly[J]. SIAM Journal on Numerical Analysis, 1978, 15(01)：162-187.

[9] CRAMER A M, SUDHOFF S D, ZIVI E L. Evolutionary Algorithms for Minimax Problems in Robust Design[J]. Evolutionary Computation, IEEE Transactions on, 2009, 13(02)： 444-453.