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