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

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

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

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

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

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

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

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

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

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

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

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