




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
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,"海口"); 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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 繪畫工作坊行業(yè)跨境出海戰(zhàn)略研究報告
- 二零二五離婚訴訟離婚
- 歌謠保護在線平臺企業(yè)制定與實施新質(zhì)生產(chǎn)力戰(zhàn)略研究報告
- 電工技能培訓班行業(yè)深度調(diào)研及發(fā)展戰(zhàn)略咨詢報告
- 羽毛球大師賽行業(yè)深度調(diào)研及發(fā)展戰(zhàn)略咨詢報告
- 機動車污染排放控制企業(yè)制定與實施新質(zhì)生產(chǎn)力戰(zhàn)略研究報告
- 耐化學品有機顏料行業(yè)跨境出海戰(zhàn)略研究報告
- 中考道德與法治一輪復習課時23 青春時光 做情緒情感的主人(第一、二單元) (含答案)
- 企業(yè)并購重組與風險管理
- 企業(yè)危機預警與預防策略
- (正式版)QB∕T 2761-2024 室內(nèi)空氣凈化產(chǎn)品凈化效果測定方法
- J22J255 河北省建筑圖集 被動式超低能耗建筑節(jié)能構(gòu)造(六)(雙限位連接件現(xiàn)澆混凝土內(nèi)置保溫系統(tǒng)建筑構(gòu)造)DBJT02-208-2022
- 2024年01月安徽省池州市公安局2024年第一批公開招考85名輔警筆試歷年典型考題及考點研判與答案解析
- 2024屆山東省濟南市萊蕪區(qū)中考數(shù)學模擬試題(一模)附答案
- 利器管制記錄表
- 2024年社區(qū)工作者考試必考1000題附完整答案(名師系列)
- 全國大唐杯大學生新一代信息通信技術(shù)大賽考試題庫(必練500題)
- 人工智能倫理與社會影響的討論
- T-CSGPC 016-2023 文物建筑健康監(jiān)測技術(shù)規(guī)范
- 高超聲速飛行器氣動設計挑戰(zhàn)
- 網(wǎng)絡安全法律知識培訓
評論
0/150
提交評論