MBSO：改進的頭腦風暴優化算法

參考文獻

《A Modified Brain Storm Optimization》

要點

• BSO通常使用分組，替換和建立來産生盡可能多的想法，以逐代解決問題的全局最優。
• 改進的BSO（MBSO）的第一個改進點是，它在分組運算中使用一種簡單分組方法（SGM）而不是聚類方法，來減少算法的計算負擔。

• 第二個改進點是MBSO在建立運算中使用一種創新想法差異政策（IDS），而不是高斯随機政策。

  IDS不僅包含開放思想的元素，可以避免想法被局部最優所困，而且還可以與搜尋環境相比對，以建立更好的新思想來解決問題。

一、引言

頭腦風暴：當人類面臨每個人都可能難以解決的難題時，一群人将聚在一起進行頭腦風暴。這些人通常具有不同的背景，他們聚在一起進行頭腦風暴過程，這有助于他們進行互動式協作以産生出色的想法。這樣，通常可以高機率解決問題。

二、頭腦風暴優化

A、人類的頭腦風暴過程

集思廣益的過程是，聚集一群人，尤其是具有不同背景的人們，以互動方式進行協作，以産生解決問題的好主意。頭腦風暴過程主要遵循Osborn的四項規則，以減少小組成員之間的社交障礙，激發想法産生并增加小組的整體創造力。這四個規則分别解釋為：

• "規則1：想法越多越好”
• “規則2：對任何想法保留批評”
• “規則3：歡迎不尋常的想法”
• “規則4：合并并改進想法”

根據Osborn的四個規則，典型的頭腦風暴過程通常具有如圖1所示的步驟。

• 第1步：聚集一組背景不同的人。
• 第2步：使人們盡可能多的按4條規則産生想法。
• 第3步：有幾個（例如3個或5個）客戶作為問題所有者，他們可以為每個所有者選擇一個想法，作為解決問題的更好想法。
• 第4步：将在第3步中抽取的創意可能比其他創意更好的作為線索，并根據這4條規則建立更多創意。
• 第5步：根據這4條規則，随機使用現場的任何客體作為線索來建立更多創意。
• 第6步：通過考慮和/或合并所建立的想法來獲得良好的解決方案，否則，執行步驟3-5進行下一次頭腦風暴會議。

B、基本BSO算法

基本BSO算法如圖2所示。

如果使用一個聚類，則通過輪盤賭選擇政策根據每個聚類中的想法數量選擇聚類j。也就是說，聚類中的想法越多，選擇它的機會就越大。選擇每個聚類j的機率為：

但是，如果使用兩個聚類，則BSO不會根據（1）選擇聚類，而隻是從M個聚類中随機選擇兩個聚類j1和j2（圖2中的第18行）。

選擇聚類後，BSO會确定是根據聚類中心還是聚類的随機想法建立新想法Yi。無論使用聚類中心（第13和20行）還是使用聚類的随機想法（第15和22行），我們都可以将所選的基于基的想法視為X，然後将新的想法Yi建立為：

其中d是次元下标，N(μ，σ)是均值為μ和方差為σ的高斯随機值，而ξ是權重高斯随機值貢獻的系數，其計算公式為：

其中logsig()是對數sigmoid傳遞函數，其值在（0,1）範圍内，g和G是目前代數和最大代數，k用于更改logsig()函數的斜率，以及random(0 ，1)是（0,1）内的随機值。

當基于兩個聚類建立新的想法Yi時，圖2中的20和22行顯示了來自聚類j1和j2的兩個想法首先将它們自身組合在一起，然後使用等式(2)創造Yi。組合定義為：

其中R是X的所有次元在(0, 1)内的随機值，而X1和X2分别是聚類j1和j2的兩個想法。

三、改進的頭腦風暴優化算法

A、分組算子中的簡單分組方法

在原始的BSO中，k-means聚類方法使BSO算法的實作更加複雜，并且計算負擔更大。在MBSO中，分組操作通過SGM簡單分組方法來實作，如下所示。

• 步驟1：從目前代中随機選擇M個不同的想法作為M個小組的種子。這些M個種子表示為Sj（1≤j≤M）。
• 步驟2：對于目前代中的每個創意Xi（1≤i≤N），計算其與每個組j的距離為：

• 步驟3：比較所有M個距離值，然後将想法Xi配置設定到最近的組中。請注意，該組的種子Sj保持不變。
• 步驟4：轉到步驟2，分組下一個想法。否則，在配置設定所有想法後，SGM将終止。

B、建立算子中的想法差異政策

式(3)中這種時變噪聲政策與通常的方法是一緻的，即在全局搜尋的早期需要大噪聲，而在後期進行局部微調則需要小噪聲。

但是，等式(3)可能有兩個缺點。首先，該等式基于生成使用固定的對數sigmoid傳遞函數。由于BSO的搜尋行為是一個随機過程，是以從搜尋過程中擷取不到回報資訊可能無法很好地抓住搜尋特征，尤其是在處理各種優化問題時。其次，由于logsig()函數傳回的值在（0,1）内，而random（0,1）也是在（0,1）内的随機值，它們的乘積ξ仍在（0,1）内。即使ξ乘以均值μ= 0和方差σ= 1的高斯随機值N（μ，σ），該最終随機噪聲在（-4,4）範圍内的機率很高，當搜尋範圍較大時，這對于全局搜尋可能不夠有效。

在本文中，建議使用IDS來生成等式（2）的噪聲值。IDS基于這樣的考慮，在人類的頭腦風暴過程中，我們可以想象到，在過程的開始，每個人的想法都會大相徑庭。當他們根據目前思想建立新思想時，應考慮目前思想的差異。例如，當基于目前想法Xi建立新想法Yi時，從所有目前想法中選取兩個不同的随機想法Xa和Xb來表示想法差異，并且Yi的建立方式為：

其中d是次元下标，且1≤a≠b≤N。 IF語句中的pr是一個新參數，可以控制思想創新中的開放元素。這模仿了人類頭腦風暴過程中奧斯本的規則3（歡迎不尋常的想法）。實驗表明，在[0.001，0.01]範圍内的值會很好。在本文中，設定pr = 0.005。

使用式（6）代替式（2）創造新思想有兩個優點。首先，（6）的計算負擔比（2）輕，因為（2）（包括（3））涉及對數sigmoid傳遞函數，高斯分布函數，随機函數，加法，減法，乘法和除法，而（6）涉及随機函數，乘法和減法以構成噪聲值。其次，等式（6）可以比公式（2）更好地比對進化過程的搜尋環境。為了與人類在解決問題上的頭腦風暴過程保持一緻，這些想法在開始時就彼此不同，是以，（6）中的（xad–xbd）早期成分較大，并且新建立的想法在早期階段可以保持解中的多樣性。在集思廣益過程的後期，人們可能會達成共識，想法差異可能會更小。在這種情況下，（6）中的（xad–xbd）項也較小，以幫助完善構想。是以，等式（6）可能擅長在進化過程中根據搜尋資訊平衡全局搜尋能力和局部搜尋能力。