【正文】 ● 交叉策略 B 變異策略 A：表 44 交叉策略 B 變異策略 A 對 burma14 的仿真結(jié)果微粒數(shù) 迭代次數(shù) 平均用時 最優(yōu)解 最差解 平均值10 50 20 50 30 50 圖 48 交叉策略 B 變異策略 A 對 burma14 的仿真的最優(yōu)路線圖 49 交叉策略 B 變異策略 A 收斂曲線 由圖可以看出交叉策略 B 變異策略 A 在收斂速度和尋優(yōu)結(jié)果上都和交叉策略 A變異策略 A 差不太多，但從表中數(shù)據(jù)可以看出，交叉策略 B 沒有交叉策略 A 的尋優(yōu)率高?！瘛?交叉策略 A 變異策略 B：表 42 交叉策略 A 變異策略 B 對 burma14 的仿真結(jié)果微粒數(shù) 迭代次數(shù) 平均用時 最優(yōu)解 最差解 平均值10 50 20 50 30 50 圖 44 交叉策略 A 變異策略 B 對 burma14 的仿真的最優(yōu)路線圖 45 交叉策略 A 變異策略 B 收斂曲線由表和圖可以看出，交叉策略 A 變異策略 B 的收斂速度較之變異策略 A 則慢了很多，但相對的尋優(yōu)率也要高一些，在對 14 個城市的仿真中基本都可以找到最優(yōu)路徑。248。225。225。246。228。254。245。209。182。189。181。217。236。228。246。201。182。168。189。217。246。178。189。180。182。181。195。187。197。238。190。200。j)211。C1163。190。j)194。C1163。190。194。181。217。230。187。206。187。218。195。187。197。238。204。184。211。168。182。181。166。202。204。184。192。175。188。245。186。其流程圖如圖 41 所示 214。j 根據(jù)當(dāng)前位置計算適應(yīng)值 ltsp1； 計算兩個位置所引起的適應(yīng)值的變化量 ΔE；若 ΔEe（e 為按允許目標(biāo)函數(shù)變壞的范圍） ，ΔE≤0，接受新值；否則，拒絕，第 j 個粒子路徑C1（j）仍然為 C0（j ） ；如果 ltsp1（j）plbest（j） ，則 pcbest（j）=C1（j） ，plbest（j）=ltsp1（j ） ； End For 根據(jù)各個粒子的個體極值 plbest, 找出全局極值 glbest 和全局極值位置gcbest。1()C39。 混合粒子群算法解 TSP 的混合粒子群算法如下：設(shè)定粒子數(shù) m，規(guī)定迭代次數(shù) N_max，隨機(jī)產(chǎn)生 m 個初始解（初始路徑）C0；根據(jù)當(dāng)前位置計算適應(yīng)值（各路徑的長度）ltsp0，設(shè)置當(dāng)前適應(yīng)值為個體極值plbest，當(dāng)前位置為個體極值位置 pcbest，根據(jù)各個粒子的個體極值 plbest，找出全局極值 glbest 和全局極值位置 gcbest；While（迭代次數(shù)N_max）do For j=1：m 第 j 個粒子路徑 C0（j）與交叉得到 ；39。3） 交叉策略 C：在第 2 個串中隨機(jī)選擇一個交叉區(qū)域；將 old2 的交叉區(qū)域加到 old1 的隨機(jī)位置，刪除 old1 中已在 old2 交叉區(qū)中出現(xiàn)過的城市。 交叉操作交叉的方法很多, 下面幾種方法最常用：1） 交叉策略 A：在第 2 個串中隨機(jī)選擇一個交叉區(qū)域；將 old2 的交叉區(qū)域加到 old1 前面（或后面） ，刪除 old1 中已在 old2 交叉區(qū)中出現(xiàn)過的城市。采用 l（n）數(shù)組記錄路徑 C0 相鄰城市之間的距離，具體數(shù)據(jù)如下： （4()[(),1],21。設(shè) d（i，j ）表示城市 i 與城市 j 的距離，在第 1~n 個城市中隨機(jī)選取城市 i1，離城市 i1最遠(yuǎn)的城市的距離為： （4max(1,)jdij?3）為了排除下一個訪問點為其本身，令 d（i1，i1）=dmax，則下一個訪問點為城市 j 的概率為： （4max1(,)jnkijpd???4）假設(shè)以公式（43）的概率選擇城市 j1，在路徑 C0 中將城市 j1 安排在 i1之后，其余不變，此時路徑為 C1。4） 變異策略 D：在第 1~n 個訪問的城市中隨機(jī)選取第 j1 次和第 j2 次訪問的城市，假設(shè) j1j2，路徑 C0 中將第 j1 次訪問的城市安排到第 j2 次訪問的城市之后，其余不變，此時路徑為 C1。2） 變異策略 B：在第 1~n 個訪問的城市中隨機(jī)選取第 j1 次訪問的城市，在路徑 C0 中交換第 j1 次和第 j+1 次訪問的城市，其余不變，此時路徑為C1。變異操作和交叉操作后，新的解可能比原來的解要壞，接受準(zhǔn)則是采用模擬退火算法的思想，允許目標(biāo)函數(shù)有限范圍內(nèi)變壞，為簡化計算并不按概率取舍，直接按 ΔEe，e 為按允許目標(biāo)函數(shù)變壞的范圍。 （41012()()kkkkvcpbestxcgbestx?????1） （411kkv??2） 式（41 ） 、 （42 ）為基本粒子群優(yōu)化算法的粒子速度和位置更新公式。與模擬退火算法、標(biāo)準(zhǔn)遺傳算法進(jìn)行比較，24 種混合粒子群算法的效果都比較好，而且簡單有效，收斂速度快，結(jié)果也比較優(yōu)，對于目前仍沒有較好解法的組合優(yōu)化問題, 通過此算法修改很容易解決。但是在需要通過多次嘗試才能找到合適種群規(guī)模的情況下，使用動態(tài)調(diào)整種群規(guī)模的方法可以節(jié)省時間。Clerc 提出了動態(tài)調(diào)整種群的規(guī)模的想法：● 如果種群的改進(jìn)質(zhì)量達(dá)不到預(yù)設(shè)置的閾值，那么如果一個粒子是所在鄰近群中的最優(yōu)粒子，為種群增加一個自己的復(fù)制● 如果種群的改進(jìn)質(zhì)量達(dá)到了預(yù)設(shè)置的閾值，那么如果一個粒子是所在鄰近群中的最差粒子，把該粒子消滅Clerc 設(shè)置了一個能量函數(shù)，用來評價固定規(guī)模 PSO 和動態(tài)規(guī)模 PSO 的性能變化。但是，仍無法提出一個最優(yōu)的群大小。同樣的，粒子數(shù)的選擇于具體問題有關(guān)。 基于種群規(guī)模的改進(jìn)粒子群的大小也是標(biāo)準(zhǔn)粒子群優(yōu)化算法的關(guān)鍵參數(shù)之一，粒子數(shù)太少，容易使粒子在陷入局部最小值，粒子數(shù)太多會減慢算法的速度。例如，使用信息交流率越高的拓?fù)洌ㄈ巛喰危?，算法的收斂速度越快，適用于單峰值分布的函數(shù)。實驗結(jié)果都表明了，選擇一種合適的鄰近群拓?fù)?，對算法性能的影響是明顯的。圖 32 兩種變形拓?fù)銴ennedy 的研究對不同鄰近群的拓?fù)浣Y(jié)構(gòu)進(jìn)行測試。因此，對鄰近群拓?fù)涞倪x擇影響了PSO 算法的性能。圖 31 反映了兩個不同鄰近群拓?fù)?PSO 中粒子之間的信息流向：圖 31 兩種不同的鄰近群拓?fù)涞?PSO從圖中可以看出，在全局 PSO 中，每個粒子的信息可以被其它所有粒子獲得，一旦某個粒子發(fā)現(xiàn)較好的位置，所有粒子都會迅速聚集到該粒子周圍，算法的收斂速度快，同時，粒子群也容易陷入局部最優(yōu)值。gp● lBest 模型在 lBest 模型中，粒子群根據(jù)選擇的拓?fù)?，劃分為多個小種群，每個粒子根據(jù)自己所屬的小種群，選擇該小種群的局部最優(yōu)解更新自己的速度和位置，因此，每個粒子選擇的 值不一定是全體粒子的最優(yōu)位置。 基于鄰近群拓?fù)涞母倪M(jìn)根據(jù)在公式（31）中對群體的全局最優(yōu)位置 的選擇方法，粒子群優(yōu)化算法gp可以分為：全局版本（gBest）和局部版本（lBest ） 。計算加速12c因子的公式如下： （3111 1()fi iitercccMAX???3） （3222()fi itre4）實驗結(jié)果表明，這種方法確實加速了算法的收斂，在單峰值函數(shù)的測試表現(xiàn)優(yōu)異。但通過實驗觀察結(jié)果，他認(rèn)為加速因子在搜索過程中不必保持不變。12Clerc 的研究表明，加速因子有助于保證算法收斂。Shi 和 Eberhart2c建議，為了平衡隨機(jī)因素的作用，一般情況下設(shè)置 ，大部分算法都采用這12?個建議。加速因子 和 決定了粒子本身經(jīng)驗信息和其他粒子的經(jīng)驗信息對粒子運(yùn)行軌1c2跡的影響，反映了粒子群之間的信息交流。第二部分是所謂的“個體認(rèn)知”部分，代表了粒子的個人經(jīng)驗，促使粒子朝著自身所經(jīng)歷過的最好位置移動。由于慣性權(quán)值的設(shè)置對 PSO 算法性能的關(guān)鍵作用，目前已經(jīng)有多個文獻(xiàn)針對慣性權(quán)值的研究，并且對算法作了不同改進(jìn)。其結(jié)果表明選擇w∈[,]導(dǎo)致收斂加速，但是大的 w 值（ ）導(dǎo)致收斂失敗。 簡要解釋 w 的效果，令 c1=c2=0，設(shè)初始速度非零，則大于 的 w 將使粒子朝最大速度 方向加速；小于 的 w 使粒子放慢速度，直至最終速度達(dá)到零，maxV粒子停止了運(yùn)動。其中的慣性權(quán)值控制了粒子以前經(jīng)歷過的速度對當(dāng)前速度的影響，決定上一時刻的速度將保留多少下來。 39。為了方便討論，這里再次列出粒子的更新公式： （339。每個潛在解與粒子運(yùn)行速度相聯(lián)系，該速度不停地根據(jù)粒子經(jīng)驗以及粒子鄰居們的經(jīng)驗來調(diào)整大小、方向，總是希望粒子能朝著更好的方向發(fā)展。當(dāng)前已經(jīng)有多種對 PSO 算法的改進(jìn)，然而正如“沒有免費(fèi)午餐”的理論所認(rèn)為的，這些改進(jìn)算法需要針對具體問題的特點，根據(jù)領(lǐng)域知識對算法參數(shù)進(jìn)行設(shè)置，在提高某種性能的同時也為此付出相應(yīng)代價?！皼]有免費(fèi)午餐”的理論認(rèn)為：不包含領(lǐng)域知識的算法不一定有效，但包含過多的問題領(lǐng)域知識也會因此導(dǎo)致算法對其它問題的脆弱性。 第 3 章 PSO 算法的改進(jìn)算法自然界是豐富多彩的，我們的生活也同樣多姿多彩。在實際應(yīng)用中，可以先用全局 PSO 找到大致的結(jié)果，再用局部PSO 進(jìn)行搜索。前者速度快不過有時會陷入局部最優(yōu)。例如，最小錯誤可以設(shè)定為 1 個錯誤分類，最大循環(huán)數(shù)設(shè)定為 2022，這個中止條件由具體的問題確定。但是一般1c2等于 并且范圍在 0 和 4 之間。● 加速因子： 和 通常等于 2?！? 粒子的范圍：由優(yōu)化問題決定,每一維可以設(shè)定不同的范圍。其實對于大部分的問題 10 個粒子已經(jīng)足夠可以取得好的結(jié)果，不過對于比較難的問題或者特定類別的問題，粒子數(shù)可以取到 100或 200。 PSO 中并沒有許多需要調(diào)節(jié)的參數(shù)，下面列出了這些參數(shù)以及經(jīng)驗設(shè)置：● 粒子數(shù)：較小的群能充分探索解空間，避免了過多的適應(yīng)值評估和計算時間。接著就可以利用前面的過程去尋優(yōu)。PSO 的一個優(yōu)勢是采用實數(shù)編碼，不需要像遺傳算法一樣是二進(jìn)制編碼（或者采用針對實數(shù)的遺傳操作） 。如此反復(fù)直至滿足終止條件。gp5）循環(huán)反復(fù)：這些過程都在群中的粒子執(zhí)行一遍后，重新從步驟 4 開始。通過對粒子速度更新公式的研究，粒子速度隨著局部和全局最優(yōu)位置的改變而改變，朝著適應(yīng)值更大的方向加速。若該值大于此時粒子的局部或全局最優(yōu)值，則當(dāng)前位置要由更恰當(dāng)?shù)奈恢么妗?）粒子在解空間中的飛行：該算法在每個粒子身上起作用。因為其初始位置也是每個粒子在運(yùn)動初期的第一個位置，所以該位置也是每個粒子自身的局部最優(yōu)位置。適應(yīng)值函數(shù)和解空間必須是針對該優(yōu)化算法而定；剩余的實現(xiàn)部分獨(dú)立于被優(yōu)化的實際問題之外。2）定義適應(yīng)值函數(shù)：這個重要步驟提供了優(yōu)化算法和實際問題的接口。N圖 22 PSO 算法流程圖 應(yīng)用 PSO 算法步驟應(yīng)用粒子群優(yōu)化算法的基本步驟可歸納如下：1）定義解空間：第一步是挑選需要優(yōu)化的參數(shù)并賦予其搜索最優(yōu)解的范圍。202。Y189。188。204。187。227。X(k)YYN N194。225。197。238。179。Fk(Xk)pBest(i)202。204。184。249。218。212。210。193。193。181。166。202。204。184。192。189。186。214。202。179。g PSO 算法的基本步驟和流程1） 初始化粒子群，即隨機(jī)設(shè)定各粒子的初始位置 x 和初始速度 v；2） 計算每個粒子的適應(yīng)度值；3） 對每個粒子，比較它的適應(yīng)度值和它經(jīng)歷的最好位置 的適應(yīng)度值；若更好，idP更新 ；idP4） 對每個粒子，比較它的適應(yīng)度值和群體所經(jīng)歷的最好位置 的適應(yīng)度值；若gd更 好，更新 ；gd5） 根據(jù)位置和速度的更新公式調(diào)整粒子的位置和速度；6） 若達(dá)到結(jié)束條件（足夠好的位置或最大迭代次數(shù)） ，結(jié)束；否則，轉(zhuǎn)步驟 2。在路gp徑上的每個點，粒子將目前位置的適應(yīng)值與全局最優(yōu)值比較。若當(dāng)前位ip置的適應(yīng)值更高，則 由當(dāng)前位置代替。4）局部最優(yōu)位置：個體獨(dú)自發(fā)現(xiàn)的有著最高適應(yīng)值的位置稱為個體最優(yōu)或局部最優(yōu)。適應(yīng)函數(shù)必須代替解空間中的位置并返回表示位置值的數(shù)字。在設(shè)置 PSO 中，需要把優(yōu)化問題化解為一組能代表解空間中位置的值。群中的所有粒子在相同組織原則下獨(dú)立運(yùn)行，不停地檢查目前位置的同時朝著最優(yōu)的局部和全局位置加速。PSO 是一種進(jìn)化算法，它有以下幾個進(jìn)化計算的典型特征：? 有一個隨機(jī)初始化過程，在這個過程中，群體中的個體被賦值為一些隨機(jī)產(chǎn)生的隨機(jī)解? 通過產(chǎn)生更好的新一代群體來搜索空間? 新一代群體產(chǎn)生在前一代的基礎(chǔ)上在粒子群優(yōu)化算法應(yīng)用中，應(yīng)先明確其特點和關(guān)鍵問題，才能對這種算法深入了解靈活應(yīng)用，以及進(jìn)一步研究開發(fā)。許多實際問題都可以歸結(jié)為函數(shù)優(yōu)化問題，PSO 問題算法用于一般的函數(shù)優(yōu)化問題并不令人意外。 粒子群優(yōu)化算法的特點及應(yīng)用關(guān)鍵PSO 算法一提出就吸引了廣泛的注意，各種關(guān)于 PSO 算法應(yīng)用研究的成果不斷涌現(xiàn)，有力地推動了 PSO 研究。盡管已經(jīng)有簡化確定性版本的收斂性分析，但將確定性向隨機(jī)性的轉(zhuǎn)化尚需進(jìn)一步研究。PSO 相對于 GA，沒有交叉和變異操作，粒子只是通過內(nèi)部速度進(jìn)行更新，因此原理