基于正交設(shè)計求解動態(tài)魯棒問題的新算法

摘要：設(shè)計了一個基于正交設(shè)計法求解動態(tài)魯棒優(yōu)化問題的新算法（RODEA）。該算法把目標(biāo)搜索區(qū)域劃分成很多小鄰域（小生境），每個小生境都有一個代表，對每個小生境用正交設(shè)計法（構(gòu)造正交矩陣進行抽樣）搜索可能成為小生境代表的潛在優(yōu)解。還設(shè)計了一個基準(zhǔn)測試函數(shù)用來測試動態(tài)魯棒優(yōu)化問題。實驗數(shù)據(jù)表明RODEA用來求解動態(tài)魯棒問題具有很好的效果。

關(guān)鍵詞：正交設(shè)計；動態(tài)魯棒優(yōu)化；小生境

中圖分類號：TP301．6文獻標(biāo)志碼：A

文章編號：1001－3695(2008)03－0732－03

在一個激烈變化的動態(tài)環(huán)境下，如果目標(biāo)對環(huán)境變化很敏感，很多算法很難找到最優(yōu)解，這時希望在解的抗擾動性（魯棒性）和解的最優(yōu)值之間尋找一個平衡點。所以研究動態(tài)魯棒優(yōu)化問題具有重要的實際意義。文獻[1~4]中提出了很多求解魯棒問題的算法。這些算法求出的解雖然不一定是最優(yōu)解，但在動態(tài)環(huán)境下具有較好的魯棒性（抗擾動性）。然而，這些算法一般通過簡單的統(tǒng)計抽樣來求解動態(tài)魯棒優(yōu)化問題，其性能會隨目標(biāo)函數(shù)復(fù)雜度的增大而顯著降低。本文在ODEA[5]基礎(chǔ)上設(shè)計了一個基于正交設(shè)計法求解動態(tài)魯棒問題的新算法RODEA；還設(shè)計了一個基準(zhǔn)測試函數(shù)，這個測試函數(shù)能很好地測試動態(tài)魯棒優(yōu)化問題。正交設(shè)計法通過構(gòu)造正交矩陣在問題域里均勻采樣，能很好地抵抗環(huán)境變化給解帶來的劇烈擾動，使求得的解具有較好的魯棒性。

1動態(tài)魯棒優(yōu)化定義

1．1優(yōu)化

定義1動態(tài)優(yōu)化問題：

xmax(t)=arg maximizex∈Sf(x，t) (1)

其中：x=(x1，x2，…，xN)是N維自變量；S是搜索空間。目標(biāo)函數(shù)f的值不僅與x有關(guān)，還與時間t有關(guān)。自變量x的維數(shù)和搜索空間S的大小是預(yù)先設(shè)定好的，它們不隨時間變化。xmax(t)是目標(biāo)函數(shù)在時間為t時的最優(yōu)解。

在求解動態(tài)優(yōu)化問題時，時間不斷變化，所以找到每一具體時刻的最優(yōu)解xmax(t)在操作上不可行。實際操作時，一般都是跟蹤解隨時間改變的運動趨勢。這里假設(shè)環(huán)境在一段相對靜止的時間后突然發(fā)生變化。這樣可以認為目標(biāo)函數(shù)的值在這段相對靜止的時間里只依賴于變量x，而不依賴于時間t。在這段相對靜止的時間里，希望算法盡可能找到最優(yōu)解。

1．2魯棒解定義

以求最大值的動態(tài)優(yōu)化問題為例，如果xrobustmax(t)是求該最大值動態(tài)優(yōu)化問題的可行解，稱xrobustmax(t)為時間為t時的動態(tài)魯棒解。

定義2動態(tài)魯棒解

xrobustmax(t)=arg maximizex∈Sf eff(x，t)(2)

這里：

f eff(x，t)=1/|y∈Bδ(x)∩S|×∫f(y，t)dyy∈Bδ(x)∩S(3)

其中：Bδ(x)是x的一個δ鄰域。該鄰域每邊的邊長構(gòu)成向量δ= (δ1，δ2，…，δN)。如果不考慮解的魯棒性可令δ=0。

2基于正交設(shè)計的動態(tài)魯棒算法

2．1RODEA的基本思想

與一般演化算法不同，RODEA把待搜索的問題域劃分成很多小生境（小鄰域），在每個小生境里用正交設(shè)計法來搜索可能成為小生境代表的潛在優(yōu)解，再把這些小生境的代表（潛在優(yōu)解）組為新的群體，對這些代表執(zhí)行變異等遺傳操作。正交設(shè)計法[5]在一個較小的鄰域里很好地利用了環(huán)境變化前后有效的相似信息。

RODEA通過評估每個小生境代表適應(yīng)性的好壞來間接評估每個小生境適應(yīng)性的好壞；通過小生境代表的位置來判斷小生境是否搜到整個搜索空間的一個峰（最優(yōu)解對應(yīng)的函數(shù)值）。如果小生境的代表位于小生境內(nèi)部，稱這個小生境找到了當(dāng)前搜索空間的一個峰；如果小生境的代表位于小生境邊緣，稱這個小生境沒有找到當(dāng)前搜索空間的一個峰。

RODEA也采用了SOS[6]算法中種群分離的思想，把小生境分成看守小生境和探索小生境兩部分。每當(dāng)環(huán)境變化時，看守小生境保存環(huán)境變化前已經(jīng)搜到的峰值，探索小生境在全局范圍里搜索新環(huán)境下新的峰值。這樣，一方面看守小生境能充分利用環(huán)境變化前后有效的相似信息；另一方面探索小生境在全局范圍里搜索新峰，增加了群體的多樣性，避免算法陷入局部最優(yōu)。

變異操作是RODEA中惟一使用到的遺傳操作。變異操作執(zhí)行如下：對于看守小生境，如果它沒有罩住峰，就向距離其最近的峰值移動，否則，就執(zhí)行收縮操作以提高算法的精度；對于探索小生境，如果它沒有罩住峰，就向距離其最近的峰值移動，如果探索小生境罩住了一個峰，就與看守小生境里保存的舊峰值比較，如果該新峰值比舊峰值中保存的峰值大，就用它替換掉舊峰值中的較低峰，再隨機生成一個新的探索小生境。

2．2RODEA的執(zhí)行步驟

如果沒有特別的說明，以下RODEA都是對解x在t時刻通過計算fest(x，t)來評估解的魯棒性，而不是直接計算目標(biāo)函數(shù)f(x，t)來評估解的性能。假定有K個看守小生境，記為W1，W2，…，WK，為降低計算的復(fù)雜度，假定只有一個探索小生境，記為E，共有K+1個小生境。用s標(biāo)記每個小生境的代表。用變量PeakIsInside來標(biāo)記每個小生境是否罩住了一個峰。初始化時PeakIsInside = 1，表示小生境沒有罩住峰。用變量t來標(biāo)記演化的代數(shù)。

3．3實驗結(jié)果

時間t=0，0.1，0.2，…，0.9，1，0代表環(huán)境的變化。在時間t分別取t=0，0.1，0.2，…，0.9，1，0時RODEA各執(zhí)行100輪，每輪演化100次，共評估10 000次。表1是RODEA在沒有約束條件下跟蹤全局最優(yōu)解的情況。表2是RODEA在鄰域半徑δi=0.02時跟蹤全局最優(yōu)解的情況。從表2可以看到：當(dāng)t從0.8增加到0.9時，最初的局部最優(yōu)解（不一定是全局最優(yōu)解）現(xiàn)在變成了魯棒優(yōu)解，而當(dāng)t從1.0變到0.0時，最初的全局最優(yōu)解的性能劣于魯棒優(yōu)解。表3顯示了鄰域半徑變?yōu)棣膇=0.03時RODEA跟蹤全局魯棒優(yōu)解的情況。

4結(jié)束語

本文介紹了動態(tài)環(huán)境下魯棒解的定義，設(shè)計了一個測試函數(shù)來闡明動態(tài)魯棒優(yōu)化問題，設(shè)計了RODEA求解動態(tài)魯棒優(yōu)化問題。實驗結(jié)果表明RODEA是求解動態(tài)魯棒優(yōu)化問題性能較好的算法。

參考文獻：

［1］BRANKE J.Efficient evolutionary algorithms for searching robust solutions[C]//Proc ofACDM.2000:275－286.

[2]BRANKE J，SCHMIDT C.Faster convergence by means of fitness estimation[J].Soft Computing，2005，9(1):13－20.

[3]BRANKE J.Creating robust solutions by means of an evolutionary algorithm[C]//Proc of Parallel Problem Solving from Nature.1998:119128.

[4]JIN Y，SENDHOFF B.Tradeoff between performance and robustness:an evolutionary multiobjective approach[C]//Proc of EMO.2003:237－251.

[5]ZENG Sanyou，KANG Lishan，DING Lixing.An orthogonal multiobjective evolutionary algorithm for multiobjective optimization problems with constraints[J].Evolutionary Computation，2004，12(1):77－98.

[6]BRANKE J.Evolutionary approaches to dynamic optimization problems:instruction and recent trends[C]//Proc of Workshop on Evolutionary Algorithms for Dynamic Optimization Problems.Chicago:[s.n.]，2003:1－3.

[7]DEB K，GUPTA H.Searching for robust Paretooptimal Solutions in Multiobjective optimization[C]//Proc of Conference on Evolutionary MultiCriterion Optimization.[S.l.]:SpringerVerlag，2005:150164.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”