梯度粒子群算法及應(yīng)用.doc

1 緒論最優(yōu)化問題是在滿足一定約束條件下，尋找一組參數(shù)值，以使某些最優(yōu)性度量得到滿足，即使系統(tǒng)的某些性能指標達到最大或者最小。它廣泛存在于農(nóng)業(yè)、國防、工程、交通、金融、化工、能源、通信、材料等許多領(lǐng)域。最優(yōu)化技術(shù)在上述領(lǐng)域的應(yīng)用已經(jīng)產(chǎn)生了巨大的經(jīng)濟效益和社會效益。國內(nèi)外的實踐表明，在同樣條件下，經(jīng)過優(yōu)化技術(shù)的處理，對系統(tǒng)效率的提高、能耗的降低、資源的合理利用及經(jīng)濟效益提高均有顯著的效果，而且隨著處理對象規(guī)模的增大，這種效果也更加顯著。傳統(tǒng)的優(yōu)化方法根據(jù)問題的性質(zhì)不同，通常將問題劃分為線性規(guī)劃問題、非線性規(guī)劃問題、整數(shù)規(guī)劃問題和多目標規(guī)劃問題。相應(yīng)的有一些成熟的常規(guī)算法，如應(yīng)用于線性規(guī)劃問題的單純形法，應(yīng)用于非線性規(guī)劃的牛頓法、共軛梯度法等，應(yīng)用于整數(shù)規(guī)劃的分枝定界法、動態(tài)規(guī)劃法等。目前，基于嚴格機理模型的開放式方程建模與優(yōu)化已成為國際上公認的主流技術(shù)方向。許多工程公司和各大科研機構(gòu)紛紛投入大量的人力物力對系統(tǒng)的建模與優(yōu)化進行深入細致的研究，希望取得突破性的進展。然而，基于嚴格機理模型所得到的優(yōu)化命題往往具有方程數(shù)多、變量維數(shù)高、非線性強等特點，這使得相關(guān)變量的存儲、計算及求解都相當困難。在國民經(jīng)濟的各個領(lǐng)域中都存在著相當多的涉及因素多、規(guī)模大、難度高和影響廣的優(yōu)化命題，如流程工業(yè)系統(tǒng)優(yōu)化、運輸中的最優(yōu)調(diào)度、生產(chǎn)流程的最優(yōu)排產(chǎn)、資源的最優(yōu)分配、農(nóng)作物的合理布局、工程的最優(yōu)設(shè)計以及國土的最優(yōu)開發(fā)等等，所有這些問題的解決也必須有一個強有力的優(yōu)化工具來進行求解。而前述傳統(tǒng)的優(yōu)化算法面對這樣的大型問題已無能為力，無論是在計算速度、收斂性、初值敏感性等方面都遠不能滿足要求。人們從生命現(xiàn)象中得到啟示，發(fā)明了許多智能的優(yōu)化方法來解決上述復(fù)雜優(yōu)化問題。例如遺傳算法(Genetic Algorithm)參考了生物種群通過遺傳和自然選擇不斷進化的功能、人工免疫系統(tǒng)(Artificail Immune Systems)模擬了生物免疫系統(tǒng)的學(xué)習(xí)和認知功能、蟻群優(yōu)化(Ant colony Optimization)算法模仿了螞蟻群體在路徑選擇和信息傳遞方面的行為，粒子群優(yōu)化（Particle swarm optimization)算法模擬了鳥群和魚群覓食遷徙中個體與群體協(xié)調(diào)一致的機理，群落選址算法(colony Location Algorithm)模擬了植物群落的形成機制等，這類借鑒模擬了生命系統(tǒng)的行為、功能和特性的科學(xué)計算方法稱之為人工生命計算(Artifieial Life Computation)。人工生命計算是生命科學(xué)、信息科學(xué)和運籌學(xué)的交叉研究學(xué)科，是進化計算的一個新的分支，是由具有生命特性的多智能體以特定計算目標為依據(jù)，有序組合起來所形成的計算方法。按照此定義，人工神經(jīng)網(wǎng)絡(luò)(Artificial Neural Network)，文化算法(Cultural Algorithm)、人工生命算法(Artifieial Life Algorithm)、捕食搜索策略(Predatory Search Strategy)等都可以被歸納為人工生命計算。粒子群優(yōu)化(PSO)算法是其中較新的一種人工生命計算方法。它同遺傳算法類似，是一種基于迭代的優(yōu)化工具。系統(tǒng)初始化為一組隨機解，通過迭代搜索最優(yōu)值。同遺傳算法等其他人工生命計算方法相比，粒子群優(yōu)化算法概念簡單、容易實現(xiàn)，沒有很多參數(shù)需要調(diào)節(jié)。目前粒子群算法越來越引起人們的關(guān)注，已成為國際上一個新的研究熱點。粒子群優(yōu)化算法的研究還處于初級階段，還有很多領(lǐng)域需要研究。在這篇文章中，首先提出了標準的粒子群算法， 標準的粒子群算法由于其簡單和解決問題的有效能力而被應(yīng)用到很多的領(lǐng)域。但在實際應(yīng)用當中，也表現(xiàn)出了一些不盡人意的問題。這些問題中最主要的是它容易產(chǎn)生早熟收斂、局部尋優(yōu)能力較差等。實際上這些缺點也是幾乎所有隨機算法的弊病。本文將梯度信息引入標準PSO算法，并在群體最優(yōu)信息陷入停滯時將群體進行部分初始化來保持群體的活性，防止群體陷入局優(yōu)，構(gòu)造出帶有梯度加速的PSO算法。帶有梯度加速優(yōu)化算法卻具有很強的局部搜索能力，一種帶有梯度加速的PSO算法是對標準PSO算法進行改進。并通過實驗討論了改進算法的適用范圍。實驗表明，對于單峰函數(shù)和多峰函數(shù)，帶有梯度加速的PSO都能夠取得更好的優(yōu)化效果。2 粒子群優(yōu)化算法及其理論基礎(chǔ)2.1概述長久以來 ，人們向往著設(shè)計的人工系統(tǒng)像自然系統(tǒng)那樣健壯，高效靈活，具有適應(yīng)性、自組織和再生能力。近幾十年來，一些新穎的優(yōu)化算法，如人工神經(jīng)網(wǎng)絡(luò)、遺傳算法及蟻群算法、粒子群算法等通過模擬或揭示某些自然現(xiàn)象或過程而得到發(fā)展，其思想和內(nèi)容涉及數(shù)學(xué)、生物進化、人工智能、神經(jīng)科學(xué)和量子統(tǒng)計學(xué)等方面，為解決復(fù)雜工程問題提供了新的思路和手段.這些算法獨特的優(yōu)點和機制，引起了國內(nèi)外學(xué)者的廣泛重視并掀起了該領(lǐng)域的研究熱潮，且在許多領(lǐng)域得到了成功應(yīng)用。在優(yōu)化領(lǐng)域，由于這些算法構(gòu)造的直觀性與自然機理，被稱作為智能優(yōu)化算法。在這些智能優(yōu)化方法中，有一類是模擬某些群體的智能行為，雖然群體中的個體僅具有簡單的智能，但通過個體與個體和個體與環(huán)境的信息交流以及個體的簡單行為，從而使群體表現(xiàn)出復(fù)雜的自組織、分布式控制、可擴展、健壯的智能體，實現(xiàn)對空間的高效搜索。也就是說，群體智能可以在適當?shù)倪M化機制引導(dǎo)下通過個體交互以某種突現(xiàn)形式發(fā)揮作用，這是個體的智能難以做到的。在群體智能優(yōu)化算法的框架下，大量基于不同物理背景的算法紛紛被提出，如，遺傳算法，粒子群算法等，并進行了廣泛的應(yīng)用嘗試。粒子群算法(Particle Swarm Optimization.簡稱PSO)，是一種基于群體智能的進化計算方法.是由PSO由Kennedy和Eberhart博士于1995年提出。PSO的基本概念源于對鳥群捕食行為的研究:一群鳥在隨機搜尋食物，在這個區(qū)域里只有一塊食物，所有鳥都不知道食物在哪里。但是他們知道當前的位置離食物還有多遠。那么找到食物的最優(yōu)策略是什么呢?最簡單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域.PSO從這種模型中得到啟示并用于解決優(yōu)化問題.在PSO中，每個優(yōu)化問題的潛在解都是搜索空間中的一只鳥，稱之為“粒子”，即問題的解空間對應(yīng)于搜索空間粒子群。所有的粒子都有一個由被優(yōu)化的問題(如，函數(shù))決定的適應(yīng)值，每個粒子還有一個速度決定他們飛翔的方向和距離。然后粒子群們就追隨當前的最優(yōu)粒子在解空間中搜索.PSO初始化為一群隨機粒子也就是隨機解，然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤“兩個極值”來更新自己。第一個就粒子本身所找到的最優(yōu)解，這個解稱為個體極值，另一個極值是整個種群目前找到的最優(yōu)解，這個極值是全局極值。另外也可以不用整個種群而是用其中一部分作為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。PSO一經(jīng)提出，立刻引起了進化計算領(lǐng)域?qū)W者們的廣泛關(guān)注，形成一個研究熱點，目前己廣泛應(yīng)用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模式分類、模糊控制等領(lǐng)域，取得了較好的效果。2.2原始粒子群優(yōu)化算法的基本概念為了更好地描述粒子群優(yōu)化算法，在此作如下定義定義1 粒子類似于遺傳算法中的染色體，PSO中粒子為基本的組成單位，代表解空間的一個候選解。定義2 種群粒子種群由n個粒子組成，代表n個候選解。定義3 粒子速度粒子速度表示粒子在單位迭代次數(shù)位置的變化即為代表解變量的粒子在d維空間的位移。定義4 適應(yīng)度函數(shù)一般由適應(yīng)度函數(shù)由優(yōu)化目標決定，用于評價粒子的搜索性能，指導(dǎo)粒子種群的搜索過程。算法迭代停止時適應(yīng)度函數(shù)最優(yōu)的解變量即為優(yōu)化搜索的最優(yōu)解。定義5 個體極值個體極值是單個粒子從搜索初始到當前迭代對應(yīng)的適應(yīng)度最優(yōu)的解。定義6 全局極值全局極值是整個粒子種群從搜索開始到當前迭代對應(yīng)的適應(yīng)度最優(yōu)的解。2.3粒子群優(yōu)化算法的一般數(shù)學(xué)模型粒子群算法的基本思想是:用隨機解初始化一群隨機粒子，然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個“極值”來更新自己:第一個就是粒子本身所找到的最好解，即個體極值(Pbest)，另一個極值是整個粒子群中所有粒子在歷代搜索過程中所達到的最優(yōu)解(Gbest)，即全局極值，在找到這兩個最好解后，接下來是PSO中最重要的“加速”過程，每個粒子不斷地改變其在解空間中的速度，以盡可能地朝Pbest和Gbest所指向的區(qū)域“飛”去?；镜牧Ｗ尤耗Ｐ陀梢粋€m維變量空間內(nèi)n個粒子(位置，速度)=（,)組成的群體構(gòu)成，表示為: (2.1) (2.2)式中 ， i=1,2,n，n為粒子群中粒子的個數(shù):j=1,2,m，m 為解向量的維數(shù);k是進化代數(shù).粒子根據(jù)如下的式(2.3)和式(2.4)來更新自己的速度和位置. (2.3) (2.4)、分別表示第i個粒子在j維方向上的當前速度和修正后的速度;、分別為第i個粒子在j維方向上的當前坐標和修正后的坐標;c1, c2是加速系數(shù)，分別調(diào)節(jié)向全局最好粒子和個體最好粒子方向飛行的最大步長;是第i個粒子在第j維的個體極值點的位置，是到第k代為止，所有粒子在第j維的全局極值點的位置:rand1,和rand2為兩個在0, 1范圍內(nèi)變化的隨機函數(shù)。2.4粒子群優(yōu)化算法的設(shè)計步驟和算法流程設(shè)計步驟:(1) 確定問題的表示方案粒子群算法在求解問題時，其首要步驟是將問題的解從解空間映射到具有某種結(jié)構(gòu)的表示空間，即用特定的編碼表示問題的解，這和遺傳算法是類似的。粒子群算法的大部分研究均集中在數(shù)值優(yōu)化領(lǐng)域中，其位置一速度計算模型使用于具有連續(xù)特征的問題函數(shù)，因此，目前算法大多采用實數(shù)向量的編碼方式，以粒子的位置向量來表示問題的解。(2) 確定優(yōu)化問題的評價函數(shù)在求解問題時，必須根據(jù)問題的具體特征，選取適當?shù)哪繕撕瘮?shù)來計算適應(yīng)值，適應(yīng)值是唯一能夠反映并引導(dǎo)優(yōu)化過程不斷進行的參量。(3) 選擇控制參數(shù)粒子群算法的控制參數(shù)通常包括粒子種群數(shù)量、算法執(zhí)行的最大代數(shù)、慣性權(quán)重系數(shù)其他一些輔助控制參數(shù)，如粒子位置和速度的控制范圍等。(4) 選擇粒子群模型目前 ， 粒子群算法己經(jīng)發(fā)展了多種位置一速度計算模型，如慣性權(quán)重PSO模型、二進制PSO模型等等，在求解不同類型優(yōu)化問題時，不同PSO模型的優(yōu)化性能也有差異。（5）確定算法的終止準則與其他進化算法一樣，PSO算法中最常用的終止準則時預(yù)先設(shè)定一個最大的迭代次數(shù)，或者當搜索過程中解的適應(yīng)值在連續(xù)多少代后不再發(fā)生明顯改變時，終止算法。PSO 的算法流程如下:Step 1 :設(shè)定加速常數(shù)C1和C2，最大進化代數(shù)等參數(shù)，將當前進化代數(shù)置為t=1,初始化一群微粒(群體規(guī)模為N)，包括隨機位置和速度;Step 2 :評價每個微粒的適應(yīng)度;Step 3 :對每個微粒，將其適應(yīng)值與其經(jīng)歷過的最好位置pbest作比較，如果較好，則將其作為當前的最好位置pbest;Step 4 :對每個微粒，將其適應(yīng)值與全局所經(jīng)歷的最好位置gbest作比較，如果較好，則重新設(shè)置gbest;Step5 : 根據(jù)方程(2.3)和(2.4)變化微粒的速度和位置;Step6 :檢查結(jié)束條件，若滿足，則結(jié)束尋優(yōu)，如未達到結(jié)束條件(通常為足夠好的適應(yīng)值或達到一個預(yù)設(shè)最大代數(shù)T)，則返回Step 2.從上述粒子群優(yōu)化算法尋優(yōu)過程可以看出其有如下特性:粒子群中的群體隨著時間的變化而進行空間位置的計算;粒子群中的群體對環(huán)境中的品質(zhì)因素做出響應(yīng)，這種品質(zhì)因素是通過PSO中每個粒子的最好位置和種群中的最優(yōu)粒子來反映的;粒子群通過一定方式(即通過對個體最優(yōu)粒子的記憶和對全局最優(yōu)粒子的學(xué)習(xí)的方式)分配這種響應(yīng)而體現(xiàn)出種群的多樣性，僅僅當粒子群中的最優(yōu)粒子發(fā)生改變時，粒子群中粒子的行為才發(fā)生改變，這正體現(xiàn)出了粒子群的穩(wěn)定性和適應(yīng)性。 初始化粒子群計算每個粒子的適應(yīng)度值根據(jù)粒子的適應(yīng)度值更新個體極值與全局極值根據(jù)公式（2.3）(2.4)更新粒子群的速度和位置滿足算法結(jié)束條件？輸出優(yōu)化結(jié)果，全局極值？YN2.5 標準的粒子群算法為了改善算法收斂性能，Shi和Eberhart在1998年的論文中引入了慣性權(quán)重的概念，引入慣性權(quán)重因子w后，公式(2.3).(2 .4)就變?yōu)?(2.5) (2.6)顯見 ， 慣性權(quán)重W描述了粒子上一代速度對當前代速度的影響，控制其取值大小可調(diào)節(jié)PSO算法的全局與局部尋優(yōu)能力。w值較大，全局尋優(yōu)能力強，局部尋優(yōu)能力弱，反之，則局部尋優(yōu)能力增強，而全局尋優(yōu)能力減弱。剛開始慣性權(quán)重為常數(shù)，但后來的試驗發(fā)現(xiàn)，動態(tài)慣性權(quán)值能夠獲得比固定值更為好的尋優(yōu)結(jié)果。動態(tài)慣性權(quán)值可以在PSO搜索過程中線性變化，亦可根據(jù)PSO性能的某個測度而動態(tài)改變。慣性權(quán)重的引入，可從不同的角度調(diào)整算法全局和局部搜索能力，使PSO算法的性能得到了很大提高，也使PSO算法得以比較成功地應(yīng)用于很多實際問題。2.6粒子群優(yōu)化的研究現(xiàn)狀（1）理論研究現(xiàn)狀在算法的理論研究方面，有部分研究者對算法的收斂性進行了分析，更多的研究者致力于研究算法的結(jié)構(gòu)和性能改善，包括參數(shù)分析，拓撲結(jié)構(gòu)，粒子多樣性保持，算法融合和性能比較等。在收斂性研究方面，Clerc和Knenedy將PSO基本公式簡化為一維空間中的單個粒子，分析了其在離散時間和連續(xù)時間的移動情況，并提出了完全描述系統(tǒng)的五維模型，里面包含的參數(shù)能夠控制系統(tǒng)收斂的趨勢。Ozcan和Mohan在假設(shè)w=1,C1和C2為常數(shù)，和為固定點情況下，通過理論分析將一個微粒隨時間變化描述為波的運行，并對不同區(qū)域進行了軌跡分析。Trealea應(yīng)用離散動態(tài)系統(tǒng)理論對簡化PSO模型的動態(tài)行為和收斂性進行了分析，推導(dǎo)出對參數(shù)選擇的參考準則。PSO的早期版本沒有慣性權(quán)重，Shi和Ebehart首次提出了慣性權(quán)重的概念，來對基本算法中的速度更新公式進行修正。修正后的公式已成為PSO的標準版本，為大多數(shù)研究者所使用。慣性權(quán)重常被設(shè)置為隨時間遞減的時變權(quán)重來提高算法性能，如將權(quán)重設(shè)為1.4到0，0.9到0.4，0.95到0.2等。shi和Eberhart還提出一個模糊系統(tǒng)來一調(diào)節(jié)慣性權(quán)重，取得較好效果。Kennedy把Cl和C2分別設(shè)置為0，得到了PSO的“只有社會(social only)的模型”(Cl=0)，“只有認知(cognition only)的模型”(C2=0)和“無私(selfless)的模型”(C2=0，且自己的最好解不包含在鄰域內(nèi))，并分析了幾種模型的表現(xiàn)。Suganthan的研究表明C1和C2為常數(shù)時可以取得較好的解，但不一定為2。有研究者在實驗中將C1和C2取為1.494，1.7等。EI一Gallad等對種群規(guī)模，迭代次數(shù)和粒子速度的選擇進行了分析并給出選擇的基本原則，并通過對約束問題的求解來驗證這些參數(shù)的基本影響。在算法的拓撲結(jié)構(gòu)研究方面，Angeline發(fā)現(xiàn)PSO可以比其他演化算法更快找到較好解，但后期精確搜索性能不好，為此suganthan引入一個變化的鄰域算子(neighborhood operator)來改善解的質(zhì)量，在優(yōu)化初始階段，粒子鄰域就是其本身，隨著迭代次數(shù)增加，鄰域逐漸增大，直至包括所有粒子?；綪SO算法中鄰域是基于索引號劃分的，Suganthan使用了基于空間位置劃分的方案，稱為空間鄰域(space neighborhoods)法。Kennedy對幾種拓撲結(jié)構(gòu)的實驗表明拓撲非常影響算法性能，且最佳拓撲結(jié)構(gòu)因問題而定。Knenedy還提出了混合空間鄰域和環(huán)形拓撲方法的局部PSO版本，稱為社會趨同(social stereotyping)法。Kennedy和Mendes系統(tǒng)分析了不同的拓撲結(jié)構(gòu)對算法性能的影響，說明了構(gòu)造種群結(jié)構(gòu)的基本原則。為克服早熟現(xiàn)象，保持粒子群體的多樣性是提高算法性能的重要途徑，很多學(xué)者對此進行了研究。Riget和Vestersrtom將排斥過程引入標準PSO，通過多樣性度量控制種群特征，從而實現(xiàn)粒子間吸引和排斥平衡以避免早熟現(xiàn)象。Lovbjerg和Krink將自組織臨界控制引入PSO來增加種群的多樣性，實驗結(jié)果表明可以使算法有更快收斂速度和找到更好的解。Krink等還提出一種粒子空間擴展的方法來解決粒子間的沖突和聚集問題，并增強了粒子逃脫局優(yōu)的能力。Al一kazemi和Mohan通過在求解離散和連續(xù)問題的不同階段設(shè)置不同的階段性目標建立了多階段(multi一phase)PSO，這種算法在實驗中表現(xiàn)出比標準PSO，GA和進化規(guī)劃更好的性能。Xie等將負嫡(negative entropy)概念引入標準PSO，通過將混沌因素加入到粒子更新過程建立了開放消耗系統(tǒng)，兩個多峰函數(shù)的優(yōu)化實驗結(jié)果表明了其有效性。在PSO和其他算法的融合以及性能的比較方面，也有很多研究成果出現(xiàn)。Angeline提出了采用進化計算中的選擇操作的混合PSO(HPSO)模型。Lovbjerg等將PSO與進化算法的思想融合，通過將繁殖和子種群的概念引入PSO，建立了兩種混合型粒子群優(yōu)化器，獲得了更快的收斂速度和發(fā)現(xiàn)更好解的潛力。Natasuki等提出了帶有高斯變異的PSO算法。Eberhart和shi將PSO與標準GA進行了分析和性能比較。國內(nèi)也有很多學(xué)者進行了這方面的研究，提出了基于模擬退火的PSO算法，免疫粒子群算法，基于群體適應(yīng)度方差自適應(yīng)變異的PSO算法，將PSO與差別進化算法結(jié)合等。PSO最初多用于解決連續(xù)優(yōu)化問題，Eberhart和Kennedy又提出了PSO的離散二進制版本，用于解決組合優(yōu)化問題。Knenedy和spears還利用多峰問題產(chǎn)生器把PSO的二進制版本和三種版本的GA進行了比較。Mohan等提出了幾種二進制方法，但是實驗有限，沒有得到確定性的結(jié)論。Hu等介紹了解決數(shù)列問題的改進PSO。目前關(guān)于PSO的離散版本的研究還很有限，并沒有一個較好的解決方案，離散變量如何進行加法和乘法處理是個嚴重的問題，并且離散型PSO非常容易陷入局優(yōu)。（2）應(yīng)用研究現(xiàn)狀PSO最早應(yīng)用于非線性連續(xù)函數(shù)的優(yōu)化和神經(jīng)元網(wǎng)絡(luò)的訓(xùn)練，后來也被用于解決約束優(yōu)化問題。Eberhart用PSO來分析人類的帕金森綜合怔等顫抖類疾病。Yoshida等通過PSO對各種離散個連續(xù)變量的優(yōu)化，達到控制核電機組輸出穩(wěn)定電壓的目的。Robinson等將PSO用于剖面波狀喇叭天線的優(yōu)化，并與GA的優(yōu)化效果進行了比較，研究了二者混合應(yīng)用的可行性。Ciuprina提出一種智能PSO(Intelligent PSO)用于電磁線圈尺寸的優(yōu)化。Abido將 PS0用于解決最優(yōu)功率通量(OPF)問題。國內(nèi)也有越來越多的學(xué)者關(guān)注PSO的應(yīng)用，將其應(yīng)用于非線性規(guī)劃，同步發(fā)電機辯識，車輛路徑，約束布局優(yōu)化，新產(chǎn)品組合投入，廣告優(yōu)化，多目標優(yōu)化等問題。還有一些學(xué)者嘗試將PSO算法應(yīng)用于解決動態(tài)優(yōu)化問題，也取得了較好效果。PSO由于其算法的簡單，易于實現(xiàn)，無需梯度信息，參數(shù)少等特點在連續(xù)非線性優(yōu)化問題和組合優(yōu)化問題中都表現(xiàn)出良好的效果。在多目標優(yōu)化、數(shù)據(jù)分類、數(shù)據(jù)聚類、模式識別、電信QOS管理、生物系統(tǒng)建模、流程規(guī)劃、信號處理、機器人控制、決策支持以及仿真和系統(tǒng)辯識等方面，都表現(xiàn)出良好的應(yīng)用前景。2.7 標準粒子群優(yōu)化算法存在的問題根據(jù)文獻和我們進行實驗得到的結(jié)果，將標準PSO算法在優(yōu)化過程中表現(xiàn)出來的問題總結(jié)如下:(l)參數(shù)控制：對不同的問題，如何選擇合適的參數(shù)來達到最優(yōu)效果。(2)缺乏速度的動態(tài)調(diào)節(jié)：爬山能力不強，有時在達到一定的精度后，很難再找到更好的解。(3)早熟:粒子群過早收斂，使尋優(yōu)停滯。3 帶有梯度加速的粒子群算法3.1引言標準PSO算法具有很強的通用性，適用于各種優(yōu)化問題，特別是實優(yōu)化問題。但是這種廣泛的適應(yīng)性也導(dǎo)致對具體問題的特性考慮不夠，比如沒有考慮很多問題中有效的梯度信息。也有研究表明標準PSO算法與遺傳算法相比，早期的迭代表現(xiàn)較好，能夠更快的發(fā)現(xiàn)質(zhì)量好的解存在的區(qū)域。但是后期迭代搜索效率不高。這是因為標準粒子群優(yōu)化缺乏速度的動態(tài)調(diào)節(jié)，爬山能力不強。針對如上問題，本文提出一種帶有梯度加速的PSO算法，對標準PSO算法進行了改進。在粒子的速度更新中以一定概率加入梯度信息，使粒子的移動更有針對性，移動更有效率。同時為了減小粒子陷入局優(yōu)的可能性，對群體最優(yōu)值進行觀察。在尋優(yōu)過程中，當最優(yōu)信息出現(xiàn)停滯時，對部分粒子進行重新初始化，從而保持群體的活性。通過實驗對帶有梯度加速的PSO算法的適用范圍進行了討論。3.2帶有梯度加速的粒子群算法3.2.1原理與步驟與其他進化算法一樣，標準PSO算法利用種群進行隨機搜索，沒有考慮具體問題的特性，不使用梯度信息，而梯度信息往往包含目標函數(shù)的一些重要信息對于函數(shù),其梯度可表示為函數(shù)值的最速下降方向是負梯度方向。帶有梯度加速的粒子群算法的思想：通過引入梯度信息來影響粒子速度的更新，構(gòu)造出一種帶有梯度加速的PSO算法每次粒子進行速度和位置更新時，每個粒子以概率P按式(2.5)和式(2.6)更新，并以概率(1一P)按梯度信息更新，在負梯度方向進行一次直線搜索來確定移動步長。直線搜索采用黃金分割法，這一步驟可以詳述如下： 產(chǎn)生一偽隨機數(shù)，若大于P，則按照公式（2.5）和（2.6）更新粒子速度和位置； 否則，試探方式確定一單谷搜索區(qū)間， 計算， 計算， 若，（為終止限），則即為粒子的下一位置；否則轉(zhuǎn) 判別是否滿足，若滿足，則置，然后轉(zhuǎn)；否則若，則置，然后轉(zhuǎn)。同時，為防止陷入局優(yōu)，在群體最優(yōu)信息陷入停滯時，對群體進行部分重新初始化，以保持群體的活性，減小群體陷入局優(yōu)的可能性。梯度信息的加入使粒子的移動更具針對性和效率，進一步提高了PS0算法的收斂速度，但也會增加算法對問題的依賴性，特別是有些梯度信息極易將粒子引入局優(yōu)。所以帶有梯度加速的PSO算法需要根據(jù)問題的性質(zhì)來調(diào)整梯度信息對于粒子移動的影響程度。綜上，帶有梯度加速的PSO算法主要步驟如下：1)在初值范圍內(nèi)隨機初始化粒子種群，包括隨機位置和速度2)評價每個粒子的適應(yīng)值3)將每個粒子的適應(yīng)值與其經(jīng)歷過的最好值進行比較，如果更好，則將其作為當前粒子的個體最優(yōu)值4)將每個粒子的個體最優(yōu)值與群體最優(yōu)值進行比較，如果更好，則將其作為群體最優(yōu)值；若規(guī)定迭代次數(shù)內(nèi)群體最優(yōu)值未得到更新，則按一定概率將部分粒子重新初始化5)對于每個粒子的速度和位置，以概率P按（2.5）和（2.6）更新，并以概率(1一p)按梯度信息更新，在負梯度方向進行一次直線搜索來確定移動步長6)若未達到終止條件，則轉(zhuǎn)步驟2)3.2.2梯度加速的流程圖改進PSO算法的梯度加速過程體現(xiàn)在上面的第5步，為直觀說明，這里將其詳細表示為圖3.1：產(chǎn)生一偽隨機數(shù), apN將方向設(shè)為負梯度方向沿方向進行直線搜索，得到 按公式（2.5）更新速度按公式（2.6）更新位置Y 圖3.1梯度加速的流程圖3.3實驗與結(jié)果分析3.3.1實驗設(shè)置為了對標準PSO算法和帶有梯度加速的PSO算法進行比較，并對改進后算法的問題依賴性進行研究，這里采用2個測試函數(shù)Schaffers f6函數(shù)和Sphere函數(shù)。 函數(shù)名 表達式 維數(shù) 初值范圍 目標值Schaffers f62 Sphere30 0.01標準PSO算法及帶有梯度加速的PSO算法分別選取種群30和種群10并選取不同的慣性權(quán)重(這里均采用時變權(quán)重)，為了全面比較優(yōu)化效果，采用兩種停止準則: 用兩種停止準則:(1)是否達到規(guī)定的達優(yōu)值(觀察其達優(yōu)率、平均迭代次數(shù)及平均計算時間);(2)迭代4000次(觀察其取得的最優(yōu)值)。改進PSO算法中，當20次迭代未取得更好的群體最優(yōu)值時，認為群體最優(yōu)信息陷入停滯，在粒子群體中隨機選取30%進行重新初始化，重新初始化的方式為在初值范圍內(nèi)隨機產(chǎn)生一個新的粒子代替原粒子