【文章內(nèi)容簡介】 么 粒 子 群 算 法 是 如 何 運 行 的 呢 ， 我 們 先 從 鳥 群 的 捕 食 開 始 說 起 ， 一 群鳥 在 隨 機 搜 索 食 物 ， 在 這 個 區(qū) 域 里 只 有 一 塊 食 物 。 所 有 的 鳥 都 不 知 道 食 物 在 那里 。 但 是 他 們 知 道 當(dāng) 前 的 位 置 離 食 物 還 有 多 遠 。 那 么 找 到 食 物 的 最 優(yōu) 策 略 是 什么 呢 。 最 簡 單 有 效 的 就 是 搜 尋 目 前 離 食 物 最 近 的 鳥 的 周 圍 區(qū) 域 。 PSO從 這 種 模型 中 得 到 啟 示 并 用 于 解 決 優(yōu) 化 問 題 。 PSO中 ， 每 個 優(yōu) 化 問 題 的 解 都 是 搜 索 空 間中 的 一 只 鳥 。 我 們 稱 之 為 “粒 子 ”。 所 有 的 粒 子 都 有 一 個 由 被 優(yōu) 化 的 函 數(shù) 決 定的 適 應(yīng) 值 (fitnessvalue)， 每 個 粒 子 還 有 一 個 速 度 決 定 他 們 飛 翔 的 方 向 和 距離 。 然 后 粒 子 們 就 追 隨 當(dāng) 前 的 最 優(yōu) 粒 子 在 解 空 間 中 搜 索 。 PSO初 始 化 為 一 群 隨機 粒 子 (隨 機 解 )， 然 后 通 過 疊 代 找 到 最 優(yōu) 解 ， 在 每 一 次 疊 代 中 ， 粒 子 通 過 跟蹤 兩 個 “極 值 ”來 更 新 自 己 。 第 一 個 就 是 粒 子 本 身 所 找 到 的 最 優(yōu) 解 ， 這 個 解叫 做 自 身 最 優(yōu) pBest， 另 一 個 極 值 是 整 個 種 群 目 前 找 到 的 最 優(yōu) 解 ， 這 個 極 值 是全 局 最 優(yōu) gBest。 群 體 的 行 為 非 常 復(fù) 雜 ， 在 尋 優(yōu) 的 過 程 中 遵 循 以 下 三 個 的 原 則 ：（ 1） 飛 離 最 近 的 個 體 ， 以 避 免 碰 撞 。（ 2） 飛 向 目 標(biāo) 。（ 3） 飛 向 群 體 的 中 心 。接 下 來 具 體 的 表 述 一 下 粒 子 群 算 法 的 原 理 ， 首 先 假 設(shè) ：為 微 粒 的 當(dāng) 前 位 置 ； 為 微 粒 的 的 當(dāng) 前??imii xx??,21?i??imii vv??,21?i飛 行 速 度 ； 為 微 粒 所 經(jīng) 歷 的 最 好 位 置 ， 也 就 是 微 粒 所??imii pp??,21 i經(jīng) 歷 過 的 具 有 最 好 適 應(yīng) 值 的 位 置 ， 稱 為 個 體 最 優(yōu) 位 置 。 對 于 最 小 化 問 題 ， 目 標(biāo)函 數(shù) 值 越 小 ， 對 應(yīng) 的 適 應(yīng) 值 越 好 。 設(shè) 為 最 小 化 的 目 標(biāo) 函 數(shù) ， 則微粒i的當(dāng)前最好位置由下式確定：??tf10 / 34 ??)1(tpi???????tpftxftxpiii iii ???11若若（21）設(shè)群體中的微粒數(shù)為s，群體中所有微粒所經(jīng)歷過的最好位置為 (ｔ)，gP稱為全局最好位置。 ??????????????tpftftpftpfttpt sgsg ,min, 1010 ???? ??且（22）根據(jù)對鳥群捕食的行為研究，總結(jié)出了粒子群算法的進化方程 ?????????txtrctxtrctvtv ijgjjijijjijij ?????21（23）這里下標(biāo) 是表示微粒的第 維， 表示第 個微粒， 表示第 代，jjiitt為加速常數(shù)，通常在02之間取值， 為兩個相互獨立的隨機數(shù)。從進21,c 21,r化方以可以看出， 調(diào) 節(jié) 微 粒 飛 向 自 身 最 好 位 置 方 向 的 步 長 ， 調(diào) 節(jié) 微 粒 向1c 2c全 局 最 好 位 置 飛 行 的 步 長 。 為 了 減 少 在 進 化 過 程 中 ， 微 粒 離 開 搜 索 空 間 的 可 能性 ， 通 常 限 定 于 一 定 范 圍 內(nèi) ， 即 如 果 問 題 的 搜 索 空 間 限 定ijv ??max,vvij??在 內(nèi) ， 則 可 設(shè) 定 ， 并 且 可 以 取 值 。??max,x??maxk???k仿真中僅利用上面三條簡單的規(guī)則，就可以非常接近的模擬出鳥群飛行的現(xiàn)象。1990年，生物學(xué)家Frank Heppner也提出了鳥類模型 [8]，它的不同之處在于：鳥類被吸引飛到棲息地。在仿真中，一開始每一只鳥都沒有特定的飛行目標(biāo)，只是使用簡單的規(guī)則確定自己的飛行方向和飛行速度（每一只鳥都試圖留在鳥群中而又不相互碰撞） ，當(dāng)有一只鳥飛到棲息地時，它周圍的鳥也會跟著飛向棲息地，這樣，整個鳥群都會落在棲息地。自20世紀(jì)30年代以來，社會心理學(xué)的發(fā)展揭示：我們都是魚群或鳥群聚集行為的遵循者。在人們的不斷交互過程中，由于相互的影響和模仿，他們總會變得更相似，結(jié)果就形成了規(guī)范和文明。人類的自然行為和魚群及鳥群并不類似，而人類在高維認知空間中的思維軌跡卻與之非常類似。思維背后的社會現(xiàn)象遠比魚群和鳥群聚集過程中的優(yōu)美動作復(fù)雜的多：首先，思維發(fā)生在信念空間，其維數(shù)遠遠高于3；其次，當(dāng)兩種思想在認知空間會聚于同一點時，我們稱其一致，而不是發(fā)生沖突。PSO 從這種模型中得到啟示并用于解決優(yōu)化問題。PSO 中，每個優(yōu)化問題的潛在解都是搜索空間中的一只鳥，稱之為粒子。所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適值( fitness value) ，每個粒子還有一個速度決定它們飛翔的方向和距離。然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索。PSO 初始化為一群隨機粒子(隨機解)，然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個極值來更新自己；第一個就是粒子本身所找到的最優(yōu)解，這個解稱為個體極值；另一個極值是整個種群目前找到的最優(yōu)解，這個極值是全局極值。另外也可以不用整個種群而只是用其中一部分作為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。11 / 34 PSO 算 法 的 基 本 步 驟 和 流 程基本粒子群優(yōu)化算法的基本步驟可歸納如下：（1）初始化粒子群，即隨機設(shè)定各粒子的初始位置 x 和初始速度 v；（2）計算每個粒子的適應(yīng)度值；（3）對每個粒子，比較它的適應(yīng)度值和它經(jīng)歷的最好位置 Pi 的適應(yīng)度值；若更好，更新Pi；（4）對每個粒子，比較它的適應(yīng)度值和群體所經(jīng)歷的最好位置 Pg 的適應(yīng)度值；若更好，更新 Pg；（5）根據(jù)位置和速度的更新公式調(diào)整粒子的位置和速度；（6）若達到結(jié)束條件（足夠好的位置或最大迭代次數(shù)） ，結(jié)束；否則，轉(zhuǎn)步驟 2。圖 21 為基本 PSO 算法的流程圖12 / 34開始初始化數(shù)值設(shè)置各參數(shù)初始化 x 變量和初始粒子位置與速度、權(quán)重值粒子速度更新粒子位置更新判斷粒子速度是否超出約束區(qū)間對粒子群進行優(yōu)化評價，并取最優(yōu)值迭代多次并和最優(yōu)值對比，是否優(yōu)于最優(yōu)值結(jié)束是否隨機產(chǎn)生加速權(quán)重系數(shù)值人r1，r2重新更新粒子速度和位置輸出最優(yōu)數(shù)值是否圖 21 PSO 算法流程圖13 / 34 基 本 PSO 參 數(shù) 設(shè) 置 PSO 中并沒有許多需要調(diào)節(jié)的參數(shù)，下面列出了這些參數(shù)以及經(jīng)驗設(shè)置：（1）粒子數(shù)：較小的群能充分探索解空間，避免了過多的適應(yīng)值評估和計算時間。一般取20－40。其實對于大部分的問題 10 個粒子已經(jīng)足夠可以取得好的結(jié)果，不過對于比較難的問題或者特定類別的問題，粒子數(shù)可以取到 100 或 200。（2）粒子的長度：這是由優(yōu)化問題決定，就是問題解的長度。（3）粒子的范圍：由優(yōu)化問題決定,每一維可以設(shè)定不同的范圍。（4） ：最大速度，決定粒子在一個循環(huán)中最大的移動距離，通常設(shè)定為粒子的范圍maxV寬度，例如，粒子 ， 屬于[－10，10]，那么 Vmax 的大小就是 10。123(,)xi（5）加速因子： 和 通常等于 2。不過在資料中也有其他的取值。但是一般 等于c 1c并且范圍在 0 和 4 之間。2c（6）中止條件：最大循環(huán)數(shù)以及最小錯誤要求。例如，最小錯誤可以設(shè)定為 1 個錯誤分類，最大循環(huán)數(shù)設(shè)定為 10000，這個中止條件由具體的問題確定。（7）全局 PSO 和局部 PSO：兩種版本的粒子群優(yōu)化算法：全局版和局部版。前者速度快不過有時會陷入局部最優(yōu)。后者收斂速度慢一點不過很難陷入局部最優(yōu)。在實際應(yīng)用中，可以先用全局 PSO 找到大致的結(jié)果，再用局部 PSO 進行搜索。（8）慣性權(quán)值：w 控制著速度前一變化量對當(dāng)前變化量的影響，如果 w 較大，則影響較大，能夠搜索以前所未能達到的區(qū)域，整個算法的全局搜索能力加強，有利于跳出局部極小點；而 w 值較小，則前一動量項的影響較小，主要是在當(dāng)前解的附近搜索，局部搜索能力較強，有利于算法收斂。 帶 慣 性 權(quán) 重 的 粒 子 群 算 法1998年，Yuhui Shi提出了帶有慣性權(quán)重的改進粒子群算法。其進化過程為： （24） )()()()(()1( 21 txtprctxtprctwvtv ijgiijijijij ????? （25）1?vxijijij在式(24)中，第一部分表示粒子先前的速度，用于保證算法的全局收斂性能；第二部分、第三部分則是使算法具有局部收斂能力。可以看出，式（25)中慣性權(quán)重 表示在多w大程度上保留原來的速度。 較大，全局收斂能力強，局部收斂能力弱； 較小，局部收w斂能力強，全局收斂能力弱。當(dāng) 時，式(23)與式(24)完全一樣，表明帶慣性權(quán)重的粒子群算法是基本粒子1?w群算法的擴展。實驗結(jié)果表明， 在 之間時， PSO算法有更快的收斂速度，而當(dāng)][?時，算法則易陷入局部極值。2.?14 / 34 粒 子 群 算 法 的 應(yīng) 用粒子群算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領(lǐng)域，對問題的種類有很強的適應(yīng)性，所以廣泛應(yīng)用于很多學(xué)科。下面是粒子群算法的一些主要應(yīng)用領(lǐng)域：（1）函數(shù)優(yōu)化。函數(shù)優(yōu)化是粒子群算法的經(jīng)典應(yīng)用領(lǐng)域，也是對粒子群算法進行性能評價的常用算例。（2）約束優(yōu)化。隨著問題的增多，約束優(yōu)化問題的搜索空間也急劇變換，有時在目前的計算機上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。粒子群算法是解決這類問題的最佳工具之一。實踐證明，粒子群算法對于約束優(yōu)化中的規(guī)劃，離散空間組合問題的求解非常有效。（3）工程設(shè)計問題。工程設(shè)計問題在許多情況下所建立起來的數(shù)學(xué)模型難以精確求解，即使經(jīng)過一些簡化之后可以進行求解，也會因簡化得太多而使得求解結(jié)果與實際相差甚遠。現(xiàn)在粒子群算法已成為解決復(fù)雜調(diào)度問題的有效工具，在電路及濾波器設(shè)計、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、控制器設(shè)計與優(yōu)化、任務(wù)分配等方面粒子群算法都得到了有效的應(yīng)用。（4）電力系統(tǒng)領(lǐng)域。在其領(lǐng)域中有種類多樣的問題，根據(jù)目標(biāo)函數(shù)特性和約束類型許多與優(yōu)化相關(guān)的問題需要求解。PSO 在電力系統(tǒng)方面的應(yīng)用主要如下：配電網(wǎng)擴展規(guī)劃、檢修計劃、機組組合、負荷經(jīng)濟分配、最優(yōu)潮流計算與無功優(yōu)化控制、諧波分析與電容配置、配電網(wǎng)狀態(tài)估計、參數(shù)辨識、優(yōu)化設(shè)計。隨著粒子群優(yōu)化理論研究的深入，它還將在電力市場競價交易、投標(biāo)策略以及電力市場仿真等領(lǐng)域發(fā)揮巨大的應(yīng)用潛在力。（5）機器人智能控制。機器人是一類復(fù)雜的難以精確建模的人工系統(tǒng)，而粒子群算法可用于此類機器人群搜索，如機器人的控制與協(xié)調(diào)，移動機器人路徑規(guī)劃。所以機器人智能控制理所當(dāng)然地成為粒子群算法的一個重要應(yīng)用領(lǐng)域。（6）交通運輸領(lǐng)域。交通方面有車輛路徑問題，在物流配送供應(yīng)領(lǐng)域中要求以最少的車輛數(shù)、最小的車輛總行程來完成貨物的派送任務(wù)；交通控制，城市交通問題是困擾城市發(fā)展、制約城市經(jīng)濟建設(shè)的重要因素。城市交通運輸系統(tǒng)的管理和控制技術(shù)進行研究，來為緩解交通擁擠發(fā)揮巨大作用。其中在其解決方法中應(yīng)用粒子群算法給解決問題提供了新的，有效的計算方式。（7）通信領(lǐng)域。其中包括路由選擇及移動通信基站布置優(yōu)化，在順序碼分多址連接方式（DSCDMA）通訊系統(tǒng)中使用粒子群算法，可獲得可移植的有力算法并提供并行處理能力。比傳統(tǒng)的先前的算法有了顯著的優(yōu)越性。還應(yīng)用到天線陣列控制和偏振模色散補償?shù)确矫妗＃?）計算機領(lǐng)域。在計算機中處理各種問題都涉及到大量的信息計算的方法選擇以減少程序運行的時間，增加系統(tǒng)解決問題的能力，其中包括任務(wù)分配問題、數(shù)據(jù)分類、圖像處理等，都得到了粒子群算法的實際問題解決效率的提高。（9）生物醫(yī)學(xué)領(lǐng)域。許多菌體的生長模型即為非線性模型提出了用粒子群算法解決非線性模型的參數(shù)估計問題。還在分子力場的參數(shù)設(shè)定和蛋白質(zhì)圖形的發(fā)現(xiàn)。根據(jù)粒子群算法提出的自適應(yīng)多峰生物測定融合算法，提高了解決問題的準(zhǔn)確性。在醫(yī)學(xué)方面，如醫(yī)學(xué)成像上得到的推廣應(yīng)用等。15 / 34 粒 子 群 優(yōu) 化 算 法 的 發(fā) 展 方 向在算法的理論研究方面。目前PSO算法還沒有成熟的理論分析，少部分研究者對算法的收斂性進行了分析，大部分研究者在算法的結(jié)構(gòu)和性能改善方面進行研究，包括參數(shù)分析，拓撲結(jié)構(gòu)，粒子多樣性保持，算法融合和性能比較等。PSO由于有簡單、易于實現(xiàn)、設(shè)置參數(shù)少、無需梯度信息等特點，其在連續(xù)非線性優(yōu)化問題和組合優(yōu)化問題中都表現(xiàn)出良好的效果。目前，粒子群算法的發(fā)展趨勢主要有：(1)粒子群優(yōu)化算法的改進。粒子群優(yōu)化算法在解決空間函數(shù)的優(yōu)化問題和單目標(biāo)優(yōu)化問題上應(yīng)用得比較多，如何應(yīng)用于離散空間優(yōu)化問題和多目標(biāo)優(yōu)化問題將是粒子群優(yōu)化算法的主要研究方向。如何充分結(jié)合其他進化類算法，發(fā)揮優(yōu)勢，改進粒子群優(yōu)化算法的不足也是值得研究的。(2)粒子群優(yōu)化算法的理論分析。粒子群優(yōu)化算法提出的時間不長，數(shù)學(xué)分析很不成熟和系統(tǒng)，存在許多不完善和未涉及