2022年西北工業(yè)大學(xué)算法設(shè)計(jì)實(shí)驗(yàn)三

1、實(shí)驗(yàn)三：遺傳算法vs回溯法一、問(wèn)題分析回溯法可以處理貨郎擔(dān)問(wèn)題， 遺傳算法也可以處理貨郎擔(dān)問(wèn)題，回溯法和遺傳算法哪個(gè)算法處理貨郎擔(dān)問(wèn)題效率更高呢？在相同計(jì)算時(shí)間內(nèi)，哪個(gè)算法得到的解更好呢？實(shí)現(xiàn)遺傳算法，通過(guò)隨機(jī)產(chǎn)生10 個(gè)不同規(guī)模的算例（城市數(shù)量分別為10，20，40，80，100，120，160，180，200，500，或者其它規(guī)模），比較上次實(shí)驗(yàn)實(shí)現(xiàn)的回溯法和遺傳算法。二、算法基本思想1、回溯法從初始狀態(tài)出發(fā)，搜索其所能到達(dá)的所有“狀態(tài)”，當(dāng)一條路走到盡頭，再后退一步或若干步，從另外一種狀態(tài)出發(fā)，繼續(xù)搜索，直到所有的路徑都搜索過(guò)。這種不斷前進(jìn)、不斷回溯尋找解的方法叫回溯法?；厮莘ㄍǔ?wèn)題

2、解空間組織成“樹(shù)”結(jié)構(gòu)，采用系統(tǒng)的方法搜索解空間樹(shù)，從而得到問(wèn)題解。搜索策略：深度優(yōu)先為主，也可以采用廣度優(yōu)先、函數(shù)優(yōu)先、廣度深度結(jié)合等。避免無(wú)效搜索策略：約束函數(shù)：在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束條件的子樹(shù)界限函數(shù)：在擴(kuò)展結(jié)點(diǎn)處剪去得不到最優(yōu)解的子樹(shù)2、遺傳算法首先針對(duì)遺傳算法要有種群，個(gè)體，適應(yīng)度函數(shù)，選擇，交叉，變異。對(duì)于種群是由若干個(gè)個(gè)體組成， 其中個(gè)體的編碼可以用走過(guò)的每一個(gè)城市的路徑表示。適應(yīng)度函數(shù)用一個(gè)路徑的代價(jià)的倒數(shù)表示。使用輪盤(pán)賭的方式進(jìn)行選擇下一代個(gè)體。 其中輪盤(pán)賭的方式可以轉(zhuǎn)換為每一個(gè)個(gè)體的適應(yīng)度與種群的適應(yīng)度的比例進(jìn)行比較。先隨機(jī)選擇兩個(gè)個(gè)體， 根據(jù)交叉的概率進(jìn)行單點(diǎn)交叉，將

3、較優(yōu)的交叉結(jié)果保留下來(lái)。 接著在種群中選擇一個(gè)個(gè)體，根據(jù)變異概率來(lái)判斷是否變異，將該個(gè)體保留， 根據(jù)生成的子代的個(gè)數(shù)重復(fù)上述的運(yùn)算。根據(jù)指定的代數(shù)， 重復(fù)上述的運(yùn)算。精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 1 頁(yè)，共 5 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 1 頁(yè)，共 5 頁(yè) - - - - - - - - -三、算法設(shè)計(jì)1、回溯法tsp問(wèn)題的目的是得到一條路徑，即一個(gè)解向量（x1,x2.xn ），為排列樹(shù)問(wèn)題。對(duì)所有城市進(jìn)行編號(hào)后，按大小順序存儲(chǔ)于

4、數(shù)組path 中，構(gòu)造一個(gè)交換函數(shù) swap （）；對(duì)數(shù)組 path 進(jìn)行遍歷，判斷當(dāng)前城市與目標(biāo)城市是否連通，若連通，通過(guò) swap函數(shù)對(duì)當(dāng)前節(jié)點(diǎn)和目標(biāo)城市進(jìn)行交換，即樹(shù)的節(jié)點(diǎn)拓展。若不連通則恢復(fù)， 并進(jìn)入下一次的循環(huán)， 循環(huán)到葉子節(jié)點(diǎn)時(shí)， 判斷葉是否與初始節(jié)點(diǎn)相連，并計(jì)算代價(jià) cost 是否小于當(dāng)前最小代價(jià)bestc ，若小于，則更新 bestc ，再返回上一節(jié)點(diǎn)，知道遍歷完樹(shù)中的所有節(jié)點(diǎn)。核心代碼：publicvoid backtrack(int depth)/depth 深度if (depth=size) if (mappathdepth-1pathdepth != -1 &

5、mappathdepthpath1!= -1 & cost +mappathdepthpath1bestc) bestp=path.clone(); bestc = cost + mappathdepthpath1; /bestc = cost +apathi-1pathi+apathipath1;/ 重復(fù)計(jì)算了上一邊 else for (int j =depth;j=size;j+) if (mappathdepthpathj!=-1) swap(path,depth+1,j); cost +=mappathdepthpathdepth+1; /system.out.println(

6、arrays.tostring(x)+:+cost);backtrack(depth+1); cost -=mappathdepthpathdepth+1; swap(path,depth+1,j); 2、遺傳算法精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 2 頁(yè)，共 5 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 2 頁(yè)，共 5 頁(yè) - - - - - - - - -先設(shè)計(jì)個(gè)體，個(gè)體里面用城市的鄰接矩陣map 表示，當(dāng)前路徑path ，當(dāng)前路徑的代價(jià) cost

7、 ，適應(yīng)度值。 主要方法有隨機(jī)初始化當(dāng)前路徑，計(jì)算路徑代價(jià)，適應(yīng)度值的求解。針對(duì)旅行商的問(wèn)題， 設(shè)計(jì)初始化種群， 生成下一代種群， 生成下一代種群包含選擇，交叉，變異的方法。在交叉的結(jié)果會(huì)產(chǎn)生同一個(gè)城市重復(fù)兩次，所以需要一個(gè)修復(fù)方法。核心代碼：publicvoid solve() inti ; intk; / 初始化種群initgroup(); / 計(jì)算初始化種群適應(yīng)度， fitnessmaxfor ( k = 0; k scale; k+) fitnessk = evaluate(oldpopulationk); / system.out.println(fitnessk); / 計(jì)算初始化

8、種群中各個(gè)個(gè)體的累積概率，pimaxcountrate(); system.out .println( 初始種群 .); for ( k = 0; k scale; k+) for ( i = 0; i size; i +) system.out .print(oldpopulationk i + , ); system.out.println(); system.out.println(- + fitnessk + + pik); for (t = 0; t max_gen; t+) /evolution1();evolution(); / 將新種群 newgroup 復(fù)制到舊種群 oldg

9、roup中，準(zhǔn)備下一代進(jìn)化for ( k = 0; k scale; k+) for ( i = 0; i size; i +) oldpopulationk i = newpopulationk i ; / 計(jì)算種群適應(yīng)度f(wàn)or ( k = 0; k scale; k+) fitnessk = evaluate(oldpopulationk); / 計(jì)算種群中各個(gè)個(gè)體的累積概率精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 3 頁(yè)，共 5 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - -

10、- - - - 第 3 頁(yè)，共 5 頁(yè) - - - - - - - - -countrate(); system.out .println( 最后種群 .); for ( k = 0; k scale; k+) for ( i = 0; i size; i +) system.out .print(oldpopulationk i + , ); system.out.println(); system.out.println(- + fitnessk + + pik); system.out .println( 最佳長(zhǎng)度出現(xiàn)代數(shù)： ); system.out .println(bestt);

11、system.out .println( 最佳長(zhǎng)度 ); system.out .println(bestc); system.out .println( 最佳路徑： ); for ( i = 0; i size; i +) system.out.print(bestpi + , ); publicstaticvoid main(string args ) throws ioexception longstarttime = system. currenttimemillis(); / 獲取開(kāi)始時(shí)間system.out .println(start.); yctsp yc = new ycts

12、p(30, 40, 1000, 0.8f, 0.9f); yc.init(c:/data.txt); yc.solve(); system.out .println( ); longendtime = system.currenttimemillis(); / 獲取程序運(yùn)行時(shí)間system.out .println( 程序運(yùn)行時(shí)間： + ( endtime - starttime ) + ms); 五、算法復(fù)雜性理論分析1、回溯法tsp問(wèn)題是排列樹(shù)問(wèn)題，因而該算法的時(shí)間復(fù)雜度為o(n!) 。2、遺傳算法六、算法代碼（單獨(dú)文件提交）見(jiàn)項(xiàng)目文件七、算法復(fù)雜性實(shí)驗(yàn)分析精品學(xué)習(xí)資料 可選擇p d f

13、- - - - - - - - - - - - - - 第 4 頁(yè)，共 5 頁(yè) - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 4 頁(yè)，共 5 頁(yè) - - - - - - - - -遺傳算法中種群規(guī)模為30，運(yùn)行代數(shù)為 1000，交叉率為 0.8 ，變異率為 0，9 問(wèn)題規(guī)模回溯法遺傳算法5 3ms 44ms 10 10ms 87ms 20 272510ms 110ms 25 - 124ms 30 - 141ms 40 - 188ms 八、實(shí)驗(yàn)中的問(wèn)題總結(jié)回溯法：優(yōu)點(diǎn)：采用深度優(yōu)先，可以快速的找到一組解，并依此為參照（bestc ）。當(dāng)搜索完解空間時(shí)便可以得最優(yōu)解。缺點(diǎn)：需要搜索大量的結(jié)點(diǎn)，工程浩大，速度慢，而且隨著結(jié)點(diǎn)的個(gè)數(shù)不斷地增加之后，解空間按照階乘的增長(zhǎng)速度增加，算法效率較低。遺傳算法：遺傳算法在問(wèn)