【正文】 SO 中，每個粒子的信息可以被其它所有粒子獲得，一旦某個粒子發(fā)現(xiàn)較好的位置，所有粒子都會迅速聚集到該粒子周圍，算法的收斂速度快，同時，粒子群也容易陷入局部最優(yōu)值。在局部 PSO 中，由于每個粒子獲得的群體最優(yōu)位置的信息不一定相同，導致粒子收斂的方向不一定相同，因此算法的收斂速度比全局 PSO 慢，不容易陷入局部最優(yōu)。因此，對鄰近群拓撲的選擇影響了PSO 算法的性能。基于 lBest 模型，產生了多種拓撲的變形，如圖 32 所示。圖 32 兩種變形拓撲Kennedy 的研究對不同鄰近群的拓撲結構進行測試。在文獻 [9]也使用了不同連接拓撲的 PSO 進行實驗。實驗結果都表明了，選擇一種合適的鄰近群拓撲，對算法性能的影響是明顯的。然而沒有一種鄰近群拓撲對所有基準函數(shù)都是最合適的，具體選擇哪一中鄰近群拓撲與具體的問題有關。例如，使用信息交流率越高的拓撲（如輪形） ，算法的收斂速度越快，適用于單峰值分布的函數(shù)。這再次驗證了“免費午餐理論” 。 基于種群規(guī)模的改進粒子群的大小也是標準粒子群優(yōu)化算法的關鍵參數(shù)之一，粒子數(shù)太少，容易使粒子在陷入局部最小值，粒子數(shù)太多會減慢算法的速度。大多數(shù)的實驗使用的粒子數(shù)為 20～40 個。同樣的，粒子數(shù)的選擇于具體問題有關。通常情況下，群大小是一個常數(shù)，群粒子的數(shù)目在算法運行中保持不變。但是，仍無法提出一個最優(yōu)的群大小。所以，算法中不時地改變群大小似乎更有優(yōu)勢。Clerc 提出了動態(tài)調整種群的規(guī)模的想法：● 如果種群的改進質量達不到預設置的閾值，那么如果一個粒子是所在鄰近群中的最優(yōu)粒子，為種群增加一個自己的復制● 如果種群的改進質量達到了預設置的閾值，那么如果一個粒子是所在鄰近群中的最差粒子，把該粒子消滅Clerc 設置了一個能量函數(shù)，用來評價固定規(guī)模 PSO 和動態(tài)規(guī)模 PSO 的性能變化。單個粒子的能量計算公式如下： （3|()|)ipifxtet??5）整個種群的能量由下式計算： （3.()()ppiEtGet?6）通過觀測種群和粒子的能量在算法運行過程中的變化，Clerc 認為，針對具體函數(shù)，一個合適的固定的種群規(guī)模的 PSO 要比動態(tài)調整種群規(guī)模的 PSO 性能更好。但是在需要通過多次嘗試才能找到合適種群規(guī)模的情況下，使用動態(tài)調整種群規(guī)模的方法可以節(jié)省時間。第 4 章 一種改進的求解 TSP 混合粒子群優(yōu)化算法本章結合遺傳算法、蟻群算法和模擬退火算法的思想,用混合粒子群算法 [1]來求解著名的旅行商問題.。與模擬退火算法、標準遺傳算法進行比較，24 種混合粒子群算法的效果都比較好，而且簡單有效，收斂速度快，結果也比較優(yōu)，對于目前仍沒有較好解法的組合優(yōu)化問題, 通過此算法修改很容易解決。 混合粒子群算法的概述混合粒子群算法的本質是利用本身信息、個體極值信息和全局極值信息 3 個信息，指導例子下一步迭代位置，對于 TSP 問題，其當前位置是基本路徑，若按基本粒子群算法，其速度難以表達，故采用遺傳算法的思想解決。 （41012()()kkkkvcpbestxcgbestx?????1） （411kkv??2） 式（41 ） 、 （42 ）為基本粒子群優(yōu)化算法的粒子速度和位置更新公式。在混合粒子群算法當中，式（41）中的 項可看作遺傳算法的變異操作，0kcv項可看作遺傳算法的交叉操作，使當前解與個體極值12()()kkcpbestxcgbestx???和全局極值分別作交叉操作，產生的解為新的位置。變異操作和交叉操作后，新的解可能比原來的解要壞，接受準則是采用模擬退火算法的思想，允許目標函數(shù)有限范圍內變壞，為簡化計算并不按概率取舍，直接按 ΔEe，e 為按允許目標函數(shù)變壞的范圍。 變異操作這里假設有 n 個城市，由路徑 C0 變異到另一條路徑 C1，常用的有以下幾種策略：1） 變異策略 A：在第 1~n 個訪問的城市中隨機選取第 j1 次和第 j2 次訪問的城市，在路徑 C0 中交換第 j1 次和第 j2 次訪問的城市，其余不變，此時路徑為 C1。2） 變異策略 B：在第 1~n 個訪問的城市中隨機選取第 j1 次訪問的城市，在路徑 C0 中交換第 j1 次和第 j+1 次訪問的城市，其余不變，此時路徑為C1。3） 變異策略 C：在第 1~n 個訪問的城市中隨機選取第 j1 次和第 j2 次訪問的城市，在路徑 C0 中第 j1 次到第 j2 次訪問的城市之間的子路徑以反方向插入，其余不變，此時路徑為 C1。4） 變異策略 D：在第 1~n 個訪問的城市中隨機選取第 j1 次和第 j2 次訪問的城市，假設 j1j2，路徑 C0 中將第 j1 次訪問的城市安排到第 j2 次訪問的城市之后，其余不變，此時路徑為 C1。5） 變異策略 E：上述策略未利用城市間距離大小的信息，變異策略 E 將利用點的鄰接關系，依據(jù)蟻群算法的思想，距離近的鄰接點以較大的概率被選為下一個訪問點，所以在局部調整時依據(jù)此思想。設 d（i，j ）表示城市 i 與城市 j 的距離，在第 1~n 個城市中隨機選取城市 i1，離城市 i1最遠的城市的距離為： （4max(1,)jdij?3）為了排除下一個訪問點為其本身，令 d（i1，i1）=dmax，則下一個訪問點為城市 j 的概率為： （4max1(,)jnkijpd???4）假設以公式（43）的概率選擇城市 j1，在路徑 C0 中將城市 j1 安排在 i1之后，其余不變，此時路徑為 C1。6） 變異策略 F：在第 1~n 個城市中隨機選取城市 i1，為了使路徑總長度之和達到最小，優(yōu)先解決薄弱環(huán)節(jié)，這里采用路徑中相鄰城市間距離大的兩個城市以較大的概率被選取，在它們之間插入其他城市。采用 l（n）數(shù)組記錄路徑 C0 相鄰城市之間的距離，具體數(shù)據(jù)如下： （4()[(),1],21。lkdckn?????5） （4()[(),]lnc6）選取城市 i 的概率為： （41()/)nikpll??7）按式（47 ）選取城市 i1，后面方法同策略變異 E，按式（44）選取城市j1，在路徑 C0 中將城市 j1 安排在 i1 之后，其余不變，此時路徑為 C1。 交叉操作交叉的方法很多, 下面幾種方法最常用：1） 交叉策略 A：在第 2 個串中隨機選擇一個交叉區(qū)域；將 old2 的交叉區(qū)域加到 old1 前面（或后面） ，刪除 old1 中已在 old2 交叉區(qū)中出現(xiàn)過的城市。2） 交叉策略 B：在第 2 個串中隨機選擇一個交叉區(qū)域；將 old2 的交叉區(qū)域加到 old1 對應的位置，刪除 old1 中已在 old2 交叉區(qū)中出現(xiàn)過的城市。3） 交叉策略 C：在第 2 個串中隨機選擇一個交叉區(qū)域；將 old2 的交叉區(qū)域加到 old1 的隨機位置，刪除 old1 中已在 old2 交叉區(qū)中出現(xiàn)過的城市。4） 交叉策略 D：在第 2 個串中隨機選擇一個交叉區(qū)域，如交叉區(qū)域為：6，5，4，3； 找非交叉區(qū)域城市離交叉區(qū)域兩端城市 6 和城市 3 最近的城市，若城市 8，3 最近，則將 old2 的交叉區(qū)域加到 old1 的城市 8 的位置（有可能逆轉） ，刪除 old1 中已在 old2 交叉區(qū)中出現(xiàn)過的城市。 混合粒子群算法解 TSP 的混合粒子群算法如下：設定粒子數(shù) m，規(guī)定迭代次數(shù) N_max，隨機產生 m 個初始解（初始路徑）C0；根據(jù)當前位置計算適應值（各路徑的長度）ltsp0，設置當前適應值為個體極值plbest，當前位置為個體極值位置 pcbest，根據(jù)各個粒子的個體極值 plbest，找出全局極值 glbest 和全局極值位置 gcbest；While（迭代次數(shù)N_max）do For j=1：m 第 j 個粒子路徑 C0（j）與交叉得到 ；39。1()Cj 與 pcbest 交叉得到 ；39。1()C39。1()j 對 產生變異得到 C1（j） ；39。j 根據(jù)當前位置計算適應值 ltsp1； 計算兩個位置所引起的適應值的變化量 ΔE；若 ΔEe（e 為按允許目標函數(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。 C0←C1 ；End While最后輸出全局極值 glbest 和全局極值位置 gcbest；混合粒子群算法的時間復雜性可估算如下：以交叉時間花費最多，內循環(huán)需要作 O（2m）交叉操作，外循環(huán)執(zhí)行 N_max 次，所以時間復雜度約為 O（2mN_max） 。其流程圖如圖 41 所示 214。200。186。179。245。202。188。187。175。198。192。185。184。246。204。229。202。211。166。214。181。ltsp1194。190。182。C0163。168。j169。211。235。184。246。204。229。238。211。197。206。187。214。195。pcbest 181。218。210。187。180。206。189。187。178。230。178。217。247。181。189。194。190。182。C1163。168。j)194。190。182。C1163。168。j)211。235。200。171。190。214。238。211。197。206。187。214。195。gcbest246。181。218。182。254。180。206。189。187。178。230。246。178。217。181。189。194。C2163。168。j)194。190。182。C2(j)212。201。237。246。177。228。210。236。178。217。247。181。195。189。194。190。182。C3(j)ltsp1(j)plbest(j)plbest(j)glbest(j)194。227。209。187。204。245。188。254。plbest(j)=ltsp(j)glbest(j)=plbest(j)202。228。179。246。189。225。185。YN YNNY189。225。202。248。圖 41 混合粒子群算法流程圖 算法測試每種算法對 burma14 進行 10 次仿真結果如下（burma14 最優(yōu)解為 ）：●　 交叉策略 A 變異策略 A：表 41 交叉策略 A 變異策略 A 對 burma14 的仿真結果微粒數(shù) 迭代次數(shù) 平均用時 最優(yōu)解 最差解 平均值10 50 20 50 30 50 圖 42 交叉策略 A 變異策略 A 對 burma14 的仿真的最優(yōu)路線圖 43 交叉策略 A 變異策略 A 收斂曲線 由表和圖可以看出，交叉策略 A 變異策略 A 的收斂速度比較快，尋優(yōu)率也比較高，在對 14 個城市的仿真中基本都可以找到最優(yōu)路徑?！瘛?交叉策略 A 變異策略 B：表 42 交叉策略 A 變異策略 B 對 burma14 的仿真結果微粒數(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)路徑。●　 交叉策略 A 變異策略 C：表 43 交叉策略 A 變異策略 C 對 burma14 的仿真結果微粒數(shù) 迭代次數(shù) 平均用時 最優(yōu)解 最差解 平均值10 50 20 50 30 50 圖 46 交叉策略 A 變異策略 C 對 burma14 的仿真的最優(yōu)路線圖 47 交叉策略 A 變異策略 C 收斂曲線由表和圖可以看出，交叉策略 A 變異策略 C 的收斂速度較之變異策略 B 還要慢一些，但相對的結果也要好一些，在對 14 個城市的仿真中基本都可以找到最優(yōu)路徑?！? 交叉策略 B 變異策略 A：表 44 交叉策略 B 變異策略 A 對 burma14 的仿真結果微粒數(shù) 迭代次數(shù) 平均用時 最優(yōu)解 最差解 平均值10 50 20 50 30 50 圖 48 交叉策略 B 變異策略 A 對 burma14 的仿真的最優(yōu)路線圖 49 交叉策略 B 變異策略 A 收斂曲線 由圖可以看出交叉策略 B 變異策略 A 在收斂速度和尋優(yōu)結果上都和交叉策略 A變異策略 A 差不太多，但從表中數(shù)據(jù)可以看出，交叉策略 B 沒有交叉策略 A 的尋優(yōu)率高?！瘛?交叉策略 B 變異策略 B：表 45 交叉策略 B 變異策略 B 對 burma14 的仿真結果微粒數(shù) 迭代次數(shù) 平均用時 最優(yōu)解 最差解 平均值10 50 20 50 30