模擬退火算法解決TSP問題

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

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

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

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

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

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

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

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

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

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

11、0); this.y = (int)(Math.random()*200); =null; /初始化一個(gè)城市的坐標(biāo) public City(int x, int y,String name) this.x = x; this.y = y; = name; /獲取城市的X坐標(biāo) public int getX() return this.x; /獲取城市的Y坐標(biāo) public int getY() return this.y; / 計(jì)算兩個(gè)城市之間的距離 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; / 生成一個(gè)空的路徑 public Tour() for (int i = 0; i < SimulatedAnnealing.allCitys.size(); i+) tour.add(null); /

14、 復(fù)雜路徑 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); / 隨機(jī)的打亂 Collections.shuffle(tour); / 獲取一個(gè)城市 public City getCity(int tourPosition) return (City)tour.get(tourPosition); public void setCity(int tourPosition, City city) tour.set(tourPosition, city); / 重新計(jì)算距離 distance = 0; / 獲得當(dāng)前的總距離 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; / 獲得當(dāng)前路徑中城市的數(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主類，是算法的實(shí)現(xiàn)類，也是

18、模擬退火算法解決TSP問題相應(yīng)的測(cè)試。package monituihuo;import java.util.ArrayList;import java.util.List;public class SimulatedAnnealing public static List<City> allCitys = new ArrayList<City>(); /計(jì)算接受的概率（依據(jù)熱力學(xué)原理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() / 設(shè)置初始化溫度 double temp = 10000; / 設(shè)置冷卻概率 double coolingRate = 0.003; / 初始化解決方案 Tour currentSolution = new Tour();currentSolution.generateIndividual(); System.out.println("Initial solution distance: " + currentSol

21、ution.getDistance(); / 設(shè)置當(dāng)前為最優(yōu)的方案 Tour best = new Tour(currentSolution.getTour(); / 循環(huán)直到系統(tǒng)冷卻 while (temp > 1) / 生成一個(gè)鄰居 Tour newSolution = new Tour(currentSolution.getTour(); / 獲取隨機(jī)位置 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); / 交換兩個(gè)城市 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(); / 冷卻（即更新當(dāng)前系統(tǒng)溫度） temp *= 1-cool

24、ingRate; return best; /初始化20個(gè)城市，并將他們保存到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,"臺(tái)灣")； allCitys.add(city20); *運(yùn)行結(jié)果:(一) Java運(yùn)行結(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 臺(tái)灣|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 臺(tái)灣|200,40 ?？趞180,60 南昌|180,100 成都|140,140 重慶|200,160 南京|180,200 上海|140,180 深圳|100,160 武漢|80,180 廣州|60,200 北京|20,160 長沙|40,120