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

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