1、實驗四 遺傳算法實驗一、 實驗目的：熟悉和掌握遺傳算法的原理、流程和編碼策略，并利用遺傳求解函數優化問題，理解求解TSP問題的流程并測試主要參數對結果的影響。二、 實驗原理：旅行商問題，即TSP問題（Traveling Salesman Problem）是數學領域中著名問題之一。假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路經的限制是每個城市只能拜訪一次，而且最后要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。TSP問題是一個組合優化問題。該問題可以被證明具有NPC計算復雜性。因此，任何能使該問題的求解得以簡化的方法，都將受到高度的評價和關注。遺傳算

2、法的基本思想正是基于模仿生物界遺傳學的遺傳過程。它把問題的參數用基因代表，把問題的解用染色體代表（在計算機里用二進制碼表示），從而得到一個由具有不同染色體的個體組成的群體。這個群體在問題特定的環境里生存競爭，適者有最好的機會生存和產生后代。后代隨機化地繼承了父代的最好特征，并也在生存環境的控制支配下繼續這一過程。群體的染色體都將逐漸適應環境，不斷進化，最后收斂到一族最適應環境的類似個體，即得到問題最優的解。要求利用遺傳算法求解TSP問題的最短路徑。三、 實驗內容及要求1、參考實驗系統給出的遺傳算法核心代碼，用遺傳算法求解TSP的優化問題，分析遺傳算法求解不同規模TSP問題的算法性能。2、對于同

3、一個TSP問題，分析種群規模、交叉概率和變異概率對算法結果的影響。3、增加1種變異策略和1種個體選擇概率分配策略，比較求解同一TSP問題時不同變異策略及不同個體選擇分配策略對算法結果的影響。4、上交源代碼。四、 實驗結果（根據實驗報告要求）1、 畫出遺傳算法求解TSP問題的流程圖。2、 分析遺傳算法求解不同規模的TSP問題的算法性能。（1） 遺傳算法執行方式說明：l 適應度值計算方法：當前路線的路徑長度l 個體選擇概率分配方法：適應度比例方法l 選擇個體方法：輪盤賭選擇l 交叉類型：PMX交叉l 變異類型: 兩點互換變異（2）實驗模擬結果：圖1 圖2 由圖1和圖2可知，遺傳算法執行時間隨著TS

4、P問題規模的增大而增大，并且大致為線性增長。3、 對于同一個TSP問題，分析種群規模、交叉概率和變異概率對算法結果的影響。（1）種群規模對算法結果的影響城市數：15實驗次數：10最大迭代步數:100交叉概率：0.85變異概率：0.15實驗結果：圖3 （2）交叉概率對算法結果的影響城市數：15實驗次數：10種群規模：100最大迭代步數:100變異概率：0.15實驗結果：圖4 在該情況下，交叉概率過低將使搜索陷入遲鈍狀態，得不到最優解。（3）變異概率對算法結果的影響 城市數：15實驗次數：10 種群規模：100 最大迭代步數:100 交叉概率：0.85 實驗結果：圖5 由圖3,4,5可知，當變異概

5、率過大或過低都將導致無法得到最優解。4、 增加1種變異策略和1種個體選擇概率分配策略，比較求解同一TSP問題時不同變異策略及不同個體選擇分配策略對算法結果的影響。（1）兩點互換變異與逆轉變異的比較：城市數:15試驗次數：10 種群規模：100最大迭代步數:100 交叉概率:0.85 變異概率:0.15個體選擇概率分配方法：適應度比例方法a. 變異類型: 兩點互換變異圖6 b. 變異類型: 逆轉變異圖7 因為逆轉變異碼串所呈現的絕對位置變化較大，所以所需的計算時間也就想較長一些。及逆轉變異比兩點互換變異復雜一些。（2）適應度比例方法與線性排序方法比較：城市數:15試驗次數：10 種群規模：100最大迭代步數:100 交叉概率:0.85 變異概率:0.15變異策略：兩點互換變異圖8 五、 實驗總結 同一個算法，參數值不同，獲得的結果