【正文】 pXuh[1]=rand()%(POPSIZE1)。icrossNum/2。 crossNum=int(POPSIZE*pc)。 int cityCross[2][CITY_NUM+1]。 遺傳交叉的主要目的是子代盡可能地繼承父代的優(yōu)秀基因。 解決這一約束問題的另一種處理方法是對交叉，變異等遺傳操作作適當(dāng)?shù)男拚蛊渥詣訚M 足 TSP 的約束條件，本文采用部分匹配交叉法 ： 部分匹配交叉中先依據(jù)均勻隨機(jī)分布產(chǎn)生兩個(gè)位串交叉點(diǎn)，定義這兩點(diǎn)之間的區(qū)域?yàn)橐黄ヅ鋮^(qū)域，并使用位置交換操作交換兩個(gè)父串的匹配區(qū)域，兩父串及匹配區(qū)域?yàn)? A=9 8 4 |5 6 7| 1 3 2 0 B=8 7 1 |2 3 0| 9 5 4 6 首先交換 A 和 B 的兩個(gè)匹配區(qū)域，得到 A1=9 8 4 |2 3 0| 1 3 2 0 16 B1=8 7 1 |5 6 7| 9 5 4 6 對于 A1， B1 兩個(gè)串中匹配區(qū)域以外出現(xiàn)的遍歷重復(fù)，依據(jù)匹配區(qū)域內(nèi)的位置映射關(guān)系， 逐一進(jìn)行交換，對于 A1 有 2 到 5,3 到 6,0 到 7 的位置符號映射，對 A1 的匹配區(qū)以外的 2， 3， 0分別以 5,6,7 替換，則得 A2=9 8 4 |2 3 0 |1 6 5 7 B2=8 0 1| 5 6 7 |9 2 4 3 這樣，每個(gè)子串的次序部分有其父串確定。 } 基于 TSP 問題 的順序編碼，若采取簡單的一點(diǎn)交叉或多點(diǎn)交叉策略，必然以極大的概率導(dǎo)致未能完全遍歷所有城市的非法路徑 1 2 3 4| 5 6 7 8 8 7 6 5 |4 3 2 1 若采取一點(diǎn)交叉，且交叉點(diǎn)隨機(jī)選為 4，則交叉后產(chǎn)生的兩個(gè)后代為 8 7 6 5 5 6 7 8 1 2 3 4 4 3 2 1 顯然，這兩個(gè)子路徑均未能遍歷所有 8 個(gè)城市，都違反了 TSP 的約束條件。i!=j) { copyColony(i,j,city)。 //if(i!=cityBestFitCityXuh) if(cityfitness[j]=cityfitness[i]amp。tempflag1==0。jPOPSIZEamp。 tempflag1=0。iPOPSIZE。 int i,j。 b)其次計(jì)算出每個(gè)個(gè)體的相對適應(yīng)度的大小，作為被選中的概率。根據(jù)個(gè)體適應(yīng)度值的大小，適應(yīng)度值越大的，其概率 Psi越大，被選擇到的機(jī)會也越多，從而其基因結(jié)構(gòu)被遺傳到下一代的可能性也越大，反 之亦 然。 在輪盤賭法中，各個(gè)個(gè)體的被選擇概率和其適應(yīng)度值成比例。 比較常用的就是輪盤賭法，以及最優(yōu)策略保留法。 (4) 期望值方法。 (2) 錦標(biāo)賽選擇。選擇操作的目的是為了避免基因缺失，提高全局收斂性和計(jì)算效率。 } cityfitness[i]=N/(cityDistance[i])。end=citycolony[i][j]。j=CITY_NUM。i++){//求適應(yīng)值 cityDistance[i]=0。 for(i=0。 void CalFitness(PTSP city) { int i,j。度量物種適應(yīng)度的函數(shù)就被稱為適應(yīng)度函數(shù)。 在研究自然界中生物的遺傳和進(jìn)化現(xiàn)象時(shí)，生物學(xué)家常常使用適應(yīng)度這個(gè)術(shù)語來衡量某個(gè)物種對環(huán)境的適應(yīng)率。在遺傳算法求解 TSP 問題中通常以隨機(jī)方式產(chǎn)生串或者個(gè)體的集合。 選擇一個(gè)群體，就是選擇一個(gè)個(gè)體的集合。這就如同研究生物遺傳是從染色體著手，而染色體則是由基因排成的串。如何將問題的解轉(zhuǎn)換為編碼表達(dá)的染色體是遺傳算法的關(guān)鍵問題。因此遺傳算法在 TSP 問題求解方面的應(yīng)用研究，對于構(gòu)造合適的遺傳算法框架，建立有效的遺傳操作以及有效地解決 TSP 等有著多方面的重要意義。 12 第 4 章 遺傳算法在 TSP 的應(yīng)用 TSP上的應(yīng)用 在遺傳算法研究中， TSP 問題已被廣泛地用于評價(jià)不同的遺傳操作及選擇機(jī)制的性能。作為神經(jīng)網(wǎng)絡(luò)的基本單元 ，神經(jīng)元模型具備三個(gè)基本要素。 (4)人工神經(jīng)網(wǎng)絡(luò) 人工神經(jīng)網(wǎng)絡(luò) (Artificial Neural Network， ANN)，是由大量處理單元即神經(jīng)元 (Neurons)互相連接而成的網(wǎng)絡(luò)，對人腦進(jìn)行抽象，簡化和模擬的一種工程系統(tǒng) ，反映人腦的基本特性 。該算法的優(yōu)點(diǎn)是 : 它是一種自 適應(yīng) 度 、自組織、本質(zhì)上并 行的方法， 而且是一種正向反饋的方法，可以促使整個(gè)系統(tǒng)向最優(yōu)解進(jìn)化，而且參數(shù)少、易于調(diào)整，易于移植到其他組合優(yōu)化問題。通過這種正向反饋， 最終將找到一條最優(yōu)路徑。它由 Marco Dorigo 于 1992年在他的 博士論文 中提出， 過模擬螞蟻的覓食行為， 螞蟻覓食的時(shí)候會在所走過的路徑上留下信息激素， 同時(shí)信息激素會隨時(shí)間而揮發(fā) .一條路徑走過的螞蟻越多， 留下的信息激素越多 。這種算法思想在求解優(yōu)化問題時(shí)，不但接受對目標(biāo)函數(shù) (能量函數(shù) )有改進(jìn)的狀態(tài)，還以某種概率接受使目標(biāo)函數(shù)惡化的狀態(tài)，從而可使之避免過早收斂到某個(gè) 局部極值點(diǎn)，也正是這種概率性的擾動能夠使之跳出局部極值點(diǎn)，故而得到的解常常很好。若禁忌長度過長，則所需內(nèi)存較大，否則， 易陷入局部最優(yōu)解。 (1)禁忌搜索算法 禁忌搜索算法是局部領(lǐng)域搜索算法的推廣，主要思想是標(biāo)記已經(jīng)得到的局部最優(yōu)解，并在進(jìn)一步的迭代中避開這些局部最優(yōu)解。 20 世紀(jì) 80 年代以來，一些新穎的智能優(yōu)化算法，如模擬退火、遺傳算法、禁忌搜索、人工神經(jīng)網(wǎng)絡(luò)、蟻群算法、粒子群算法、郭濤算法、免疫算法等，通過模擬或揭示某些自然現(xiàn)象 (或過程 )而得到發(fā)展，其思想和內(nèi)容涉及數(shù)學(xué)、物理學(xué)、生物進(jìn) 化、人工智能、神經(jīng)科學(xué)和統(tǒng)計(jì)力學(xué)等方面，為解決復(fù)雜問題提供了新的思路和手段．由于這些算法構(gòu)造的直觀性和自然機(jī)理，通常稱作智能演化算法，或稱為現(xiàn)代啟發(fā)式算法。 傳統(tǒng)算法有精確算法和近似優(yōu)化算法，精確算法又有線性規(guī)劃方法、動態(tài)規(guī)劃方法、分支定界方法等，而近似算法有插入法、最近鄰算法、 ropt 算法、混合算法、概率算法等。 。 TSP 問題的分類 從 TSP問題映射到圖的類型 ,可以分為兩類 : (1)城市間的距離都是對稱的 ,它對應(yīng)的是圖論中的無向圖 。盡管 TSP 仍未找到最優(yōu)解，但是求解它的算法逐漸在改進(jìn)。因此尋求一種求解時(shí)間短，能滿足實(shí)際問題精度要求的解，成為解決該問題的主要途徑。所以對于輸入規(guī)模為 n個(gè)城市 TSP 找到最優(yōu)解的時(shí)間復(fù)雜性函數(shù)的數(shù)量級是 O(n!)，當(dāng) n比較大時(shí)，耗費(fèi)的時(shí)間己經(jīng)是個(gè)天文數(shù)字，至今尚未找到有效的求解方法。雖然陳述起來很簡單，但求解卻很困難，它 一直是運(yùn)籌學(xué)中最富挑戰(zhàn)性的問題之一，且已經(jīng)被證明是 NP 完全問題。 除此之外，模型還有其它一些等價(jià)的書寫形式，這就不一一列舉。為了通過 TSP解決這個(gè)時(shí)間的節(jié)約問題，對每個(gè)節(jié)點(diǎn)做了簡化，用需要鉆孔的位置來代替，而邊用節(jié)點(diǎn)之間的距離來代替。旅行商問題的解可以用來找出孔被加工的最優(yōu)順序。在某個(gè)局部的區(qū)域，鉆頭可以沿著軌跡移動到任何位置。材料可能是電路板、汽車底盤 甚至是用來做書架的木板。例如在組裝線上的機(jī)器。為解決以上提及的實(shí)例，僅需要把期望訪問的地理位置具體化，然后用旅行商問題的算法進(jìn)行求解就行了。對提到的實(shí)例，圖中的節(jié)點(diǎn)將通過地理位置順序連接，而且連接兩節(jié)點(diǎn)的路徑的長度是公制的。直觀上，最普通的 TSP 的運(yùn)用莫過于找出 旅行商為遍歷每個(gè)地理位置上的點(diǎn)的順序，使他所經(jīng)歷的路徑最短。但是遺憾的 是，計(jì)算復(fù)雜性理論給予我們的結(jié)論卻是，這種可能性尚屬未知 。旅行商問題是組合數(shù)學(xué)中一個(gè)古老而又困難的問題，它易于描述但至今尚未徹底解決，現(xiàn)己歸入經(jīng)典的NPhard 組合優(yōu)化問題之一。人工生命與遺傳算法有著密切的關(guān)系，基于遺傳算法的進(jìn)化模型是研究人工生命現(xiàn)象的重要基礎(chǔ)理論?；谶z傳算法的參數(shù)辨識，基于遺傳算法的模糊控制規(guī)則的學(xué)習(xí)，利用遺傳算法進(jìn)行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計(jì)和權(quán)值學(xué)習(xí)等，都顯示出了遺傳算法在這些領(lǐng)域中應(yīng)用的可能性。實(shí)踐證明，遺傳算法對于組合優(yōu) 7 化中的 NP問題非常有效。 (2) 組合優(yōu)化 隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇增大，有時(shí)在目前的計(jì)算上用枚舉法很難求出最優(yōu)解。 (1)函數(shù)優(yōu)化 函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是遺傳算法進(jìn)行性能評價(jià)的常 用算例，許多人構(gòu)造出了各種各樣復(fù)雜形式的測試函數(shù)：連續(xù)函數(shù)和離散函數(shù)、凸函數(shù)和凹函數(shù)、低維函數(shù)和 高維 函數(shù)、單峰函數(shù)和多峰函數(shù)等。 (6)遺傳算法對給定的問題，可以產(chǎn)生許多的潛在解，最終選擇可以由使用者確定 。 (4)遺傳算法強(qiáng)調(diào)概率轉(zhuǎn)換規(guī)則，而不是確定的轉(zhuǎn)化規(guī)則。使用這種搜索方式，雖然每次只執(zhí)行與種群規(guī)模 n成比例的計(jì)算，但實(shí)質(zhì)上已經(jīng)進(jìn)行了大約 O(n3)次有效搜索，這就使遺傳算法能以較少的計(jì)算獲得較大的收益。二是遺傳算法的內(nèi)含并行性 (implicitparallelism)。最簡單的并行方式是讓幾百甚至上千臺計(jì)算機(jī)各自進(jìn)行獨(dú)立種群的演化計(jì)算，運(yùn)行過程中甚至不進(jìn)行任何通信 (獨(dú)立的種群之間若有少量的通信一般會帶來更好的 結(jié)果 )，等到運(yùn)算結(jié)束才通信比較，選取最佳個(gè)體。遺傳算法按并行方式搜索一個(gè)種群數(shù)目的點(diǎn)，而不是單點(diǎn)。因此，利用遺傳算法的方法，我們可以解決那些復(fù)雜的非結(jié)構(gòu)化的問題。 6 進(jìn)化算法的這種自組織、自適應(yīng)特征，使它同時(shí)具有能根據(jù)環(huán)境變化來自動發(fā)現(xiàn)環(huán)境的特性和規(guī)律的能力。由于自然選擇策略為“適者生存，不適應(yīng)淘汰 ，因而適應(yīng)度大的個(gè)體具有較高的生存概率。主要區(qū)別在于 (1)自組織、自適應(yīng)和自學(xué)習(xí)性。 列出了 表 21 生物遺傳與遺傳算法部分概念的對 照 4 表 21 生物遺傳與遺傳算法的概念對照 生物遺傳 遺傳算法 基因 解中每一分量的特征 染色體 解的編碼 個(gè)體 解 種群 一組解 交配 交叉操作 變異 編碼的某一個(gè)分量發(fā)生變化的過程 適應(yīng)性 編碼解碼后得到的適應(yīng)度函數(shù)值 適者生存 選擇操作 遺傳算法的基本步驟 步驟一 :確定參變量及其各種約束條件 .即確定個(gè)體的表現(xiàn)形式和問題的解空間 . 步驟二 : 建立優(yōu)化模型 . 即確定出求解問題的目標(biāo)函數(shù)和數(shù)學(xué)描述形式及量化方法 . 步驟三 :確定染色體的編碼方法 .即 確定個(gè)體的基因形式 . 步驟四 :確定解碼方法 .即確定出個(gè)體的基因形式到個(gè)體的表現(xiàn)形式的對應(yīng)關(guān)系和轉(zhuǎn)化方式 . 步驟五 : 確定個(gè)體適應(yīng)度的量化評價(jià)方法 .即確定出目標(biāo)函數(shù)值同個(gè)體適應(yīng)度的轉(zhuǎn)化規(guī)則 . 步驟六 : 設(shè)計(jì)遺傳算子 .即確定出選擇算子 ,交叉算子和變異算子等遺傳算子的具體操作方法 . 步驟七 : 確定遺傳算法的有關(guān)運(yùn)行參數(shù) .即確定出遺傳算法 遺傳算法的流程圖 5 圖 21遺傳算法流程圖 遺傳算法的特點(diǎn) 傳統(tǒng)的優(yōu)化方法主要有三種：枚舉法、啟發(fā)式算法和搜索算法。新一代形成中，根據(jù)適應(yīng)度的大小選擇部分后代，淘汰部分后代，從而保持種群大小的穩(wěn)定性。生成的下一代染色體稱為后代(offspring)。這些染色體在后續(xù)迭代中不斷進(jìn)化，稱為遺傳。與傳統(tǒng)搜索算法不同，遺傳算法是從一組隨機(jī)產(chǎn)生的初始解開始搜索過程。這個(gè)過程導(dǎo)致種群象自然進(jìn)化一樣，后代種群比前代更加適應(yīng)于環(huán)境，末代種群中最優(yōu)個(gè)體經(jīng)過解碼 (Decoding)，可以作為問題的近似最優(yōu)解。初始種群產(chǎn)生以后按照優(yōu)勝劣汰、適者生存的原理，逐代演化產(chǎn)生出越來越好的近似解。每個(gè)個(gè)體實(shí)際上是染色體(Chromosome)帶有特征的實(shí)體。 1994 年 1月， IEEE 神經(jīng)網(wǎng)絡(luò)委員會出版了第一本《進(jìn)化計(jì)算》專集，同年 6 月 組織召開第一屆“進(jìn)化計(jì)算”國際會議，以后每年舉行一次。 1985 年，美國召開了第一屆遺傳算法國際會議 (ICGA)，在遺傳算法發(fā)展史上具有里程碑式的意義。進(jìn)入 90年代，遺傳算法進(jìn)入了興 盛期，無論是理論研究還是應(yīng)用研究都成了十分熱門的課題。 1980 年， Smith 將遺傳算法應(yīng)用于機(jī)器學(xué)習(xí)領(lǐng)域； Bethke 對函數(shù)優(yōu)化的遺傳算法進(jìn)行了系統(tǒng)的研究。 美國 De． Jong 博士基于遺傳算法的思想在計(jì)算機(jī)上進(jìn)行了 3 大量的純數(shù)值函數(shù)優(yōu)化計(jì)算實(shí)驗(yàn)，建立了著名的 De． Jong 五函數(shù)測試平臺。 1967 年，他的學(xué)生 Ba