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