【正文】 tempflag1=1。amp。 for(j=0。i++)//選 POPSIZE 次 { tempRand=(rand()%100000)/*3。 for(i=0。 void Select(PTSP city) { //選擇算子 double tempRand,tempflag1。 輪盤賭的具體執(zhí)行過程如下： a)先計(jì)算出種群中所有個(gè)體的適應(yīng)度的總和。設(shè)群體大小為 N，個(gè)體 i 的適應(yīng)度值 Fi，則個(gè)體 i 被選擇的概率 Psi為： Psi=Fi／ ??nj j1F (n=l， 2?．． n) 顯然，概率 Psi反映了個(gè)體 i的適應(yīng)度在整個(gè)群體的個(gè)體適應(yīng)度總和中所占的比例。本文采用的是 輪盤賭法 。 (5) 排序選擇方法。 (3) 最優(yōu)保存策略。常用的選擇可略包括以下幾種： (1) 輪盤賭法。 } } 遺傳算法中的選擇操作就是用來確定如何從父代群體中按某種方法選 取哪 些個(gè)體遺傳到福建農(nóng)林大學(xué)本科畢業(yè)論文 14 下一代群體中的一種遺傳運(yùn)算。 cityDistance[i]=cityDistance[i]+CityDistance[start][end]。j++){ start=citycolony[i][j1]。 for(j=1。iPOPSIZE。 int start,end。 本文中適應(yīng)度函數(shù)取為哈密爾頓圈的長(zhǎng)度的倒數(shù)。適應(yīng)度較高的物種將會(huì)得到更多的繁殖的機(jī)會(huì)；從而導(dǎo)致適應(yīng)度低的物種被淘汰。初始種群個(gè)數(shù)越多，得到最優(yōu)解的希望越大，但個(gè)數(shù)過多會(huì)導(dǎo)致每進(jìn)行一輪的機(jī)器時(shí)間變長(zhǎng)，致使算法效率低下。這個(gè)初始群體也就是問題假設(shè)解得集合。遺傳算法中經(jīng)常使用二進(jìn)制串進(jìn)行編碼，其優(yōu)點(diǎn)是編碼、解碼操作簡(jiǎn)單，交叉、變異等操作也易于實(shí)現(xiàn)，且便于應(yīng)用模式定理進(jìn)行理論分析；其缺點(diǎn)主要是處理 連續(xù)函數(shù)的優(yōu)化問題時(shí)存在映射誤差：編碼長(zhǎng)度較小時(shí)達(dá)不到精度要求， 度較大時(shí)又會(huì)使算法搜索空間過大。編碼機(jī)制的主要工作是把對(duì)象抽象為由特定符號(hào)按一定順序排成的串。 圖 41遺傳算法運(yùn)用在 TSP上的流圖程 福建農(nóng)林大學(xué)本科畢業(yè)論文 13 遺傳算法的進(jìn)化過程是建立在編碼機(jī)制基礎(chǔ)上的，編碼對(duì) 于算法的性能，如搜索能力和種群多樣性等影響很大。 TSP問題因其典型性已成為各種啟發(fā)式的搜索，優(yōu)化算法的間接比較標(biāo)準(zhǔn)，而遺傳算法方法就本質(zhì)來說，主要處理復(fù)雜問題的一個(gè)魯棒性強(qiáng)的啟發(fā)式隨機(jī)搜索算法。其一是有一組突觸或連接，常用表示內(nèi)部神經(jīng)元的聯(lián)接強(qiáng)度，或者稱 為權(quán)值，取值 范圍 可在負(fù)值和正值之間 ， 其二是 可以 反映生物神經(jīng)元時(shí)空整合功能的輸入信號(hào)累加器 ， 其三是具有一個(gè)激勵(lì)函數(shù)用于限制神經(jīng)元的輸出 。人工神經(jīng)網(wǎng)絡(luò)算法成為近年來的熱點(diǎn)研究領(lǐng)域，涉及到 數(shù)學(xué) 、電氣工程、 計(jì)算機(jī)工程 、 物理學(xué) 等諸多學(xué)科，其應(yīng)用領(lǐng)域包括了建模、時(shí)間序列分析、模式識(shí)別和控制等，并且仍然在一斷擴(kuò)展。 但是，它存在收斂慢、易于陷人局部最優(yōu) 的缺點(diǎn) 。為了避免螞蟻兩次走上同 一條路徑 ( 非法路徑 ) ， 為每個(gè)螞蟻設(shè)置一個(gè)禁忌表以記錄它福建農(nóng)林大學(xué)本科畢業(yè)論文 11 已走過的路徑。 反過來， 信息激素濃度高的路徑上會(huì)吸引更多的螞蟻。 (3)蟻群算法 又稱 螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機(jī)率型算法。 (2)模擬退火算法 這是一種源 于五十年代、基于 Monte Carlo 迭代求解思想的隨機(jī)搜索算法，八十年代才開始應(yīng)用于組合優(yōu)化領(lǐng)域，其出發(fā)點(diǎn)是將組合優(yōu)化問題與統(tǒng)計(jì)力學(xué)的熱平衡作類比，把優(yōu)化的目標(biāo)函數(shù)視作能量函數(shù)，模仿物理學(xué)中固體物質(zhì)的退火處理，先加溫使之具有足夠高的能量，然后再逐漸降溫，其內(nèi)部能量也相應(yīng)下降，在熱平衡條件下，物體內(nèi)部處于不同狀態(tài)的概率服從 Boltzmann分布，若退火步驟恰當(dāng)，則最終會(huì)形成最低能量的基態(tài)。此方法需較 強(qiáng)技術(shù)性，禁忌長(zhǎng)度較難取。引入智能演化算法的原因在于避免陷人局部最優(yōu)解，希望得到更好的解上界。 雖然傳統(tǒng)算法能夠找 TSP 問題的最優(yōu)解，但隨著問題規(guī)模的不斷增長(zhǎng)，算法所需要的時(shí)間非常巨大，因此只適用于求解規(guī)模較小的 TSP 問題。 TSP 問題 ,即 EuclidTSP,它給出每個(gè)點(diǎn)在歐式平面 上的坐標(biāo) ,而城市間的距離就是以他們的歐式距離來定義 . 福建農(nóng)林大學(xué)本科畢業(yè)論文 10 現(xiàn)有的求解 TSP 問題的幾種算法 在求解 TSP的算法的過程中，人們一直在尋找切實(shí)有效的方法，按招時(shí)間出現(xiàn)的順序大致可分為：傳統(tǒng) 算法和智能演化算法。 (2)兩個(gè)城市間的距離是非對(duì)稱的 ,它所對(duì)應(yīng)的是圖論中的有向圖 . 從問題本身的限制條件的強(qiáng)弱 ,可分為三類 : (但是一般都要求城市間的費(fèi)用不為負(fù)數(shù) ),只是給出距離矩陣 ,求最小回路 。 1954 年 Dantzig， Fulkerson 和 Johnson 解決了 49 個(gè)城市數(shù)目的 TSP 問題，經(jīng)過半個(gè)世紀(jì)的研究，目前，最大的已成功求解的旅行商問題有 24798 個(gè)城市。快速、有效地解決 TSP 問題有著極高的實(shí)際應(yīng)用價(jià)值，也就吸引了眾多領(lǐng)域的學(xué)者對(duì)它進(jìn)行研究。在理論上雖然枚舉法可以解這一問題，但是當(dāng) n較大時(shí)，解題的時(shí)間消耗會(huì)使枚舉法顯得沒有任何實(shí)際價(jià)值。對(duì)于具有一個(gè)城市的 TSP 問題，其可能的路徑數(shù)目為 (n1)!／ 2， 5 個(gè)城市的情形對(duì)應(yīng)120／ 10=12 條路線， 10個(gè)城市的情景對(duì)應(yīng) 3628800／ 20=181440 條路線。 TSP 問題是組合優(yōu)化領(lǐng)域中的一個(gè)典型問題，涉及求多個(gè)變量的函數(shù)的最小值。 福建農(nóng)林大學(xué)本科畢業(yè)論文 9 TSP問題的數(shù)學(xué)模型 TSP 問題的數(shù)學(xué)模型如下：設(shè)有 n個(gè)城 市，尋找一條巡回路徑 T=(t1， t2，．．．， tn)，使得下列目標(biāo)函數(shù)最小： f(T)= ???1n1di(ti,ti+1)+d(tn,t1) 其中 ti為 城 市號(hào)，取值為 1 到 n 之間的自然數(shù)， d(i,j)為城市 i 和城市 j 之間的距離，對(duì)于對(duì)稱式 TSP，有 d(i， j)=d(j， i)。在裝配線的實(shí)例中，對(duì)每個(gè)工件為完成裝配過程節(jié)約的少許時(shí)間意味著一天的產(chǎn)量的相應(yīng)增加。鉆頭的重定位所消耗的時(shí)間依賴于鉆頭需要移動(dòng)的距離。鉆頭通過定位裝置在材料片上重定位。一些機(jī)器的目標(biāo)就是為了在某種材料片上鉆削不同的孔。 TSP 在其他領(lǐng)域還有很多重要的實(shí)際應(yīng)用。在當(dāng)前，很多的現(xiàn)實(shí)事物，包括城市，建筑和地標(biāo)都已經(jīng)有了平面電子地圖。了解了對(duì)每個(gè)城市訪問一次的最優(yōu)旅行路徑能夠?yàn)槁眯泄?jié)約很多潛在的時(shí)間。 TSP的應(yīng)用與價(jià)值 TSP 在現(xiàn)實(shí)生活中有很多應(yīng)用。該問題在圖論的意義下就是所謂的最小 Hamilton 圈問題，由于可以廣泛應(yīng)用在許多領(lǐng)域，所以尋找出實(shí)際而有效的算法就顯得比較重要了。 福建農(nóng)林大學(xué)本科畢業(yè)論文 8 第 3 章 TSP 問題及研究的基本方法 TSP問題概述 旅行商問題 (Travelling Salesman Problem，簡(jiǎn)記 TSP) 經(jīng)典說法為：有一名旅行商要從一個(gè)城市去若干個(gè)城市推銷貨物，從城市 A 出發(fā)，經(jīng)其余各城 市且每個(gè)城市只能訪問一次，然后回到城市 A，問選擇怎樣的旅行路線，才能使旅行的總長(zhǎng)度最短 (各城市間距離為已知 )。 (4)人工生命 人工生命是用計(jì)算機(jī)，機(jī)械等人工媒體模擬或構(gòu)造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)，自組織能力和自學(xué)能力是人工生命的兩大主要特征。例如遺傳算法已經(jīng)在求解旅行商問題、 背包問題、裝箱問題、圖形劃分問題等方面得到成功的應(yīng)用 (3) 自動(dòng)控制 在自動(dòng)控制領(lǐng)域中有很多與優(yōu)化相關(guān)的問題需要求解，遺傳算法已在其中得到了初步的應(yīng)用，并顯示了良好的效果。對(duì)這 類復(fù)雜的問題，人們已經(jīng)意識(shí)到應(yīng)把主要精力放在尋求滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。對(duì)于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，用其它優(yōu)化方法較難求解，而遺傳算法可以方便的得到較好的結(jié)果。 遺傳算法的應(yīng)用 遺傳算法提供了一種求解復(fù)雜系統(tǒng)問題的通用框架，它不依賴于問題的具體領(lǐng)域，對(duì)問題的種類有很強(qiáng)的 魯棒性 ，所以廣泛應(yīng)用于許多科學(xué) 。 (5)遺傳算法可以更加直接的應(yīng)用。 (3)遺傳算法不需要求導(dǎo)或其他輔助知識(shí)，而只需要影響搜索方向的目標(biāo)函數(shù)和相應(yīng)的適應(yīng)度函數(shù)。由于遺傳算法采用種群的方式組織搜索，因而可同時(shí)搜索解空間內(nèi)的多個(gè)區(qū)域，并相互交流信息。這種并行處理方式對(duì)并行系統(tǒng)結(jié)構(gòu)沒有什么限制和要求，可以說，遺傳算法適合在目前所有的并行機(jī)或分布式系統(tǒng)上進(jìn)行并行處理，而且對(duì)運(yùn)行效率沒有太大的影響。它的并行性表現(xiàn)在兩個(gè)方面，一是遺傳算法的內(nèi)在并行性 (inherentparallelisml，即遺傳算法本身非常適合大規(guī)模并行。 (2)遺傳算法的本質(zhì)并行性。自然選擇消除 了算法設(shè)計(jì)過程中的一個(gè)最大障礙，即需要事先描述問題的全部特點(diǎn)，并要說明針對(duì)問題的不同特點(diǎn)算法應(yīng)采取的措施。通常，適應(yīng)度大的個(gè)體具有更適應(yīng)環(huán)境的基因結(jié)構(gòu)，在通過基因重組和基因突變等遺傳操作，就可能產(chǎn)生更適應(yīng)環(huán)境的后代。應(yīng)用遺傳算法求解問題時(shí)，在編碼方案、適應(yīng)度函數(shù)及遺傳算子確定后，算法將利用進(jìn)化過程中獲得的信息自行組織搜索。隨著問題種類的不同以及問題規(guī)模的擴(kuò)大，需要尋求一種能以有限的代價(jià)來解決搜索和優(yōu)化的通用方法，遺傳算法 正是為我們提供了一個(gè)有效途徑，它不同于傳統(tǒng)的 搜索和優(yōu)化方法。適應(yīng)度高的染色體被選中的概率高，這樣，經(jīng)過若干代之后，算法收斂于最好的染色體，它很可能就是問題的最優(yōu)解或次優(yōu)解。后代是由前一代染色體通過交叉 (crossover)或者變異 (mutation)運(yùn)算形成的。在每一代中用適應(yīng)度 (fitness)來測(cè)量染色體的好壞。種群中的每個(gè)個(gè)體是問題的一個(gè)解 ，稱為“染色體 ，染色體是一串符號(hào)，比如二進(jìn)制 01 串。 遺傳算法采納了自然進(jìn)化模型，如選擇、交叉、變異、遷移、局域與鄰域等。在每一代， 根據(jù)問題域中個(gè)體的適應(yīng)度 (fitness)大小挑選個(gè)體，并借助代表于自然遺傳學(xué)的遺傳算子 (Geic Operators)進(jìn)行交叉 (Grossover)和變異(Mutation)，產(chǎn)生出代表新的解集的種群。作為多個(gè)基因的集合，單個(gè)染色體是遺傳物質(zhì)的主要載體，其在種群中的命運(yùn)由其基因組合決定。 遺傳算法 基本原理 遺傳算法是從代表問題可能潛在解集的一個(gè)種群 (Population)開始的，而一個(gè)種群則由經(jīng)過基因 (Gene)編碼 (Coding)的一定數(shù)目的個(gè)體 (Individual)組成。此后 ICGA 每隔一年舉行一次， 1999 年期， ICGA 與 GP 的系列會(huì)議合并為一年一次的遺傳與進(jìn)化國(guó)際會(huì)議 (GECCO)。尤其是遺傳算法的應(yīng)用研究顯得格外活躍，被廣 泛地應(yīng)用于組合優(yōu)化、生產(chǎn)調(diào)度 、機(jī)器學(xué)習(xí)、圖像處理、人工生命等領(lǐng)域，不僅如此，利用遺傳算法進(jìn)行優(yōu)化和規(guī)則學(xué)習(xí)的能力也顯著提高。 1989 年， David Goldberg 出版了 ((GeicAlgorithm in Search,Optimization and Machine Leaming》一書， 成為論述遺傳算法的第一本專著。 80 年代，遺傳算法開始在各個(gè)領(lǐng)域得到廣泛應(yīng)用。 70 年代， Holland 教授出版了專著 {(Adaptation in Nature and Artificial Systems))，系統(tǒng)闡述了遺傳算法的基本理論和方法，提出了遺傳算法的基本定理 —— 模式定理，為遺傳算法的 發(fā)展奠定了理論基礎(chǔ)。 上個(gè)世紀(jì) 60 年代， Michigan 大學(xué)的 J． H． Holland 教授開始認(rèn)識(shí)到生物的遺傳和自然進(jìn)化現(xiàn)象與人工自適應(yīng)系統(tǒng)的相似關(guān)系，并將生物遺傳機(jī)制引入人工自適應(yīng)系統(tǒng)的研究。同時(shí)，通過基因重組、基因變異和染色體在結(jié)構(gòu)和數(shù)目上的變異產(chǎn)生豐富多彩的變異現(xiàn)象?；蚩梢跃_的復(fù)制，也可以發(fā)生突變，并可以通過控制蛋白質(zhì)的合成而控制生物的性狀。經(jīng)過存優(yōu)去劣的自然淘汰，適應(yīng)性高的基因結(jié)構(gòu)得以保存下來。所以，每個(gè)基因產(chǎn)生的個(gè)體對(duì)環(huán)境具有某種適應(yīng)性。他認(rèn)為遺傳以密碼方式存在于細(xì)胞中，并以基因形式包含在染色體內(nèi)。 Darwin 把這種在生存斗爭(zhēng)中適者生存、不適者淘汰的過程稱為自然選擇。斗爭(zhēng)是多方面的，有種內(nèi)斗爭(zhēng)、種間斗爭(zhēng)以及生物與無機(jī)環(huán)境間的斗爭(zhēng) 。“物競(jìng)天擇，適者生存”。 Darwin 進(jìn)化論最核心的是自然選擇學(xué)說 。 第 5章 總結(jié) 福建農(nóng)林大學(xué)本科畢業(yè)論文 2 第 2 章 遺傳 算法理論概述 起源和發(fā)展 20 世紀(jì) 40年代以來，科學(xué)家努 力從生物學(xué)中尋找用于計(jì)算機(jī)科學(xué)和人工系統(tǒng)的新思維、新方法和新途徑，生命科學(xué)與工程科學(xué)相互交叉、相互滲透、相互促進(jìn)成為近代科學(xué)發(fā)展的顯著特點(diǎn)之一。 第 4章 本章論述如何用基于 遺傳 算法求解 TSP 問題。 第 2章，概要介紹了 遺傳 算法的 起源和發(fā)展、 思想 及應(yīng)用等問題，并重點(diǎn)介紹了基本 遺傳算法。 論文的組織結(jié)構(gòu) 第 1章緒論。而 遺傳 算法是一種的元啟發(fā)式優(yōu)化算法 ,基于 遺傳 算