摘 要粒子群優化(PSO)算法是一種新穎的演化算法，該算法通過粒子間的相互作用在複雜搜索空間中發現最優區域。PSO的優勢在於簡單而功能強大。本文介紹了基本的PSO算法、 研究 現狀及其在神經 網絡 中的 應用 ，並探討了未來的研究 內容 及 發展 方向。
關鍵詞粒子群優化算法；神經網絡；人工生命；群智能
許多群體生物的自適應優化現象不斷給人類以啟示，群居生物的群體行為使許多在人類看起來高度複雜的 問題 得到了完美的解決。 自然 界那些群居生物表現出來的智能讓人驚嘆不已，比如蜜蜂建造的巢穴結構龐大、複雜而精美；螞蟻能夠完成覓食、清掃、搬運等高效的工作等等。這種生物群體行為的奇妙之處在於個體都很簡單，但他們卻能協同工作，依靠群體的能力，發揮超出個體的智能，表現出極其複雜而有序的行為。這些奇妙的現象吸引著越來越多的學者進入到這個領域，研究這些簡單的個體如何通過協作湧現出如此複雜而奇妙行為，通過 計算 機模擬來探索其中的可循 規律 ，用於指導並解決一些常規 方法 沒有解決的傳統問題以及實際應用中出現的新問題[1-3]。這些研究孕育並產生了一門新興的學科領域：群體智能(Swarm Intelligence)[1]。優化技術是一種以各種形式的數學處理方法為基礎，用於求解各種工程問題優化解的應用技術，在諸多工程領域得到普遍的應用。鑒於實際工程問題的複雜性、約束性、非線性、多局部極小和建模困難等特點，尋找各種適合於工程實踐需求的新型智能優化方法一直是許多學科的一個重要研究方向。群體智能作為一種新興的智能計算技術已成為越來越多研究者的關注焦點，它與人工生命，特別是進化策略以及遺傳算法有著特殊的聯繫。群體智能使得在沒有集中控制且不提供全局模型的前提下，為尋找複雜的分布式問題的解決方案提供了基礎。
微粒群算法[2]最初是為了圖形化地模擬鳥群優美而不可預測的運動。自然界中，鳥群運動的主體是離散的，其排列看起來是隨機的，但整體的運動卻使它們保持著驚人的同步性，個體運動非常流暢而極富美感。研究者對鳥群的運動進行了計算機仿真，他們通過對個體設定簡單的運動規則，來模擬鳥群整體的複雜行為。例如，1986年Craig Reynolds提出了Boid模型用以模擬鳥類聚集飛行的行為，通過對現實世界中這些群體運動的觀察在計算機中複製重建這些運動軌跡，並對這些運動進行抽象建模以發現新的運動模式。上述模型關鍵在於對個體間距離的操作，即群體行為的同步性在於個體努力維持自身與鄰居之間的距離為最優，為此每個個體必須知道自身位置和鄰居的信息。生物 社會 學家Wilson E.O.認為 「至少從 理論 上，在搜索食物的過程中群體中的個體成員可以得益於所有其它成員的發現和先前的經歷。當食物源不可預測地零星分布時，這種協作帶來的優勢是決定性的，遠大於對食物的競爭帶來的劣勢。」以上兩例說明，群體中個體之間信息的社會共享有助於進化。受上述鳥群運動模型的 影響 ，社會心 理學 博士JamesK Ennedy和 電子 工程學博士Russell Eberhart於1995年提出了微粒群算法，微粒群算法是一種演化計算技術，在算法中，將鳥群運動模型中的棲息地類比於所求問題解空間中可能解的位置，通過個體間的信息傳遞，導引整個群體向可能解的方向移動，增加發現較好解的可能性。群體中的鳥被抽象為沒有質量和體積的「微粒」，通過這些「微粒」的相互協作和信息共享，其運動速度受到自身和群體的 歷史 運動狀態信息影響，以自身和群體的歷史最優位置來對微粒當前的運動方向和運動速度加以影響，較好地協調微粒本身和群體運動之間的關係，在複雜的解空間中尋找最優解。
微粒群算法自提出以來，已經歷了許多變形和改進。包括數學家、工程師、物理學家、生物化學家以及心理學家在內的研究者對它進行 分析 和實驗。到 目前 為止，國內外的研究者對微粒群算法的研究與發展，可以歸納為以下幾個方面：[3]
(1) 參數選擇與設計：在微粒群算法中存在幾個顯參數和隱參數，它們的值可被調整，以產生算法搜索問題空間的方式的變化。
(2) 種群拓撲結構：從19世紀40年代起的研究已經表明，組內的交流及最終組的性能要受社會網絡結構的影響。於是，微粒群研究者提出了幾種簡單的社會結構，並對幾種種群結構模型進行了分析與比較。全局最優模型(Gbest)和局部最優模型(Lbest) 是最常見的兩種類型。
(3) 群體組織與進化[4]：社會心理學研究表明。人們的態度、信仰和行為傾向於朝同伴的方向變化，他們會根據自己所處群體的規範選擇自己的意見和行為，受此啟發，提出用簇來表示群體中的子種群，用簇中心代替最優值的算法模式。此外，為了保證群體的多樣性，研究者將變異、繁殖和差異進化等思想引入微粒群，並提出了很多改進算法模式。
(4) 混合微粒群算法：將進化計算中的選擇、交叉和變異等特性、混沌、免疫系統的免疫信息處理機制以及熱力學中熵的概念等與微粒群算法中的尋優機制相結合，提出了相應的混合算法。
(5) 離散微粒群算法：微粒群算法最初是用來對連續函數進行優化的。而實際中許多問題是組合優化問題，因此，Kennedy和Eberhart博士在基本算法的基礎上提出了一種離散二進制決策模型。
PSO算法不像遺傳算法那樣對個體進行選擇、交叉和變異操作，而是將群體中的每個個體視為多維搜索空間中一個沒有質量和體積的粒子(點)，這些粒子在搜索空間中以一定的速度飛行，並根據粒子本身的飛行經驗以及同伴的飛行經驗對自己的飛行速度進行動態調整，即每個粒子通過統計疊代過程中自身的最優值和群體的最優值來不斷地修正自己的前進方向和速度大小，從而形成群體尋優的正反饋機制。PSO算法就是這樣依據每個粒子對環境的適應度將個體逐步移到較優的區域，並最終搜索、尋找到問題的最優解。設在一個d維的目標搜索空間中，有m個粒子組成一個群體，其中，在第t次疊代時粒子i的位置表示為Xi(t)=(xi1(t)，xi2(t)，...，xid(t))，相應的飛行速度表示為Vi(t)=(vi2(t)，vi2(t)， ...，vid(t))。開始執行PSO算法時，首先隨機初始化m個粒子的位置和速度，然後通過疊代尋找最優解，在每一次疊代中，粒子通過跟蹤兩個極值來更新自己的速度和位置：一個極值是粒子本身迄今搜索到的最優解，稱為個體極值，表示為Pi(t)=(pi1(t)，pi2(t)，...，pid (t))；另一個極值是整個粒子群到目前為止找到的最優解，稱為全局極值，表示為Pg(t)=(pg1 (t)，pg2(t)，...，pgd(t))。在第（t+1）次疊代計算時，粒子i根據下列規則來更新自己的速度和位置[5]：
Vik(t+l)=ωVik(t)+c1randl(Pik(t)-Xik(t))+c2rand2(Pgk(t)-Xik(t)) (1)
Xik(t+l)=Xik(t)+Vik(t+l) (2)
式中ω為慣性權重，ω取大值可使算法具有較強的全局搜索能力，ω取小值則算法傾向於局部搜索。一般的做法是將ω初始取0.9並使其隨疊代次數的增加而線性遞減至0.4，這樣就可以先側重於全局搜索，使搜索空間快速收斂於某一區域，然後採用局部精細搜索以獲得高精度的解；c1，c2為兩個 學習 因子，一般取為2；randl和rand2為兩個均勻分布在(0，l)之間的隨機數；i=1，2，⋯，m； k=1，2，⋯，d。另外，粒子在每一維的速度Vi都被一個最大速度Vmax所限制。如果當前粒子的加速度導致它在某一維的速度超過該維上的最大速度Vmax，則該維的速度被限制為最大速度。
科學 研究與工程實踐中有一些多目標優化問題[5](Multi - objective Optimization Problems， MOPs)通常難以處理，實際問題常由多個相互衝突的指標組成，問題的解一般不是單個的最優解，而是一組非劣解，因而採用傳統多目標優化方法通常無法解決。由於PSO算法的生命力在於工程應用，為此開拓新的PSO算法的應用領域特別是在解決多目標優化問題上是一項很有意義的工作。
轉貼於論文聯盟 http://www.lwlm.com
關鍵詞粒子群優化算法；神經網絡；人工生命；群智能
1 引言
許多群體生物的自適應優化現象不斷給人類以啟示，群居生物的群體行為使許多在人類看起來高度複雜的 問題 得到了完美的解決。 自然 界那些群居生物表現出來的智能讓人驚嘆不已，比如蜜蜂建造的巢穴結構龐大、複雜而精美；螞蟻能夠完成覓食、清掃、搬運等高效的工作等等。這種生物群體行為的奇妙之處在於個體都很簡單，但他們卻能協同工作，依靠群體的能力，發揮超出個體的智能，表現出極其複雜而有序的行為。這些奇妙的現象吸引著越來越多的學者進入到這個領域，研究這些簡單的個體如何通過協作湧現出如此複雜而奇妙行為，通過 計算 機模擬來探索其中的可循 規律 ，用於指導並解決一些常規 方法 沒有解決的傳統問題以及實際應用中出現的新問題[1-3]。這些研究孕育並產生了一門新興的學科領域：群體智能(Swarm Intelligence)[1]。優化技術是一種以各種形式的數學處理方法為基礎，用於求解各種工程問題優化解的應用技術，在諸多工程領域得到普遍的應用。鑒於實際工程問題的複雜性、約束性、非線性、多局部極小和建模困難等特點，尋找各種適合於工程實踐需求的新型智能優化方法一直是許多學科的一個重要研究方向。群體智能作為一種新興的智能計算技術已成為越來越多研究者的關注焦點，它與人工生命，特別是進化策略以及遺傳算法有著特殊的聯繫。群體智能使得在沒有集中控制且不提供全局模型的前提下，為尋找複雜的分布式問題的解決方案提供了基礎。
2 PSO的產生與發展
2.1 微粒群算法的起源
微粒群算法[2]最初是為了圖形化地模擬鳥群優美而不可預測的運動。自然界中，鳥群運動的主體是離散的，其排列看起來是隨機的，但整體的運動卻使它們保持著驚人的同步性，個體運動非常流暢而極富美感。研究者對鳥群的運動進行了計算機仿真，他們通過對個體設定簡單的運動規則，來模擬鳥群整體的複雜行為。例如，1986年Craig Reynolds提出了Boid模型用以模擬鳥類聚集飛行的行為，通過對現實世界中這些群體運動的觀察在計算機中複製重建這些運動軌跡，並對這些運動進行抽象建模以發現新的運動模式。上述模型關鍵在於對個體間距離的操作，即群體行為的同步性在於個體努力維持自身與鄰居之間的距離為最優，為此每個個體必須知道自身位置和鄰居的信息。生物 社會 學家Wilson E.O.認為 「至少從 理論 上，在搜索食物的過程中群體中的個體成員可以得益於所有其它成員的發現和先前的經歷。當食物源不可預測地零星分布時，這種協作帶來的優勢是決定性的，遠大於對食物的競爭帶來的劣勢。」以上兩例說明，群體中個體之間信息的社會共享有助於進化。受上述鳥群運動模型的 影響 ，社會心 理學 博士JamesK Ennedy和 電子 工程學博士Russell Eberhart於1995年提出了微粒群算法，微粒群算法是一種演化計算技術，在算法中，將鳥群運動模型中的棲息地類比於所求問題解空間中可能解的位置，通過個體間的信息傳遞，導引整個群體向可能解的方向移動，增加發現較好解的可能性。群體中的鳥被抽象為沒有質量和體積的「微粒」，通過這些「微粒」的相互協作和信息共享，其運動速度受到自身和群體的 歷史 運動狀態信息影響，以自身和群體的歷史最優位置來對微粒當前的運動方向和運動速度加以影響，較好地協調微粒本身和群體運動之間的關係，在複雜的解空間中尋找最優解。
2.2 微粒群算法的發展
微粒群算法自提出以來，已經歷了許多變形和改進。包括數學家、工程師、物理學家、生物化學家以及心理學家在內的研究者對它進行 分析 和實驗。到 目前 為止，國內外的研究者對微粒群算法的研究與發展，可以歸納為以下幾個方面：[3]
(1) 參數選擇與設計：在微粒群算法中存在幾個顯參數和隱參數，它們的值可被調整，以產生算法搜索問題空間的方式的變化。
(2) 種群拓撲結構：從19世紀40年代起的研究已經表明，組內的交流及最終組的性能要受社會網絡結構的影響。於是，微粒群研究者提出了幾種簡單的社會結構，並對幾種種群結構模型進行了分析與比較。全局最優模型(Gbest)和局部最優模型(Lbest) 是最常見的兩種類型。
(3) 群體組織與進化[4]：社會心理學研究表明。人們的態度、信仰和行為傾向於朝同伴的方向變化，他們會根據自己所處群體的規範選擇自己的意見和行為，受此啟發，提出用簇來表示群體中的子種群，用簇中心代替最優值的算法模式。此外，為了保證群體的多樣性，研究者將變異、繁殖和差異進化等思想引入微粒群，並提出了很多改進算法模式。
(4) 混合微粒群算法：將進化計算中的選擇、交叉和變異等特性、混沌、免疫系統的免疫信息處理機制以及熱力學中熵的概念等與微粒群算法中的尋優機制相結合，提出了相應的混合算法。
(5) 離散微粒群算法：微粒群算法最初是用來對連續函數進行優化的。而實際中許多問題是組合優化問題，因此，Kennedy和Eberhart博士在基本算法的基礎上提出了一種離散二進制決策模型。
3 PSO的基本原理
PSO算法不像遺傳算法那樣對個體進行選擇、交叉和變異操作，而是將群體中的每個個體視為多維搜索空間中一個沒有質量和體積的粒子(點)，這些粒子在搜索空間中以一定的速度飛行，並根據粒子本身的飛行經驗以及同伴的飛行經驗對自己的飛行速度進行動態調整，即每個粒子通過統計疊代過程中自身的最優值和群體的最優值來不斷地修正自己的前進方向和速度大小，從而形成群體尋優的正反饋機制。PSO算法就是這樣依據每個粒子對環境的適應度將個體逐步移到較優的區域，並最終搜索、尋找到問題的最優解。設在一個d維的目標搜索空間中，有m個粒子組成一個群體，其中，在第t次疊代時粒子i的位置表示為Xi(t)=(xi1(t)，xi2(t)，...，xid(t))，相應的飛行速度表示為Vi(t)=(vi2(t)，vi2(t)， ...，vid(t))。開始執行PSO算法時，首先隨機初始化m個粒子的位置和速度，然後通過疊代尋找最優解，在每一次疊代中，粒子通過跟蹤兩個極值來更新自己的速度和位置：一個極值是粒子本身迄今搜索到的最優解，稱為個體極值，表示為Pi(t)=(pi1(t)，pi2(t)，...，pid (t))；另一個極值是整個粒子群到目前為止找到的最優解，稱為全局極值，表示為Pg(t)=(pg1 (t)，pg2(t)，...，pgd(t))。在第（t+1）次疊代計算時，粒子i根據下列規則來更新自己的速度和位置[5]：
Vik(t+l)=ωVik(t)+c1randl(Pik(t)-Xik(t))+c2rand2(Pgk(t)-Xik(t)) (1)
Xik(t+l)=Xik(t)+Vik(t+l) (2)
式中ω為慣性權重，ω取大值可使算法具有較強的全局搜索能力，ω取小值則算法傾向於局部搜索。一般的做法是將ω初始取0.9並使其隨疊代次數的增加而線性遞減至0.4，這樣就可以先側重於全局搜索，使搜索空間快速收斂於某一區域，然後採用局部精細搜索以獲得高精度的解；c1，c2為兩個 學習 因子，一般取為2；randl和rand2為兩個均勻分布在(0，l)之間的隨機數；i=1，2，⋯，m； k=1，2，⋯，d。另外，粒子在每一維的速度Vi都被一個最大速度Vmax所限制。如果當前粒子的加速度導致它在某一維的速度超過該維上的最大速度Vmax，則該維的速度被限制為最大速度。
4 PSO在神經網絡中的應用
科學 研究與工程實踐中有一些多目標優化問題[5](Multi - objective Optimization Problems， MOPs)通常難以處理，實際問題常由多個相互衝突的指標組成，問題的解一般不是單個的最優解，而是一組非劣解，因而採用傳統多目標優化方法通常無法解決。由於PSO算法的生命力在於工程應用，為此開拓新的PSO算法的應用領域特別是在解決多目標優化問題上是一項很有意義的工作。
轉貼於論文聯盟 http://www.lwlm.com
收藏