【導(dǎo)讀】PSO算法已經(jīng)被證明是一種有效的全局優(yōu)化方法，并且廣泛應(yīng)用于函。數(shù)優(yōu)化，神經(jīng)網(wǎng)絡(luò)訓(xùn)練以及模糊系統(tǒng)控制等領(lǐng)域。目前對粒子群優(yōu)化算法的研究尚處。于初期，它今后的發(fā)展還有許多工作需要不斷充實提高。要研究對象，尋找求解實際問題的更加有效的改進(jìn)算法是很有意義的。題，是一個典型的NP難題，許多實際問題都可以轉(zhuǎn)化為旅行商問題。的進(jìn)化粒子群算法在TSP中的應(yīng)用研究。法的思想來解決TSP問題。仿真，得到了較為滿意的結(jié)果。

　　

【正文】 c1=c2=0，設(shè)初始速度非零，則大于 的 w 將使粒子朝最大速度 maxV 方向加速；小于 的 w 使粒子放慢速度，直至最終速度達(dá)到零，粒子停止了運動。 Shi 和 Eberhart 研究了 w 在范圍 P[0,]的影響。其結(jié)果表明選擇 w∈[,]導(dǎo)致收斂加速，但是大的 w 值（ ）導(dǎo)致收斂失敗。 由于 PSO 的搜索過程是非線性的且非常復(fù)雜，對搜索過程數(shù)學(xué)模型化，從而動態(tài)地修改慣性權(quán)值是非常困難 的。由于慣性權(quán)值的設(shè)置對 PSO 算法性能的關(guān)鍵作用，目前已經(jīng)有多個文獻(xiàn)針對慣性權(quán)值的研究，并且對算法作了不同改進(jìn)。 基于加速因子的 PSO 改進(jìn) 從粒子的速度更新公式來看，第一部分表示了粒子當(dāng)前速度對粒子飛行的影響，這部分提供了粒子在搜索空間飛行的動力。第二部分是所謂的“個體認(rèn)知”部分，代表了粒子的個人經(jīng)驗，促使粒子朝著自身所經(jīng)歷過的最好位置移動。第三部分是所謂“群體認(rèn)知”部分，代表了群體經(jīng)驗對粒子飛行軌跡的影響，促使粒子朝著群體發(fā)現(xiàn)的最好位置移動。 加速因子 1c 和 2c 決定了粒子本身經(jīng)驗信息和其他粒子的經(jīng)驗信息對粒子運行軌跡的影響，反映了粒子群之間的信息交流。設(shè)置較大 1c 的值，會使粒子過多的在局部范圍徘徊，相反，較大的 2c 值會促使粒子過早收斂到局部最小值。 Shi 和 Eberhart 建議，為了平衡隨機(jī)因素的作用，一般情況下設(shè)置 122cc??，大部分算法都采用這個建議 。但是一般 1c 等于 2c 并且范圍在 0 和 4 之間。 Clerc 的研究表明，加速因子有助于保證算法收斂。 Suganthan 測試了一種根據(jù)疊代次數(shù)線性遞減加速因子的方法，實驗結(jié)果比使用加速因子固定值等于 2 的 PSO 算法差。但通過實驗觀察結(jié)果，他認(rèn)為加速因子在搜索過程中不必保持不變。 Ratnaweera 和 Halgamuge在文獻(xiàn) [8]使用根據(jù)疊代次數(shù)修改加速因子的方法進(jìn)行實驗，在算法初期使用較大 1c 值，較小 2c 值，允許粒子在局部范圍搜索，而不是直接向全局最優(yōu)位置移動；算法后期減小 1c 值，增大 2c 值，促使算法收斂。計算加速因子的公式如下： 1 1 1 1()f i iite rc c c cM A X ite r? ? ? （ 33） 2 2 2 2()f i iite rc c c cM A X ite r? ? ? （ 34） 實驗結(jié)果表明，這種方法確實加速了算法的收斂，在單峰值函數(shù)的測試表現(xiàn)優(yōu)異。為此付出的代價是算法容易陷入局部最小值，在多峰值函數(shù)的測試中容易過早收斂。 基于鄰近群拓?fù)涞母倪M(jìn) 根據(jù)在公式（ 31）中對群體的全局最優(yōu)位置 gp 的選擇方法，粒子群優(yōu)化算法可以分為：全局版本（ gBest）和局部版本（ lBest）。 ● gBest模型 在 gBest 模型中，選擇整個群中的最 優(yōu)粒子作為唯一的最優(yōu)解，群的所有粒子都使用相同的 gp 值更新自己的速度和位置，朝著這個最優(yōu)粒子聚集。 ● lBest模型 在 lBest 模型中，粒子群根據(jù)選擇的拓?fù)?，劃分為多個小種群，每個粒子根據(jù)自己所屬的小種群，選擇該小種群的局部最優(yōu)解更新自己的速度和位置，因此，每個粒子選擇的gp值不一定是全體粒子的最優(yōu)位置。也就是說，更新粒子群的gp的值有多個。 圖 31 反映了兩個不同鄰近群拓?fù)?PSO 中粒子之間的信息流向： 圖 31 兩種不同的鄰近群拓?fù)涞?PSO 從圖中可以看出，在全局 PSO 中，每個粒子的信息可以被其它所有粒子獲得，一旦某個粒子發(fā)現(xiàn)較好的位置，所有粒子都會迅速聚集到該粒子周圍，算法的收斂速度快，同時，粒子群也容易陷入局部最優(yōu)值。在局部 PSO 中，由于每個粒子獲得的群體最優(yōu)位置的信息不一定相同，導(dǎo)致粒子收斂的方向不一定相同，因此算法的收斂速度比全局 PSO 慢，不容易陷入局部最優(yōu)。因此，對鄰近群拓?fù)涞倪x擇影響了 PSO算法的性能。 基于 lBest 模 型，產(chǎn)生了多種拓?fù)涞淖冃危鐖D 32 所示。 圖 32 兩種變形拓?fù)? Kennedy 的研究對不同鄰近群的拓?fù)浣Y(jié)構(gòu)進(jìn)行測試。在文獻(xiàn) [9]也使用了不同連接拓?fù)涞?PSO 進(jìn)行實驗。實驗結(jié)果都表明了，選擇一種合適的鄰近群拓?fù)?，對算法性能的影響是明顯的。然而沒有一種鄰近群拓?fù)鋵λ谢鶞?zhǔn)函數(shù)都是最合適的，具體選擇哪一中鄰近群拓?fù)渑c具體的問題有關(guān)。例如，使用信息交流率越高的拓?fù)洌ㄈ巛喰危惴ǖ氖諗克俣仍娇?，適用于單峰值分布的函數(shù)。這再次驗證了“免費午餐理論”。 基于種群規(guī)模的改進(jìn) 粒子群的大小也 是標(biāo)準(zhǔn)粒子群優(yōu)化算法的關(guān)鍵參數(shù)之一，粒子數(shù)太少，容易使粒子在陷入局部最小值，粒子數(shù)太多會減慢算法的速度。大多數(shù)的實驗使用的粒子數(shù)為20～ 40 個。同樣的，粒子數(shù)的選擇于具體問題有關(guān)。 通常情況下，群大小是一個常數(shù)，群粒子的數(shù)目在算法運行中保持不變。但是，仍無法提出一個最優(yōu)的群大小。所以，算法中不時地改變?nèi)捍笮∷坪醺袃?yōu)勢。 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的性能變化。單個粒子的能量計算公式如下： | ( ( )) |() ipi f x tet ?? （ 35） 整個種群的能量由下式計算： .( ) ( )p p iiE t G e t? ? （ 36） 通過觀測種群和粒子的能量在算法運行過程中的變化， Clerc 認(rèn)為，針對具體函數(shù) ，一個合適的固定的種群規(guī)模的 PSO 要比動態(tài)調(diào)整種群規(guī)模的 PSO 性能更好。但是在需要通過多次嘗試才能找到合適種群規(guī)模的情況下，使用動態(tài)調(diào)整種群規(guī)模的方法可以節(jié)省時間。 第 4 章 一種改進(jìn)的求解 TSP 混合粒子群優(yōu)化算法 本章結(jié)合遺傳算法、蟻群算法和模擬退火算法的思想 ,用混合粒子群算法 [1]來求解著名的旅行商問題 .。與模擬退火算法、標(biāo)準(zhǔn)遺傳算法進(jìn)行比較， 24 種混合粒子群算法的效果都比較好，而且簡單有效，收斂速度快，結(jié)果也比較優(yōu)，對于目前仍沒有較好解法的組合優(yōu)化問題 , 通過此算法修改很容易解決。 混 合粒子群算法的概述 混合粒子群算法的本質(zhì)是利用本身信息、個體極值信息和全局極值信息 3 個信息，指導(dǎo)例子下一步迭代位置，對于 TSP 問題，其當(dāng)前位置是基本路徑，若按基本粒子群算法，其速度難以表達(dá)，故采用遺傳算法的思想解決。 1 0 1 2( ) ( )k k k k k kv c v c p b e st x c g b e st x? ? ? ? ? ? （ 41） 11k k kx x v???? （ 42） 式（ 41）、（ 42）為基本粒子群優(yōu)化算法的粒子速度和位置更新公式。在 混合粒子 群 算 法 當(dāng) 中 ， 式 （ 41 ） 中 的 0kcv 項 可 看 作 遺 傳 算 法 的 變 異 操 作 ，12( ) ( )k k k kc pbe st x c gbe st x? ? ?項可看作遺傳算法的交叉操作，使當(dāng)前解與個體極值和全局極值分別作交叉操作，產(chǎn)生的解為新的位置。變異操作和交叉操作后，新的解可能比原來的解要壞，接受準(zhǔn)則是采用模擬退火算法的思想，允許目標(biāo)函數(shù)有限范圍內(nèi)變壞，為簡化計算并不按概率取舍，直接按 Δ Ee， e 為按允許目標(biāo)函數(shù)變壞的范圍。 變異操作 這里假設(shè)有 n 個城市，由路徑 C0 變異到另一條路徑 C1，常用的有以下幾種策略： 1） 變異策略 A：在第 1~n 個訪問的城市中隨機(jī)選取第 j1 次和第 j2 次訪問的城市，在路徑 C0 中交換第 j1 次和第 j2 次訪問的城市，其余不變，此時路徑為 C1。 2） 變異策略 B：在第 1~n 個訪問的城市中隨機(jī)選取第 j1 次訪問的城市，在路徑 C0 中交換第 j1 次和第 j+1 次訪問的城市，其余不變，此時路徑為C1。 3） 變異策略 C：在第 1~n 個訪問的城市中隨機(jī)選取第 j1 次和第 j2 次訪問的城市，在路徑 C0 中第 j1 次到第 j2 次訪問的城市之間的子路徑以反方向插入，其余不變，此時路徑為 C1。 4） 變 異策略 D：在第 1~n 個訪問的城市中隨機(jī)選取第 j1 次和第 j2 次訪問的 城市，假設(shè) j1j2，路徑 C0 中將第 j1 次訪問的城市安排到第 j2 次訪問的城市之后，其余不變，此時路徑為 C1。 5） 變異策略 E：上述策略未利用城市間距離大小的信息，變異策略 E 將利用點的鄰接關(guān)系，依據(jù)蟻群算法的思想，距離近的鄰接點以較大的概率被選為下一個訪問點，所以在局部調(diào)整時依據(jù)此思想。設(shè) d（ i， j）表示城市 i 與城市 j 的距離，在第 1~n 個城市中隨機(jī)選取城市 i1，離城市 i1 最遠(yuǎn)的城市的距離為 ： m ax m ax ( 1, )jd d i j? （ 43） 為了排除下一個訪問點為其本身，令 d（ i1， i1） =dmax，則下一個訪問點為城市 j 的概率為 ： m a xm a x1( 1, )( ( 1, ))j nkd d i jpd d i j????? （ 44） 假設(shè)以公式（ 43）的概率選擇城市 j1，在路徑 C0 中將城市 j1 安排在 i1之后，其余不變，此時路徑為 C1。 6） 變異策略 F：在第 1~n 個城市中隨機(jī)選取城市 i1，為了使路徑總長度之和達(dá)到最小，優(yōu)先解決薄弱環(huán)節(jié)，這里采用路徑中相鄰城市 間距離大的兩個城市以較大的概率被選取，在它們之間插入其他城市。采用 l（ n）數(shù)組記錄路徑 C0 相鄰城市之間的距離，具體數(shù)據(jù)如下： ( ) [ ( ) , ( 1 ) ] 1 , 2 , , 1 。l k d c k c k k n? ? ? ? （ 45） ( ) [ ( ), (1)]l n d c n c? （ 46） 選取城市 i 的概率為： 1( ) / ( ( ))ni kp l i l k?? ? （ 47） 按式（ 47）選取城市 i1，后面方法同策略變異 E， 按式（ 44）選取城市j1，在路徑 C0 中將城市 j1 安排在 i1 之后，其余不變，此時路徑為 C1。 交叉操作 交叉的方法很多 , 下面幾種方法最常用： 1） 交叉策略 A：在第 2 個串中隨機(jī)選擇一個交叉區(qū)域；將 old2 的交叉區(qū)域加到 old1 前面（或后面），刪除 old1 中已在 old2 交叉區(qū)中出現(xiàn)過的城市。 2） 交叉策略 B：在第 2 個串中隨機(jī)選擇一個交叉區(qū)域；將 old2 的交叉區(qū)域 加到 old1 對應(yīng)的位置，刪除 old1 中已在 old2 交叉區(qū)中出現(xiàn)過的城市。 3） 交叉策略 C：在第 2 個串中隨機(jī)選擇一個交叉區(qū)域；將 old2 的交叉區(qū)域加到 old1 的隨機(jī)位置，刪除 old1 中已在 old2 交叉區(qū)中出現(xiàn)過的城市。 4） 交叉策略 D：在第 2 個串中隨機(jī)選擇一個交叉區(qū)域，如交叉區(qū)域為： 6， 5，4， 3； 找非交叉區(qū)域城市離交叉區(qū)域兩端城市 6 和城市 3 最近的城市，若城市 8， 3 最近，則將 old2 的交叉區(qū)域加到 old1 的城市 8 的位置（有可能逆轉(zhuǎn)），刪除 old1 中已在 old2 交叉區(qū)中出現(xiàn)過的城市。 混合粒子群算法 解 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。1()Cj； 39。1()Cj與 pcbest 交叉得到 39。39。1()Cj； 對 39。39。1()Cj產(chǎn)生變異得到 C1（ 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（