最壞情況下的魯棒優(yōu)化問(wèn)題研究﹡

宮 韜

0 引言

由于實(shí)際中存在噪聲等不確定干擾，解的實(shí)際性能會(huì)受到很大影響，此時(shí)解的魯棒性決定了解的實(shí)用性。例如：在電路設(shè)計(jì)[1-2]中，電路性能應(yīng)能承受溫度變化帶來(lái)的影響；在通信領(lǐng)域的多用戶分集優(yōu)化[3]、復(fù)雜網(wǎng)絡(luò)社區(qū)劃分[4]中，設(shè)計(jì)方案應(yīng)具有抗干擾能力?？梢?jiàn)質(zhì)量好而抗干擾能力不好的解在實(shí)際中往往難有好的表現(xiàn)，因此魯棒優(yōu)化問(wèn)題日漸成為國(guó)內(nèi)外學(xué)者研究的一個(gè)熱點(diǎn)。

由于魯棒優(yōu)化問(wèn)題需要進(jìn)行大量的抽樣計(jì)算，因而具有著計(jì)算量大、難收斂等特點(diǎn)。而演化算法具有自組織、自適應(yīng)、魯棒性強(qiáng)、易于全局搜索等優(yōu)點(diǎn)，因此魯棒優(yōu)化問(wèn)題自然也成為了演化算法研究的重要方面之一[5]。其中，協(xié)同演化算法能夠利用少數(shù)起演化導(dǎo)向作用的個(gè)體，減少了不必要的計(jì)算量，使收斂的速度加快[6]。因此協(xié)同演化算法在求解魯棒優(yōu)化問(wèn)題的過(guò)程中會(huì)有更好的表現(xiàn)。

根據(jù)應(yīng)用場(chǎng)景不同，對(duì)解的魯棒性評(píng)價(jià)分為均值評(píng)價(jià)和最壞情況評(píng)價(jià)等。當(dāng)前國(guó)內(nèi)外學(xué)者主要關(guān)注均值評(píng)價(jià)下的魯棒優(yōu)化問(wèn)題，對(duì)最壞情況下的問(wèn)題求解研究不多[7]。通過(guò)研究最壞情況下的魯棒優(yōu)化問(wèn)題，提出一種將最壞情況下魯棒優(yōu)化問(wèn)題轉(zhuǎn)化為極小化極大問(wèn)題（minimax problem）[8]，進(jìn)而利用協(xié)同演化算法進(jìn)行求解的思路，最后實(shí)驗(yàn)證明了該方法的有效性。

1 最壞情況下的魯棒優(yōu)化問(wèn)題

在介紹最壞情況下魯棒優(yōu)化問(wèn)題前，我們先引入魯棒優(yōu)化問(wèn)題及解的魯棒性概念。

定義1 魯棒優(yōu)化問(wèn)題

與一般最優(yōu)化問(wèn)題不同，魯棒優(yōu)化問(wèn)題考慮了決策向量中存在干擾的情況，即：

式中， X = ( x1, x2,???,xn)是決策向量，Ω 是可行解空間， Δ = ( δ1, δ2,? ??,δn)為一干擾向量，n為決策變量的維數(shù)。

由式（1）可見(jiàn)，當(dāng)決策向量X存在干擾向量Δ時(shí)，目標(biāo)函數(shù)向量同時(shí)也會(huì)產(chǎn)生一個(gè)波動(dòng)，這個(gè)波動(dòng)越小，解的魯棒性就越好。由圖1可見(jiàn)，雖然該函數(shù)的全局最優(yōu)解為A，但其魯棒最優(yōu)解為B。在魯棒優(yōu)化問(wèn)題中，魯棒最優(yōu)解與原函數(shù)全局最優(yōu)解是不一樣的。

圖1 魯棒最優(yōu)解示意

定義2 最壞情況下魯棒優(yōu)化問(wèn)題

要求使得變量在干擾范圍內(nèi)最壞情況下的目標(biāo)函數(shù)值最優(yōu)。即：

利用式（2）已經(jīng)可以進(jìn)行優(yōu)化求解，由于要使用協(xié)同演化算法思想來(lái)求解，這里進(jìn)一步將式（2）轉(zhuǎn)換為更一般的minimax問(wèn)題，即：

2 基于協(xié)同演化算法的優(yōu)化求解

采用兩個(gè)種群進(jìn)行演化，種群間交叉、變異的過(guò)程各自獨(dú)立，在適應(yīng)度評(píng)價(jià)的環(huán)節(jié)中相互緊密關(guān)聯(lián)，種群間個(gè)體的適應(yīng)度計(jì)算取決于它和另一個(gè)種群中個(gè)體的結(jié)合情況[9]。

對(duì)于式（3）描述的問(wèn)題，在算法設(shè)計(jì)中我們將其劃分為XP與PΔ兩個(gè)種群。

種群XP中個(gè)體目標(biāo)函數(shù)如下：

相應(yīng)的，種群PΔ中的個(gè)體目標(biāo)函數(shù)如下：

該目標(biāo)函數(shù) ()Gδ需要最大化，即函數(shù)值越大的個(gè)體，其適應(yīng)度越大。

2.1 交替式協(xié)同演化算法

圖2 交替式協(xié)同演化算法流程

2.2 并行式協(xié)同演化算法

圖3 并行式協(xié)同演化算法流程

2.3 隨機(jī)群體采樣演化算法

在隨機(jī)群體采樣算法（RSGA）中，種群PΔ用隨機(jī)種群取代了協(xié)同演化種群，整個(gè)過(guò)程中只對(duì)種群PX進(jìn)行演化操作，其適應(yīng)度評(píng)價(jià)由式（4）給出。該算法可作為對(duì)照算法。

3 測(cè)試函數(shù)計(jì)算結(jié)果

下面對(duì)具體的測(cè)試函數(shù)進(jìn)行實(shí)驗(yàn)驗(yàn)證，測(cè)試函數(shù)為

函數(shù)圖象如圖4所示。

圖4 測(cè)試函數(shù)

可看出該函數(shù)具有多個(gè)局部最優(yōu)解，同時(shí)每個(gè)局部最優(yōu)解處的魯棒性情況也不同。圖中虛線為取干擾向量 Δ =[-0.2,0.2]的情況下描繪出的最壞情況下目標(biāo)函數(shù)曲線。

算法參數(shù)為種群XP大小為10，交叉概率為0.6，變異概率為 0.001，迭代次數(shù)為 100代，抽樣次數(shù)100，種群PΔ大小為100。重復(fù)實(shí)驗(yàn)30次，實(shí)驗(yàn)結(jié)果如表1所示。

表1 算法實(shí)驗(yàn)結(jié)果

從實(shí)驗(yàn)結(jié)果可看出，協(xié)同演化算法可以有效的求解最壞情況下魯棒優(yōu)化問(wèn)題。

4 結(jié)語(yǔ)

由此可見(jiàn)，最壞情況下魯棒優(yōu)化問(wèn)題與傳統(tǒng)優(yōu)化問(wèn)題在問(wèn)題模型及求解思路上有著不同，該問(wèn)題是一個(gè)值得研究的課題。將最壞情況下魯棒優(yōu)化問(wèn)題轉(zhuǎn)化為極小化極大問(wèn)題，并利用協(xié)同演化算法進(jìn)行求解的算法思路，能夠有效的尋找到魯棒最優(yōu)解。

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

[2] 胡紅明. 2M電路切換器對(duì)提升電路可靠性的應(yīng)用研究[J].通信技術(shù),2010,43(06)：051.

[3] 唐冬,劉扳浩等.多用戶空間分集合并系統(tǒng)的魯棒性研究[J].通信技術(shù),2010,43(06)：014.

[4] 季青松,趙郁忻,等.有效改善標(biāo)簽傳播算法魯棒性的途徑[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.