遺傳算法研究與應(yīng)用論文

畢業(yè)設(shè)計（論文） 5 月 22 日設(shè)計論文題目： 遺傳算法研究與應(yīng)用 學(xué)生姓名： 學(xué)生學(xué)號： 專業(yè)班級： 學(xué)院名稱： 指導(dǎo)老師： 學(xué)院院長： 畢業(yè)設(shè)計 (論文 ) 第 I 頁 遺傳算法研究與應(yīng)用 摘要 遺傳算法 （ Genetic algorithms, GAs） 是借鑒生物界自然選擇和 重組 機(jī)制的隨機(jī)的搜索算法。由于它簡單易行、魯棒性強(qiáng)，應(yīng)用范圍極為廣泛，并且已在眾多領(lǐng)域得到了實際應(yīng)用 ， 引起了廣大學(xué)者和工程人員的關(guān)注。 Traveling Salesman Problem（ TSP） 問題是一個典型 NP難題，是衡量近似算法效率的主要標(biāo)準(zhǔn)，因此設(shè)計 TSP問題的近似算法具有非常重要的意義。本文討論遺傳算法 及其 對于 TSP問題的解決 方法 。 論文首先介 紹 了遺傳算法的基本概念、原理、意義及發(fā)展現(xiàn)狀。通過對遺傳算法基本理論的學(xué)習(xí)和研究，提出了 解決 TSP問題的算法，并詳細(xì)給出了算法中的編碼方案、適應(yīng)度函數(shù)、選擇算子、交叉算子、變異算子。最后用 C+語言設(shè)計并實現(xiàn)了該算法，結(jié)果表明該算法可以在較短的時間內(nèi)得到 TSP問題的近似最優(yōu)解。 關(guān)鍵詞 ： 遺傳 算法 ； TSP 問題 ； 適應(yīng)度函數(shù) ； 交叉 ； 變異 畢業(yè)設(shè)計 (論文 ) 第 II 頁 Research and Application of Genetic Algorithms Abstract Genetic algorithms (GAs) are optimization search algorithms based on the mechanics of artificial selection and genetic recombination operators. They are simple, robust and easy to implement. They have been used in many fields. For these reasons now they are the hot research field which has got many scholars attention. Traveling Salesman Problem (TSP) is a classic NP problem, which is the main standard of measuring the efficiency of approximative algorithms. So the solution of the problem has has very important significance. The paper discusses the basic genetic algorithms and their application. The essay first introduces the basic concepts, principle, procedure, significance and characteristics of genetic algorithms. By learning the basic theory of genetic algorithms one solution of TSP is given. The detailed coding scheme, fitness function, selection operator, cross operator and mutation operator of the solution are also given. Finally using C+ implement the solution. The result of the program show that the algorithm can get optimal solution of the problem quickly. Keywords: Genetic Algorithms(G A)； Traveling Salesman Problem( TSP)； fitness function； cross operator； mutation operator； 畢業(yè)設(shè)計 (論文 ) 第 III 頁 目 錄 1 緒論 . 1 1.1 課題背景 . 1 1.2 課題研究意義 . 2 1.3 國內(nèi)外研究現(xiàn)狀 . 3 1.4 論文內(nèi)容 . 5 2 遺傳算法簡介 . 6 2.1 遺傳算法基本概念 . 6 2.2 遺傳算法基本原理 . 7 2.3 遺傳算法的步驟 . 8 3 遺傳算法基本理論 . 11 3.1 模式定理 . 11 3.2 積木塊假設(shè)與欺騙問題 . 12 3.3 收斂性分析 . 13 4 旅行商問題概述 . 14 4.1 旅行商問題的定義和數(shù)學(xué)模型 . 14 4.1.1 定義 . 14 4.1.2 數(shù)學(xué)模型 . 14 4.2 旅行商問題的計算復(fù)雜性 . 15 4.3 研究旅行商問題的意義 . 16 5 遺傳算法在巡回旅行商問題中的應(yīng)用 . 18 5.1 旅行商問題的建模 . 18 5.1.1 編碼 . 18 5.1.2 適應(yīng)度函數(shù) . 18 畢業(yè)設(shè)計 (論文 ) 第 IV 頁 5.2 遺傳算法中三個算子的設(shè)計 . 19 5.2.1 選擇算子的設(shè)計 . 20 5.2.2 交叉算子的設(shè)計 . 21 5.2.3 變異算子的設(shè)計 . 25 5.3 遺傳算法求解旅行商問題的步驟 . 27 5.4 測試結(jié)果 . 27 6 結(jié)束語 . 29 致 謝 . 30 參考文獻(xiàn) : . 31 畢業(yè)設(shè)計 (論文 ) 第 1 頁 1 緒論 1.1 課題背景 遺傳算法（ Genetic Algorithm， GA），是一 類 以 達(dá)爾 文的 自 然進(jìn) 化 論與遺傳 變異 理論為基 礎(chǔ) 的 求 解復(fù) 雜 全 局 優(yōu) 化問題 的 仿 生 型 算法。它借 鑒 生 物界自 然 選擇 和 自 然遺傳機(jī)制，以概 率 論為基 礎(chǔ) 在解 空 間中進(jìn)行 隨 機(jī) 化搜索 ，最 終找到問題 的最優(yōu)解。 遺傳算法的 興起 是在 80年 代末 90年 代初 期， 但 是它的 歷史 可以 追溯到 60年 代初 期。 早期的研究大 多 以對 自 然遺傳 系統(tǒng) 的計算機(jī)模 擬 為主。 早 期遺傳算法的研究特 點(diǎn) 是 側(cè)重 于對一 些 復(fù) 雜 的 操 作的研究。其中 像自動博弈 、生 物系統(tǒng) 模 擬 、模式識別和 函數(shù) 優(yōu) 化等給 人 以深刻 的印 象 ， 但總 的說 來 ， 這 是一個 無 明確 目 標(biāo)的發(fā) 展 時期， 缺乏帶 有指導(dǎo)性的理論和計算工 具 的 開拓 。 這種 現(xiàn) 象直到 70年 代 中期 由 于 Holland和 DeJong的 創(chuàng)造 性研究成果的發(fā)表 才得 到改觀 。 1967年， Bagley在他的論文中 首次提出 了遺傳算法 1這 一術(shù) 語 ，并 討 論了遺傳算法在 自動博弈 中的應(yīng)用。 1970年， Cavicchio把 遺傳算法應(yīng)用于模式識別中。第一個 把 遺傳算法應(yīng)用于 函數(shù) 優(yōu) 化 的是 Hollstien， 1971年他在論文 計算機(jī) 控 制 系統(tǒng) 中的人工遺傳 自適 應(yīng) 方 法 中 闡述 了遺傳算法用于 數(shù)字反饋控 制的 方 法。 1975年 在遺傳算法研究的 歷史上是 十 分 重 要的一年， Holland出版 了他的 著 名 專著自 然 系統(tǒng) 和人工 系統(tǒng) 的 適配 ， 該 書 系統(tǒng) 的 闡述 了遺傳算法的基本理論和 方 法，并 提出 了對遺傳算法理論研究和發(fā) 展極 為 重 要的模式理論（ schemata theory）， 該 理論 首次 確 認(rèn) 了 結(jié) 構(gòu) 重組 遺傳 操 作對于獲得 隱 并行性的重 要性。 J. Holland教授和他的研究 小組圍繞 遺傳算法進(jìn)行研究的 宗旨 有 兩 個：一是 抽 取和解 釋自 然 系統(tǒng) 的 自適 應(yīng)過 程 ，二是 設(shè) 計 具 有 自 然 系統(tǒng) 機(jī)理的人工 系統(tǒng) 。同年， DeJong完成了他的 重 要論文 遺傳 自適 應(yīng) 系統(tǒng) 的行為分 析 ，他 把 Holland的模式理論和他的計算實驗結(jié) 合 起來 ， 這 可以 看 作遺傳算法發(fā) 展 過 程 中的一個 里程碑 ，盡 管 DeJong和 Hollstien一 樣主要 側(cè)重 于 函數(shù) 優(yōu) 化 的研究， 但 他 將選擇 、交 叉 和 變異操 作進(jìn)一步完 善 和 系統(tǒng)化 ，同時 又提出 了 諸如代溝 （ generation gap） 等新 的遺傳 操 作技術(shù)，為遺傳算法及其應(yīng)用 打 下了 堅實的基 礎(chǔ) 。進(jìn) 入 80年 代 ，遺傳算法 迎來 了 興盛 發(fā) 展 時期，理論研究和應(yīng)用研究 都 成了 十 分熱門 的 話題 。 可以認(rèn)為， DeJong的研究工作為遺傳算法及其應(yīng)用打下了堅實的基礎(chǔ)，他所 畢業(yè)設(shè)計 (論文 ) 第 2 頁 得出的許多結(jié)論，迄今仍具有普遍的指導(dǎo)意義。 1.2 課題研究意義 由于遺傳算法不受搜索空間的限制性假設(shè)的約束 , 因此不必要求諸如連續(xù)性、導(dǎo)數(shù)存在和單峰等條件，同時遺傳算法還具有以下特點(diǎn)： 1、遺傳算法是利用決策變量集的某種編碼進(jìn)行運(yùn)算，而不是直接作用在決策變量集上，通用性強(qiáng)。 2、遺傳算法能同時使用多個搜索點(diǎn)的搜索信息。傳統(tǒng)的優(yōu)化算法往往是從解空間中的一個初始解開始最優(yōu)解的迭代搜索過程。而遺傳算法從一個解的種群開始搜索，而不是從單個解開始，就像在解空間撒網(wǎng)一樣，可以對不同區(qū)域采樣，并不斷交換信息。這使得它減少了陷入局部優(yōu)解的風(fēng)險，能以較大概率找到全局最優(yōu)解。 3、遺傳算 法在尋優(yōu)過程中僅利用解的適應(yīng)度函數(shù)信息作為尋優(yōu)的依據(jù)。它對目標(biāo)函數(shù)幾乎無要求，也不涉及映射空間或函數(shù)的連續(xù)性，僅使用由目標(biāo)函數(shù)值變換來的適應(yīng)度函數(shù)值，就可確定進(jìn)一步的搜索方向和搜索范圍。而傳統(tǒng)搜索算法不僅要利用目標(biāo)函數(shù)值，而且往往需要目標(biāo)函數(shù)的導(dǎo)數(shù)值等其他一些輔助信息才能確定搜索方向。 4、遺傳算法使用概率搜索技術(shù)，以一種概率的方式來進(jìn)行搜索，從而增加了其搜索過程的靈活性。而很多傳統(tǒng)的優(yōu)化算法使用的是確定性的搜索方法，這種確定性往往可能使得搜索永遠(yuǎn)達(dá)不到最優(yōu)點(diǎn)，因而也限制了算法的應(yīng)用范圍。 5、遺傳算法具有 本質(zhì)并行性，包括內(nèi)在并行性和隱并行性。內(nèi)在并行性說明遺傳算法非常適合大規(guī)模并行運(yùn)算，而隱并行性使得遺傳算法能以較少的計算獲得較大的收益。 遺傳算法的這些特點(diǎn)使得它比傳統(tǒng)搜索方法具有更大的優(yōu)越性，適用范圍更廣并且能夠應(yīng)用于一些到目前為止人們知之甚少的困難問題領(lǐng)域。遺傳算法提供了一種求解復(fù)雜、困難優(yōu)化問題的通用框架，它不依賴于問題的具體領(lǐng)域，不要求目標(biāo)函數(shù)有明確的解析表達(dá)，對問題的種類有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于很多學(xué)科。下面是遺傳算法的一些主要應(yīng)用領(lǐng)域 6 7： 函數(shù)優(yōu)化問題。函數(shù)優(yōu)化是遺傳算法的經(jīng)典 應(yīng)用領(lǐng)域，也是對遺傳算法進(jìn)行性能評價 畢業(yè)設(shè)計 (論文 ) 第 3 頁 的常用算例。很多人構(gòu)造出了各種各樣的復(fù)雜形式的測試函數(shù)來評價遺傳算法的性能。而且對于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，用其他優(yōu)化方法較難求解，而遺傳算法卻可以方便地得到較好的結(jié)果。 組合優(yōu)化問題。隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴(kuò)大，有時在目前的計算機(jī)上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。對這類復(fù)雜問題，人們已意識到應(yīng)把主要精力放在尋求其滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。實踐證明，遺傳算法對于求解組合優(yōu)化問題非常有效。遺傳算 法已經(jīng)在求解旅行商問題、圖形劃分問題等方面得到成功的應(yīng)用。 生產(chǎn)調(diào)度問題。生產(chǎn)調(diào)度問題在很多情況下所建立起來的數(shù)學(xué)模型難以精確求解，即使經(jīng)過一些簡化之后可以求解，也會因簡化太多而使求解結(jié)果與實際相差甚遠(yuǎn)。由于可以采用字符編碼，而且不必使用恰好的目標(biāo)函數(shù)估值，遺傳算法也成為解決復(fù)雜調(diào)度問題的有效工具。在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配、虛擬企業(yè)中的伙伴選擇方面遺傳算法都得到了有效的應(yīng)用。 自動控制。在自動控制領(lǐng)域有很多與優(yōu)化相關(guān)的問題需要求解，而且這些優(yōu)化問題通常要么是通過積分表達(dá)的， 要么是寫不出明確而嚴(yán)格的解析表達(dá)式。遺傳算法在求解這類自動控制問題方面已顯示出其獨(dú)特的優(yōu)點(diǎn)。例如，用遺傳算法進(jìn)行航空控制系統(tǒng)的優(yōu)化、用遺傳算法優(yōu)化設(shè)計透平機(jī)械、設(shè)計模糊控制器等，都取得了較好的效果。 機(jī)器學(xué)習(xí)。學(xué)習(xí)能力是高級自適應(yīng)系統(tǒng)所應(yīng)具備的特征之一?；谶z傳算法的機(jī)器學(xué)習(xí)在很多方面都得到成功應(yīng)用。例如，遺傳算法被用于學(xué)習(xí)模糊控制規(guī)則、確定模糊集的隸屬函數(shù)、改進(jìn)模糊系統(tǒng)的性能；被用來調(diào)整人工神經(jīng)網(wǎng)絡(luò)的連接權(quán)及網(wǎng)絡(luò)拓?fù)鋬?yōu)化。 此外，遺傳算法還被應(yīng)用到反問題求解、機(jī)器人學(xué)習(xí)、生物計算、圖像處理、人工生命以及遺 傳編程等領(lǐng)域。 1.3 國內(nèi)外研究現(xiàn)狀 進(jìn)入 90 年代，遺傳算法迎來了興盛發(fā)展時期，無論是理論研究還是應(yīng)用研究都成了十分熱門的課題。尤其是遺傳算法的應(yīng)用研究顯得格外活躍，不但它的應(yīng)用領(lǐng)域擴(kuò)大，而且利用遺傳算法進(jìn)行優(yōu)化和規(guī)則學(xué)習(xí)的能力也顯著提高，同時產(chǎn)業(yè)應(yīng)用方面的研究也在摸索 畢業(yè)設(shè)計 (論文 ) 第 4 頁 之中。此外一些新的理論和方法在應(yīng)用研究中亦得到了迅速的發(fā)展，這些無疑均給遺傳算法增添了新的活力。遺傳算法的應(yīng)用研究已從初期的組合優(yōu)化求解擴(kuò)展到了許多更新、更工程化的應(yīng)用方面。 隨著應(yīng)用領(lǐng)域的擴(kuò)展，遺傳算法的研究出現(xiàn)了幾個引人注目的新動向：一是基于遺 傳算法的機(jī)器學(xué)習(xí)，這一新的研究課題把遺傳算法從歷來離散的搜索空間的優(yōu)化搜索算法擴(kuò)展到具有獨(dú)特的規(guī)則生成功能的嶄新的機(jī)器學(xué)習(xí)算法。這一新的學(xué)習(xí)機(jī)制對于解決人工智能中知識獲取和知識優(yōu)化精煉的瓶頸難題帶來了希望。二是遺傳算法正日益和神經(jīng)網(wǎng)絡(luò)、模糊推理以及混沌理論等其它智能計算方法相互滲透和結(jié)合，這對開拓 21 世紀(jì)中新的智能計算技術(shù)將具有重要的意義。三是并行處理的遺傳算法的研究十分活躍。這一研究不僅對遺傳算法本身的發(fā)展，而且對于新一代智能計算機(jī)體系結(jié)構(gòu)的研究都是十分重要的。四是遺傳算法和另一個稱為人工生命的嶄新研究領(lǐng) 域正不斷滲透。所謂人工生命即是用計算機(jī)模擬自然界豐富多彩的生命現(xiàn)象，其中生物的自適應(yīng)、進(jìn)化和免疫等現(xiàn)象是人工生命的重要研究對象，而遺傳算法在這方面將會發(fā)揮一定的作用，五是遺傳算法和進(jìn)化規(guī)劃（ Evolution Programming ,EP）以及進(jìn)化策略（ Evolution Strategy ,ES）等進(jìn)化計算理論日益結(jié)合。 EP 和 ES 幾乎是和遺傳算法同時獨(dú)立發(fā)展起來的，同遺傳算法一樣，它們也是模擬自然界生物進(jìn)化機(jī)制的只能計算方法，即同遺傳算法具有相同之處，也有各自的特點(diǎn)。目前，這三者之間的比較研究和彼此結(jié)合 的探討正形成熱點(diǎn)。 1991 年 D.Whitey 在他的論文中提出了基于領(lǐng)域交叉的交叉算子 （ Adjacency based crossover） ， 這個算子是特別針對用序號表示基因的個體的交叉，并將其應(yīng)用到了 TSP 問題中 ， 通過實驗對其進(jìn)行了驗證。 D.H.Ackley 等提出了隨即迭代遺傳爬山法（ Stochastic Iterated Genetic Hill-climbing， SIGH） 采用了一種復(fù)雜的概率選舉機(jī)制，此機(jī)制中由 m 個 “投票者 ”來共同決定新個體的值（ m 表示群體的大?。?。實驗結(jié)果表明， SIGH 與單點(diǎn)交叉、 均勻交叉的神經(jīng)遺傳算法相比，所測試的六個函數(shù)中有四個表現(xiàn)出更好的性能，而且總體來講，SIGH 比現(xiàn)存的許多算法在求解速度方面更有競爭力。 H.Bersini 和 G.Seront 將遺傳算法與單一方法（ simplex method）結(jié)合起來，形成了一種叫單一操作的多親交叉算子（ simplex crossover），該算子在根據(jù)兩個母體以及一個額外的個體產(chǎn)生新個體，事實上他的交叉結(jié)果與對三個個體用選舉交叉產(chǎn)生的結(jié)果一致。同時，文獻(xiàn)還將三者交叉算子與點(diǎn)交叉、均勻 畢業(yè)設(shè)計 (論文 ) 第 5 頁 交叉做了比較，結(jié)果表明，三者交叉算子比其余兩個有更好的性能。 國內(nèi)也有不少的專家和學(xué)者對遺傳算法的交叉算子進(jìn)行改進(jìn)。 2002 年，戴曉明等應(yīng)用多種群遺傳并行進(jìn)化的思想，對不同種群基于不同的遺傳策略，如變異概率，不同的變異算子等來搜索變量空間，并利用種群間遷移算子來進(jìn)行遺傳信息交流，以解決經(jīng)典遺傳算法的收斂到局部最優(yōu)值問題 2004 年，趙宏立等針對簡單遺傳算法在較大規(guī)模組合優(yōu)化問題上搜索效率不高的現(xiàn)象，提出了一種用基因塊編碼的并行遺傳算法（ Building-block Coded Parallel GA， BCPGA）。該方法以粗粒度并行遺傳算法為基本框架，在染色體 群體中識別出可能的基因塊，然后用基因塊作為新的基因單位對染色體重新編碼，產(chǎn)生長度較短的染色體，在用重新編碼的染色體群體作為下一輪以相同方式演化的初始群體 。 2005 年，江雷等針對并行遺傳算法求解 TSP 問題 ,探討了使用彈性策略來維持群體的多樣性 ,使得算法跨過局部收斂的障礙 ,向全局最優(yōu)解方向進(jìn)化 。 1.4 論文內(nèi)容 本文內(nèi)容安排如下： 第一章：緒論。 介紹本課題的選題背景和研究現(xiàn)狀以及文章結(jié)構(gòu)。 第二章：簡要介紹了遺傳算法的基本概念、原理、實現(xiàn)步驟。 第三章：敘述了遺傳算法的主要理論：模式定理、積木塊假設(shè)，以及遺傳算法的收 斂性的簡單說明。 第四章：就在旅行推銷商問題做了簡要介紹，并對旅行推銷商問題的數(shù)學(xué)模型，計算的復(fù)雜度和求解該問題的意義進(jìn)行簡單概要。 第五章：提出了遺傳算法求解旅行商問題的一種方式， 并詳細(xì)給出了算法中的編碼方案、適應(yīng)度函數(shù)、選擇算子、交叉算子、變異算子及部分源碼。 第六章：結(jié)束語。 文章的最后是參考致謝和參考文獻(xiàn)。 畢業(yè)設(shè)計 (論文 ) 第 6 頁 2 遺傳算法簡介 2.1 遺傳算法基本概念 遺傳算法的基本 思想 是基于 Darwin進(jìn) 化 論和 Mendel的遺傳學(xué)說的。 Darwin進(jìn) 化 論最 重 要的是 適者 生存原理。它 認(rèn) 為 每 一 物種 在發(fā) 展 中 越 來 越 適 應(yīng) 環(huán)境 。物 種 每 個個 體 的基本特 征由 后 代 所 繼 承， 但 后 代又 會 產(chǎn)生一 些異 于 父 代 的 新變化 。在 環(huán)境變化 時， 只 有 那 些能適 應(yīng) 環(huán)境 的個 體 特 征才能 保留下 來 。 Mendel遺傳學(xué)說最 重 要的是基 因 遺傳原理。它 認(rèn) 為遺傳以密 碼方 式存在 細(xì)胞 中，并以基 因 形 式包含在 染色 體 內(nèi)。 每 個基 因 有特 殊 的位 置 并 控 制 某 種 特 殊 性 質(zhì) ；所以， 每 個基 因產(chǎn)生的個 體 對 環(huán)境具 有 某 種適 應(yīng)性?；?因突 變 和基 因 雜 交可產(chǎn)生 更 適 應(yīng)于 環(huán)境 的后 代 。經(jīng)過存優(yōu) 去劣 的 自 然 淘汰 ， 適 應(yīng)性 高 的基 因 結(jié) 構(gòu)得以保存下 來 。 由 于遺傳算法是 由 進(jìn) 化 論和遺傳學(xué)機(jī)理產(chǎn)生的 直 接 搜索 優(yōu) 化方 法，所以在 這 個算法中要用 到 各 種 進(jìn) 化 和遺傳學(xué)的概念。 這些 概念 如 下： 1.串 它是個 體 的 形 式，在算法中為二進(jìn)制 串 ，并 且 對應(yīng)于遺傳學(xué)中的 染色 體 。 2.種群 個 體 的 集 合 稱 為 群體 ， 串 是 種群 中的 元素 3.種群 大 小 在 種群 中個 體 的 數(shù)量 稱 為 種群 的大 小 。 4.基 因 基 因 是 串 中的 元素 ，基 因 用于表示個 體 的特 征 。 例如 有一個 串 S 1011， 則 其中的 1011這 4個 元素 分別 稱 為基 因 。 5.基 因 位 置 一個基 因 在 串 中的位 置稱 為基 因 位 置 ，有時也簡 稱 基 因 位?；?因 位 置 在 串 中 由 左向右計算， 例如 在 串 S 1101中， 0的基 因 位 置 是 3。基 因 位 置 對應(yīng)于遺傳學(xué)中的 地點(diǎn) 。 畢業(yè)設(shè)計 (論文 ) 第 7 頁 6.基 因 特 征值 在用 串 表示 整 數(shù) 時，基 因 的特 征值 與二進(jìn)制 數(shù) 的權(quán)一致； 例如 在 串 S=1011中，基 因 位置 3中的 1，它的基 因 特 征值 為 2；基 因 位 置 1中的 1，它的基 因 特 征值 為 8。 7.串 結(jié) 構(gòu) 空 間 在 串 中，基 因 任意 組 合所構(gòu)成的 串 的 集 合?；?因 操 作是在 結(jié) 構(gòu) 空 間中進(jìn)行的。 串 結(jié) 構(gòu)空 間對應(yīng)于遺傳學(xué)中的基 因 型 的 集 合。 8.參數(shù)空 間 sp這 是 串 空 間在 物 理 系統(tǒng) 中的 映射 ，它對應(yīng)于遺傳學(xué)中的表現(xiàn) 型 的 集 合。 九 、 適 應(yīng) 度 表示 某 一個 體 對于 環(huán)境 的 適 應(yīng) 程度 。 遺傳算法 還 有一 些 其它的概念， 這些 概念在 介 紹 遺傳算法的原理和 執(zhí) 行過 程 時， 再 進(jìn)行說明。 2.2 遺傳算法基本原理 遺傳算法 GA把問題 的解表示成 “ 染色 體 ” ，在算法中也 就 是二進(jìn)制 編碼 的 串 。并 且 ，在 執(zhí) 行遺傳算法之 前 ， 給出 一 群 “ 染色 體 ” ，也 就 是 假 設(shè) 解。然后， 把這些 假 設(shè) 解 置 于 問題 的 “ 環(huán)境 ” 中，并 按 適者 生存的原 則 ， 從 中 選擇出較適 應(yīng) 環(huán)境 的 “ 染色 體 ” 進(jìn)行復(fù)制，再通 過交 叉 ， 變異 過 程 產(chǎn)生 更 適 應(yīng) 環(huán)境 的 新 一 代 “ 染色 體 ” 群 。 這樣 ，一 代 一 代 的進(jìn) 化 ，最后 就會 收斂到 最 適 應(yīng) 環(huán)境 的一個 “ 染色 體 ” 上 ，它 就 是 問題 的最優(yōu)解。 很 明 顯 ，遺傳算法是一 種 最優(yōu) 化方 法，它 通 過進(jìn) 化 和遺傳機(jī)理， 從 給出 的原 始 解 群 中 ，不 斷 進(jìn) 化 產(chǎn)生 新 的解，最后 收斂到 一個特定的 串 bi處，即 求出 最優(yōu)解。 長 度 為 L的 n個二進(jìn)制 串 bi(i 1， 2， ， n)組 成了遺傳算法的 初 始 解 群 ，也 稱 為 初 始 群體 。在 每 個 串 中， 每 個二進(jìn)制位 就 是個 體 染色 體 的基 因 。 根據(jù) 進(jìn) 化 術(shù) 語 ，對 群體 執(zhí) 行的 操作有 三種 ： 1 選擇 這 是 從 群體 中 選擇出較適 應(yīng) 環(huán)境 的個 體 。 這些選 中的個 體 用于 繁殖 下一 代 。 故 有時也稱 這 一 操 作為 再 生。 由 于在 選擇 用于 繁殖 下一 代 的個 體 時，是 根據(jù) 個 體 對 環(huán)境 的 適 應(yīng) 度來 畢業(yè)設(shè)計 (論文 ) 第 8 頁 決 定其 繁殖 量 的， 故 而有時也 稱 為 非 均 勻再 生。 2 交 叉 這 是在 選 中用于 繁殖 下一 代 的個 體 中，對 兩 個不 同的個 體 的相同位 置 的基 因 進(jìn)行交 換 ，從 而產(chǎn)生 新 的個 體 。交 叉 算子示意 如 圖 1.1。 圖 1.1 交 叉 算子示意 圖 3 變異 這 是在 選 中的個 體 中，對個 體 中的 某 些 基 因按 變異 概 率 P 執(zhí) 行 異 向轉(zhuǎn) 化 。在 串 bi中，如 果 某 位基 因 為 1，產(chǎn)生 變異 時 就 是 把 它 變 成 0； 反之亦然 。 2.3 遺傳算法的步驟 1 初 始 化 選擇 一個 群體 ，即 選擇 一個 串 或個 體 的 集 合 bi， i=1， 2， .n。 這 個 初 始 的 群體 也 就 是問題 假 設(shè) 解的 集 合。一 般 取 n 30-160。 通 常 以 隨 機(jī) 方 法產(chǎn)生 串 或個 體 的 集 合 bi,i 1， 2， .n。 問題 的最優(yōu)解 將 通 過 這些初 始假 設(shè) 解 進(jìn) 化 而 求出 。 畢業(yè)設(shè)計 (論文 ) 第 9 頁 2 選擇 根據(jù)適者 生存原 則 選擇 下一 代 的個 體 。在 選擇 時，以 適 應(yīng) 度 為 選擇 原 則 。 適 應(yīng) 度 準(zhǔn)則體 現(xiàn)了 適者 生存，不 適 應(yīng) 者 淘汰 的 自 然法 則 。 給出目 標(biāo) 函數(shù) f， 則 f(bi)稱 為個 體 bi的 適 應(yīng) 度 。以公式（ 1-1） P選 中 bin)()(1njbjfbif (1-1) 為 選 中 bi為下一 代 個 體 的 次數(shù) 。 顯 然 。從 上 式可知： (1)適 應(yīng) 度較高 的個 體 ， 繁殖 下一 代 的 數(shù)目較多 。 (2)適 應(yīng) 度較小 的個 體 ， 繁殖 下一 代 的 數(shù)目較 少 ， 甚至被淘汰 。 這樣 ， 就 產(chǎn)生了對 環(huán)境適 應(yīng) 能力較 強(qiáng) 的后 代 。 從 問題求 解 角 度來 講 ， 就 是 選擇出 和最優(yōu)解 較 接近 的中間解。 3 交 叉 對于 選 中用于 繁殖 下一 代 的個 體 ， 隨 機(jī) 地選擇兩 個個 體 的相同位 置 ， 按 交 叉 概 率 P。在 選 中的位 置 實行交 換 。 這 個過 程反 映 了 隨 機(jī) 信息 交 換 ； 目 的在于產(chǎn)生 新 的基 因 組 合，也即產(chǎn)生 新 的個 體 。交 叉 時，可實行單 點(diǎn) 交 叉 或 多點(diǎn) 交 叉 。 例如 有個 體 S1=100101 S2=010111 選擇 它 們 的 左邊 3位進(jìn)行交 叉操 作， 則 有 S1=010101 S2=100111 一 般 而言，交 叉 概 率 P。取 值 為 0.25 0.75。 4 變異 根據(jù) 生 物 遺傳中基 因 變異 的原理，以 變異 概 率 Pm對 某 些 個 體 的 某 些 位 執(zhí) 行 變異 。在 變 畢業(yè)設(shè)計 (論文 ) 第 10 頁 異 時，對 執(zhí) 行 變異 的 串 的對應(yīng)位 求反 ，即 把 1變 為 0， 把 0變 為 1。 變異 概 率 Pm與生 物變異極小 的 情況 一致，所以， Pm的取 值較小 ，一 般 取 0.01-0.2。 例如 有個 體 S 101011。 對其的第 1， 4位 置 的基 因 進(jìn)行 變異 ， 則 有 S=001111 單 靠 變異 不 能 在 求 解中得 到好 處。 但 是，它 能 保證算法過 程 不 會 產(chǎn)生 無 法進(jìn) 化 的單一群體 。 因 為 當(dāng) 所有的個 體 一 樣 時，交 叉 是 無 法產(chǎn)生 新 的個 體 的， 這 時 只 能 靠 變異 產(chǎn)生 新 的個 體 。也 就 是說， 變異 增 加了全 局 優(yōu) 化 的特 質(zhì) 。 5 全 局 最優(yōu) 收斂 當(dāng) 最優(yōu)個 體 的 適 應(yīng) 度達(dá)到給 定的 閥 值 ，或 者 最優(yōu)個 體 的 適 應(yīng) 度 和 群體適 應(yīng) 度 不 再 上 升時， 則 算法的 迭 代 過 程收斂 、算法 結(jié)束 。 否則 ，用經(jīng)過 選擇 、交 叉 、 變異 所得 到 的 新 一 代群體 取 代上 一 代群體 ，并 返回 到 第 2步即 選擇操 作處 繼續(xù)循 環(huán) 執(zhí) 行。 圖 1.2中表示了遺傳算法的 執(zhí) 行過 程 圖 1.2 遺傳算法原理 畢業(yè)設(shè)計 (論文 ) 第 11 頁 3 遺傳算法基本理論 3.1 模式定理 模式定理是由 Holland 在 1971 年提出的，它是 GA 的基本定理。它將 GA的運(yùn)算過程理解為模式運(yùn)算過程，并從模式運(yùn)算的角度解釋 GA 的性能特點(diǎn)。模式是 描述字符串集的模板，反映字符串集中串的某些位置上存在的相似性。在本節(jié)的敘述中，僅就二進(jìn)制編碼的情況進(jìn)行討論。 【定義 2.1】基于三值字符集 0,1,*所產(chǎn)生的能描述具有某些結(jié)構(gòu)相似性的 0、 1 字符串集的字符串稱作模式。 例如，模式 S = 01*0*描述了所有在位置 1 和位置 4 上為 0，在位置 2 上為 1的字符串，該模式描述的字符串集合為 01000， 01001， 01100， 01101。 也就是： S = 01*0* = 01000， 01001， 01100， 01101 事實上，模式的概念使得我們可以簡明地 描述具有相似結(jié)構(gòu)特點(diǎn)的個體編碼字符串。 在引入模式的概念后，遺傳算法的本質(zhì)就是對模式所進(jìn)行的一系列運(yùn)算，遺傳運(yùn)算過程中的個體通過模式聯(lián)系起來。通過這些遺傳運(yùn)算，一些比較差的模式逐漸被淘汰，而一些較好的模式逐步被遺傳和進(jìn)化。 在進(jìn)行遺傳算法的理論分析時，往往需要定量地估計模式運(yùn)算。因此，有必要引入以下兩個概念：模式階和模式定義距。 【定義 2.2】模式 H 中確定位置的個數(shù)稱為模式的模式階 (Schemata Order)，記作 O(H)。模式 H 中第一個確定位置和最后一個確定位置之間的距離稱為模式的定義距 (Schemata Defining Length)，記作 (H)。 根據(jù)定義 2.2， O(101*0) = 4， (101*0) = 4； O(0*1*) = 2， (0*1*) = 3。而對于 H = *1、 H = *0*之類的模式，由于他們只有一個確定位置，所以我們規(guī)定它們的定義距為 0，如 (*0*) = 0。 當(dāng)字符串的長度確定時，模式的階數(shù)越高，與該模式相匹配的樣本數(shù)目就越少，該模式的確定性也就越高。而模式的定義距越大，則在遺傳運(yùn)算中，該模式被遺傳運(yùn)算破壞的 畢業(yè)設(shè)計 (論文 ) 第 12 頁 概率越大，生存概率越小。 【定 理 2.1】模式定理在遺傳算子選擇、交叉和變異的作用下，具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式在子代中將得以指數(shù)級增長。 模式定理可以用數(shù)學(xué)形式表示為： )()1/()()/)(),()1,( mc pHolHpfHftHmtHm （ 2 1） 其中， H 表示一個模式， m(H,t) 表示在第 t 代種群中存在的模式 H 中串的個數(shù)。 f (H) 表示在第 t 代種群中模式 H 串的平均適應(yīng)度， f 表示第 t 代種群的平均適應(yīng)度， l 表示串的長度 , pc是串之間發(fā)生交叉的概率， pm是一個串發(fā)生變異的概率， (H) 表示模式 H 的定義距 , o(H) 表示模式 H 的階。 模式定理保證了遺傳優(yōu)化過程中較優(yōu)解的樣本呈指數(shù)級增長，在一定意義上可以解釋基本遺傳算法的優(yōu)化本質(zhì)，同時也給遺傳算法的應(yīng)用提供了指導(dǎo)作用。 3.2 積木塊假設(shè)與欺騙問題 模式定理說明，低階、短定義距、平均適應(yīng)度高的模式被交叉切斷的可能性低，隨著世代交替其數(shù)量將增加。這種類型的模式稱為積木塊。 【定義 2.3】具 有低階、短定義距以及高適應(yīng)度的模式稱作積木塊。 【假設(shè) 2.1】積木塊假設(shè)積木塊在遺傳算子的作用下相互結(jié)合，能生成高階、長定義距、高平均適應(yīng)度的模式，并最終生成全局最優(yōu)解。 模式定理說明了積木塊的樣本數(shù)呈指數(shù)級增長，亦即說明了用遺傳算法尋求最優(yōu)樣本的可能性；而積木塊假設(shè)說明了用遺傳算法求解各種問題的基本思想，即通過積木塊之間的相互拼接能夠產(chǎn)生出問題更好的解，表明遺傳算法具有全局尋優(yōu)能力，能夠?qū)で蟮阶顑?yōu)樣本。到目前為止，上述假設(shè)并未得到完整而嚴(yán)密的數(shù)學(xué)證明，但大量的實踐對這一假設(shè)提供了強(qiáng)有力的支持。 如果一個問 題的編碼滿足積木塊假設(shè)，那么用遺傳算法求解的效率較高，否則用遺傳算法求解的效率較低。應(yīng)用實踐表明，存在一類用遺傳算法難以求解的問題，稱為 “GA-難 ”問題。屬于 “GA-難 ”的問題一般包括有孤立的最優(yōu)點(diǎn)，在搜索過程中，低階積木塊錯誤地引導(dǎo)搜索過程，不能發(fā)現(xiàn)高階積木塊，通過欺騙遺傳算法，使其進(jìn)化過程偏離最優(yōu)解，最 畢業(yè)設(shè)計 (論文 ) 第 13 頁 終使遺傳算法發(fā)散，這種現(xiàn)象稱為欺騙。實際上，目前尚未沒有解決這類問題的較好的方法，也無法判斷一個問題包含欺騙的多少與問題相對于遺傳算法的難易程度。不過，現(xiàn)實中遇到的各種應(yīng)用問題中，遺傳算法大部分是適用的。 3.3 收斂性分析 模式定理雖然指出了具有優(yōu)良結(jié)構(gòu)的模式在算法的進(jìn)化過程中的演變趨勢，但是，它并未回答了遺傳算法最終收斂于最優(yōu)解的概率為多少。積木塊假設(shè)雖然指明了遺傳算法能夠收斂于全局最優(yōu)解，但是僅僅是通過大量的應(yīng)用數(shù)據(jù)來證明其有效性，還沒有完整而嚴(yán)密的數(shù)學(xué)證明。利用馬爾可夫鏈對遺傳算法的分析嚴(yán)格論證了遺傳算法收斂性方面的一些重要性質(zhì)，有力地支撐了遺傳算法的理論基礎(chǔ)。下面是由馬爾可夫鏈推導(dǎo)出來的一些結(jié)論，具體證明可以參考文獻(xiàn) 8。 【定理 2.3】基本遺傳算法收斂于最優(yōu)解的概率小于 1。 【定理 2.4】使用保留最佳 個體策略的遺傳算法夠收斂于最優(yōu)解的概率為 1。 通過上述定理可以看出，基本遺傳算法收斂于最優(yōu)解的概率小于 1，而通過對基本遺傳算法進(jìn)行改進(jìn)，修正它的選擇策略，就能使算法一定收斂于最優(yōu)解。這兩個定理不僅在理論上是模式定理和積木塊假設(shè)的有力補(bǔ)充，更為實際的應(yīng)用中的算法收斂提供了保證。 畢業(yè)設(shè)計 (論文 ) 第 14 頁 4 旅行商問題概述 4.1 旅行商問題的定義和數(shù)學(xué)模型 4.1.1 定義 旅行商問題是組合數(shù)學(xué)中一個古老而又困難的問題，它易于描述但至今尚未徹底解決，現(xiàn)己歸入所謂的 NP完全問題類，經(jīng)典提法為 : 有一貨物推銷員要去若干個城市推銷貨物，從城市 1出發(fā)，經(jīng)其余各 城市一次，然后回到城市 1，問選擇怎樣的行走路線，才能使總行程最短 (各城市間距離為己知 )。 該問題在圖論的意義下就是所謂的最小 Hamilton圈問題，由于在許多領(lǐng)域中都有著廣泛的應(yīng)用，因而尋找其實際而有效的算法就顯得頗為重要了。遺憾的是，計算復(fù)雜性理論給予我們的結(jié)論卻是，這種可能性尚屬未知。 若設(shè)城市數(shù)目為 n時，那么組合路徑數(shù)則為 (n-1)!。很顯然，當(dāng)城市數(shù)目不多時要找到最短距離的路線并不難，但隨著城市數(shù)目的不斷增大，組合路線數(shù)將呈指數(shù)級數(shù)規(guī)律急劇增長，以至達(dá)到無法計算的地步，這就是所謂的“組合爆炸問題 ” 。 假設(shè)現(xiàn)在城市的數(shù)目增為 20個，組合路徑數(shù)則為 (20-1)!，如此龐大的組合數(shù)目，若計算機(jī)以每秒檢索 1000萬條路線的速度計算，也需要花上 386年的時間。 盡管現(xiàn)在計算機(jī)的計算速度大大提高，而且己有一些指數(shù)級的算法可精確地求解旅行商問題，但隨著它們在大規(guī)模問題上的組合爆炸，人們退而求其次，轉(zhuǎn)向?qū)ふ医扑惴ɑ騿l(fā)式算法，經(jīng)過幾十年的努力，取得了一定的進(jìn)展。 4.1.2 數(shù)學(xué)模型 設(shè) G=(V, E)為賦權(quán)圖， V=l ,2,. .n為頂點(diǎn)集， E為邊集，各頂點(diǎn)間距離為 cij。 已知 (cij 0, cij= ,i,j V )，并設(shè) xij=，其它）在最優(yōu)路線上，邊（0ji1 （ 3 1） 畢業(yè)設(shè)計 (論文 ) 第 15 頁 則旅行商問題的數(shù)學(xué)模型可寫成如下的線性規(guī)劃形式： MinZ ji ijc xijs.t VjixVKKxVjxVixijSjiijjiijijji,1,0,1,1,1,這里， K 為 V 的所有非空子集， K 為集合 K 中所含圖 G 的頂點(diǎn)個數(shù)。前兩個約束意味著對每個頂點(diǎn)而言，僅有一條邊進(jìn)出，后一約束則保證了沒有任何子回路解的產(chǎn)生。于是，滿足上述約束的解構(gòu)成了一條 Hamilton 回路。除此之外，模型還有其它一些等價的書寫形式 。 4.2 旅行商問題的計算復(fù)雜性 一般的，我們定義一個組合優(yōu)化問題 : 設(shè) RSf : ，其中 S為一個有限集， f為映射函數(shù)，對每個 Sx 產(chǎn)生唯一的實數(shù) f(x)，則最大 (小 )化問題即找一個 Sx ，使得對于任何其它 Sx 有 )()()( xfxf 。 此組合優(yōu)化問題的一個基本算法是 :對于每個 Sx ，求 f(x)的值，挑選 x ，使對于所有的 Sx ， )()()( xfxf 。 這就是窮舉搜索法，它在理論上可以解決任何有限的組合最優(yōu)化問題。 但對于 n個城市的 TSP，可能的回路數(shù)有2 )!1( n條，計算每一條路徑需求 n個距離之和，故計算量將正比于2!n。表 4 1顯示了運(yùn)算速度 510 億次 /秒的 CrayXT3巨型計算機(jī)按窮舉搜索法計算 TSP所需的時間，這里還未考慮算法所需的巨大存貯空間。由此足見 TSP時空復(fù)雜度之高。 畢業(yè)設(shè)計 (論文 ) 第 16 頁 表 4.1 4.3 研究旅行商問題的意義 旅行商問題是 一個 NP完全問題，目前任何 NP完全問題都不能用任何已知的多項式算法求解；若任何一個 NP完全問題有多項式算法，則一切 NP完全問題都有多項式算法。 由此，不少人猜測任何 NP完全問題都沒有多項式算法，但至今無人證明。事實上，人們普遍認(rèn)為，不發(fā)展全新的數(shù)學(xué)技術(shù)就證明不了這個猜想。這樣一種認(rèn)識的實際意義就在于許多人相信，難計算是這樣一類問題的固有性質(zhì)，因此它們不可能用有效算法求解，而所有能精確求解 NP完全問題的算法，在最壞情況下都需要指數(shù)級的時間。 另外，旅行商問題是一個理想化的問題，大多數(shù)對于此問題的研究都不是為了 直接的實際應(yīng)用，但這些研究可以經(jīng)轉(zhuǎn)化后用于許多現(xiàn)實的組合優(yōu)化問題。很自然地可以想到，旅行商問題的成果可以應(yīng)用于運(yùn)輸和物流問題。旅行商問題最早的應(yīng)用是在上個世紀(jì)的四十年代，應(yīng)用于校車路線的優(yōu)化?，F(xiàn)在，旅行商問題在越來越多的領(lǐng)域得到應(yīng)用。 1電路板鉆孔進(jìn)度的安排。在這個應(yīng)用當(dāng)中，電路板上的孔代表旅行商問題中的城 市，鉆頭從一個鉆孔移動到另一個鉆孔。尋找最短路徑變成了尋找最省時的鉆頭移動時間。盡管目前鉆機(jī)的工藝技術(shù)發(fā)展很塊，但鉆頭的移動時間仍然是一個令人頭疼的問題。 2基因測序。 Concorde是一種求解旅行 商問題的程序。美國國家衛(wèi)生機(jī)構(gòu)的研究人 員利用這一程序來進(jìn)行基因測序。在這一應(yīng)用中，局部的基區(qū)圖譜作為城市，城市與城市的距離代表某張圖譜與其它圖譜相連的可能性。研究人員試圖尋找一種可能性最高的連接方城市數(shù) N 回路數(shù)2 )!1( n加法量2!n搜索時間 5 12 60 12106 秒 10 5108144.1 6108144.1 7108144.1 秒 20 161008.6 181022.1 51022.1 秒 40 461002.1 471008.4 271032.1 年 100 155106.4 157106.4 1361048.1 年 200 371100.5 374100.1 3561022.3 年 畢業(yè)設(shè)計 (論文 ) 第 17 頁 式把這些局部的圖譜合成為整張基因圖譜。 3半導(dǎo)體的線路設(shè)計。一家半導(dǎo)體生產(chǎn)廠家應(yīng)用 Concorde程序來優(yōu)化半導(dǎo)體的線路 設(shè)計，這樣可以節(jié)省刻制半導(dǎo)體的時間，也能減少半導(dǎo)體電路消耗的能量。 4光纜的線路設(shè)計。貝爾電話公司利用 Concorde程序來設(shè)計光纜的鋪設(shè)線路，同樣 的方法也應(yīng)用于電話和電力線路的鋪設(shè)當(dāng)中 。 5在機(jī)器人控制等其它方面，旅行商問題也有許多應(yīng)用。 畢業(yè)設(shè)計 (論文 ) 第 18 頁 5 遺傳算法在巡回旅行商問題中的應(yīng)用 5.1 旅行商問題的建模 5.1.1 編碼 在遺傳算法中，染色體通常采用簡單的二進(jìn)制串編碼，但這種簡單的編碼方式不能較好的適用于 TSP和其它組合優(yōu)化問題。 TSP常用的編碼表達(dá)方式主要有鄰接表達(dá)、矩陣表達(dá)、邊表達(dá)、隨機(jī)鍵表達(dá)和序表達(dá)等。其中，序表達(dá)和隨機(jī)鍵表達(dá)不僅適用于 TSP，也適用于其它組合優(yōu)化問題。 本文使用序表達(dá)形式。序表達(dá)是 TSP問題的最自然的表達(dá)，其中城市是按訪問的順序排列的。例如，對于 9個城市的 TSP:3 2 5 4 7 1 6 9 8可簡單表示為向量 3 2 5 4 7 1 6 9 8，表示從城市 3出發(fā)依次經(jīng)過城市 2， 5， 4， 7， 1， 6， 9， 8然后返回城市 3的一條路徑。序表達(dá)方式滿足完全無向圖 TSP問題的約束條件。保證了每個城市經(jīng)過且只經(jīng)過一次，并且保證在任何一個城市子集中不形成回路 . 5.1.2 適應(yīng)度函數(shù) 適應(yīng)度是生物學(xué)家在研究自然界中生物的遺傳與進(jìn)化現(xiàn)象時用以度量某個物種對其生存環(huán)境的適應(yīng)程度。在遺傳算法中適應(yīng)度用來度量個體作為全局最優(yōu)解的可接受程度，它是模擬進(jìn)化算法評價和選擇個體的度量依據(jù)。適應(yīng)度的取值與適應(yīng)度函數(shù)成正比。適 應(yīng)度函數(shù)的確定通常反映應(yīng)用者對個體的評價標(biāo)準(zhǔn)和搜索機(jī)理 。 適應(yīng)度函數(shù)是遺傳進(jìn)化操作的基礎(chǔ)，它的構(gòu)造是遺傳算法的關(guān)鍵 。 合理的適應(yīng)度函數(shù)能引導(dǎo)搜索朝最優(yōu)化方向進(jìn)行 。 本文構(gòu)造基于序的適應(yīng)度函數(shù) 。 它的特點(diǎn)是個體被選擇的概率與目標(biāo)函數(shù)的具體值無關(guān) 。 將種群中的所有個體按其目標(biāo)函數(shù)值的大小降序排列，設(shè)參數(shù) )1,0( ， 定義基于序的適應(yīng)度函數(shù) e 1)1()( iiv a l x i 1， 2， 3， psize（ 3 2） 式中： xi 種群排序后第 i個個體； 畢業(yè)設(shè)計 (論文 ) 第 19 頁 psize 種群中個體總數(shù)。 程序源碼： void CreateFitnessofPop( ) std:vector:iterator iter_router； double alpha = EVAL_BASE； std:vector vecSort； for( iter_router=vecPop.begin()；iter_router!=vecPop.end()；iter_router+ ) vecSort.push_back( iter_router-m_fTotalDistance )； iter_router-m_fFitness = -100.0； std:sort( vecSort.begin(), vecSort.end() )； std:vector:iterator iter_sort； int nIndex = 0； for( iter_sort=vecSort.begin()；iter_sort!=vecSort.end()；iter_sort+ ) for( iter_router=vecPop.begin()； iter_router!=vecPop.end()；iter_router+ ) if( fabs(iter_router-m_fTotalDistance-(*iter_sort) m_fFitness m_fFitness = alpha*pow(1-alpha,(double)nIndex)； nIndex+； 5.2 遺傳算法中三個算子的設(shè)計 畢業(yè)設(shè)計 (論文 ) 第 20 頁 5.2.1 選擇算子的設(shè)計 按照某種選擇策略從群體中選擇出若干個體進(jìn)入交配池。交配池中的個體通過遺傳算子的作用產(chǎn)生新一代群體。選擇策略應(yīng)遵守的基本原則是 :適應(yīng)度值越大的個體被選中的概率應(yīng)該越大。即選擇策略應(yīng)遵循自然界 “優(yōu)勝劣汰、適者生存”的自然選擇規(guī)律。從群體中選擇優(yōu)勝的個體，淘汰劣質(zhì)個體的操作叫選擇。選擇算子有時又稱為再生算子。選擇的目的是把優(yōu)化的個體 (或解 )直接遺傳到下一代或通過交叉產(chǎn)生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應(yīng)度評估基礎(chǔ)上的。在遺傳算法中，目前常用的選擇機(jī)制有以下幾種 :適應(yīng)度比例方法、最佳個體保存方法、期望值方法、排序選擇機(jī)制、聯(lián)賽選擇機(jī)制。 本文適應(yīng)度比例方法是目前遺傳算法中最基本也是最常用的選擇方法。它也叫賭輪或蒙特卡羅 (Monte Carlo)選擇。在該方法中，各個個體的選擇概 率和其適應(yīng)度值成比例。 程序源碼如下： void SelectPop() /群體競爭 輪盤賭選擇 std:vector vecRoll； std:vector vecSelPop； int nRollNumber, nRollRange； int nPopSize = vecPop.size()； int i, j； for( i=0；inPopSize；i+ ) double fsumfitness = 0.0； for( int j=0；j=i；j+ ) fsumfitness += vecPopj.m_fFitness*10000； vecRoll.push_back( fsumfitness )； nRollRange = (int)fsumfitness； 畢業(yè)設(shè)計 (論文 ) 第 21 頁 for( i=0；inPopSize；i+ ) nRollNumber = rand()%nRollRange； for( j=0；jnPopSize；j+ ) if( nRollNumber ncrossoverbegin ) break； else if( ncrossoverend ncrossoverbegin ) std:swap( ncrossoverbegin, ncrossoverend )； 畢業(yè)設(shè)計 (論文 ) 第 23 頁 break； for( int i=ncrossoverbegin；i:iterator iter_father, iter_son； bool hasCity = false； int naddbegin = 0； for( iter_father=vecPopnFatherB.m_CityRout