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