模擬退火算法解決TSP問題

1、 智能優(yōu)化方法課題報告 專業(yè)班級： 電子信息科學與技術(shù)12-3班 課題名稱： 模擬退火算法解決TSP問題 指導教師： 姚 睿 學生姓名： 蔣文斌 學 號： 08123453 （課題設計時間：2015年3月28日2015年 4月13日）中國礦業(yè)大學計算機學院一、問題描述旅行商問題（Traveling monituihuolesman Problem，簡稱TSP）又名貨郎擔問題，是威廉·哈密爾頓爵士和英國數(shù)學家克克曼(T.P.Kirkman)于19世紀初提出的一個數(shù)學問題，也是著名的組合優(yōu)化問題。問題是這樣描述的：一名商人要到若干城市去推銷商品，已知城市個數(shù)和各城市間的路程（或旅費），要

2、求找到一條從城市1出發(fā)，經(jīng)過所有城市且每個城市只能訪問一次，最后回到城市1的路線，使總的路程（或旅費）最小。TSP剛提出時，不少人認為這個問題很簡單。后來人們才逐步意識到這個問題只是表述簡單，易于為人們所理解，而其計算復雜性卻是問題的輸入規(guī)模的指數(shù)函數(shù)，屬于相當難解的問題。這個問題數(shù)學描述為：假設有n個城市，并分別編號，給定一個完全無向圖G=（V，E），V=1，2，n，n>1。其每一邊(i,j)E有一非負整數(shù)耗費 Ci,j(即上的權(quán)記為Ci,j，i，jV)。并設 G的一條巡回路線是經(jīng)過V中的每個頂點恰好一次的回路。一條巡回路線的耗費是這條路線上所有邊的權(quán)值之和。TSP問題就是要找出G的最

3、小耗費回路。人們在考慮解決這個問題時，一般首先想到的最原始的一種方法就是:列出每一條可供選擇的路線(即對給定的城市進行排列組合)，計算出每條路線的總里程，最后從中選出一條最短的路線。假設現(xiàn)在給定的4個城市分別為A、B、C和D，各城市之間的耗費為己知數(shù)，如圖1-1所示。我們可以通過一個組合的狀態(tài)空間圖來表示所有的組合，如圖1-2所示。 圖 1-1 頂點帶權(quán)圖 圖 1-2 TSP問題的解空間樹1.模擬退火是什么?首先,讓我們看看模擬退火是如何工作的,以及為什么它是善于解決旅行商問題。模擬退火（Simulated Annealing，簡稱monituihuo）是一種通用概率算法，用來在一個大的搜尋空

4、間內(nèi)找尋命題的最優(yōu)解。該算法是源于對熱力學中退火過程的模擬，在某一給定初溫下，通過緩慢下降溫度參數(shù)，使算法能夠在多項式時間內(nèi)給出一個近似最優(yōu)解。退火與冶金學上的“退火”相似，而與冶金學的淬火有很大區(qū)別，前者是溫度緩慢下降，后者是溫度迅速下降。我們將熱力學的理論套用到統(tǒng)計學上，將搜尋空間內(nèi)每一點想像成空氣內(nèi)的分子；分子的能量，就是它本身的動能；而搜尋空間內(nèi)的每一點，也像空氣分子一樣帶有“能量”，以表示該點對命題的合適程度。算法先以搜尋空間內(nèi)一個任意點作起始：每一步先選擇一個“鄰居”，然后再計算從現(xiàn)有位置到達“鄰居”的概率。2.模擬退火的優(yōu)點先來說下爬山算法：爬山算法是一種簡單的貪心搜索算法，該算

5、法每次從當前解的臨近解空間中選擇一個最優(yōu)解作為當前解，直到達到一個局部最優(yōu)解。爬山算法實現(xiàn)很簡單，其主要缺點是會陷入局部最優(yōu)解，而不一定能搜索到全局最優(yōu)解。如圖1-3所示：假設C點為當前解，爬山算法搜索到A點這個局部最優(yōu)解就會停止搜索，因為在A點無論向那個方向小幅度移動都不能得到更優(yōu)的解。爬山法是完完全全的貪心法，每次都鼠目寸光的選擇一個當前最優(yōu)解，因此只能搜索到局部的最優(yōu)值。 圖1-3 爬山算法模擬退火其實也是一種貪心算法，但是它的搜索過程引入了隨機因素。模擬退火算法以一定的概率來接受一個比當前解要差的解，因此有可能會跳出這個局部的最優(yōu)解，達到全局的最優(yōu)解。以圖1-3為例，模擬退火算法在搜索

6、到局部最優(yōu)解A后，會以一定的概率接受到E的移動。 也許經(jīng)過幾次這樣的不是局部最優(yōu)的移動后會到達D點，于是就跳出了局部最大值A(chǔ)。3.模擬退火算法描述：若J(Y(i+1)>=J(Y(i)(即移動后得到更優(yōu)解)，則總是接受該移動。若J(Y(i+1)< J(Y(i)(即移動后的解比當前解要差)，則以一定的概率接受移動，而且這個概率隨著時間推移逐漸降低（逐漸降低才能趨向穩(wěn)定）這里的“一定的概率”的計算參考了金屬冶煉的退火過程，這也是模擬退火算法名稱的由來。根據(jù)熱力學的原理，在溫度為T時，出現(xiàn)能量差為dE的降溫的概率為P(dE)，表示為：P(dE) = exp(dE/(kT)其中k是一個常數(shù)，

7、exp表示自然指數(shù)，且dE<0。這條公式說白了就是：溫度越高，出現(xiàn)一次能量差為dE的降溫的概率就越大；溫度越低，則出現(xiàn)降溫的概率就越小。 又由于dE總是小于0（否則就不叫退火了），因此dE/kT < 0 ，所以P(dE)的函數(shù)取值范圍是(0,1) 。 隨著溫度T的降低，P(dE)會逐漸降低。我們將一次向較差解的移動看做一次溫度跳變過程，我們以概率P(dE)來接受這樣的移動。關(guān)于爬山算法與模擬退火，有一個有趣的比喻：爬山算法：兔子朝著比現(xiàn)在高的地方跳去。它找到了不遠處的最高山峰。但是這座山不一定是珠穆朗瑪峰。這就是爬山算法，它不能保證局部最優(yōu)值就是全局最優(yōu)值。模擬退火：兔子喝醉了。它

8、隨機地跳了很長時間。這期間，它可能走向高處，也可能踏入平地。但是，它漸漸清醒了并朝最高方向跳去。這就是模擬退火。4.接受函數(shù)接受函數(shù)決定選擇哪一個解決方案，從而可以避免掉一些局部最優(yōu)解。首先我們檢查如果相鄰的解決方案是比我們目前的解決方案好，如果是，我們接受它。否則的話，我們需要考慮的幾個因素：1) 相鄰的解決方案有多不好; 2) 當前的溫度有多高。在高溫系統(tǒng)下更有可能接受較糟糕的解決方案。這里是簡單的數(shù)學公式：exp( (solutionEnergy neighbourEnergy) / temperature )，即上面的P(dE) = exp( dE/(kT) )5.模擬退火的基本思想它

9、可以分解為解空間、目標函數(shù)和初始解三部分。(1) 初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點)， 每個T值的迭代次數(shù)L(2) 對k=1，L做第(3)至第6步：(3) 產(chǎn)生新解S(4) 計算增量t=C(S)-C(S)，其中C(S)為評價函數(shù)(5) 若t<0則接受S作為新的當前解，否則以概率exp(-t/T)接受S作為新的當前解.(6) 如果滿足終止條件則輸出當前解作為最優(yōu)解，結(jié)束程序。終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法。(7) T逐漸減少，且T>0，然后轉(zhuǎn)第2步。6.模擬退火算法的流程7.算法過程描述（1) 首先,需要設置初始溫度和創(chuàng)建一個隨機的初

10、始解。（2) 然后開始循環(huán),直到滿足停止條件。通常系統(tǒng)充分冷卻,或找到一個足夠好的解決方案。（3) 把當前的解決方案做一些小的改變，然后選擇一個新的相鄰的方案。（4) 決定是否移動到相鄰的解決方案。（5) 降低溫度,繼續(xù)循環(huán)二、程序代碼實現(xiàn)1.City類，用來描述城市的基本坐標信息，以及計算兩城市之間的距離。package monituihuo;public class City int x;/保存城市的X坐標int y;/保存城市的Y坐標String name;/保存城市的名稱 / 生成一個隨機的城市 public City() this.x = (int)(Math.random()*20

11、0); this.y = (int)(Math.random()*200); =null; /初始化一個城市的坐標 public City(int x, int y,String name) this.x = x; this.y = y; = name; /獲取城市的X坐標 public int getX() return this.x; /獲取城市的Y坐標 public int getY() return this.y; / 計算兩個城市之間的距離 public double distanceTo(City city) int xDistance = Ma

12、th.abs(getX() - city.getX(); int yDistance = Math.abs(getY() - city.getY(); double distance = Math.sqrt( (xDistance*xDistance) + (yDistance*yDistance) ); return distance; / 重寫toString方法 Override public String toString() return getX()+", "+getY()+" "+name; 2.Tour類，用來初始化旅行商路徑，完成路徑的

13、解決方案。package monituihuo;import java.util.ArrayList;import java.util.Collections;public class Tour / 保存城市的列表 private ArrayList tour = new ArrayList<City>(); / 保存距離 private int distance = 0; / 生成一個空的路徑 public Tour() for (int i = 0; i < SimulatedAnnealing.allCitys.size(); i+) tour.add(null); /

14、 復雜路徑 public Tour(ArrayList tour) this.tour = (ArrayList) tour.clone(); / 獲取路徑 public ArrayList getTour() return tour; / Creates a random individual public void generateIndividual() for (int cityIndex = 0; cityIndex < SimulatedAnnealing.allCitys.size(); cityIndex+) setCity(cityIndex, SimulatedAnn

15、ealing.allCitys.get(cityIndex); / 隨機的打亂 Collections.shuffle(tour); / 獲取一個城市 public City getCity(int tourPosition) return (City)tour.get(tourPosition); public void setCity(int tourPosition, City city) tour.set(tourPosition, city); / 重新計算距離 distance = 0; / 獲得當前的總距離 public int getDistance() if (distanc

16、e = 0) int tourDistance = 0; for (int cityIndex=0; cityIndex < tourSize(); cityIndex+) City fromCity = getCity(cityIndex); City destinationCity; if(cityIndex+1 < tourSize() destinationCity = getCity(cityIndex+1); else destinationCity = getCity(0); tourDistance += fromCity.distanceTo(destinatio

17、nCity); distance = tourDistance; return distance; / 獲得當前路徑中城市的數(shù)量 public int tourSize() return tour.size(); public String toString() String printString = "|" for (int i = 0; i < tourSize(); i+) printString += getCity(i)+"|" return printString; 3. SimulatedAnnealing主類，是算法的實現(xiàn)類，也是

18、模擬退火算法解決TSP問題相應的測試。package monituihuo;import java.util.ArrayList;import java.util.List;public class SimulatedAnnealing public static List<City> allCitys = new ArrayList<City>(); /計算接受的概率（依據(jù)熱力學原理P(dE) = exp(dE/(kT)） public static double acceptanceProbability(int energy, int newEnergy, dou

19、ble temperature) / 如果新的解決方案較優(yōu)，就接受 if (newEnergy < energy) return 1.0; return Math.exp(energy - newEnergy) / temperature); public static void main(String args) / 創(chuàng)建所有的城市列表 init(); Tour best = monituihuo(); System.out.println("Final solution distance: " + best.getDistance();System.out.pri

20、ntln("Tour: " + best); /返回近似的最佳旅行路徑 private static Tour monituihuo() / 設置初始化溫度 double temp = 10000; / 設置冷卻概率 double coolingRate = 0.003; / 初始化解決方案 Tour currentSolution = new Tour();currentSolution.generateIndividual(); System.out.println("Initial solution distance: " + currentSol

21、ution.getDistance(); / 設置當前為最優(yōu)的方案 Tour best = new Tour(currentSolution.getTour(); / 循環(huán)直到系統(tǒng)冷卻 while (temp > 1) / 生成一個鄰居 Tour newSolution = new Tour(currentSolution.getTour(); / 獲取隨機位置 int tourPos1 = (int) (newSolution.tourSize() * Math.random(); int tourPos2 = (int) (newSolution.tourSize() * Math.

22、random(); City citySwap1 = newSolution.getCity(tourPos1); City citySwap2 = newSolution.getCity(tourPos2); / 交換兩個城市 newSolution.setCity(tourPos2, citySwap1); newSolution.setCity(tourPos1, citySwap2); / 獲得新的解決方案的總路程 int currentEnergy = currentSolution.getDistance(); int neighbourEnergy = newSolution.g

23、etDistance(); / 決定是否接受新的方案 if (acceptanceProbability(currentEnergy, neighbourEnergy, temp) > Math.random() currentSolution = new Tour(newSolution.getTour(); / 更新最優(yōu)方案 if (currentSolution.getDistance() < best.getDistance() best = new Tour(currentSolution.getTour(); / 冷卻（即更新當前系統(tǒng)溫度） temp *= 1-cool

24、ingRate; return best; /初始化20個城市，并將他們保存到allCitys。 private static void init() City city = new City(60, 200,"北京"); allCitys.add(city); City city2 = new City(180, 200,"上海"); allCitys.add(city2); City city3 = new City(80, 180,"廣州"); allCitys.add(city3); City city4 = new City

25、(140, 180,"深圳"); allCitys.add(city4); City city5 = new City(20, 160,"長沙"); allCitys.add(city5); City city6 = new City(100, 160,"武漢"); allCitys.add(city6); City city7 = new City(200, 160,"南京"); allCitys.add(city7); City city8 = new City(140, 140,"重慶")

26、; allCitys.add(city8);City city9 = new City(40, 120,"西安"); allCitys.add(city9); City city10 = new City(100, 120,"徐州"); allCitys.add(city10); City city11 = new City(180, 100,"成都"); allCitys.add(city11); City city12 = new City(60, 80,"天津"); allCitys.add(city12);

27、 City city13 = new City(120, 80,"蘇州"); allCitys.add(city13); City city14 = new City(180, 60,"南昌"); allCitys.add(city14); City city15 = new City(20, 40,"鄭州"); allCitys.add(city15); City city16 = new City(100, 40,"大連"); allCitys.add(city16); City city17 = new Ci

28、ty(200, 40,"?？?quot;); allCitys.add(city17); City city18 = new City(20, 20,"香港"); allCitys.add(city18); City city19 = new City(60, 20,"澳門"); allCitys.add(city19); City city20 = new City(160, 20,"臺灣")； allCitys.add(city20); *運行結(jié)果:(一) Java運行結(jié)果（1）Initial solution dist

29、ance: 2101Final solution distance: 919Tour: |80,180 廣州|100,160 武漢|140,180 深圳|180,200 上海|200,160 南京|140,140 重慶|180,100 成都|180,60 南昌|200,40 ?？趞160,20 臺灣|120,80 蘇州|100,120 徐州|100,40 大連|60,20 澳門|20,20 香港|20,40 鄭州|60,80 天津|40,120 西安|20,160 長沙|60,200 北京|（2）Initial solution distance: 2178Final solution distance: 906Tour: |100,40 大連|160,20 臺灣|200,40 海口|180,60 南昌|180,100 成都|140,140 重慶|200,160 南京|180,200 上海|140,180 深圳|100,160 武漢|80,180 廣州|60,200 北京|20,160 長沙|40,120