沈兆琪 曹倬銘 王文國
摘要：頭腦風暴算法是目前僅有的受人類社會性行為啟發的優化算法，該算法和其它群體智能算法一樣，存在執行效率低和收斂速度慢等缺點。首次定義了一個香農多樣性指數來估算樣本群落的多樣性以及均勻性，並對原始頭腦風暴優化算法進行多次初始化，從而有效加快算法後期的收斂性。利用6個標準測試函數對改進後的算法進行了可行性驗證，統計分析後表明，該算法只要選擇多樣性及均勻性足夠好的初始種群，就能顯著減少疊代次數。改進後的頭腦風暴算法在執行效率和收斂速度上都有所提高。
關鍵詞：頭腦風暴算法；多樣性指數；均勻性；收斂速度
DOIDOI：10.11907/rjdk.172450
中圖分類號：TP312
文獻標識碼：A文章編號文章編號：16727800（2018）003007103
英文摘要Abstract：Brain storm is the only swarm intelligence algorithm with origin from modeling human activities， which can help solve some NP problems but often behaves odd and converges slowly. To overcome its shortcomings， a new idea of diversity index arising from ecology is introduced for brain storm optimization， which will measure diversity and uniformity of a solution group， and help us select a good starting point for optimization. Simulation tests with 6 benchmark functions have been conducted， and results show that the improved brain storm optimization with diversity index can speed up convergence and reduce number of iterations significantly.
英文關鍵詞Key Words：brain storm； diversity index； uniformity； convergence rate
0引言
群體智能算法是一種基於隨機搜索機制的優化方法，具有靈活應對群體內部和外部搜索環境變化的能力，即當搜索條件多變或自身的某些個體失敗時，能夠自組織逃離並發現更優的位置。群體智能算法與傳統的完備算法相比，儘管不一定能找到最優解，但可以確保在短時間內找到較優質的解。由於其在解決優化問題上具有獨特的優勢，群體智能算法應用於很多實際問題中，如機器人控制、無人駕駛交通工具、社會性行為預測、通信網絡加強、醫學圖像處理等。然而這些算法常常存在易陷入局部最優、早熟或收斂過慢等問題。
大多數經典算法是受低等生物的社會性行為啟發的，但長期沒有由人類的社會行為啟發而提出的智能算法。2011年史玉回[12]提出了頭腦風暴優化算法。頭腦風暴優化算法是一種非常有潛力的方法，通常能夠產生超出經典智能算法的結果。
目前，頭腦風暴優化算法的研究與應用還處於初級階段。許多人在過去的幾年中嘗試對頭腦風暴優化算法進行各種研究及改進。史玉回等[3]提出了引入兩種組件提高傳統頭腦風暴優化的性能，第一個組件使用一個簡單分組操作符的分組方法（SGM），代替聚類方法從而減輕算法的計算負擔；第二個組件使用一個想法不同的策略（IDS）代替高斯隨機策略來創建操作符；Jingqian Xue等[4]提出了一種新的基於頭腦風暴過程的多目標優化算法（MOBSO），在目標空間採用了聚類策略，並通過兩種不同的變異運算元——高斯變異和柯西變異產生新個體；史玉回等[5]在原始頭腦風暴優化算法基礎上改進了新個體的生成和選擇策略。首先根據個體在每個維度的動態範圍調整步長，然後用一個批處理模式生成新個體並選擇新個體；楊玉婷等[6]引入分組合作機制以優化算法的實現過程，提出了基於討論機制的頭腦風暴優化算法，同時進一步引入差分步長從而避免算法進入局部最優。頭腦風暴優化算法迅速發展，不同領域都開展了應用研究[712]。
頭腦風暴算法的改進算法依然存在缺點，如執行效率低和收斂速度慢等。為克服此類缺陷，本文將首次定義一個香農多樣性指數來估算樣本群落的多樣性以及均勻性，並對原始頭腦風暴優化算法進行多次初始化，從而有效加快算法後期的收斂性。
1基本頭腦風暴優化算法
頭腦風暴優化（Brain Storm Optimization， BSO）算法是受頭腦風暴過程啟發而產生的優化算法。頭腦風暴過程的核心思想是將一群不同背景的人聚集起來，就同一個問題進行頭腦風暴，為待解決問題提出大量解決方案，最後通過交流及方案的融合共同解決問題。在面對許多問題時，個人的能力有限，但若是由一群來自不同背景的人進行頭腦風暴，通常可以極大程度地提高解決問題的可能性。
基於人類的頭腦風暴過程，史玉回提出了BSO算法。BSO算法過程簡單，算法中的毎個個體都代表一個潛在的問題解，算法包含3個操作：初始化、聚類和更新個體，如圖1所示。
圖1BSO算法流程
BSO算法實現過程中，通過kmeans聚類算法將n個個體聚成m個類；更新個體則根據機率選擇4種方式進行，分別為類中心添加隨機值、個體添加隨機值、兩個類中心融合添加隨機值、兩個隨機個體融合添加隨機值。融合過程可用以下公式表示：
xdcombined=vxd1+（1-v）xd2（1）
式（1）中，xcombined是隨機選中的個體xd1和xd2融合生成的個體，d是d維上的取值；v∈[0，1]是一個符合均勻分布的隨機數。
添加隨機值生成新個體的過程按式（2）進行：
xdnew=xdselect+ξ×n（μ，σ）（2）
式（2）中，xdnew是新生成個體的d維值，xdselect是隨機選中個體的d維值，n（μ，σ）是均值為μ、方差為σ的一個高斯隨機函數，ξ是步長，用來控制隨機擾動幅度。
ξ值按如下公式計算得到：
ξ=logsig0.5Nmax_gen-Ncur_genkrand（）（3）
式（3）中，logsig（）是對數變換函數，k用來控制logsig（）的變化速率， rand（）是0-1之間符合均勻分布的隨機值。
2改進的頭腦風暴算法
在上述基本頭腦風暴算法搜索機制中，初始化步驟僅隨機產生n個個體，這些初始解實際上距離最優解可能有很大的偏離，使得後續的尋優過程很漫長或者幾乎不可達。基於這一考慮，本文將首次引進一個多樣性指數來評估初始種群的多樣性以及均勻性。
新算法根據兩個判定條件選擇出最有潛力或最優秀的初始種群：①種群多樣性，判斷依據是群內類的數目越多，種群多樣性就越複雜，越能夠包容全局最優；②均勻性，用來描述群內各個物種的相對丰度或所占比例，即在類數目相同條件下，群內所有類中的個體數量越均勻越好。
多樣性指數是一個統計量，通常被用來描述一個群落或種群的多樣性。在生態學中，往往使用香農多樣性指數估計群落多樣性，其公式如下：
H=-∑ni=1pilogpi2（4）
式（4）中，n代表種群總數，pi是第i個種群占總種數的比值。種群數越多，或者個體分配越均勻，則多樣性指數越高，對應的群落越優秀。
香農多樣性指數中包含兩個重要部分：種群數目及每個種群之間個體分配的均勻性。H值的大小取決於每個種群之間個體分配是否均勻，均勻性越大H值就越大，反之則越小。因此，上述香農多樣性指數既可以表示種群多樣性，也可以反映種群均勻性。根據這兩個判定條件挑選出相對優秀的初始群，就能確保BSO算法的正確方向和收斂速度，從而平衡控制算法的全局搜索方向和局部搜索能力。
改進後的算法流程如下：①多次初始化並聚類分析；②用多樣性指數估計種群的多樣性和均勻性，挑選出最有潛力的初始種群；③更新個體等後續BSO操作。
3仿真測試與分析
為了評測改進頭腦風暴算法的效果，選取了6個測試函數進行測試，分別為Sphere、Step、Griewank、Rastrigin、Rosenbrock、Schaffer。其中6個經典函數中，Sphere、Step是單模函數，其餘4個函數是多模函數。所採用的6 個測試函數及其值域範圍見表1。
改進算法的主要參數取值與原始BSO算法中對應參數一致，其它參數根據經驗設定，所有參數取值如表2所示。
仿真實驗對6個測試函數進行50次獨立測試，並對所得的優化結果進行對比分析。實驗仿真平台為：Intel（R） Pentium E6500，CPU 主頻2.93GHz，2GB內存，Windows 7 作業系統下的MATLAB 7.8 。 圖2、表3分別為Sphere函數H值曲線對比和6個測試函數的收斂過程對比。可以看出，只要選擇多樣性及均勻性好的初始種群，就能顯著減少疊代次數。
4結語
本文在深入研究原始頭腦風暴算法的基礎上，首次引入香農多樣性指數來選擇初始種群，以便獲得最接近最優解的出發點進行尋優。仿真實驗結果表明，改進的算法能極大提升原始算法的尋優效果，在優化速度和算法穩定性方面有明顯優勢。改進後的算法易於實現，對處理單模問題和多模問題均表現出良好的潛力及可塑性。
參考文獻參考文獻：
[1]SHI Y. Brain storm optimization algorithm[C].Springer Berlin Heidelberg，2011：303309.
[2]SHI Y. An optimization algorithm based on brainstorming process[J].International Journal of Swarm Inteligence Research（IJSIR），2011，2（4）：3562.
[3]ZHAN AH，ZHANG J，SHI YH，et al.A modified brain storm optimization[C]. In IEEE Congress on Evolutionary Computation， Brisbane，QLD，2012：18.
[4]XUE J，WU Y，SHI Y，et al.Brain storm optimization algorithm for multiobjective optimization problems[C].Springer Berlin Heidelberg，2012：513519.
[5]ZHOU D，SHI Y，CHENG S.Brain storm optimization algorithm with modified stepsize and individual generation[C].Springer Berlin Heidelberg，2012：243252.
[6]楊玉婷，史玉回，夏順仁.基於討論機制的頭腦風暴優化算法[J].浙江大學學報：工學版，2013，47（10）：17051711.
[7]SUN C，DUAN H，SHI Y.Optimal satellite formation reconfiguration based on closedloop brain storm optimization[J].IEEE Computational Intelligence Magazine，2013，8（4）：3951.
[8]DUAN H，LI S，SHI Y.Predatorprey based brain storm optimization for DC brushless motor[J].IEEE Transactions on Magnetics，2013，49（10）：53365340.
[9]KENNEDY J， KENNEDY J F， EBERHART R C， et al. Swarm intelligence[M]. Morgan Kaufmann，2001：123265.
[10]余建平，周新民，陳明.群體智能典型算法研究綜述[J].計算機工程與應用，2010，46（25）：7074.
[11]DUAN H，LI S，SHI Y.Predatorprey based brain storm optimization for DC brushless motor[J].IEEE Transactions on Magnetics，2013，49（10）：53365340.
[12]楊玉婷.頭腦風暴優化算法與基於視頻的非接觸式運動定量分析方法研究[D].杭州：浙江大學，2015.
責任編輯（責任編輯：杜能鋼）
摘要：頭腦風暴算法是目前僅有的受人類社會性行為啟發的優化算法，該算法和其它群體智能算法一樣，存在執行效率低和收斂速度慢等缺點。首次定義了一個香農多樣性指數來估算樣本群落的多樣性以及均勻性，並對原始頭腦風暴優化算法進行多次初始化，從而有效加快算法後期的收斂性。利用6個標準測試函數對改進後的算法進行了可行性驗證，統計分析後表明，該算法只要選擇多樣性及均勻性足夠好的初始種群，就能顯著減少疊代次數。改進後的頭腦風暴算法在執行效率和收斂速度上都有所提高。
關鍵詞：頭腦風暴算法；多樣性指數；均勻性；收斂速度
DOIDOI：10.11907/rjdk.172450
中圖分類號：TP312
文獻標識碼：A文章編號文章編號：16727800（2018）003007103
英文摘要Abstract：Brain storm is the only swarm intelligence algorithm with origin from modeling human activities， which can help solve some NP problems but often behaves odd and converges slowly. To overcome its shortcomings， a new idea of diversity index arising from ecology is introduced for brain storm optimization， which will measure diversity and uniformity of a solution group， and help us select a good starting point for optimization. Simulation tests with 6 benchmark functions have been conducted， and results show that the improved brain storm optimization with diversity index can speed up convergence and reduce number of iterations significantly.
英文關鍵詞Key Words：brain storm； diversity index； uniformity； convergence rate
0引言
群體智能算法是一種基於隨機搜索機制的優化方法，具有靈活應對群體內部和外部搜索環境變化的能力，即當搜索條件多變或自身的某些個體失敗時，能夠自組織逃離並發現更優的位置。群體智能算法與傳統的完備算法相比，儘管不一定能找到最優解，但可以確保在短時間內找到較優質的解。由於其在解決優化問題上具有獨特的優勢，群體智能算法應用於很多實際問題中，如機器人控制、無人駕駛交通工具、社會性行為預測、通信網絡加強、醫學圖像處理等。然而這些算法常常存在易陷入局部最優、早熟或收斂過慢等問題。
大多數經典算法是受低等生物的社會性行為啟發的，但長期沒有由人類的社會行為啟發而提出的智能算法。2011年史玉回[12]提出了頭腦風暴優化算法。頭腦風暴優化算法是一種非常有潛力的方法，通常能夠產生超出經典智能算法的結果。
目前，頭腦風暴優化算法的研究與應用還處於初級階段。許多人在過去的幾年中嘗試對頭腦風暴優化算法進行各種研究及改進。史玉回等[3]提出了引入兩種組件提高傳統頭腦風暴優化的性能，第一個組件使用一個簡單分組操作符的分組方法（SGM），代替聚類方法從而減輕算法的計算負擔；第二個組件使用一個想法不同的策略（IDS）代替高斯隨機策略來創建操作符；Jingqian Xue等[4]提出了一種新的基於頭腦風暴過程的多目標優化算法（MOBSO），在目標空間採用了聚類策略，並通過兩種不同的變異運算元——高斯變異和柯西變異產生新個體；史玉回等[5]在原始頭腦風暴優化算法基礎上改進了新個體的生成和選擇策略。首先根據個體在每個維度的動態範圍調整步長，然後用一個批處理模式生成新個體並選擇新個體；楊玉婷等[6]引入分組合作機制以優化算法的實現過程，提出了基於討論機制的頭腦風暴優化算法，同時進一步引入差分步長從而避免算法進入局部最優。頭腦風暴優化算法迅速發展，不同領域都開展了應用研究[712]。
頭腦風暴算法的改進算法依然存在缺點，如執行效率低和收斂速度慢等。為克服此類缺陷，本文將首次定義一個香農多樣性指數來估算樣本群落的多樣性以及均勻性，並對原始頭腦風暴優化算法進行多次初始化，從而有效加快算法後期的收斂性。
1基本頭腦風暴優化算法
頭腦風暴優化（Brain Storm Optimization， BSO）算法是受頭腦風暴過程啟發而產生的優化算法。頭腦風暴過程的核心思想是將一群不同背景的人聚集起來，就同一個問題進行頭腦風暴，為待解決問題提出大量解決方案，最後通過交流及方案的融合共同解決問題。在面對許多問題時，個人的能力有限，但若是由一群來自不同背景的人進行頭腦風暴，通常可以極大程度地提高解決問題的可能性。
基於人類的頭腦風暴過程，史玉回提出了BSO算法。BSO算法過程簡單，算法中的毎個個體都代表一個潛在的問題解，算法包含3個操作：初始化、聚類和更新個體，如圖1所示。
圖1BSO算法流程
BSO算法實現過程中，通過kmeans聚類算法將n個個體聚成m個類；更新個體則根據機率選擇4種方式進行，分別為類中心添加隨機值、個體添加隨機值、兩個類中心融合添加隨機值、兩個隨機個體融合添加隨機值。融合過程可用以下公式表示：
xdcombined=vxd1+（1-v）xd2（1）
式（1）中，xcombined是隨機選中的個體xd1和xd2融合生成的個體，d是d維上的取值；v∈[0，1]是一個符合均勻分布的隨機數。
添加隨機值生成新個體的過程按式（2）進行：
xdnew=xdselect+ξ×n（μ，σ）（2）
式（2）中，xdnew是新生成個體的d維值，xdselect是隨機選中個體的d維值，n（μ，σ）是均值為μ、方差為σ的一個高斯隨機函數，ξ是步長，用來控制隨機擾動幅度。
ξ值按如下公式計算得到：
ξ=logsig0.5Nmax_gen-Ncur_genkrand（）（3）
式（3）中，logsig（）是對數變換函數，k用來控制logsig（）的變化速率， rand（）是0-1之間符合均勻分布的隨機值。
2改進的頭腦風暴算法
在上述基本頭腦風暴算法搜索機制中，初始化步驟僅隨機產生n個個體，這些初始解實際上距離最優解可能有很大的偏離，使得後續的尋優過程很漫長或者幾乎不可達。基於這一考慮，本文將首次引進一個多樣性指數來評估初始種群的多樣性以及均勻性。
新算法根據兩個判定條件選擇出最有潛力或最優秀的初始種群：①種群多樣性，判斷依據是群內類的數目越多，種群多樣性就越複雜，越能夠包容全局最優；②均勻性，用來描述群內各個物種的相對丰度或所占比例，即在類數目相同條件下，群內所有類中的個體數量越均勻越好。
多樣性指數是一個統計量，通常被用來描述一個群落或種群的多樣性。在生態學中，往往使用香農多樣性指數估計群落多樣性，其公式如下：
H=-∑ni=1pilogpi2（4）
式（4）中，n代表種群總數，pi是第i個種群占總種數的比值。種群數越多，或者個體分配越均勻，則多樣性指數越高，對應的群落越優秀。
香農多樣性指數中包含兩個重要部分：種群數目及每個種群之間個體分配的均勻性。H值的大小取決於每個種群之間個體分配是否均勻，均勻性越大H值就越大，反之則越小。因此，上述香農多樣性指數既可以表示種群多樣性，也可以反映種群均勻性。根據這兩個判定條件挑選出相對優秀的初始群，就能確保BSO算法的正確方向和收斂速度，從而平衡控制算法的全局搜索方向和局部搜索能力。
改進後的算法流程如下：①多次初始化並聚類分析；②用多樣性指數估計種群的多樣性和均勻性，挑選出最有潛力的初始種群；③更新個體等後續BSO操作。
3仿真測試與分析
為了評測改進頭腦風暴算法的效果，選取了6個測試函數進行測試，分別為Sphere、Step、Griewank、Rastrigin、Rosenbrock、Schaffer。其中6個經典函數中，Sphere、Step是單模函數，其餘4個函數是多模函數。所採用的6 個測試函數及其值域範圍見表1。
改進算法的主要參數取值與原始BSO算法中對應參數一致，其它參數根據經驗設定，所有參數取值如表2所示。
仿真實驗對6個測試函數進行50次獨立測試，並對所得的優化結果進行對比分析。實驗仿真平台為：Intel（R） Pentium E6500，CPU 主頻2.93GHz，2GB內存，Windows 7 作業系統下的MATLAB 7.8 。 圖2、表3分別為Sphere函數H值曲線對比和6個測試函數的收斂過程對比。可以看出，只要選擇多樣性及均勻性好的初始種群，就能顯著減少疊代次數。
4結語
本文在深入研究原始頭腦風暴算法的基礎上，首次引入香農多樣性指數來選擇初始種群，以便獲得最接近最優解的出發點進行尋優。仿真實驗結果表明，改進的算法能極大提升原始算法的尋優效果，在優化速度和算法穩定性方面有明顯優勢。改進後的算法易於實現，對處理單模問題和多模問題均表現出良好的潛力及可塑性。
參考文獻參考文獻：
[1]SHI Y. Brain storm optimization algorithm[C].Springer Berlin Heidelberg，2011：303309.
[2]SHI Y. An optimization algorithm based on brainstorming process[J].International Journal of Swarm Inteligence Research（IJSIR），2011，2（4）：3562.
[3]ZHAN AH，ZHANG J，SHI YH，et al.A modified brain storm optimization[C]. In IEEE Congress on Evolutionary Computation， Brisbane，QLD，2012：18.
[4]XUE J，WU Y，SHI Y，et al.Brain storm optimization algorithm for multiobjective optimization problems[C].Springer Berlin Heidelberg，2012：513519.
[5]ZHOU D，SHI Y，CHENG S.Brain storm optimization algorithm with modified stepsize and individual generation[C].Springer Berlin Heidelberg，2012：243252.
[6]楊玉婷，史玉回，夏順仁.基於討論機制的頭腦風暴優化算法[J].浙江大學學報：工學版，2013，47（10）：17051711.
[7]SUN C，DUAN H，SHI Y.Optimal satellite formation reconfiguration based on closedloop brain storm optimization[J].IEEE Computational Intelligence Magazine，2013，8（4）：3951.
[8]DUAN H，LI S，SHI Y.Predatorprey based brain storm optimization for DC brushless motor[J].IEEE Transactions on Magnetics，2013，49（10）：53365340.
[9]KENNEDY J， KENNEDY J F， EBERHART R C， et al. Swarm intelligence[M]. Morgan Kaufmann，2001：123265.
[10]余建平，周新民，陳明.群體智能典型算法研究綜述[J].計算機工程與應用，2010，46（25）：7074.
[11]DUAN H，LI S，SHI Y.Predatorprey based brain storm optimization for DC brushless motor[J].IEEE Transactions on Magnetics，2013，49（10）：53365340.
[12]楊玉婷.頭腦風暴優化算法與基於視頻的非接觸式運動定量分析方法研究[D].杭州：浙江大學，2015.
責任編輯（責任編輯：杜能鋼）
收藏