OLBSO：通過正交學習設計提高頭腦風暴優化的學習效率
參考文獻
《Enhancing Learning Efficiency of Brain Storm Optimization via Orthogonal Learning Design》
要點
在BSO中，收斂操作利用聚類政策将種群分成多個聚類，而發散操作則利用這些聚類資訊産生新的個體。然而，這一機制在規範探索和開發搜尋方面效率低下。
本文首先分析了影響BSO算法性能的主要因素，然後提出了一種正交學習架構來改進BSO算法的學習機制。在這個架構中，引入了兩個正交設計引擎（即探索引擎和開發引擎）來發現和利用有用的搜尋經驗來提高性能。此外，還保留了一組具有不同特征的輔助傳輸向量，并通過OD決策機制平衡了它們的偏差。
OLBSO主要貢獻
- 提出OL架構，分析和實驗表明，該架構對提高探索和開發搜尋效率是有效的。
- 為了減少計算量，該方法在每次疊代中以較小的機率觸發OD算子。
- 在失效進行中，提出了一種局部重初始化政策，以增強種群多樣性，幫助個體跳出局部最優解。
一、背景和動機（BACKGROUND AND MOTIVATION）
正交設計-OD（Orthogonal Design）
OD用于對一小部分具有代表性的組合進行取樣，以進行多因素和多水準的試驗。這些因素是一組需要調整的實驗變量，每個因素可以設定為幾個水準中的一個。在一個實驗中，如果實驗結果取決于 N N N個因子，并且每個因子都有 Q Q Q個水準，則存在 Q N Q^N QN個測試組合，其數量呈指數增長，是以建議使用OD來提供因子水準的最佳組合，并進行少量的測試。
正交數組-OA（Orthogonal Array）
OA是一種構造互相正交的拉丁方的圖形方法，表示為 L M ( Q N ) L_M{(Q^N)} LM(QN)，其中 M M M是組合的數目， L L L是具有 N N N個因子且每個因子具有 Q Q Q個水準的OA。例如， L 9 ( 3 4 ) L_9{(3^4)} L9(34)表示為：
其中有4個因素，每個因素3個水準，9個水準組合。注意，OA的任何子列也是OA。這意味着我們隻能用 L 9 ( 3 4 ) L_9{(3^4)} L9(34)的前3列（或任意3列）來構造 L ′ {L'} L′的三因子OA。
然後，我們給出了一個使用OD的例子。在一個實驗中，有三個因素 （ A 、 B 、 C ） （A、B、C） （A、B、C）會影響實驗結果，每個因素有三個水準 （ 1 、 2 、 3 ） （1、2、3） （1、2、3），我們的目的是确定最佳水準組合，使實驗結果最小化。我們可以使用從 L 9 ( 3 4 ) L_9{(3^4)} L9(34)導出的三因子數組 L ′ {L'} L′來指定要測試的九個代表性組合，如表1所示。
因子分析-FA（Factor Analysis）
根據OA的表格，FA評估每個水準對每個因素的影響，并确定每個因素的最佳水準。FA結果見表2。
計算過程如下。首先，假設 f m f_m fm是第 m （ m = 1 , 2 ， … ， M ） m（m=1,2，…，M） m（m=1,2，…，M）組合的實驗結果， S i j S_{ij} Sij是第 j （ j = A ， B ， C ） j（j=A，B，C） j（j=A，B，C）因子中第 i （ i = 1 ， … ， Q ） i（i=1，…，Q） i（i=1，…，Q）水準的影響，定義為：
若第 m m m個組合的第 i i i個系數為 j j j，則 ϕ m i j = 1 \phi_{mij}=1 ϕmij=1；否則， ϕ m i j = 0 \phi_{mij}=0 ϕmij=0。然後，通過使用（6），我們可以評估和比較每個水準對不同因子的影響，如表2所示。例如，水準1對因子 A A A的影響稱為 A 1 A1 A1，依此類推。由于表2中的例子是一個最小化問題， S i j S_{ij} Sij越小第 j j j因子的第 i i i水準越好。是以，确定了 （ A 3 、 B 2 、 C 2 ） （A3、B2、C2） （A3、B2、C2）的最佳組合。
研究動機（Motivation）
首先，個體進化退化問題很可能是由公式（4）引起的。
也就是說，新的選擇比方程中兩個被選擇的個體中的任何一個有更差的适應度，這意味着選擇的某些次元被他們惡化了。為了說明這一點，我們使用了一個簡化的方程來代替（4），即：
其中 S 1 S_1 S1和 S 2 S_2 S2是兩個群内個體， r d r_d rd是均勻分布在 [ 0 ， 1 ] [0，1] [0，1]中的随機值。
給定最小化目标函數 f ( S ) = Σ i = 1 D ∣ 2 S i + 3 / S i ∣ f(S)=\Sigma_{i=1}^{D}|2Si+3/Si| f(S)=Σi=1D∣2Si+3/Si∣，（7）中的 S 1 S_1 S1和 S 2 S_2 S2分别屬于 [ − 3 ， − 0.5 ] [−3，−0.5] [−3，−0.5]和 [ 0 ， 3 ] [0，3] [0，3]。這裡，我們隻考慮一維優化情況 （ D = 1 ） （D=1） （D=1）， f ( S ) f(S) f(S)的情況如圖1所示。
從圖中我們可以觀察到，一旦 S 1 S_1 S1和 S 2 S_2 S2落入紅色箭頭标記的特定間隔内，新的 S s e l e c t S_{select} Sselect将比它們中的任何一個都差。
例如，當 S 1 = − 2.5 S_1=−2.5 S1=−2.5和 S 2 = 1.5 S_2=1.5 S2=1.5時，根據（7）我們可以得到：
S s e l e c t = 0.2 ∗ ( − 2.5 ) + ( 1 − 0.2 ) ∗ 1.5 = 0.06 S_{select}=0.2∗(−2.5)+(1−0.2)∗1.5=0.06 Sselect=0.2∗(−2.5)+(1−0.2)∗1.5=0.06，
f ( S s e l e c t ) = 50.12 f(S_{select})=50.12 f(Sselect)=50.12，
f ( S 1 ) = 6.2 f(S_1)=6.2 f(S1)=6.2，
f ( S 2 ) = 5 f(S_2)=5 f(S2)=5，
然後，可以看到 f ( S s e l e c t ) > f ( S 1 ) > f ( S 2 ) f(S_{select})>f(S_1)>f(S_2) f(Sselect)>f(S1)>f(S2)。
是以，在這一代中， S s e l e c t S_{select} Sselect不受益于所選擇的兩個個體 S 1 S_1 S1和 S 2 S_2 S2。另外，随着世代的增加，兩個個體 S 1 S_1 S1和 S 2 S_2 S2也趨于相似。這種現象将進一步降低生成更好的 S s e l e c t S_{select} Sselect的機率。
第二，思想想法（5）是一個盲搜尋算子，隻在 S s e l e c t S_{select} Sselect的每個維上産生一個随機擾動。
在（5）中，高斯随機函數用于在 S s e l e c t S_{select} Sselect周圍執行随機局部搜尋。然而， S s e l e c t S_{select} Sselect維數的最優搜尋方向往往不同。式（5）由于缺乏必要的方向引導，開發能力較差。這種觀察激勵我們發現最佳的組合方向來指導局部搜尋。
關于 S s e l e c t S_{select} Sselect構造的另一個相關問題是（3）中簡單地使用先驗機率來選擇聚類間想法所引起的種群進化衰減。
為了說明這一點，我們在球面函數上做了一個實驗，其中在搜尋空間中有兩個聚類A和B，兩種情況如圖2（a）和（b）所示。
在情形1中，個體數較多的聚類A比聚類B離全局最優解較遠。執行個體2與執行個體1相反，根據（3）所述，來自較大聚類的個體由于其較大的選擇機率而可能優先被選擇來建構 S s e l e c t S_{select} Sselect。是以，如圖2（c）所示，情況1的演化比情況2的演化差，這表明一個具有較多個體的壞聚類會破壞探索能力。而且，一旦一組個體聚集到這樣一個小的區域中，新生成的個體之間就會非常相似，這很容易導緻過早收斂。
從以上的觀察，我們是以有動機使用OD來設計一組引導向量，有效地利用來自多個聚類的搜尋資訊。這一概念旨在獲得更多有用的資訊，以有效地規範探索和開發搜尋。特别地，為了加強探索，利用OD來發現由兩種政策産生的兩種群内搜尋經驗的最佳組合[即圖3（a）中的old1和old2]。一種政策是從所選的兩個聚類中選擇最佳的思想作為兩個樣本，這有利于收斂。另一種政策是從兩個聚類中随機選擇兩個普通的想法，這有助于保持解決方案的多樣性。這樣，兩個示例的最佳組合産生了更好的 S s e l e c t S_{select} Sselect。然後，利用OD法确定 S s e l e c t S_{select} Sselect的各維上的最佳擾動方向，以提高開發能力。是以，每個次元上的兩個搜尋方向示例（即向前或向後）的最佳組合可以引導 S n e w S_{new} Snew沿着更好的方向移動，如圖3（b）所示。
二、提議的算法-OLBSO（PROPOSED APPROACH）
主架構（Main Framework）
OLBSO的主要架構如算法1所示。其關鍵組成部分包括：
- 1）基本BSO操作，包括聚類（行6）、聚類中心打斷（行7）、更新（行13和19）；
- 2）OD決策操作（行8）；
- 3）探索OD政策（行11）；
- 4）開發OD政策（行17）；
- 5）失效處理（行27）。
其中，基于OD的學習政策是提高學習效率的關鍵。使用輔助傳輸向量池來構造有效的樣本。
在探索OD階段，可以随機選擇任何個體探索其鄰近區域（第10行）。在開發OD階段，選擇全局最優個體開發其鄰域（第16行），因為它更可能接近全局最優，進而引導搜尋向更好的方向發展。為了降低計算成本，OD決策隻允許在每一代中激活一個OD引擎。
OD決策（OD Decision）
OD決策機制（算法1中的第8行）用于決定激活哪個OD引擎以及使用哪個示例。事實上，基于指導範例庫的OD操作有利于搜尋的不同方面，例如探索和開發。如算法2所示，在每一代中，将使用小機率 p u pu pu選擇一個OD引擎進行勘探或開發（第3-7行）。相對較大的 p u pu pu有利于勘探，而相對較小的 p u pu pu有利于開發。是以， p u pu pu被設定為随着世代數的增加而線性減小（第2行）。如果 S s e l e c t S_{select} Sselect的最佳值在一定的生成次數内沒有得到改進，則應激活探索OD引擎（算法3）以重新定位 S s e l e c t S_{select} Sselect的位置（第4行）。否則，如果一個個體在若幹代中沒有得到改進，則應該激活開發OD引擎（算法4），以便圍繞這個 S s e l e c t S_{select} Sselect（第6行）找到更好的搜尋方向。最後，對于探索OD引擎，從輔助傳輸向量池中選擇一個示例（第9-18行）。注意，從第3-7行可以看出，每一代中隻觸發一個OD操作，這大大降低了計算成本。
輔助傳輸矢量（Auxiliary Transmission Vectors）
在探索OD引擎中，利用 S s e l e c t S_{select} Sselect資訊和輔助傳輸向量構造了一個新的範例。如果OD僅使用單個固定傳輸向量（例如 S b e s t S_{best} Sbest），則其影響可随着搜尋的進行而減小。原因如下。
- 首先，所使用的輔助向量容易與 S s e l e c t S_{select} Sselect相似，導緻資訊丢失惡化。
- 第二，單個引導向量可能有偏差，導緻個體收斂到局部最優區域。
為此我們構造了輔助傳輸向量的四重結構，即 T S = { T S 1 ， T S 2 ， T S 3 ， T S 4 } TS=\{TS_1，TS_2，TS_3，TS_4\} TS={TS1，TS2，TS3，TS4}，其中 T S i = { T S i 1 ， T S i 2 ， T S i 3 ， T S i 4 } ， i = 1 ， … ， 4 TSi=\{TS_{i1}，TS_{i2}，TS_{i3}，TS_{i4}\}，i=1，…，4 TSi={TSi1，TSi2，TSi3，TSi4}，i=1，…，4，定義如下。
- 具有全局最佳資訊的收斂向量
T S 1 = S s e l e c t + r a n d ( ) × ( S b e s t − S s e l e c t ) TS_1= S_{select}+rand()× (S_{best}−S_{select}) TS1=Sselect+rand()×(Sbest−Sselect)
- 具有聚類中心資訊的收斂向量
T S 2 = S s e l e c t + r a n d ( ) × ( C R − S s e l e c t ) TS_2= S_{select}+rand()× (C_R−S_{select}) TS2=Sselect+rand()×(CR−Sselect)
- 具有普通個體資訊的多樣性向量
T S 3 = P i TS_3= P_i TS3=Pi
- 基于對立學習（OBL）資訊的多樣性向量
T S 4 = r a n d ( ) × ( U + V ) − P i TS_4= rand()×(U +V)−P_i TS4=rand()×(U+V)−Pi
探索OD引擎（Exploration OD Engine）
算法3給出了主要步驟。
探索OD操作的目的是通過使用兩個示範向量來更新 S s e l e c t S_{select} Sselect。具體地說，由 S s e l e c t = S e x a m p l e 1 ⊕ S e x a m p l e 2 S_{select}=S_{example1}\oplus S_{example2} Sselect=Sexample1⊕Sexample2生成的選擇，其中 S e x a m p l e 1 S_{example1} Sexample1和 S e x a m p l e 2 S_{example2} Sexample2是示例性向量。這裡，可以使用兩種替代方法來形成用于更新 S s e l e c t S_{select} Sselect的示例向量。一種是在一個聚類時利用由算法2生成的輔助傳輸矢量（第2和第3行）。另一種方法是在兩個聚類時使用兩個標明想法的良好組合資訊（第4行和第5行）。
在算法3中，每一個 D D D維都被看作一個因子，每個因子有兩個層次，即1和2，是以，有 M = 2 ⌈ l o g 2 D + 1 ⌉ M=2^{\lceil log_2{D+1}\rceil} M=2⌈log2D+1⌉個正交組合在OA中的應用。在我們的實作中，如果OA中的 l e v e l level level值是1，那麼相應的因子（次元）選擇 S e x a m p l e 1 S_{example1} Sexample1的相應元素；否則，選擇 S e x a m p l e 2 S_{example2} Sexample2。
具體而言，首先基于（第1行）構造兩等級OA，即 L M ( 2 D ) L_M(2^D) LM(2D)。
如果 S s e l e c t S_{select} Sselect是從一個聚類導出的，則輔助傳輸向量 T S O − T S TS_{O−TS} TSO−TS中的 T S TS TS用作 S e x a m p l e 1 S_{example1} Sexample1，目前 S s e l e c t S_{select} Sselect被視為 S e x a m p l e 2 S_{example2} Sexample2（第2行和第3行）。
如果兩個聚類參與生成 S s e l e c t S_{select} Sselect，則兩個聚類内向量分别被用作 S e x a m p l e 1 S_{example1} Sexample1和 S e x a m p l e 2 S_{example2} Sexample2（第4行和第5行）。
然後，評估來自OA的每個候選樣本以确定最佳解 S b S_b Sb（第7行和第8行），并且确定每個因子的最佳水準以導出預測解 S p S_p Sp（第9行和第10行）。
最後，使用 S b S_b Sb和 S p S_p Sp之間的較好的一個作為新的 S s e l e c t S_{select} Sselect（第11行）。
第5行的OD運算可以充分利用兩個聚類内思想較好的維，引導搜尋向更好的方向發展。這樣可以避免個體進化的退化問題。
開發OD引擎（Exploitation OD Engine）
算法4給出了主要程式。
開發OD引擎就是在 S s e l e c t S_{select} Sselect的每個次元上尋找最佳的搜尋方向，以便更深入地開發最有前景的區域。動機是通過調整搜尋方向來補救缺陷搜尋，如圖3（b）所示。公式（5）隻在所選思想的每個次元上産生一個随機擾動，使用率低。
在算法4中，将待更新候選解的每個次元視為一個因子，是以存在 D D D個因子，每個因子有兩個層次，即1和2。然後，按照算法3（第1行）中相同的步驟構造一個兩層OA，即 L M ( 2 D ) L_M(2^D) LM(2D)。這裡，對于每個因子，級别值1表示向前搜尋方向，即在候選解上添加正步，級别值2表示向後搜尋方向，即在候選解上添加負步。為了說明這一點，我們給出了以下搜尋公式：
其中 L i d L_{id} Lid是組合 d d d與 L M ( 2 D ) L_M(2^D) LM(2D)中因子 i i i的水準值， S i d k S^k_{id} Sidk是組合 d d d的想法 S i S_i Si的第 d d d維， ∣ ξ ( k ) η d ( μ , σ ) ∣ |ξ(k)η_d(μ, σ )| ∣ξ(k)ηd(μ,σ)∣ 是步長。
接下來，通過選擇相應的水準值并使用它們來生成基于公式（8）的解（第2行），進而組成 M = 2 ⌈ l o g 2 D + 1 ⌉ M=2^{\lceil log_2{D+1}\rceil} M=2⌈log2D+1⌉個被測解。然後，分别确定各因子水準最佳的最佳候選解 S b S_b Sb和預測解 S p S_p Sp（第3行和第4行）。最後，根據 S b S_b Sb和 S p S_p Sp（第7行）确定最終候選解 S n e w S_{new} Snew。
失效處理（Invalidation Processing）
如果OD在一定的代數内沒有貢獻，則部分解會重新初始化它們在整個搜尋空間中的位置（算法1的第27行），目的是增加解“跳出”局部最優解的可能性。設計了一種自适應政策來調節重新初始化解 N r N_r Nr的數目，如下所示：
其中 k k k是目前的世代數， M a x G e n MaxGen MaxGen是最大世代數， N 0 N_0 N0是重新初始化解的初始數目，經驗上等于人口的一半， N 1 N_1 N1是結果數，通常設定為1。
從（9）可以看出，在搜尋過程中， N r N_r Nr是下降的。在搜尋開始時有一半解重新初始化，然後 N r N_r Nr在每次重新初始化時線性減小。這一政策是先進行勘探，後期進行開發。