【正文】 化、列表尋優(yōu) (TABU)法、模擬退火法等 )。遺傳算法就其本質來說 ， 主要是解決復雜問題的一種魯棒性強的啟發(fā)式隨機搜索算法 。 因此遺傳算法在 TSP問題求解方面的應用研究 ， 對于構 造合適的遺傳算法框架、建立有效的遺傳操作以及有效地解決 TSP問題等有著多方面的重要意義 。 第一章 基本遺傳算法 遺傳算法的產(chǎn)生及發(fā)展 最早美國 Ｍ ichigan(密執(zhí)安大學 )的 Holland教授提出，起源于 60年代對自然和人工自適應系統(tǒng)的研究。 70年代 De Jong基于遺傳算法的思想在計算機上進行了大量純數(shù)值函數(shù)優(yōu)化計算實驗。在一系列研究工作的基礎上 80年代 Goldberg進行總結歸納，形成了遺傳算的基本框架。 主要以一些關鍵人物所做出的主要貢獻見證了遺傳算法的發(fā)展進程 : 1 60年代提出在研究和設計人工自適應系統(tǒng)時 ,可以借鑒生物遺傳的機制； 70年代初提出了遺傳算法的基本定理－模式定理 (Schema Theorem)，從而奠定了遺傳算法的理論基礎； 80年代實現(xiàn)了第一個基于遺傳算法的機器學系統(tǒng)－分類器系統(tǒng) (Classifier Systems),開創(chuàng)了基于遺傳算法的機器學習的新概念。 2 1967年在其博士論文中首次提出了：“遺傳算法”一詞，發(fā)展了復制、交叉、變異、顯性、倒位等遺傳算子，創(chuàng)立了自適應遺傳算法的概念。 3 Jong 1975年在其博士論文中結合模式定理進行了大量的純數(shù)值函數(shù)優(yōu)化計算實驗，樹立了遺傳算法的工作框架，定義了評價遺傳算法性能的在線指標和離線指標 。 4 1989年出版了專著《搜索、優(yōu)化和機器學習中的遺傳算法 (Geic Algorithms in Search， Optimization and Machine Learning)》，系統(tǒng)總結了遺傳算法的主要研究成果，全面而完整的論述了遺傳算法的基本原理及其應用。 5 1991年 編輯出版了《遺傳算法手冊 (Handbook of Geic Algorithms)》書中包括遺傳算法在科學計算、工程技術和社會經(jīng)濟中的大量應用實例。 6 1992年將遺傳算法應用于計算機程序的優(yōu)化設計及自動生成，提出了遺傳編程 (Geic Programming) 的概念，并成功的將其提出的遺傳編程應用于人工智能、機器學習符號處理等方面。 基本原理 遺傳算法是一種借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法 ， 由美國 ， 其主要特 點是群體搜索策略和群體中個體之間的信息交換 ， 搜索不依賴于梯度信息 。 它是一種全局化搜索算法 ， 尤其適用于傳統(tǒng)搜索算法難于解決的復雜和非線性問題 。 選擇 (selection)算子、交叉 (crossover)算子和變異 (mutation)算子是遺傳算法的 3個主要操作算子。遺傳算法中包含了如下 5個基本要素 : (1) 對參數(shù)進行編碼； (2) 設定初始種群大??； (3) 適應度函數(shù)的設計； (4) 遺傳操作設計； (5) 控制參數(shù)設定 (包括種群大小、最大進化代數(shù)、交叉率、變異率等 )。 遺傳算法的特點 (1) 遺傳算法對優(yōu)化問題沒有太多的數(shù)學要求 ， 而且只要知道目標函數(shù)的信息即可； (2) 遺傳算法采用的是啟發(fā)性的知識智能搜索算法 ， 在搜索高度空間復雜問題上比以往有更好的效果； (3) 遺傳算法是對問題參數(shù)或者變量編碼群進行優(yōu)化 ， 而不是參數(shù)或變量本身； (4) 遺傳算法使用的選擇、交叉、變異算子都是隨機的； 基本遺傳算法描述 基于對自然界中生物遺傳與進化機理的模仿，針對不同的問題，很多學者設計了許多不同的編碼方法來表示問題的可行解，開發(fā)出了許多種不同的遺傳算子來模仿不同環(huán)境下生物遺傳特性。這樣，由不同的編碼 方法和不同的遺傳算子就構成了各種不同的遺傳算法。但這些遺傳算法都有共同的特點，即通過對生物遺傳和進化過程中選擇、交叉、變異機理的模仿，來完成對問題最優(yōu)解的自適應搜索過程。基于這個特點， Goldberg總結出了一種統(tǒng)一的最基本的遺傳算法 —— 基本遺傳算法（ Simple Geic Algorithms，簡稱 SGA）?；具z傳算法只使用選擇算子、交叉算子和變異算子這三種基本遺傳算子，其遺傳進化操作過程簡單，容易理解，是其他一些遺傳算法的雛形和基礎，它不僅給各種遺傳算法提供了一個基本框架，同時也具有一定的應用價 值。 基本遺傳算法描述： 基本遺傳算法只使用選擇算子 ( Selection Operator)、交叉算子(Crossover Operator)、變異算子 (Mutation Operator)這三種算子。 基本遺傳算法可以形式化定義為一個八元組： SGA=(C,E,Po,M,φ ,τ ,ψ ,T) C —— 個體的編碼方法 ； E —— 個體適應度評價函數(shù) ； Po—— 初始群體 ； M —— 群體大小 ； φ —— 選擇算子 ； τ —— 交叉算子 ； ψ —— 變異算子 ； T —— 遺傳運算終止條件 。 遺傳算法的應用步驟： 第一步： 確定決策變量及其各種約束條件，即確定出個體的表現(xiàn)型 X和問題的解空間。 第二步： 建立優(yōu)化模型，即確定出目標函數(shù)的類型 (是求目標函數(shù)的最大值還是求目標函數(shù)的最小值？ )及其數(shù)學描述形式或量化方法。 第三步：確定表示可行解的染色體編碼方法，也即確定出個體的基因型 X及遺傳算法的搜索空間。 第四步：確定解碼方法，即確定出個體基因型 X到個體表現(xiàn)型 X的對應關系轉換方法。 第五步：確定個體適應度的量化評價方法，即確定出由目標函數(shù)值 f(X)到個體適應度 F(X)的轉換規(guī)則。 第六步：設計遺傳算子，即確定出選擇運算、 交叉運算、變異運算等遺傳算子的具體操作方法。 第七步：確定遺傳算法的有關運行參數(shù)，即確定出遺傳算法的 M、 T、 Pc、 Pm等參數(shù)。 遺傳算法構造流程 遺傳算法的構造過程可以用下圖進行描述： 圖 1－ 1 遺傳算法的主要構造過程示意圖 第二章 遺傳算法的實現(xiàn)技術 編碼方法 在遺傳算法中如何描述問題的可行解，即把一個問題的可行解從其解空間轉換到遺傳算法所能處理的搜索空間的轉換方法稱為編碼。 編碼是應用遺傳算法時要解決的主要問題，也是設計 遺傳算法的一個關鍵步驟。編碼方法除了決定個體染色體排列形式之外，還決定了個體從搜索空間的基因型變換到解空間的表現(xiàn)型時的解碼方法，編碼方法也影響到交叉算子、變異算子等遺傳算子的運算方法。 針對一個具體問題，如何設計一個完美的編碼方案一直是遺傳算法的應用難點之一，也是遺傳算法的一個重要研究方向。目前還沒有一套既嚴密有完整的指導理論及評價準則能夠指導我們設計編碼方案。 De Jong曾提出了兩條操作性較強的實用編碼原則： 編碼原則一 (有意義積木塊編碼原則 ):應使用能易于產(chǎn)生與所求問題相關的且具有低階，短定義長度的編 碼方案。 編碼原則二 (最小字符集編碼原則 ):應使用能使問題得到自然表示或描述的具有最小字符集的編碼方案。 迄今為止人們已經(jīng)提出了許多的編碼方法，總的來說，可以分為三類：二進制編碼方法，浮點數(shù)編碼方法，符號編碼方法。 二進制編碼 二進制編碼方法是遺傳算法中最常用的一種編碼方法，它使用的編碼符號集是由二進制符號 0和 0組成的二值符號集｛ 0， 1｝，它所構成的個體基因型是一個二進制編碼符號串。它有如下幾個優(yōu)點： (1)編碼，解碼簡單易行 。 (2)交叉，變異等遺傳操作便于實現(xiàn)。 (3)符合最小字符集編碼原則 。 (4)便于利用模式定理對算法進行理論分析。 二進制編碼符號串的長度與問題所要求的精度有關。 由于二進制不便于反映所求問題的結構特征，對于一些連續(xù)函數(shù)的優(yōu)化問題等，也由于遺傳運算的隨機特性而使得其局部搜索能力較差，因而人們提出了用格雷碼來對個體進行編碼。 格雷碼編碼 格雷碼，連續(xù)的兩個整數(shù)所對應的編碼值之間只有一個碼位不相同。格雷碼有這樣一個特點：任意兩個整數(shù)的差是這兩個整數(shù)所對應的海明距離（ Hamming distance）。這個特點是遺傳算法中使用格雷碼進行個體編碼的主要原因。格雷碼編碼 方法的主要優(yōu)點是： (1)便于提高遺傳算法的局部搜索能力。 (2)交叉，變異等遺傳操作易于實現(xiàn)。 (3)符合最小字符集編碼原則。 (4)便于用模式定理對算法進行理論分析。 假設一個二進制編碼為 B=bnbn1? b2b1，其對應的格雷碼為 G=gngn1?g2g1。格雷碼到二進制碼的轉換公式： 格雷碼編碼方法是二進制編碼方法的一種變形，其編碼精度與相同長度二進制編碼方法的精度相同。 由于二進制編碼存在著連續(xù)函數(shù)離散化時的映射誤差，而且不便于反映所求問題的特定知識，因而人們提出了用符點數(shù)來對個 體進行編碼。 符點數(shù)編碼 符點數(shù)編碼方法 :指個體的每個基因值用某一范圍內的一個浮點數(shù)來表示個體的編碼長度等于其決策變量的個數(shù)，個體變量的長度等于去決策變量的真實值，所以也叫真值編碼方法．它有以下幾個優(yōu)點： (1)適合于在遺傳算法中表示范圍較大的數(shù)。 (2)適合于精度較高的遺傳算法。 (3)便于較大空間的遺傳搜索。 (4)改善了遺傳算法的復雜性，提高了運算效率。 (5)便于遺傳算法與經(jīng)典優(yōu)化方法的混合使用。 (6)便于設計針對問題的專門知識的知識型遺傳算子。 (7)便于處理復雜的決策變量約束條件。 符號編碼方法是指個體染色體編碼串中的基因值取自一個無數(shù)值含義，而只有代碼含義的符號集．它的主要優(yōu)點如下： (1)符合有意義積木塊編碼原則。 (2)便于在遺傳算法中利用所求解問題的專門知識。 (3)便于遺傳算法與相近似算法之間的混合使用。 但對于使用符號編碼方法的遺傳算法，一般需要認真設計交叉、變異等遺傳運算的操作方法，以滿足問題的各種約束要求，這樣才能提高算法的搜索性能。 最后，簡要介紹一下參數(shù)編碼方法。 參數(shù)編碼 參數(shù)編碼方法是對含有多個變量的個體進行編碼的方法，包含兩種編碼方法： 多參數(shù)級 聯(lián)編碼方法：將各個參數(shù)分別以某種編碼方法進行編碼，然后再將它們的編碼按一定順序聯(lián)接在一起就組成了表示全部參數(shù)的個體編碼。 多參數(shù)交叉編碼方法：將各個參數(shù)中起主要作用的碼位集中在一起。 適應度函數(shù) 在研究自然界中生物的遺傳和進化現(xiàn)象時，生物學家使用適應度這個術語來度量某個物種對其生存環(huán)境的適應程度。對生存環(huán)境適應程度較高的物種將有更多的繁殖機會；而對生存環(huán)境適應度較低的物種，其繁殖的機會就相對較少，甚至會逐漸滅絕。適應度較高的個體遺傳到下一代的概率就相對大一些；而適應度較低的個體遺傳到下一代的概率就 相對較小一些。度量個體適應度的函數(shù)就稱為適應度函數(shù)。 根據(jù)個體的適應值，就可決定在此環(huán)境下的生存能力。個體適應度大小決定該個體被遺傳到下一代群體中的概率。遺傳算法僅使用所求問題的目標函數(shù)值就可以得到下一步的有關搜索信息。目標函數(shù)值的使用是通過評價個體適應度來體現(xiàn)的。 由于個體適應度大小決定該個體被遺傳到下一代群體中的概率。評價個體適應度的一般過程： (1)對個體編碼串進行解碼處理后，可得到個體的表現(xiàn)型。 (2)由個體的表現(xiàn)型可計算出對應個體的目標函數(shù)值。 (3)根據(jù)最優(yōu)化問題的類型，由目標函數(shù)值按一定的轉換 規(guī)則求出個體的適應度。 但是，在僅用適應度函數(shù)來計算個體適應度時 ,有些遺傳算法收斂很快 ,有些遺傳算法收斂很慢，因此在運行到不同的階段時須對個體的適應度進行適當?shù)臄U大或縮小。 適應度尺度變換 (Fitness Scaling):對個體的適應度進行適當?shù)臄U大或縮小變換。 個體適應度尺度變換的三種方法： 線性尺度變換公式如下： F＇ =aF+b F— 原適應度； F＇ — 尺度變換后的新適應度； a和 b— 系數(shù)。 乘冪尺度變換公式如下： F＇ =F ? 冪指數(shù) n與所求解的問題有關。 指數(shù)尺度變換公式如下： F＇ =exp(β F) 系數(shù)β決定了選擇的強制性。 選擇算子 遺 傳算法中使用選擇算子（也叫復制算子 Reproduction Operator）來對群體中的個體進行優(yōu)勝劣汰操作：適應度較高的個體被遺傳到下一代的概率較大；適應度較低的個體被遺傳到下一代的概率較小。遺傳算法中的選擇操作就是用來確定如何從父代群體中按某種方法選取哪些個體遺傳到下一代群體中的一種遺傳運算。 選擇操作建立在對個體的適應度進行評價的基礎上。選擇的主要目的為了避免基因缺失、提高全局收斂性和計算效率。有以下幾種常用的選擇算子的操作方法：比例選擇 、最優(yōu)保存策略、確定式采樣選擇、無放回隨機選擇、無放回余數(shù)隨機選擇、排序選擇和隨機聯(lián)賽選擇等。 最常用的幾種選擇策略有以下幾種： (1) 輪盤賭選擇 (Roulette Wheel Selection) 個體適應度按比例轉換為選中概率，將輪盤分成 n個扇區(qū)進行 n次選擇，產(chǎn)生 n個0～ 1之間的隨機數(shù)相當于轉