基于正交設計求解動態魯棒問題的新算法

摘要：設計了一個基于正交設計法求解動態魯棒優化問題的新算法（RODEA）。該算法把目標搜索區域劃分成很多小鄰域（小生境），每個小生境都有一個代表，對每個小生境用正交設計法（構造正交矩陣進行抽樣）搜索可能成為小生境代表的潛在優解。還設計了一個基準測試函數用來測試動態魯棒優化問題。實驗數據表明RODEA用來求解動態魯棒問題具有很好的效果。

關鍵詞：正交設計；動態魯棒優化；小生境

中圖分類號：TP301．6文獻標志碼：A

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

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

1動態魯棒優化定義

1．1優化

定義1動態優化問題：

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

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

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

1．2魯棒解定義

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

定義2動態魯棒解

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的一個δ鄰域。該鄰域每邊的邊長構成向量δ= (δ1，δ2，…，δN)。如果不考慮解的魯棒性可令δ=0。

2基于正交設計的動態魯棒算法

2．1RODEA的基本思想

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

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

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

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

2．2RODEA的執行步驟

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

3．3實驗結果

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

4結束語

本文介紹了動態環境下魯棒解的定義，設計了一個測試函數來闡明動態魯棒優化問題，設計了RODEA求解動態魯棒優化問題。實驗結果表明RODEA是求解動態魯棒優化問題性能較好的算法。

參考文獻：

［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.

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