微粒群優化算法簡介

高世博

摘 要：本文簡要介紹了微粒群優化算法的原理，并對算法參數設置、核心思想等進行了分析，對算法在圖像分割應用上的部分改進算法進行了簡述，可為初次接觸、學習、使用微粒群優化算法的研究者算法提供一定的幫助。

關鍵詞：微粒群算法;優化算法;圖像分割

1 引言

微粒群（Particle Swarm Optimization，PSO） 算法，也稱為粒子群算法，是由Eberhart博士和Kennedy博士于基于對鳥群、魚群等生物群體和人類社會行為的研究，在1995年的IEEE國際神經網絡學術會議上提出的一種進化尋優算法。其基本概念源于對鳥群捕食行為簡化社會模型的模擬，后來研究發現PSO是一種很好的優化工具，并被應用到各個領域。

2 微粒群算法原理簡介

PSO算法中，每個優化問題的解都是搜索空間中的一只鳥，稱之為“微粒”。所有的微粒都有一個被優化函數決定的適應度值，每個微粒有一個速度，決定他們飛翔的方向和距離。微粒群體根據自身所處位置，追隨當前的最優微粒在解空間中搜索，達到尋優的目的。以最小優化問題為例，將PSO算法原理簡介如下：

在PSO算法中，微粒的位置代表問題的可能解，通過計算微粒位置的適應度來衡量該位置的優劣。每個微粒根據自身和其它微粒的最佳位置，在解空間中向全局最優位置“飛行”，以搜索問題的最優解。

（4）式確保微粒以一定的速度飛行。

（5）式對微粒位置進行調節。

（6）式確保在指定的解空間中進行搜索。

算法程序結束條件為找到最優解（期望輸出與尋優結果之差小于某一閾值ε）或達到最大迭代次數tmax。

以上各式中t表示迭代次數;ω為慣性權重，取定值或呈線性減少;c1、c2為加速常數，通常在0～2之間取值;r1、r2為兩個相互獨立的生成函數，產生在（0，1）之間的隨機數。

3 微粒群算法參數簡介

PSO算法參數包括群體規模m，慣性權重ω，最大速度Vmax，加速常數c1和c2，最大迭代代數tmax。

群體規模微粒數m：一般取20～40。對于大部分的問題10個微粒已經足夠可以取得好的結果。微粒的范圍由優化問題決定，每一維可設定不同的范圍，對于大規模問題可選取相對大的值。

慣性權重ω ：慣性權重ω控制著微粒的先前速度對當前速度的影響程度，使微粒保持運動的慣性，使其有擴展搜索空間的趨勢，從而有能力探索新的區域。慣性權重ω使算法具有全局搜索的能力，改變其取值可以調整算法全局和局部搜索能力的平衡。

最大速度Vmax ：最大速度決定在當前位置與最優位置之間區域的分辨率，決定微粒在一個循環中最大的移動距離，可以防止計算溢出，通常設定為微粒的范圍寬度。同慣性權重ω一樣，它也起著平衡全局和局部搜索能力的作用。一般將速度限值Vmax，d設置為每維變量的變化范圍。

加速常數c1和c2：加速常數也稱為學習因子，代表將每個微粒推向Pi和Pg位置的統計加速項的權重。低的c1和c2值允許微粒在被拉回來之前可以在目標區域外徘徊，而高的c1和c2值將導致微粒突然的沖向或者越過目標區域。學習因子c1和c2一般相同，范圍在0和4之間。

最大迭代代數tmax ：根據不同的優化問題，為了實現對目標問題的優化，所需要的最大迭代次數也有所不同。合適的迭代次數需要程序設計者對具體解決的問題通過多次實驗來確定。

適應度函數：適應度函數是確定微粒位置優劣的評判標準，根據處理問題的不同，需要選擇的與處理問題相關的適應度函數。

4 微粒群算法核心思想討論

（3）式體現了微粒群優化算法的核心思想，含三部分，第一部分為微粒先前行為的慣性，第二部分為“認知”部分，表示微粒本身的思考;第三部分為“社會”部分，表示微粒間的信息共享與相互合作，對其構成做如下討論。

當c1=0，則微粒沒有認知能力。在微粒的相互作用下，有能力到達新的搜索空間。它的收斂速度比標準版本更快，但是對復雜問題，比標準版本更容易陷入局部優值點。

當c2=0，則微粒之間沒有社會信息共享。因為個體間沒有交互，一個規模為m的群體等價于m個單個微粒的運行，因而得到解的幾率非常小。

當c1=c2= 0，微粒將一直以當前的速度飛行，直到到達邊界。由于它只能搜索有限的區域，將很難找到優化解。

當ω=0，則速度只取決于微粒當前的位置和它們歷史最好位置Pi和Pg，速度本身沒有記憶性，微粒群將收縮到當前的全局最好位置，變成一個局部優化算法，無法實現全局搜索尋優。

5 微粒群改進算法

微粒群算法提出后，在很多領域獲得了廣泛應用，但算法本身存在易早熟、收斂速度慢等不足。在圖像分割處理中，就提出了很多改進算法，并取得了較好的應用效果。

劉洋提出，在算法運行的過程中設置一個輔助最優點Xbest，通過正交試驗產生，用Xbest代替全局最優位置Pg，有效克服了算法搜索速度慢、易陷入局部最優等不足，獲得了較高精度的圖像分割結果。

胥田田等在算法的運行過程中，在每次迭代后的粒子群中設置粒子總數的30%認為是促進粒子群收斂的敏感粒子，根據敏感粒子適應度值與全局粒子適應度均值相比，確定算法是否陷入局部最優和出現早熟現象，從而決定是否需要初始化粒子位置及速度。結果表明此改進算法有效改善了標準粒子群算法難收斂、易早熟的缺點，在鐵軌異物圖像的分割應用中取得良好效果。

6 結束語

本文簡要介紹了微粒群優化算法的原理、參數設置、核心理念及其在圖像分割應用上的一些改進算法，希望對初次接觸粒子群優化算法的研究者學習、使用微粒群優化算法提供一定幫助。

參考文獻

[1]Kennedy J，Eberhart R.C.Particle Swarm Optimization [C].In： proc.IEEE Intl.conf.On Neural Networks，IV.Piscataway，NJ：IEEE Service Center，1995：1942-1948.

[2]武飛周，薛源.智能算法綜述 [J].工程地質計算機應用，2005，（2）：9-15.

[3]曾建潮，介倩，崔志華.微粒群算法[M].北京：科學出版社，2004：12-53.

[4]沈洪遠，彭小奇，王俊年，等.基于混沌序列的多峰函數微粒群尋優算法 [J].計算機工程與應用，2006，（7）：36-38.

[6]謝曉鋒，張文俊，楊之廉.微粒群算法綜述[J].控制與決策，2003，18（2）：129-134.

[5]Shi Y，Eberhart R C.Parameter selection in particle swarm optimization [C].In：Evolutionary programming VII： Proc.Ep98.New York：Springer-Verlag，1998：591-600.

[7]Kennedy J.Thinking is social： experiments with the adaptive culture model [J].Journal of conflict resolution，1998，42（1）：56-76.

[8]劉洋.基于改進粒子群優化算法的圖像分割[J].吉林大學學報（理學版），2018，56（4）：956-964.

[9]胥田田，李積英，任臻，等.粒子群優化的改進Tsallis熵圖像閾值分割[J].森林工程，2019，35（1）：47-52.