第3章粒子群算法及其MATLAB實現(xiàn)
　　粒子群算法，也稱粒子群優(yōu)化算法(particleswarmoptimization,PSO)，是近年來發(fā)展起來的一種新的進化算法(evolutionaryalgorithm,EA)。
　　這種算法以其實現(xiàn)容易、精度高、收斂快等優(yōu)點引起了學術界的重視，并且在解決實際問題中展示了其優(yōu)越性。粒子群算法是一種并行算法。
　　本章主要講解了粒子群算法的原理及其在MATLAB上的運用。
　　學習目標：
　　■了解粒子群算法的發(fā)展。
　　■掌握粒子群算法的基本原理。
　　■熟悉MATLAB粒子群算法工具箱。
　　■掌握MATLAB在粒子群算法中的運用。
　　3.1粒子群算法基礎
　　PSO算法屬于進化算法的一種，和模擬退火算法相似，它也是從隨機解出發(fā)，通過迭代尋找最優(yōu)解，它也是通過適應度來評價解的品質(zhì)，但它比遺傳算法規(guī)則更為簡單，它沒有遺傳算法的“交叉”和“變異”操作，它通過追隨當前搜索到的最優(yōu)值來尋找全局最優(yōu)。
　　3.1.1粒子群算法的發(fā)展
　　1995年美國電氣工程師Eberhart和社會心理學家Kenndy基于鳥群覓食行為提出了粒子群優(yōu)化算法(PSO)，簡稱粒子群算法。由于該算法概念簡明、實現(xiàn)方便、收斂速度快、參數(shù)設置少，是一種高效的搜索算法。
　　PSO是模擬鳥群隨機搜尋食物的捕食行為。假設在搜索食物區(qū)域里只有一塊食物，所有的小鳥都不知道食物在什么地方，所以Kenndy等認為鳥之間存在著互相交換信息，通過估計自身的適應度值，它們知道當前的位置離食物還有多遠，所以搜索目前離食物最近的鳥的周圍區(qū)域是找到食物的最簡單有效的辦法，通過鳥之間的集體協(xié)作使群體達到最優(yōu)。
　　PSO就是從這種模型中得到啟示并用于解決優(yōu)化問題。在PSO中每個優(yōu)化問題的潛在解都可以想象成搜索空間中的一只鳥，稱之為“粒子”。粒子主要追隨當前的最優(yōu)粒子在解空間中搜索，PSO初始化為一群隨機粒子(隨機解)，然后通過迭代找到最優(yōu)解。
　　在每一次迭代中，粒子通過跟蹤兩個“極值”來更新自己，第一個就是粒子本身所找到的最優(yōu)解，這個解稱為個體極值pbest，另一個極值是整個種群目前找到的最優(yōu)解，這個極值是全局極值gbest。
　　這兩個最優(yōu)變量使得鳥在某種程度上朝著這些方向靠近，此外也可以不用整個種群而只用其中一部分作為粒子的鄰居，那么所有鄰居的極值就是局部極值，粒子始終跟隨這兩個極值變更自己的位置和速度，直到找到最優(yōu)解。
　　到目前為止，粒子群算法的發(fā)展得到越來越多的眾多領域?qū)W者的關注和研究，成為解決許多問題的熱點算法的研究重點。
　　其中對PSO算法的改進也非常多，有增強算法自適應性的改進、增強收斂性的改進、增加多種群多樣性的改進、增強局部搜索的改進、與全局優(yōu)化算法相結(jié)合、與確定性的局部優(yōu)化算法相融合等。
　　以上所述的是對于算法改進的目的的討論，實際改進中應用的方法有基于參數(shù)的改進，即對PSO算法的迭代公式的形式上做改進；還有從粒子的行為模式進行改進，即粒子之間的信息交流方式，如拓撲結(jié)構(gòu)的改進、全局模式與局部模式相結(jié)合的改進等；還有基于算法融合的粒子群算法的改進，算法融合可以引入其他算法的優(yōu)點來彌補PSO算法的缺點，設計出更適合問題求解的優(yōu)化算法。
　　目前，粒子群算法的發(fā)展趨勢如下。
　　(1)粒子群優(yōu)化算法的改進。粒子群優(yōu)化算法在解決空間函數(shù)的優(yōu)化問題和單目標優(yōu)化問題上應用得比較多，如何應用于離散空間優(yōu)化問題和多目標優(yōu)化問題將是粒子群優(yōu)化算法的主要研究方向。如何充分結(jié)合其他進化類算法，發(fā)揮優(yōu)勢，改進粒子群優(yōu)化算法的不足也是值得研究的。
　　(2)粒子群優(yōu)化算法的理論分析。粒子群優(yōu)化算法提出的時間不長，數(shù)學分析很不成熟和系統(tǒng)，存在許多不完善和未涉及的問題，對算法運行行為、收斂性、計算復雜性的分析比較少。如何知道參數(shù)的選擇和設計，如何設計適應值函數(shù)，如何提高算法在解空間搜索的效率算法收斂以及對算法模型本身的研究都需要在理論上進行更深入的研究。這些都是粒子群優(yōu)化算法的研究方向之一。
　　(3)粒子群算法的生物學基礎。如何根據(jù)群體進行行為完善算法，將群體智能引入算法中，借鑒生物群體進化規(guī)則和進化的智能性也是學者關注的問題。
　　(4)粒子群優(yōu)化算法與其他進化類算法的比較研究。與其他進化算法的融合，如何將其他進化算法的優(yōu)點和粒子群優(yōu)化算法相結(jié)合，構(gòu)造出有特色有實用價值的混合算法是當前算法改進的一個重要方向。
　　(5)粒子群優(yōu)化算法的應用。算法的有效性必須在應用中才能體現(xiàn)，廣泛地開拓粒子群優(yōu)化算法的應用領域，也對深入研究粒子群優(yōu)化算法非常有意義。
　　3.1.2粒子群算法研究內(nèi)容
　　粒子群算法是一個非常簡單的算法，且能夠有效地優(yōu)化各種函數(shù)。從某種程度上說，此算法介于遺傳算法和進化規(guī)劃之間。
　　此算法非常依賴于隨機的過程，這也是和進化規(guī)劃的相識之處，算法中朝全局最優(yōu)和局部最優(yōu)靠近的調(diào)整非常類似于遺傳算法中的交叉算子。
　　粒子群算法的主要研究內(nèi)容如下。
　　(1)尋找全局最優(yōu)點。
　　(2)有較高的收斂速度。
　　算法還是用了適應值的概念，這是所有進化計算方法所共有的特征。
　　3.1.3粒子群算法的特點
　　粒子群算法的本質(zhì)是一種隨機搜索算法，它是一種新興的智能優(yōu)化技術，是群體智能中一個新的分支，它也是對簡單社會系統(tǒng)的模擬。
　　該算法能以較大的概率收斂于全局最優(yōu)解。實踐證明，它適合在動態(tài)、多目標優(yōu)化環(huán)境中尋優(yōu)，與傳統(tǒng)的優(yōu)化算法相比較具有更快的計算速度和更好的全局搜索能力。
　　其具體特點如下：
　　(1)粒子群優(yōu)化算法是基于群體智能理論的優(yōu)化算法，通過群體中粒子間的合作與競爭產(chǎn)生的群體智能指導優(yōu)化搜索。與進化算法比較，PSO是一種更為高效的并行搜索算法。
　　(2)PSO與GA有很多共同之處，兩者都是隨機初始化種群，使用適應值來評價個體的優(yōu)劣程度和進行一定的隨機搜索。但PSO是根據(jù)自己的速度來決定搜索，沒有GA的明顯交叉和變異。與進化算法比較，PSO保留了基于種群的全局搜索策略，但是其采用的速度�参灰颇Ｐ筒僮骱唵危�避免了復雜的遺傳操作。
　　(3)由于每個粒子在算法結(jié)束時仍然保持著其個體極值。因此，若將PSO用于調(diào)度和決策問題時可以給出多種有意義的選擇方案。而基本遺傳算法在結(jié)束時，只能得到最后一代個體的信息，前面迭代的信息沒有保留。
　　(4)PSO特有的記憶使其可以動態(tài)地跟蹤當前的搜索情況并調(diào)整其搜索策略。
　　(5)PSO有良好的機制來有效地平衡搜索過程的多樣性和方向性。
　　(6)在收斂的情況下，由于所有的粒子都向最優(yōu)解的方向飛去，所以粒子趨向同一化(失去了多樣性)使得后期收斂速度明顯變慢，以致算法收斂到一定精度時無法繼續(xù)優(yōu)化。因此很多學者都致力于提高PSO算法的性能。
　　(7)PSO算法對種群大小不十分敏感，即種群數(shù)目下降時性能下降不是很大。
　　3.1.4粒子群算法的應用
　　粒子群算法提供了一種求解復雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領域，對問題的種類有很強的適應性，所以廣泛應用于很多學科。粒子群算法的一些主要應用領域如下。
　　(1)約束優(yōu)化。隨著問題的增多，約束優(yōu)化問題的搜索空間也急劇變換，有時在目前的計算機上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。粒子群算法是解決這類問題的最佳工具之一。實踐證明，粒子群算法對于約束優(yōu)化中的規(guī)劃，離散空間組合問題的求解非常有效。
　　(2)函數(shù)優(yōu)化。是粒子群算法的經(jīng)典應用領域，也是對粒子群算法進行性能評價的常用算例。
　　(3)機器人智能控制。機器人是一類復雜的難以精確建模的人工系統(tǒng)，而粒子群算法可用于此類機器人群搜索，如機器人的控制與協(xié)調(diào)，移動機器人路徑規(guī)劃。所以機器人智能控制理所當然地成為粒子群算法的一個重要應用領域。
　　(4)電力系統(tǒng)領域。在其領域中有種類多樣的問題，根據(jù)目標函數(shù)特性和約束類型許多與優(yōu)化相關的問題需要求解。PSO在電力系統(tǒng)方面的應用如配電網(wǎng)擴展規(guī)劃、檢修計劃、機組組合等。隨著粒子群優(yōu)化理論研究的深入，它還將在電力市場競價交易等其他領域發(fā)揮巨大的應用潛在力。
　　(5)工程設計問題。在許多情況下所建立起來的數(shù)學模型難以精確求解，即使經(jīng)過一些簡化之后可以進行求解，也會因簡化得太多而使得求解結(jié)果與實際相差甚遠�，F(xiàn)在粒子群算法已成為解決復雜調(diào)度問題的有效工具，在電路及濾波器設計、神經(jīng)網(wǎng)絡訓練、控制器設計與優(yōu)化、任務分配等方面粒子群算法都得到了有效的應用。
　　(6)生物醫(yī)學領域。許多菌體的生長模型即為非線性模型提出了用粒子群算法解決非線性模型的參數(shù)估計問題。還在分子力場的參數(shù)設定和蛋白質(zhì)圖形的發(fā)現(xiàn)。根據(jù)粒子群算法提出的自適應多峰生物測定融合算法，提高了解決問題的準確性。在醫(yī)學方面，如醫(yī)學成像上得到的推廣應用等。
　　(7)通信領域。包括路由選擇及移動通信基站布置優(yōu)化，在順序碼分多址連接方式(DS�睠DMA)通信系統(tǒng)中使用粒子群算法，可獲得可移植的有力算法并提供并行處理能力。比傳統(tǒng)先前的算法有了顯著的優(yōu)越性，還可以應用到天線陣列控制和偏振模色散補償?shù)确矫妗?br /> 　　(8)交通運輸領域。在物流配送供應領域中要求以最少的車輛數(shù)、最小的車輛總行程來完成貨物的派送任務；在交通控制控制領域，城市交通問題是困擾城市發(fā)展、制約城市經(jīng)濟建設的重要因素。
　　3.2基本粒子群算法
　　PSO算法是起源對簡單社會系統(tǒng)的模擬，具有很好的生物社會背景而易理解、參數(shù)少而易實現(xiàn)，對非線性、多峰問題均具有較強的全局搜索能力，在科學研究與工程實踐中得到了廣泛關注。同時，PSO是一種很好的優(yōu)化工具。
　　3.2.1基本原理
　　PSO從這種模型中得到啟示并用于解決優(yōu)化問題。PSO中，每個優(yōu)化問題的潛在解都是搜索空間中的一只鳥，稱之為粒子。所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適值(fitnessvalue)，每個粒子還有一個速度決定它們“飛行”的方向和距離。然后粒子就追隨當前的最優(yōu)粒子在解空間中搜索。
　　粒子位置的更新方式如圖3��1所示。
　　圖3��1每代粒子位置的更新方式
　　……