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