最壞情況下的魯棒優化問題研究﹡

宮 韜

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.