【正文】 Kennedy 博士提出，它源于對(duì)鳥(niǎo)群和魚(yú)群群體覓食運(yùn)動(dòng)行為的模擬。 PSO 算法是一種基于迭代的優(yōu)化工具，系統(tǒng)初試化為一組隨機(jī)解，通過(guò)迭代搜尋最優(yōu)解，粒子在解空間中追隨最優(yōu)的粒子進(jìn)行搜索。 目前，粒子群優(yōu)化算法應(yīng)用于神經(jīng)網(wǎng)絡(luò)的訓(xùn)練、函數(shù)優(yōu)化、多目標(biāo)優(yōu)化等領(lǐng)域并取得了較好的效果，有著廣闊的應(yīng)用 前景。粒子群優(yōu)化算法根據(jù)全體粒子和自身粒子的搜索經(jīng)驗(yàn)向著最優(yōu)解的方向發(fā)展，在進(jìn)化后期收斂速度變慢，同時(shí)，算法收斂精度不高，尤其是對(duì)于高維多極值的復(fù)雜優(yōu)化問(wèn)題。對(duì)粒子群優(yōu)化算法的理論基礎(chǔ)和研究現(xiàn)狀作了簡(jiǎn)要介紹，分析了粒子群優(yōu)化算法的原理和算法流程。粒子群收斂于局部極值的根本原因在于進(jìn)化后期沒(méi)有找到優(yōu) 于全局最優(yōu)的位置，對(duì)個(gè)體極值和全局極值進(jìn)行隨機(jī)擾動(dòng)，提出了帶極值擾動(dòng)的粒子群優(yōu)化算法。 （ 3） 簡(jiǎn)要介紹了粒子群優(yōu)化算法在整定 PID 參數(shù)中的應(yīng)用。 particle velocity。美國(guó)工程院院士哈佛大學(xué)何毓琦（ Yuchi Ho）教授指 出“任何控制與決策問(wèn)題本質(zhì)均可以歸結(jié)為優(yōu)化問(wèn)題”。通過(guò)求解該類問(wèn)題，可以為絕餓著提供最佳選擇或最佳信息，即針對(duì)給出的實(shí)際問(wèn)題，從眾多的方案中選出最佳方案。而計(jì)算機(jī)的出現(xiàn)為各種優(yōu)化算法的快速實(shí)現(xiàn)提供了更為便捷的計(jì)算工具，這些因素促使優(yōu)化逐漸成為一門應(yīng)用廣泛、生機(jī)勃勃的學(xué)科。例如，在資源分配中，如何分配有限資源，使得分配方案既能滿足各方面的基本要求，又能獲得較好的經(jīng)濟(jì)效益；在工程設(shè)計(jì)中，如何選擇設(shè)計(jì)參數(shù)，使得設(shè)計(jì)方案既能滿足設(shè)計(jì)要求又能降低成本。尋找函數(shù) f 的最大值等價(jià)于 f 的最小值尋優(yōu)，所以兩種情況可歸結(jié)到一起研究。 優(yōu)化問(wèn)題中經(jīng)常用到的概念： 1. 解之間的距離測(cè)度函數(shù) 設(shè) A,f是某優(yōu)化問(wèn)題的一個(gè)實(shí)例，定義 Dist： A A R??? 為計(jì)算該優(yōu)化問(wèn)題中的兩個(gè)解之間的距離測(cè) 度函數(shù)。 2. 解的鄰域 設(shè) A,f是某優(yōu)化問(wèn)題的一個(gè)實(shí)例， Dist 為解之間距離測(cè)度函數(shù)。也就是對(duì)任意一個(gè) vA? ，集合 :eN x A? 被稱為 v 的鄰域， : ( )eN x Ne v? 稱為 v 的一個(gè) 鄰居。對(duì)于確定的 eN ，若 eN 滿足( *) ( )f x f x? ， *()x Ne x?? ，則稱 eN 為在 A 上的局部最優(yōu)。 5. 可接受解 設(shè) A,f是某優(yōu)化問(wèn)題的一個(gè)實(shí)例 ， eN 為在 A 上的局部最優(yōu)?？山邮芙庠趦?yōu)化問(wèn)題中是非常重要的，因?yàn)樵诜浅６嗟膶?shí)例中，有限的時(shí)間內(nèi)保證搜索到全局最優(yōu)幾乎是不可能的。 優(yōu)化算法 隨著對(duì)最優(yōu)化不斷的深入研究，人們發(fā)現(xiàn)優(yōu)化問(wèn)題有線性的、非線性的、連續(xù)的、離散的，在復(fù)雜情況下要想完全精確地求出其最優(yōu)解是不 可能的，因而求出近似最優(yōu)解或滿意解是人們的主要著眼點(diǎn)之一。 1)枚舉法。對(duì)于連續(xù)問(wèn)題，該方法要求先對(duì)其進(jìn)行離散化處理，這樣就有可能產(chǎn)生離散誤差而永遠(yuǎn)達(dá)不到最優(yōu)解。 2)啟發(fā)式算法。該方法的求解效率雖然比較高，但對(duì)每一個(gè)需要求解的問(wèn)題都必須找出其特有的啟發(fā)式規(guī)則，這種啟發(fā)式 規(guī)則無(wú)通用性，不適合于其他問(wèn)題。尋找一種搜索算法，該算法在可行解空間的一個(gè)子空間內(nèi)進(jìn)行搜索操作，以找到問(wèn)題的最優(yōu)解或近似最優(yōu)解。 搜索算法可分為確定性搜索法和隨機(jī)性搜索法兩種。隨機(jī)性搜索算法在執(zhí)行 過(guò)程中加入隨機(jī)性 (因?yàn)檎嬲碚撘饬x下的隨機(jī)數(shù)是不可能由計(jì)算機(jī)產(chǎn)生的，所以實(shí)際上用的是偽隨機(jī)數(shù) )，需要計(jì)算算法輸出結(jié)果的概率平均值。粒子群優(yōu)化算法就是一種隨機(jī)性概率搜索方法。同時(shí)， 隨著人類生存空間的擴(kuò)大，以及認(rèn)識(shí)世界和改造世界范圍的拓寬，現(xiàn)實(shí)中碰到的許多科學(xué)、工程和經(jīng)濟(jì)問(wèn)題呈復(fù)雜化、多極化、非線性、強(qiáng)約束、建模困難等特點(diǎn)。 經(jīng)典的優(yōu)化算法通常采用局部搜索方法，這些局部搜索方法要么是與特定問(wèn)題相關(guān)，要么是局部搜索方法的變型，但它們有一個(gè)共同的特點(diǎn)就是通過(guò)迭代來(lái)提高問(wèn)題域中唯一的候選解的近似程度。解決實(shí)際工程問(wèn)題，這些算法要么是解的精度，要么是執(zhí)行時(shí)間，總是不能令人十分滿意。 群體智能 群體智能（ Swarm Intelligence， SI）就是無(wú)智能或具有簡(jiǎn)單 智能的個(gè)體在無(wú)集中控制的情況下，通過(guò)單個(gè)個(gè)體自身的簡(jiǎn)單行為，使得整個(gè)群體表現(xiàn)粗某種智能行為，從而解決特定的問(wèn)題。 1999年， Bonabeau、 Dorigo 和 Theraulaz 在 《 Swarm Intelligence： From Natural to Artificial Systems》 一文中對(duì)群智能進(jìn)行了詳細(xì)的論述和分析，給出了群智能算法的一種定義：任何一種由昆蟲(chóng)群體或其它動(dòng)物社會(huì)行為機(jī) 制而激發(fā)設(shè)計(jì)出的算法或分布式解決問(wèn)題的策略均屬于群智能算法。《 Swarm Intelligence》最重要的觀點(diǎn)是“ Mind is Social”，也就是認(rèn)為人的智能是源于社會(huì)性的相互作用，文化和認(rèn)知是人類社會(huì)性不可分割的重要部分，這一觀點(diǎn)成了群體智能發(fā)展的基石。 SI 的思路為在沒(méi)有集中控制且不提供全局模型的前提下尋找復(fù)雜的分布式問(wèn)題求解方案提供了基礎(chǔ)。目前，已有的基于 SI 的優(yōu)化算法都是源于 對(duì)動(dòng)物社會(huì)通過(guò)協(xié)作解決問(wèn)題行為的模擬，它主要強(qiáng)調(diào)對(duì)社會(huì)系統(tǒng)中個(gè)體之間相互協(xié)同作用的模擬?；?SI 的優(yōu)化算法是概率搜索算法。 無(wú)論是從理論研究還是應(yīng)用研究的角度分析， SI 理論及應(yīng)用研究都是具有重要學(xué)術(shù)意義和現(xiàn)實(shí)價(jià)值的。首先，算法中涉及的各種參數(shù)設(shè)置一直沒(méi)有確切的理論依據(jù)，通常都是按照經(jīng)驗(yàn)方法確定，對(duì)具體問(wèn)題和應(yīng)用環(huán)境的依賴性比較大。 粒子群優(yōu)化算法 研究背景 本文研究的粒子群優(yōu)化算法 (Particle Swarm Optimization，簡(jiǎn)稱 PSO)是 Kennedy Eberhart 源于群 體 智能和人類認(rèn)知的學(xué)習(xí)過(guò)程而發(fā)展的另外一種智能優(yōu)化算法。因而， PSO 算法從誕生起， 就引起了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注，并掀起了該方向的研究熱潮，且在諸多領(lǐng)域得到了成功應(yīng)用，但是， PSO 的發(fā)展歷史尚短，在理論基礎(chǔ)與應(yīng)用推廣上都還存在一些問(wèn)題，有待解決。僅僅從實(shí)驗(yàn)數(shù)據(jù)對(duì)粒子群優(yōu)化算法進(jìn)行研究，終將無(wú)法了解其內(nèi)部機(jī)理。 第二，工程上存在的很多復(fù)雜優(yōu)化問(wèn)題急需解決，由于粒子群優(yōu)化算法 在求解復(fù)雜優(yōu)化問(wèn)題存在易陷局部極值的事實(shí)，對(duì)粒子群優(yōu)化算法進(jìn)行適當(dāng)改進(jìn)，以能更好更準(zhǔn)確地求解工程的優(yōu)化問(wèn)題是一個(gè)有現(xiàn)實(shí)意義的課題。這是由于每個(gè)算法都具有自身的特點(diǎn)，在具體應(yīng)用中針對(duì)具體問(wèn)題都需進(jìn)行適當(dāng)改進(jìn)，才能用于實(shí)際問(wèn)題的求解，同時(shí)對(duì)同一個(gè)優(yōu)化問(wèn)題、使用同一個(gè)算法，若調(diào)整策略不同，最后得到 的效果也是不一樣的。 針對(duì)以上問(wèn)題，本文展 開(kāi) 了細(xì)致的研究，對(duì) PID 參數(shù) 優(yōu)化問(wèn)題 ，提出了改進(jìn)策略，以適應(yīng)問(wèn)題的求解，提高算法的運(yùn)行速度與最終結(jié)果的精確性。自 PSO 提出以來(lái)，由于它的計(jì)算快速性和算法本身的易實(shí)現(xiàn)性，引起了國(guó)際上相關(guān)領(lǐng)域眾多學(xué)者的關(guān)注和研究，其研究大致 可以 分為：算法本身 參數(shù)選取、拓?fù)浣Y(jié)構(gòu)、與其他進(jìn)化技術(shù)的融合及應(yīng)用。 起初， PSO 是為實(shí)值問(wèn)題而設(shè)計(jì)。為了提高收斂性能，在原始 PSO 算法的速度項(xiàng)中引入了新參數(shù)慣性權(quán)重 (Inertia Weight)，慣性權(quán)重的引入是為了平衡全局與局部搜索能力，慣性權(quán)重較大，全局搜索能力強(qiáng)，局部搜索能力弱，反之，則局部搜索能力增強(qiáng)，而全局搜索能力減弱。動(dòng)態(tài)慣性權(quán)重可以在 PSO 搜索過(guò)程中線性變化，亦可根據(jù)PSO 性能的某個(gè)測(cè)度而動(dòng)態(tài)改變，比如模糊規(guī)則系統(tǒng)。從數(shù)學(xué)上分析，這兩個(gè)參數(shù)是等價(jià)的。此外，為提高 PSO 的性能，研究者又設(shè)計(jì)了許多不同的鄰域結(jié)構(gòu)， Suganthan 在 PSO 算法中引入了空間鄰域的概念，將處于同一個(gè)空間領(lǐng)域的微粒構(gòu)成 一個(gè)子微粒群分別進(jìn)行進(jìn)化，并隨著進(jìn)化動(dòng)態(tài)地改變選擇閾值以保證群體的多樣性； Kennedy 引入鄰域拓?fù)涞母拍顏?lái)調(diào)整鄰域的動(dòng)態(tài)選擇，同時(shí)引入社會(huì)信念將空間鄰域與鄰域拓?fù)渲械沫h(huán)拓?fù)湎嘟Y(jié)合以增加鄰域間的信息交流，提高群體 的多樣性。有些研究者向 PSO 當(dāng)中引入了一些算子，包括選擇、交叉和變異，通過(guò)選擇算子，最好性能的粒子將被直接復(fù)制到下一代，從而保持最優(yōu)性能的粒子，同進(jìn)化算法類似，通過(guò)交叉算子，成對(duì)的粒子將交換相互的信息，以便有向新的搜索空間飛翔的能力，變異算子主要目的是為了增強(qiáng) PSO 跳出局部極小的能力。除了將進(jìn)化算法中的選擇、交叉以及變異算子引入 PSO 外，還有很多與其他經(jīng)典優(yōu)化技術(shù)相結(jié)合的混合 PSO 算法，例如梯度下降、 K 均值聚 類算法、免疫算法等。 第 2 章 粒子群優(yōu)化算法 基本 粒子群算法 粒子群優(yōu)化 (Particle Swarm Optimization，簡(jiǎn)稱 PSO)算法的基本思想是通過(guò)群體中個(gè)體之間的協(xié)作和信息共享來(lái)尋找最優(yōu)解，它包含有進(jìn)化計(jì)算和群集智能的特點(diǎn)。 設(shè)想這樣一個(gè)場(chǎng)景：一群鳥(niǎo) 在空間中隨機(jī) 的搜索食物。那么找到食物的最優(yōu)策略是什么 ?最簡(jiǎn)單有效的方法就是搜尋目前距離食物最近的鳥(niǎo)的周圍區(qū)域，通過(guò)鳥(niǎo)之間的集體協(xié)作與競(jìng)爭(zhēng)使群 體達(dá)到目的。當(dāng)個(gè)體察覺(jué)其它個(gè)體的信念較好的時(shí)候，它將進(jìn)行適應(yīng)性地調(diào) 整 。 如果我們把一個(gè)優(yōu)化問(wèn)題看作是在空中覓食的鳥(niǎo)群，那么在空中飛行的一只覓食的“鳥(niǎo)”就是 PSO 算法中在解空間中進(jìn)行搜索的一個(gè)“ 粒子 ” (Particle)，也是優(yōu)化問(wèn)題的一個(gè)解。粒子的概念是一個(gè)折衷的選擇，它只有速度和位置用于本身狀態(tài)的調(diào)整，而 沒(méi)有質(zhì) 量和體積。因此 PSO 算法也可以看作是對(duì)簡(jiǎn)化了的社會(huì)模型的模擬，社會(huì)群體中的信息共享是推動(dòng)算法的主要機(jī)制。 1c , 2c 為大于零的學(xué)習(xí)因子或稱作加速系數(shù)，分別調(diào)節(jié)該粒子向自身己尋找到的最優(yōu)位置和同伴己尋找到的最優(yōu)位置方向飛行的最大步長(zhǎng)，通常情況下取 1c = 2c =2； 1r , 2r 為介于 [0,1]之間的隨機(jī)數(shù)； t 為迭代次數(shù)，即粒子的飛行步數(shù)。當(dāng)粒子的飛行速度足夠小或達(dá)到預(yù)設(shè)的迭代步數(shù)時(shí)，算法停止迭代，輸出最優(yōu)解。粒子正是通過(guò)自己的經(jīng)驗(yàn)和同伴中最好的經(jīng)驗(yàn)來(lái)決定下一步的運(yùn)動(dòng)。 算法流程 PSO 的具體實(shí)現(xiàn)步驟如下： 步驟 1：初始化粒子群， 包括群體規(guī)模、粒子的初始速度和位置等； 步驟 2：計(jì)算每個(gè)粒子的適應(yīng)度值 (fitness)，存儲(chǔ)每個(gè)粒子的最好位置 ip 和 fitness，并從種群中選擇 fitness 最好的粒子位置作為種群的 gp ； 步驟 3：根據(jù)公式 ()和 ()更新每個(gè)粒子的速度和位置； 步驟 4：計(jì)算位置更新后每個(gè)粒子的適應(yīng)度，將每個(gè)粒子的 fitness 與其以前經(jīng)歷過(guò)的最好位置 ip 時(shí)所對(duì)應(yīng) 的 fitness 比較，如果較好，則將其當(dāng)前的位置作為該粒子的最佳gp ； 步驟 5：將每一個(gè)粒子的適應(yīng)度值 (fitness)與全體粒子所經(jīng)歷過(guò)的最好位置 gp 的適應(yīng)度值比較，如果較好，則將更新 gp 的值； 步驟 6：判斷搜索結(jié)果是否滿足算法設(shè)定的結(jié)束條件 (通常為足夠好的適應(yīng) 度 值或達(dá)到預(yù)設(shè)的最大迭代步數(shù) )，如果沒(méi)有達(dá)到預(yù)設(shè)條件，則返回步驟 3；如果滿足預(yù)設(shè)條件，則停止迭代， 輸出最優(yōu)解。尋找函數(shù) 1 cos 3 xy x e?? ? ? 的在 [0,4]最大值。為了得到該函數(shù)的最大值，我們?cè)?[0， 4]之間隨機(jī)的灑一些點(diǎn)，為了演示，我們放置兩個(gè)點(diǎn)，并且計(jì)算這兩個(gè)點(diǎn)的函數(shù)值，同時(shí)給這兩個(gè)點(diǎn)設(shè)置在 [0， 4]之間的一個(gè)速度。直到最后在 y= 這個(gè)點(diǎn)停止自己的更新。 （ 2） 該函數(shù)的最大值就是鳥(niǎo)群中的食物 。 （ 4） 更新自己位置的一定公式就是粒子群算法中的位置速度更新公式。 算法分析 參數(shù)設(shè)置是粒子群優(yōu)化算法研究的一項(xiàng)重要內(nèi)容，它對(duì)算法的優(yōu)化結(jié)果有較大的影響。不論在基本粒子群優(yōu)化算法還是標(biāo)準(zhǔn)粒子群優(yōu)化算法中，都有一些參數(shù)需要設(shè)定， 下面對(duì)其進(jìn)行全面的分析： （ 1） 粒子種群數(shù)目 m： m 是整型參數(shù)，當(dāng) m=l 的時(shí)候，表示種群中只有一個(gè)粒子， PSO算法變?yōu)榛趥€(gè)體搜索的技術(shù)，一旦陷入局部最優(yōu)，將不能跳出；當(dāng) m 設(shè)置較小時(shí)，算法收斂速度快，但是易陷入局部最優(yōu)；當(dāng) m設(shè)置很大時(shí)， PSO 算法的優(yōu)化能力很好，但是收斂速度非常慢。其實(shí)對(duì)于大部分的問(wèn)題 1020 個(gè)粒子就可以取得很好的效果，而對(duì)于比較復(fù)雜的搜索空間或者特定類型的問(wèn)題，粒子數(shù)可以取到 100 或者更大。 （ 2） 粒子的維數(shù) D： D 也是整型參數(shù)。 （ 3） 粒子的最大速度 maxv ： maxv 是一個(gè)非常重要的參數(shù)，決定 問(wèn) 題空間搜索的力度。 粒子在解空間中的每一維上都有一個(gè)最大速度 maxv ，用來(lái)對(duì)粒子的速度進(jìn)行限制，使速度控制在 max max[ , ]vv? 范圍內(nèi)，這也就決定了粒子在迭代中速度的變化范圍。 （ 4）學(xué)習(xí)因子 12,cc：學(xué)習(xí)因子具有自我總結(jié)和向群體中優(yōu)秀個(gè)體學(xué)習(xí)的能力，從而使粒子向群體內(nèi)或鄰域內(nèi)的最優(yōu)點(diǎn)靠近。當(dāng)學(xué)習(xí)因子值較小時(shí)，可能使粒子在遠(yuǎn)離目標(biāo)區(qū)域內(nèi)徘徊；而當(dāng)學(xué)習(xí)因子較大時(shí)，可能使粒子迅速向目標(biāo)區(qū)域移動(dòng)，甚至越過(guò)目標(biāo)區(qū)域。在粒子相互作用下，算法有能力達(dá)到新的搜索空間。 如果 2 0c? ，則粒子沒(méi)有群體共享信息，即“只有認(rèn)知 (cognition— only)” 模型 。 如果 120cc??，則粒子將以當(dāng)前速度飛行，直到邊界。因此， Shi 和 Eberhart 建議，為了平衡隨機(jī)因素的作用，一般情況下設(shè)置 122cc??，大部分算法都采用這個(gè)建議。 （ 5）