基于GA的TSP求解

1、 第十七章第十七章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用第第17章章 基于基于GA的的TSP求解求解 第十七章第十七章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用17.1 旅行商問題分析旅行商問題分析 旅行商問題（Traveling Salesman Problem，簡稱TSP），也稱貨郎擔問題，是數(shù)學(xué)領(lǐng)域中的著名問題之一。TSP問題已經(jīng)被證明是一個NP-hard問題，由于TSP問題代表一類組合優(yōu)化問題，因此對其近似解的研究一直是算法設(shè)計的一個重要問題。該問題的求解算法主要分為兩類。一類是與問題特征相關(guān)的啟發(fā)式搜索算法。主要有動態(tài)規(guī)劃法、分支界定法等。另一類是獨立

2、于問題的智能優(yōu)化算法，如模擬退火法、禁忌搜索法、蟻群算法、遺傳算法、粒子群算法等。本文將基于遺傳算法進行TSP問題的求解。 第十七章第十七章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用17.2 遺傳算法遺傳算法算子分析算子分析 在遺傳算法中，通過編碼組成初始群體后，遺傳操作的任務(wù)就是對群體的個體按照它們對環(huán)境適應(yīng)度施加一定的操作，從而實現(xiàn)優(yōu)勝劣汰的進化過程。從優(yōu)化搜索的角度而言，遺傳操作可使問題的解，一代又一代地優(yōu)化，并逼進最優(yōu)解。遺傳操作包括以下三個基本遺傳算子，選擇算子、交叉算子和變異算子。17.2.1 選擇算子（選擇算子（selection） 從群體中選擇優(yōu)勝的個體，淘汰劣質(zhì)

3、個體的操作叫選擇。選擇的目的是把優(yōu)化的個體直接遺傳到下一代或通過配對交叉產(chǎn)生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應(yīng)度評估基礎(chǔ)上的，目前常用的選擇算子有適應(yīng)度比例方法、隨機遍歷抽樣法、局部選擇法。 其中輪盤賭選擇法（Roulette Wheel Selection）是最簡單也是最常用的選擇方法。 第十七章第十七章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用17.2 遺傳算法遺傳算法算子分析算子分析17.2.2 交叉算子（交叉算子（crossover）交叉算子根據(jù)交叉率將種群中的兩個個體隨機地交換某些基因，能夠產(chǎn)生新的基因組合，期望將有益基因組合在一起。根據(jù)編碼表示方

4、法的不同分為實值重組和二進制交叉兩類算法。其中實值重組（real valued recombination）可分為：（1）離散重組 （discrete recombination）；（2）中間重組（intermediate recombination）；（3）線性重組（linear recombination）；（4）擴展線性重組（extended linear recombination）。二進制交叉（binary valued crossover）可分為：（1）單點交叉（single-point crossover）；（2）多點交叉（multiple-point crossover）；（3

5、）均勻交叉（uniform crossover）；（4）洗牌交叉（shuffle crossover）；（5）縮小代理交叉（crossover with reduced surrogate）。其中，最常用的交叉算子為單點交叉(one-point crossover)。具體操作是，在個體串中隨機設(shè)定一個交叉點，實行交叉時，該點前或后的兩個個體的部分結(jié)構(gòu)進行互換，并生成兩個新個體。 第十七章第十七章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用17.2 遺傳算法遺傳算法算子分析算子分析17.2.3 變異算子（變異算子（mutation）一般來說，變異算子操作的分兩步完成。 （1）對群中所

6、有個體以事先設(shè)定的編譯概率判斷是否進行變異； （2）對進行變異的個體隨機選擇變異位進行變異。 遺傳算法引入變異的目的有兩個：一是使遺傳算法具有局部的隨機搜索能力。當遺傳算法通過交叉算子已接近最優(yōu)解鄰域時，利用變異算子的這種局部隨機搜索能力可以加速向最優(yōu)解收斂。顯然，此種城市的指定為一個明確的目標情況下的變異概率應(yīng)取較小值，否則接近最優(yōu)解的積木塊會因變異而遭到破壞。二是使遺傳算法可維持群體多樣性，以防止出現(xiàn)未成熟收斂現(xiàn)象。此時收斂概率應(yīng)取較大值。 遺傳算法中，交叉算子因其全局搜索能力而作為主要算子，變異算子因其局部搜索能力而作為輔助算子。遺傳算法通過交叉和變異這對相互配合又相互競爭的操作而使其具

7、備兼顧全局和局部的均衡搜索能力。 所謂相互配合，是指當群體在進化中陷于搜索空間中某個超平面而僅靠交叉不能擺脫時，通過變異操作可有助于這種擺脫。所謂相互競爭，是指當通過交叉已形成所期望的積木塊時，變異操作有可能破壞這些積木塊。如何有效地配合使用交叉和變異操作，是目前遺傳算法的一個重要研究內(nèi)容。 第十七章第十七章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用17.3 基于基于GA的旅行商問題求解的旅行商問題求解17.3.1 TSP問題定義問題定義 TSP問題從描述上來看是一個非常簡單的問題，給定 個城市和各城市之間的距離，尋找一條遍歷所有城市且每個城市只被訪問一次的路徑。并保證總路徑距離

8、最短。TSP問題的數(shù)學(xué)模型表示如下：jiijijxcZmin vjixvkKxvjxvjxtsijsjiijjiijijij,1 , 01-11. ., 第十七章第十七章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用17.3 基于基于GA的旅行商問題求解的旅行商問題求解17.3.2 基于遺傳算法的基于遺傳算法的TSP算法框架算法框架遺傳算法求解TSP的基本步驟如下：（1）種群初始化。個體編碼方法有二進制編碼和實數(shù)編碼，在解決TSP問題過程中個體編碼方法為實數(shù)編碼。對于TSP問題，實數(shù)編碼為1-n的實數(shù)的隨機排列，初始化的參數(shù)有種群個數(shù)M、染色體基因個數(shù)N（即城市的個數(shù)）、迭代次數(shù)C、

9、交叉概率Pc、變異概率Pm。（2）適應(yīng)度函數(shù)。在TSP問題中，對于任意兩個城市之間的距離 已知，每個染色體（即n個城市的隨機排列）可計算出總距離，因此可將一個隨機全排列的總距離的倒數(shù)作為適應(yīng)度函數(shù)，即距離越短，適應(yīng)度函數(shù)越好，滿足TSP要求。（3）選擇操作。遺傳算法選擇操作有輪盤賭法、錦標賽法等多種方法，本程序采用基于適應(yīng)度比例的選擇策略，即適應(yīng)度越好的個體被選擇的概率越大，同時在選擇中保存適應(yīng)度最高的個體。（4）交叉操作。遺傳算法中交叉操作有多種方法。本程序中對于個體，隨機選擇兩個個體，在對應(yīng)位置交換若干個基因片段，同時保證每個個體依然是1-n的隨機排列，防止進入局部收斂。（5）變異操作。本

10、程序中對于變異操作，隨機選取個體，同時隨機選取個體的兩個基因進行交換以實現(xiàn)變異操作。,D i j 第十七章第十七章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用17.3 基于基于GA的旅行商問題求解的旅行商問題求解17.3.3 TSP算法流程框圖算法流程框圖 第十七章第十七章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用17.3 基于基于GA的旅行商問題求解的旅行商問題求解17.3.4 固定地圖固定地圖TSP求解求解圖17-3 30城市TSP圖1 第十七章第十七章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用17.3 基于基于GA的旅行商問題求解的旅行商問題求解1

11、7.3.4 固定地圖固定地圖TSP求解求解圖17-3 50城市TSP圖1 第十七章第十七章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用17.3 基于基于GA的旅行商問題求解的旅行商問題求解17.3.5 隨機地圖隨機地圖TSP求解求解012345678910012345678910Total Distance = 86.1202, Iteration = 149圖17-8 隨機動態(tài)地圖1 第十七章第十七章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用17.3 基于基于GA的旅行商問題求解的旅行商問題求解17.3.5 隨機地圖隨機地圖TSP求解求解圖17-9 隨機城市點位置0

12、12345678910012345678910城 市 位 置 第十七章第十七章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用17.3 基于基于GA的旅行商問題求解的旅行商問題求解17.3.5 隨機地圖隨機地圖TSP求解求解圖17-10 城市之間的歐氏距離距 離 矩 陣 -imagesc51015202530354045505101520253035404550 第十七章第十七章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用17.3 基于基于GA的旅行商問題求解的旅行商問題求解17.3.5 隨機地圖隨機地圖TSP求解求解圖17-11 TSP可行解012345678910012345678910最 短 距 離 = 62.4236 第十七章第十七章MATLAB優(yōu)化算法案例分析與應(yīng)用優(yōu)化算法案例分析與應(yīng)用17.3 基于基于GA的旅行商問題求解的旅行商問題求解17.3.5 隨機地圖隨機地圖TSP求解求解圖17-12 遺傳算法適應(yīng)度收斂曲線010002000300040005000600070008000900010000050100150200250最 佳 適 應(yīng) 度 曲 線 第十七章第十七章MATLAB優(yōu)