自適應(yīng)粒子群算法研究及其在多目標(biāo)優(yōu)化中應(yīng)用(編輯修改稿)

　

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