1、機(jī)器學(xué)習(xí)實(shí)驗(yàn)報(bào)告遺傳算法在旅行商問(wèn)題中的應(yīng)用遺傳算法在旅行商問(wèn)題中的應(yīng)用一、旅行商(TSP)問(wèn)題旅行商問(wèn)題中，一個(gè)售貨員必須訪問(wèn)n個(gè)城市。如果把該問(wèn)題模型化為一個(gè) 具有n個(gè)頂點(diǎn)的完全圖，就可以說(shuō)這個(gè)售貨員希望進(jìn)行一次巡回旅行，或經(jīng)過(guò)哈 密頓回路，恰好訪問(wèn)每個(gè)城市一次，并最終回到出發(fā)的城市。從城市i到城市j 的旅行費(fèi)用為一個(gè)整數(shù)c(i,j)，這個(gè)售貨員希望使整個(gè)旅行的費(fèi)用最低，而所需的 全部費(fèi)用是他旅行經(jīng)過(guò)的各邊費(fèi)用之和。旅行商問(wèn)題是NP完全問(wèn)題。二、遺傳算法遺傳算法(GA)是一種受生物進(jìn)化啟發(fā)的學(xué)習(xí)方法。它不再是從一般到特殊或 從簡(jiǎn)單到復(fù)雜的搜索假設(shè)，而是通過(guò)變異和重組當(dāng)前已知的最好假設(shè)來(lái)生成

2、后續(xù) 假設(shè)。GA研究的問(wèn)題是搜索候選假設(shè)空間并確定最佳的假設(shè)。在GA中，最佳 假設(shè)被定義為是使適應(yīng)度最優(yōu)的假設(shè)，適應(yīng)度是當(dāng)前問(wèn)題預(yù)先定義的數(shù)字?jǐn)?shù)量。遺傳算法的共同結(jié)構(gòu)：算法迭代更新一個(gè)假設(shè)池，這個(gè)假設(shè)池成為群體。在 每一次迭代中，根據(jù)適應(yīng)度函數(shù)評(píng)估群體中的所有成員，然后從當(dāng)前群體中用概 率方法選取適應(yīng)度最高的個(gè)體產(chǎn)生新一代群體。在這些被選中的個(gè)體中，一部分 保持原樣地進(jìn)入下一代群體，其他的被用作產(chǎn)生后代個(gè)體的基礎(chǔ)，其中應(yīng)用像交 叉和變異這樣的遺傳方法。遺傳算法的輸入包括：用來(lái)排序候選假設(shè)的適應(yīng)度函數(shù)；定義算法終止時(shí)適 應(yīng)度的閾值；要維持的群體大小；決定如何產(chǎn)生后繼群體的參數(shù)，即每一代群體 中被

3、淘汰的比例和變異率。Fitness :適應(yīng)度評(píng)分函數(shù)，為給定假設(shè)賦予一個(gè)評(píng)估分?jǐn)?shù)Fitness_threshold:指定終止判據(jù)的閾值p：群體中包含的假設(shè)數(shù)量r：每一步中通過(guò)交叉取代群體成員的比例m：變異率遺產(chǎn)算法原型的偽代碼如下：Algorithm 4透?jìng)魉汜t(yī)原型, 1：初始化群體：P一菌機(jī)產(chǎn)生的p個(gè)痕讀近 評(píng)估：對(duì)于F中的每一個(gè)b,開算Fitiiess(h)3：當(dāng)max Fitnesyi-thresiiohl,做:4: 產(chǎn)星新的一代05： U 選擇：用概率方法選擇P的(l-r)p個(gè)成員加入從P中選擇假設(shè)法的概 率Pr(hi)用下面公式計(jì)算皎口 “、 Fitness(hi)5 很= Fatn

4、eas(Zij)j=i7： A交叉：根據(jù)上面籍出的Pe仇山從P中按橫率選擇廠工#/2對(duì)低設(shè).對(duì)于每 時(shí)愜設(shè),應(yīng)用吏叉算子產(chǎn)生兩個(gè)后代口耙所有的后代如入巳密 3,變異：踐用均勻的概率從己中選擇也.的成員口對(duì)于選出的每個(gè)成員在 他的表示中隨機(jī)選擇一位取反9：4.更新：F J P&m： 5*評(píng)估：對(duì)于P中的令h計(jì)算FimesHh)n：威P中退回適應(yīng)度最高的假設(shè)算法流程圖如下:圖1遺傳算法流程圖三、算法實(shí)現(xiàn)本文算法將每個(gè)城市用他們?cè)跀?shù)組中的下標(biāo)來(lái)表示，用所有下標(biāo)的一個(gè)排列 來(lái)表示商人旅行的路線，而遺傳算法中的一個(gè)單體就可以用一個(gè)商人旅行的路線 來(lái)表示，一個(gè)種群就是一些旅行路線的集合。遺傳算法的初始化操

5、作主要進(jìn)行的是初始種群的生成和選取，在本程序中， 采取隨機(jī)生成旅行路線的方式來(lái)生成一組集合作為初始種群。由于本文用遺傳算法來(lái)求解TSP問(wèn)題，因此，衡量一個(gè)解的質(zhì)量好壞的標(biāo)準(zhǔn) 就是這個(gè)旅行線路總的旅行長(zhǎng)度，因此，我們用一個(gè)解的總體旅行距離來(lái)作為一 個(gè)解的適應(yīng)度，適應(yīng)度越大則說(shuō)明解越差。本文采用旅行路徑來(lái)作為基因編碼，而每一種旅行路線都是一組相同的數(shù)字 的排列，因此，變異操作隨機(jī)選取一條旅行路徑中的兩個(gè)城市，交換這兩個(gè)城市 的位置即達(dá)到了變異的效果。程序隨機(jī)選取種群中的兩個(gè)個(gè)體進(jìn)行交叉操作，統(tǒng)計(jì)兩個(gè)個(gè)體中對(duì)應(yīng)路線順 序中不同的部分，按照一定的概率將其中不同的路線段進(jìn)行交換，從而完成交叉 工作。其中

6、選擇交叉的兩段路線，其所覆蓋的城市是相同的。四、實(shí)驗(yàn)及結(jié)果分析4.1開發(fā)語(yǔ)言及運(yùn)行環(huán)境開發(fā)語(yǔ)言：Java運(yùn)行環(huán)境：Microsoft Windows 7操作系統(tǒng)2G內(nèi)存4.2問(wèn)題范圍實(shí)驗(yàn)輸入的訓(xùn)練樣例如下：該旅行商問(wèn)題規(guī)模為一個(gè)包含34個(gè)節(jié)點(diǎn)的完全圖，分別代表北京廣上海, 天津,重慶,哈爾濱廣長(zhǎng)春,沈陽(yáng),呼和浩特,石家莊,太原,濟(jì)南,鄭州廣 西安,蘭州,銀川,西寧,烏魯木齊,合肥,南京,杭州廣長(zhǎng)沙,南昌廣武漢 ,成都,貴州,福建,臺(tái)北,廣州,海口 ,南寧,昆明,拉薩,香港,澳門 這32個(gè)城市，存放在一個(gè)長(zhǎng)度為34的數(shù)組中。城市i和城市j的距離為數(shù)組中 對(duì)應(yīng)元素的相對(duì)位移。如北京與上海的距離為1

7、，對(duì)應(yīng)完全圖中的邊長(zhǎng)為1;- 北京與天津的距離為2,對(duì)應(yīng)完全圖中的邊長(zhǎng)為2，以此類推。求解目標(biāo)為從一個(gè)城市出發(fā)進(jìn)行一次巡回，經(jīng)過(guò)每個(gè)城市一次最終回到出發(fā) 城市，并使整個(gè)旅行的費(fèi)用最低，即遍歷的城市距離和最短。4.3數(shù)據(jù)結(jié)構(gòu)private class genotype int city = new intcityNum;long fitness;double selectP;double exceptp;isSelected;int private privateprivate private private private private private private單個(gè)基因的城市序列該基因

8、的適應(yīng)度選擇概率期望概率是否被選擇genotype citys = new genotypepopSize;String cityName=北京”，上海”，天津,重慶”，哈爾濱”，長(zhǎng)春”，沈 陽(yáng),”呼和浩特”，石家莊”，太原”，濟(jì)南”，鄭州”， 西安”，蘭州”，銀川”，西寧”，烏魯木齊”，合肥”，” 南京”，杭州”，長(zhǎng)沙”，南昌”，武漢”，成都”，貴州 ”,福建”，臺(tái)北”，廣州”，海口”，南寧”，昆明”，拉 薩”，香港”，澳門;int cityNum=cityName.length; 城市個(gè)數(shù)long distance = new longcityNumcityNum; /城市距離 int p

9、opSize = 50;int maxgens = 10000;double pxover = 0.8;double pmultation = 0.05;int range = 2000;種群數(shù)量迭代次數(shù)交叉概率變異概率用于判斷何時(shí)停止的數(shù)組區(qū)間4.4實(shí)驗(yàn)結(jié)果進(jìn)行若干次重復(fù)試驗(yàn)，四類運(yùn)行結(jié)果如下：1、迭代10000次，得到最優(yōu)的結(jié)果。本次實(shí)驗(yàn)結(jié)果表示從南京出發(fā)，依次經(jīng) 過(guò)以下城市，最終到達(dá)杭州再回到南京，旅行路程為66。 第9992代最優(yōu)的解：6色 第9993代最優(yōu)的解：66 第9994代最優(yōu)的解：66 第9995代最優(yōu)的解：66 第9996代最優(yōu)的解：6色 第9997代最優(yōu)的解：66 第99

10、98代最優(yōu)的解：66 第9999代最優(yōu)的解：66第 10000 代最優(yōu)的解:66最佳路徑的序列：南京烏皆木齊銀J11西安鄭州濟(jì)南重慶天津上海北京哈爾濱長(zhǎng)春沈陽(yáng)呼和浩特石家莊太原蘭州西寧 合肥昆明拉薩香港虞門南寧海口廣州臺(tái)北福建貴州成都武漢南昌長(zhǎng)沙杭州算法執(zhí)行時(shí)間：3.189秒2、迭代未滿10000次，即連續(xù)2000次得到的結(jié)果相同，提前終止。結(jié)果如下所 示：在第6859次迭代后停止了算法，得到的解為從鄭州出發(fā)，依次經(jīng)過(guò)后續(xù) 城市，最終到達(dá)西安后再返回鄭州。旅行路程為66。最優(yōu)的解：66 第6852代最伉的解：66 第6853代最伉的解：66 第6854代最伉的解：66 第6855代最優(yōu)的解：6

11、6 第6856代最優(yōu)的解：66 第6857代最優(yōu)的解：66 第6858代最優(yōu)的解：66 第6859代最優(yōu)的解：66最佳路徑的序列：鄭州濟(jì)南太原石家莊呼和浩特沈陽(yáng)長(zhǎng)春重慶天津上海北京哈爾濱銀JII烏舍木齊合肥福建奧門香港 拉薩昆明南寧海口廣州臺(tái)北貴州成都武涅南昌長(zhǎng)沙杭州南京西寧蘭州西安算法執(zhí)行時(shí)間：1-350秒3、迭代滿10000次，但仍未得到最優(yōu)結(jié)果。程序運(yùn)行結(jié)果如下圖所示：得到的解為從南昌出發(fā)，依次經(jīng)過(guò)后續(xù)城市，最終到達(dá)合肥后再返回南昌。旅行 路程為82，比最優(yōu)解66要大。 第9994代最優(yōu)的解：82 第9995代-最優(yōu)的解：82 第9996代最優(yōu)的解：82 第9997代最優(yōu)的解：82 第泗

12、98代-最優(yōu)的解：82 第9999代最優(yōu)的解：82 第10000代最優(yōu)的解：82最佳路徑的序列：南昌武漢成都貴州廣州奧門香港拉薩昆明南寧海口臺(tái)北福建長(zhǎng)沙杭州南京蘭州沈陽(yáng) 哈爾濱重慶天津上海北京長(zhǎng)春呼和浩特西安銀川烏魯木齊西寧鄭州濟(jì)南太原石家莊合肥 算法執(zhí)行時(shí)間：2.608秒4、迭代未滿10000次，但有連續(xù)2000次得到相同結(jié)果，然而結(jié)果不是最優(yōu)的， 程序運(yùn)行結(jié)果如下所示：得到的解為從南寧出發(fā)，依次經(jīng)過(guò)后續(xù)城市，最終到 達(dá)杭州后再返回南寧。旅行路程為106，比最優(yōu)解66要大。用十】 |勺最優(yōu)的解：106 第4440代最優(yōu)的解：106 第4441代最優(yōu)的解：106 第4442代最優(yōu)的解：106

13、第4443代最優(yōu)的解：106 第4444代最優(yōu)的解：106 第4445代最優(yōu)的解：106 第4446代最優(yōu)的解：106 第4447代最優(yōu)的解：106最佳路徑的序列:其他對(duì)比實(shí)驗(yàn)薩昆明海口廣州臺(tái)北烏魯木齊西寧西安哈爾濱北京上海天津重慶蘭州南昌成都福建貴州武漢長(zhǎng)沙鄭州濟(jì)南石家莊長(zhǎng)春沈陽(yáng)呼和浩特太原銀JII合肥南京杭州 算法執(zhí)行時(shí)間：1-316秒使用控制變量法，通過(guò)修改迭代次數(shù)和停止閾值可以得到不同的實(shí)驗(yàn)結(jié)果， 理論上迭代次數(shù)與停止閾值越大，越可能得到最優(yōu)解。如將10000改成5000， 則很難得到最優(yōu)解，或者將2000改成500，則很容易在非最優(yōu)解時(shí)停止迭代， 同樣很難得到優(yōu)化解。由此可見(jiàn)迭代次數(shù)與停止閾值能影響程序的遺傳算法的優(yōu) 化效果。五總結(jié)遺傳算法維護(hù)一個(gè)由競(jìng)爭(zhēng)假設(shè)組成的多樣化群體。在每次