機(jī)器學(xué)習(xí)報(bào)告(修改版)

機(jī)器學(xué)習(xí)實(shí)驗(yàn)報(bào)告遺傳算法在旅行商問題中的應(yīng)用遺傳算法在旅行商問題中的應(yīng)用一、旅行商〔TSP〕問題旅行商問題中，一個(gè)售貨員必須訪問n個(gè)城市。如果把該問題模型化為一個(gè)具有n個(gè)頂點(diǎn)的完全圖，就可以說這個(gè)售貨員希望進(jìn)行一次巡回旅行，或經(jīng)過哈密頓回路，恰好訪問每個(gè)城市一次，并最終回到出發(fā)的城市。從城市i到城市j的旅行費(fèi)用為一個(gè)整數(shù)c(i,j)，這個(gè)售貨員希望使整個(gè)旅行的費(fèi)用最低，而所需的全部費(fèi)用是他旅行經(jīng)過的各邊費(fèi)用之和。旅行商問題是NP完全問題。二、遺傳算法遺傳算法(GA)是一種受生物進(jìn)化啟發(fā)的學(xué)習(xí)方法。它不再是從一般到特殊或從簡單到復(fù)雜的搜索假設(shè)，而是通過變異和重組當(dāng)前的最好假設(shè)來生成后續(xù)假設(shè)。GA研究的問題是搜索候選假設(shè)空間并確定最正確的假設(shè)。在GA中，“最正確假設(shè)”被定義為是使適應(yīng)度最優(yōu)的假設(shè)，適應(yīng)度是當(dāng)前問題預(yù)先定義的數(shù)字?jǐn)?shù)量。遺傳算法的共同結(jié)構(gòu)：算法迭代更新一個(gè)假設(shè)池，這個(gè)假設(shè)池成為群體。在每一次迭代中，根據(jù)適應(yīng)度函數(shù)評估群體中的所有成員，然后從當(dāng)前群體中用概率方法選取適應(yīng)度最高的個(gè)體產(chǎn)生新一代群體。在這些被選中的個(gè)體中，一局部保持原樣地進(jìn)入下一代群體，其他的被用作產(chǎn)生后代個(gè)體的根底，其中應(yīng)用像交叉和變異這樣的遺傳方法。遺傳算法的輸入包括：用來排序候選假設(shè)的適應(yīng)度函數(shù)；定義算法終止時(shí)適應(yīng)度的閾值；要維持的群體大??；決定如何產(chǎn)生后繼群體的參數(shù)，即每一代群體中被淘汰的比例和變異率。Fitness：適應(yīng)度評分函數(shù)，為給定假設(shè)賦予一個(gè)評估分?jǐn)?shù)Fitness_threshold：指定終止判據(jù)的閾值p：群體中包含的假設(shè)數(shù)量r：每一步中通過交叉取代群體成員的比例m：變異率遺產(chǎn)算法原型的偽代碼如下：算法流程圖如下：圖1遺傳算法流程圖三、算法實(shí)現(xiàn)本文算法將每個(gè)城市用他們在數(shù)組中的下標(biāo)來表示，用所有下標(biāo)的一個(gè)排列來表示商人旅行的路線，而遺傳算法中的一個(gè)單體就可以用一個(gè)商人旅行的路線來表示，一個(gè)種群就是一些旅行路線的集合。遺傳算法的初始化操作主要進(jìn)行的是初始種群的生成和選取，在本程序中，采取隨機(jī)生成旅行路線的方式來生成一組集合作為初始種群。由于本文用遺傳算法來求解TSP問題，因此，衡量一個(gè)解的質(zhì)量好壞的標(biāo)準(zhǔn)就是這個(gè)旅行線路總的旅行長度，因此，我們用一個(gè)解的總體旅行距離來作為一個(gè)解的適應(yīng)度，適應(yīng)度越大那么說明解越差。本文采用旅行路徑來作為基因編碼，而每一種旅行路線都是一組相同的數(shù)字的排列，因此，變異操作隨機(jī)選取一條旅行路徑中的兩個(gè)城市，交換這兩個(gè)城市的位置即到達(dá)了變異的效果。程序隨機(jī)選取種群中的兩個(gè)個(gè)體進(jìn)行交叉操作，統(tǒng)計(jì)兩個(gè)個(gè)體中對應(yīng)路線順序中不同的局部，按照一定的概率將其中不同的路線段進(jìn)行交換，從而完成交叉工作。其中選擇交叉的兩段路線，其所覆蓋的城市是相同的。四、實(shí)驗(yàn)及結(jié)果分析4.1開發(fā)語言及運(yùn)行環(huán)境開發(fā)語言：Java運(yùn)行環(huán)境：MicrosoftWindows7操作系統(tǒng) 2G內(nèi)存4.2問題范圍實(shí)驗(yàn)輸入的訓(xùn)練樣例如下：該旅行商問題規(guī)模為一個(gè)包含34個(gè)節(jié)點(diǎn)的完全圖，分別代表"北京","上海","天津","重慶","哈爾濱","長春","沈陽","呼和浩特","石家莊","太原","濟(jì)南","鄭州","西安","蘭州","銀川","西寧","烏魯木齊","合肥","南京","杭州","長沙","南昌","武漢","成都","貴州","福建","臺北","廣州","?？?,"南寧","昆明","拉薩","香港","澳門"這32個(gè)城市，存放在一個(gè)長度為34的數(shù)組中。城市i和城市j的距離為數(shù)組中對應(yīng)元素的相對位移。如"北京"與"上海"的距離為1，對應(yīng)完全圖中的邊長為1;"北京"與"天津"的距離為2，對應(yīng)完全圖中的邊長為2，以此類推。求解目標(biāo)為從一個(gè)城市出發(fā)進(jìn)行一次巡回，經(jīng)過每個(gè)城市一次最終回到出發(fā)城市，并使整個(gè)旅行的費(fèi)用最低，即遍歷的城市距離和最短。4.3數(shù)據(jù)結(jié)構(gòu)privateclassgenotype{intcity[]=newint[cityNum]; //單個(gè)基因的城市序列l(wèi)ongfitness; //該基因的適應(yīng)度doubleselectP; //選擇概率doubleexceptp; //期望概率intisSelected; //是否被選擇}privategenotype[]citys=newgenotype[popSize];privateStringcityName[]={"北京","上海","天津","重慶","哈爾濱","長春","沈 陽","呼和浩特","石家莊","太原","濟(jì)南","鄭州"," 西安","蘭州","銀川","西寧","烏魯木齊","合肥"," 南京","杭州","長沙","南昌","武漢","成都","貴州 ","福建","臺北","廣州","?？?,"南寧","昆明","拉 薩","香港","澳門"};privateintcityNum=cityName.length; //城市個(gè)數(shù)privatelong[][]distance=newlong[cityNum][cityNum];//城市距離privateintpopSize=50; //種群數(shù)量privateintmaxgens=10000; //迭代次數(shù)privatedoublepxover=0.8; //交叉概率privatedoublepmultation=0.05; //變異概率privateintrange=2000; //用于判斷何時(shí)停止的數(shù)組區(qū)間4.4實(shí)驗(yàn)結(jié)果進(jìn)行假設(shè)干次重復(fù)試驗(yàn)，四類運(yùn)行結(jié)果如下：1、迭代10000次，得到最優(yōu)的結(jié)果。本次實(shí)驗(yàn)結(jié)果表示從”南京”出發(fā)，依次經(jīng)過以下城市，最終到達(dá)”杭州”再回到”南京”，旅行路程為66。2、迭代未滿10000次，即連續(xù)2000次得到的結(jié)果相同，提前終止。結(jié)果如下所示：在第6859次迭代后停止了算法，得到的解為從”鄭州”出發(fā)，依次經(jīng)過后續(xù)城市，最終到達(dá)”西安”后再返回”鄭州”。旅行路程為66。3、迭代滿10000次，但仍未得到最優(yōu)結(jié)果。程序運(yùn)行結(jié)果如下列圖所示：得到的解為從”南昌”出發(fā)，依次經(jīng)過后續(xù)城市，最終到達(dá)”合肥”后再返回”南昌”。旅行路程為82，比最優(yōu)解66要大。4、迭代未滿10000次，但有連續(xù)2000次得到相同結(jié)果，然而結(jié)果不是最優(yōu)的，程序運(yùn)行結(jié)果如下所示：得到的解為從”南寧”出發(fā)，依次經(jīng)過后續(xù)城市，最終到達(dá)”杭州”后再返回”南寧”。旅行路程為106，比最優(yōu)解66要大。其他比照實(shí)驗(yàn)使用控制變量法，通過修改迭代次數(shù)和停止閾值可以得到不同的實(shí)驗(yàn)結(jié)果，理論上迭代次數(shù)與停止閾值越大，越可能得到最優(yōu)解。如將10000改成5000，那么很難得到最優(yōu)解，或者將2000改成500，那么很容易在非最優(yōu)解時(shí)停止迭代，同樣很難得到優(yōu)化解。由此可見迭代次數(shù)與停止閾值能影響程序的遺傳算法的優(yōu)化效果。五總結(jié)遺傳算法維護(hù)一個(gè)由競爭假設(shè)組成的多樣化群體。在每次迭代中，選出群體中適應(yīng)度最高的成員來產(chǎn)生后代，替代群體中適應(yīng)度最差的成員，假設(shè)常被編碼成位