【文章內(nèi)容簡介】 研究分支。據(jù)不完全統(tǒng)計，短短十幾年的時間，國外針對粒子群算法研究已完成的博士論文就達十余篇之多；在IEEE的國際學術會議上，有20篇左右的論文均是反映粒子群算法的研究成果的。國內(nèi)在該領域的研究剛剛起步，深入的研究和應用還很少，已發(fā)表的論文也不多PSO算法的研究還有大量工作要做，主要的研究方向如下幾個方面：1）粒子群算法的改進粒子群算法由于算法原理簡單，存在早熟收斂和穩(wěn)定性差的問題，如何改進算法以預防早熟收斂和提高算法穩(wěn)定性值得深入研究。2）粒子群算法的理論分析到目前為止，PSO算法的分析方法還很不成熟，存在許多不完善之處。如何利用有效數(shù)學工具對PSO算法的運行行為、收斂性以及計算復雜性進行分析也是目前的研究熱點之一。3）粒子群算法與其他進化算法的比較、融合目前，進化算法的研究在理論和應用兩方面都得到迅速發(fā)展，效果顯著。其中比較成熟的有遺傳算法、蟻群算法等，而粒子群算法是一個新興的群體智能算法，目前已成為今后算法的一個重要分支，如何從多方面比較各種算法從而得到各自的特長和不足，如何吸引其他進化類算法的優(yōu)勢來彌補PSO算法的不足也是當前研究的熱點之一。4）粒子群算法的應用算法研究的目的是應用，如何將PSO算法應用于更多領域，同時研究應用中存在的問題也是值得關注的熱點。 粒子群算法的主要應用粒子群算法由于計算快速和本身的易實現(xiàn)性，一經(jīng)提出就受到了廣泛關注，各種關于粒子群算法應用研究的成果不斷涌現(xiàn)。研究發(fā)現(xiàn)，粒子群算法在求解非線性連續(xù)優(yōu)化問題、組合優(yōu)化問題和混合整數(shù)非線性優(yōu)化問題時非常有效，目前已廣泛應用于：函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡訓練、工程應用等方面，取得了不錯的效果。1） 函數(shù)優(yōu)化許多實際的工程問題本質(zhì)上是函數(shù)優(yōu)化問題或可以轉換為函數(shù)優(yōu)化問題進行求解，對于函數(shù)優(yōu)化已經(jīng)有一些成熟的解決方法如遺傳算法。但是對于超高維、多局部極值的復雜函數(shù)而言，遺傳算法往往在優(yōu)化的收斂速度和精度上難以達到期望的要求。Angeline經(jīng)過大量的使用研究發(fā)現(xiàn)，粒子群優(yōu)化算法在解決一些典型的函數(shù)優(yōu)化問題時，能夠取得比遺傳算法更好的優(yōu)化結果[14]。Shi與Eberhart的實驗證明，對大多數(shù)的非線性Benehmark函數(shù)，PSO在優(yōu)化速度和精度上均較遺傳算法有一定的改善，這說明粒子群算法在解決函數(shù)優(yōu)化時同樣具有很好的應用前景。2） 神經(jīng)網(wǎng)絡訓練工業(yè)、經(jīng)濟、醫(yī)療等領域的許多實際問題如質(zhì)量控制、破產(chǎn)預測、圖像識別、醫(yī)療診斷等可以轉換為模式分類問題求解。神經(jīng)網(wǎng)絡自學習、自組織、容錯以及模擬非線性關系的能力使其特別適合解決上述復雜的實際應用問題。神經(jīng)網(wǎng)絡的訓練問題屬于非線性的高復雜度的優(yōu)化問題。研究表明，PSO是一種很有潛力的神經(jīng)網(wǎng)絡訓練算法，粒子群優(yōu)化算法保留了基于種群的、并行的全局搜索策略，其采用的速度位移模型操作簡單，避免了復雜的遺傳操作，在實際應用問題（如運用PSO算法訓練神經(jīng)網(wǎng)絡進行醫(yī)療診斷）取得了較高的成功率，目前正在將其推廣到更多的應用領域。3） 工程應用實際的工程問題往往可以轉化為函數(shù)優(yōu)化問題求解。下面簡要介紹粒子群算法在一些實際工程領域的應用。首先，通過訓練神經(jīng)網(wǎng)絡，粒子群優(yōu)化算法已成功應用到對醫(yī)學中震顫的分析。震顫行為的診斷仍是醫(yī)學研究的挑戰(zhàn)性領域之一。經(jīng)粒子群算法訓練的人工神經(jīng)網(wǎng)絡已經(jīng)能夠區(qū)分人的本能震顫和病理性震顫。Eberhart和Hu研究發(fā)現(xiàn)，這種方法在上述的應用中處理速度快，診斷結果準確。在其他疾病的診斷如乳腺腫瘤良性或惡性的判斷，心臟病的診斷，粒子群算法訓練的神經(jīng)網(wǎng)絡也取得了較高的診斷成功率。其次，日本的Fuji電力公司的研究人員將電力企業(yè)著名的RPVC（Reactive Power and Voltage Control）問題簡化為函數(shù)優(yōu)化問題，并使用改進的粒子群算法進行優(yōu)化求解。與傳統(tǒng)方法如專家系統(tǒng)、敏感性分析相比，實驗結果證明粒子群算法在解決該題上具有一定的優(yōu)勢。此外，粒子群算法已被美國一家公司用于各種生物化學成分的優(yōu)化組合，進而人工合成微生物。與傳統(tǒng)的工業(yè)優(yōu)化方法比較，粒子群算法產(chǎn)生合成結果的適應度是傳統(tǒng)方法的兩倍。實驗充分顯示粒子群算法的優(yōu)越性：盡管劣質(zhì)成分在一定的迭代代數(shù)內(nèi)能夠影響優(yōu)化搜索的進程，但由于粒子群算法能夠搜索到更大范圍內(nèi)的優(yōu)化問題的解空間，合成結果總能比較理想?？偟膩碚f，粒子群優(yōu)化算法與其他進化算法一樣，可以解決大部分的優(yōu)化問題，或可以轉換為優(yōu)化問題進行求解的問題。目前，在模糊控制器的設計、車間任務調(diào)度、實時機器人路徑規(guī)劃、圖像分割、EEG信號模擬、語音識別、燒傷診斷以及探測移動目標等方面已經(jīng)有成功應用的先例。 本章小結本章詳細介紹了粒子群算法的起源背景、基本思想以及基本粒子群算法的實現(xiàn)，最后簡單介紹了該算法的主要應用及其研究方向。但是通過研究發(fā)現(xiàn)，作為一種新興的智能優(yōu)化算法，基本粒子群還存在早熟收斂和穩(wěn)定性差的不足，有必要對其進行改進，進一步地探討與研究。第三章 改進的粒子群算法 引言針對基本粒子群算法早熟收斂和穩(wěn)定性差的缺點，基于不同的策略，已產(chǎn)生大量改進的粒子群優(yōu)化算法。從根本上來說，大多數(shù)改進方案都基于與其他優(yōu)化算法結合的改進，是以大幅度提高算法理解的難度和實現(xiàn)的復雜度為代價的，這就使得粒子群優(yōu)化算法失去了一些誘人的核心優(yōu)點，如理解的簡單性、實現(xiàn)的簡潔性等，這對該算法的大面積工程應用是有所不利的。因此，以改進粒子群算法為出發(fā)點尋找盡量簡單有效的改進粒子群算法，是十分必要和有意義的。 改進的粒子群算法綜述對粒子群算法的改進主要集中在對參數(shù)的改進以及算法融合兩個方面。對參數(shù)的改進包括對慣性權值、學習因子和、每一代粒子的飛行時間等的調(diào)整。對于算法融合方面，許多學者嘗試了將粒子群算法與其他智能計算方法相融合，有結合遺傳算法交叉算子的混合粒子群優(yōu)化算法[14]、基于模擬退火的粒子群算法[32]、免疫粒子群算法[35]、基于群體適應度方差自適應變異的粒子群算法[37]、與差別進化相結合的粒子群算法[48]等，下面簡要介紹粒子群算法的幾類改進算法。1）慣性權重法粒子群優(yōu)化算法以種群行為來激勵粒子的運動。每個潛在的解與粒子的速度相聯(lián)系，該速度不斷地根據(jù)粒子自身經(jīng)驗和粒子的社會經(jīng)驗來調(diào)整大小、方向，總是希望粒子能朝更好的方向運動。在搜索過程中，全局搜索能力和局部搜索能力的平衡關系對于算法的性能起著舉足輕重的作用。初始時，Shi將慣性權值取值定為常數(shù)，但后來實驗發(fā)現(xiàn)，較大的值有利于跳出局部極小點，較小的值有利于算法的收斂，而動態(tài)的慣性權重能夠取得比固定值更好的尋優(yōu)結果?，F(xiàn)在采用較多的是Shi建議的線性遞減權重（LDW）策略， 速度更新公式在式（21）的基礎上加上慣性權值，調(diào)整為式（31）（32）所示。 （31） （32）式中，為初始慣性權重；為最終慣性權重；為最大迭代次數(shù)；為當前迭代次數(shù)。在算法初期，取值較大，有利于粒子探索未知區(qū)域，擴大搜索空間。在算法后期收斂的情況下，取值較小，有利于微調(diào)對最優(yōu)區(qū)域周圍的搜索，從而提高了搜索的精度。典型取值=、=，但是還有兩個缺點：其一迭代初期局部搜索能力較弱，即使初始粒子已接近于全局最優(yōu)點，也往往錯過，而在迭代后期，則因全局搜索能力變?nèi)酰紫萑刖植繕O值。其二最大迭代次數(shù)較難預測,從而將影響算法的調(diào)節(jié)功能。2001年Shi又提出用模糊規(guī)則動態(tài)地修改值和隨機慣性權重（RIW）取值策略。張選平等提出了一種動態(tài)的改變慣性權值（Dynamically Changing Weight,DCW）的粒子群算法。在該算法中，慣性權重的變化受算法運行態(tài)勢影響，是由粒子群的進化速度和粒子群的聚集度綜合決定的。與LDW算法相比，平均迭代次數(shù)至少平均降低25%，收斂速度和收斂精度都明顯提高。陳貴敏等在LDW的基礎上，又給出了三種非線性的慣性權重遞減策略，發(fā)現(xiàn)對于多數(shù)連續(xù)優(yōu)化問題，凹函數(shù)遞減策略優(yōu)于線性策略，而線性策略優(yōu)于凸函數(shù)策略。帶慣性權值的粒子群算法在剛開始的時候傾向于開掘，然后逐漸轉向于開拓，從而在局部區(qū)域調(diào)整解。這是目前使用最廣泛的粒子群算法形式。2）收縮因子法Clerc[41]的研究表明使用收縮因子可以保證粒子群算法收斂。收縮因子是關于、的函數(shù)，定義的公式如式（33）、（34）所示。 （33） （34）。相當于在速度更新公式中。收縮因子法可使粒子軌跡最終收斂，且可以有效搜索不同的區(qū)域，能得到高質(zhì)量的解，若與此同時將每維的最大速度設置為一維搜索空間的大小，則可得到更好的效果。但是，收縮因子法在處理單峰函數(shù)或者其它比較光滑的較為簡單的函數(shù)時，比起基本粒子群算法，收斂速度稍微慢一點。3）基于學習因子和的改進學習因子和代表了粒子向自身極值和全局極值推進的隨機加速權值。小的加速常數(shù)值，可使粒子在遠離目標區(qū)域內(nèi)振蕩；而大的加速常數(shù)可使粒子迅速向目標區(qū)域移動，甚至又離開目標區(qū)域。如果，則粒子將以當前速度飛行，直到邊界。此時，由于粒子只能搜索有限的區(qū)域，故很難找到好解。當則粒子沒有自身認知能力，亦即“只有社會（socialonly）認知”的模型。在粒子相互作用下，算法有能力達到新的搜索空間。其收斂速度比標準算法更快，但碰到復雜問題，比標準算法更容易陷入局部極值點。當，則粒子之間沒有社會信息共享，亦即“只有自身認知（cognitiononly）”的模型。由于個體之間沒有交互，一個規(guī)模為的群體等價于個單個粒子的運行，因而得到最優(yōu)解的概率非常小。Shi和Eberhar建議，為了平衡隨機因素的作用，通常設，后來Clerc推導出，也有研究者認為和不等，并由實驗得出。Ratnaweera等采用了根據(jù)迭代次數(shù)來動態(tài)地修改加速因子的方法，模擬實驗結果表明，，算法所獲得適應值最優(yōu)。這種方法確實加速了算法的收斂，尤其在單峰值函數(shù)的測試表現(xiàn)突出。為此付出的代價是算法容易陷入局部最小值，在多峰值函數(shù)的測試中容易過早收斂。但是，實際上這些研究也僅僅局限于部分問題的應用，無法推廣到所有問題域。4）小生境粒子群算法粒子群算法啟發(fā)性強、收斂速度快，使得粒子在尋優(yōu)時過分集中，最后粒子都移向全局最優(yōu)點，不能用于多模態(tài)函數(shù)優(yōu)化。2002年Brits等[50]將小生境技術引入粒子群優(yōu)化算法中，小生境法除去影響粒子間信息交流的“社會部分”，增強粒子局部搜索能力，每個粒子飛向離它最近的山峰，即形成小生境。小生境粒子群算法速度更新公式如式（35）所示。 （35）小生境粒子群法收斂速度較慢，主要應用于多峰函優(yōu)化，對單峰函數(shù)效果不佳。5）自適應調(diào)整飛行時間基本粒子群算法在解空間搜索時，每代粒子的飛行時間恒為1，有時會導致粒子在最優(yōu)解的附近來回“振蕩”現(xiàn)象[51]。自適應調(diào)整飛行時間法動態(tài)調(diào)整飛行時間，隨著迭代代數(shù)的增加，飛行時間線性減少。具體調(diào)整公式如式（36）、（37）所示。 （36） （37）式中，表示第代粒子的飛行時間；表示粒子最長飛行時間；為比例系數(shù)，起調(diào)節(jié)作用。自適應調(diào)整飛行時間法適用于復雜函數(shù)，最優(yōu)值處在狹長或陡峭的山峰上。但是對于簡單函數(shù)后期收斂速度較慢。6）算法融合Angeline[52]將選擇算子引入粒子群算法中，選擇每次迭代后較好的粒子復制到下一代，以保證每次迭代的粒子群都具有良好的性能，這種算法對某些單峰函數(shù)效果良好。Lvbjerg[53]在粒子群每次迭代后，按幾率在粒子間交換各維，通過交叉來生成更優(yōu)秀的粒子群算法對某些多峰函數(shù)效果較好。Higash[54]等人分別提出了自己的變異粒子群算法，基本思路均是希望通過引入變異算子跳出局部極值點的吸引，從而提高算法的全局搜索能力，得到較高的搜索成功率。高鷹等人則引入免疫機制的概念，提高粒子群的多樣性和自我調(diào)節(jié)能力，以增強粒子的全局搜索能力。Baskar等人提出了協(xié)同粒子群算法，通過使用多群粒子分別優(yōu)化問題的不同維來對基本算法進行改進嘗試。另外，還出現(xiàn)了一些量子粒子群算法、基于模擬退火的粒子群算法以及求解幾何約束問題的粒子群算法等。以上改進算法各有優(yōu)缺點，它們引入了一些新的參數(shù)，在改進算法性能的同時也一定程度上增加了算法的復雜性。(粒子群算法及應用P19)為了改善基本粒子群算法的性能，Shi和Eberhart在1998年的IEEE國際進化計算學術會議上發(fā)表了題為“A modified particle swarm optimizer”的理論，引入了慣性權重，逐漸地大家都默認這個改進粒子群算法為“標準粒子群算法”。 算法思想在基本粒子群算法的速度公式上包括三部分：第一部分是粒子調(diào)整前的速度；第二部分和第三部分是對粒子速度的調(diào)整。如果沒有后面兩部分，粒子將會保持相同的速度朝一個方向飛行，直到到達邊界，這樣粒子很大可能會找不到最優(yōu)解，除非最優(yōu)解恰好在粒子直線飛行的軌跡上，但這種情況是很少的。如果沒有第一部分，粒子的飛行速度將僅由它們當前位置和歷史最好位置決定，則速度本身是無記憶的，無法將優(yōu)質(zhì)信息保留。假定剛開始粒子處于較優(yōu)位置，那么粒子的飛行速度將會是0，即它會保持靜止狀態(tài)，直到其他粒子找到比粒子所處位置還要好的解，從而替代了全局最優(yōu)解。此時，每個粒子將會飛向它自身最好位置和群體全局最好位置的權重中心。所以如果沒有第一部分，粒子群算法的搜索空間將會隨著進化而收縮。此時只有當全局最優(yōu)解在初始搜索區(qū)間時，粒子群算法才可能找到解。所以求解結果非常依賴于初始群體。當沒有第一部分時，此算法更像是局部最優(yōu)算法。對于不同的問題，局部最優(yōu)能力和全局最優(yōu)能力的權衡也不一樣?？紤]到這個問題，并結合以上的討論，Shi和Eberhart添加了一個慣性權重到速度更新公式，即式(32)。 （32）位置更新公式與基本粒子群算法更新公式相同。慣性權重起著權衡局部最優(yōu)能力和全局最優(yōu)能力的作用。為了研究慣性權重對粒子群算法性能的影響，Shi和Eberhart將此算法應用到Schaffer’s 函數(shù)中，這是個著名的評價優(yōu)化算法的基準函數(shù)。他們改變慣性權重的大小，通過大量的實驗得到兩個結論：1）當慣性權重較小時（），如果粒子群算法能找到全局最優(yōu)解的話，那么它所經(jīng)歷的搜索時間是很短的，即所有的粒子趨向于快