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