【正文】 想簡單、易于實現(xiàn)、應(yīng)用效果明顯等優(yōu)點而被眾多應(yīng)用領(lǐng)域所接受，并在自適應(yīng)控制、組合優(yōu)化、模式識別、機(jī)器學(xué)習(xí)、人工生命、管理策略等領(lǐng)域得到了廣泛應(yīng)用。遺傳算法 給我們呈現(xiàn)出的是一類通用的算法框架，該框架不依賴于問題的種類。遺傳算法是一類具有較強(qiáng)魯棒性的優(yōu)化算法，特別是對于一些大型、復(fù)雜非線性系統(tǒng)，它更表現(xiàn)出了比其他傳統(tǒng)優(yōu)化方法更加獨(dú)特和優(yōu)越的性能。隱含并行性和全局搜索特性是遺傳算法的兩大顯著特征。 遺傳算法是新發(fā)展起來的一門學(xué)科，各種理論、方法尚未成熟，有待于進(jìn)一步地發(fā)展和完善，但它卻為我們解決許多復(fù)雜問題提供了希望。盡管在遺傳算法的研究和應(yīng)用過程中出現(xiàn)許多難題，同時也會產(chǎn)生許多不同的算法設(shè)計觀點，然而，目前遺傳算法的各種應(yīng)用實踐已經(jīng)展現(xiàn)出了其優(yōu)異的性能和巨大的發(fā) 展?jié)摿?，它的發(fā)展前景激勵著各類專業(yè)技術(shù)人員把遺傳算法的理論和方法運(yùn)用于自己的工作實踐中。我們相信，隨著研究工作的進(jìn)一步深入和發(fā)展，遺傳算法必將在智能計算領(lǐng)域中起到關(guān)鍵作用。 貨郎擔(dān)問題 (Traveling Salesman Problem ,TSP)， 也稱為巡回旅行商問題 ， 是一個較古的問題 。 最早可以追溯到 1759年 Euler提出的騎士旅行問題 。 TSP問題是一個典型的、容易描述但是難以處理的 NP完全問題，同時 TSP問題也是諸多領(lǐng)域內(nèi)出現(xiàn)的多種復(fù)雜問題的集中概括和簡化形式。目前求解 TSP問題的主要方法有啟發(fā)式搜 索法、模擬退火算法、遺傳算法、 Hopfield神經(jīng)網(wǎng)絡(luò)算法、二叉樹描述算法。所以，有效解決 TSP問題在計算理論上和實際應(yīng)用上都有很高的價值，而且 TSP問題由于其典型性已經(jīng)成為各種啟發(fā)式的搜索、優(yōu)化算法的間接比較標(biāo)準(zhǔn) (如遺傳算法、神經(jīng)網(wǎng)絡(luò)優(yōu)化、列表尋優(yōu) (TABU)法、模擬退火法等 )。遺傳算法就其本質(zhì)來說 ， 主要是解決復(fù)雜問題的一種魯棒性強(qiáng)的啟發(fā)式隨機(jī)搜索算法 。 因此遺傳算法在 TSP問題求解方面的應(yīng)用研究 ， 對于構(gòu)造合適的遺傳算法框架、建立有效的遺傳操作以及有效地解決 TSP問題等有著多方面的重要意義 。 7 第一章 基 本遺傳算法 遺傳算法的產(chǎn)生及發(fā)展 最早美國 Ｍ ichigan(密執(zhí)安大學(xué) )的 Holland教授提出，起源于 60年代對自然和人工自適應(yīng)系統(tǒng)的研究。 70年代 De Jong基于遺傳算法的思想在計算機(jī)上進(jìn)行了大量純數(shù)值函數(shù)優(yōu)化計算實驗。在一系列研究工作的基礎(chǔ)上 80年代 Goldberg進(jìn)行總結(jié)歸納，形成了遺傳算的基本框架。 主要以一些關(guān)鍵人物所做出的主要貢獻(xiàn)見證了遺傳算法的發(fā)展進(jìn)程 : 1 60年代提出在研究和設(shè)計人工自適應(yīng)系統(tǒng)時 ,可以借鑒生物遺傳的機(jī)制； 70年代 初提出了遺傳算法的基本定理－模式定理 (Schema Theorem)，從而奠定了遺傳算法的理論基礎(chǔ)； 80年代實現(xiàn)了第一個基于遺傳算法的機(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)化計算實驗，樹立了遺傳 算法的工作框架，定義了評價遺傳算法性能的在線指標(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年編輯出版了《遺傳算法手冊 (Handbook of Geic Algorithms)》書中包括遺傳 算法在科學(xué)計算、工程技術(shù)和社會經(jīng)濟(jì)中的大量應(yīng)用實例。 6 1992年將遺傳算法應(yīng)用于計算機(jī)程序的優(yōu)化設(shè)計及自動生成，提出了遺傳編程 (Geic Programming) 的概念，并成功的將其提出的遺傳編程應(yīng)用于人工智能、機(jī)器學(xué)習(xí)符號處理等方面。 8 基本原理 遺傳算法是一種借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法 ， 由美國 ， 其主要特點是群體搜索策略和群體中個體之間的信息交換 ， 搜索不依賴于梯度信息 。 它是一種全局化搜索算法 ， 尤其適用于傳統(tǒng) 搜索算法難于解決的復(fù)雜和非線性問題 。 選擇 (selection)算子、交叉 (crossover)算子和變異 (mutation)算子是遺傳算法的 3個主要操作算子。遺傳算法中包含了如下 5個基本要素 : (1) 對參數(shù)進(jìn)行編碼； (2) 設(shè)定初始種群大小； (3) 適應(yīng)度函數(shù)的設(shè)計； (4) 遺傳操作設(shè)計； (5) 控制參數(shù)設(shè)定 (包括種群大小、最大進(jìn)化代數(shù)、交叉率、變異率等 )。 遺傳算法的特點 (1) 遺傳算法對優(yōu)化問題沒有太多的數(shù)學(xué)要求 ， 而且只要知道目標(biāo)函數(shù)的信息即可； (2) 遺傳算法采用的是啟發(fā)性 的知識智能搜索算法 ， 在搜索高度空間復(fù)雜問題上比以往有更好的效果； (3) 遺傳算法是對問題參數(shù)或者變量編碼群進(jìn)行優(yōu)化 ， 而不是參數(shù)或變量本身； (4) 遺傳算法使用的選擇、交叉、變異算子都是隨機(jī)的； 基本遺傳算法描述 基于對自然界中生物遺傳與進(jìn)化機(jī)理的模仿，針對不同的問題，很多學(xué)者設(shè)計了許多不同的編碼方法來表示問題的可行解，開發(fā)出了許多種不同的遺傳算子來模仿不同環(huán)境下生物遺傳特性。這樣，由不同的編碼方法和不同的遺傳算子就構(gòu)成了各種不同的遺傳算法。但這些遺傳算法都有共同的特點，即通過對生物遺傳和進(jìn)化過程 中選擇、交叉、變異機(jī)理的模仿，來完成對問題最優(yōu)解的自適應(yīng)搜索過程?；谶@個特點， Goldberg總結(jié)出了一種統(tǒng)一的最基本的遺傳算法 —— 基本遺傳算法（ Simple Geic Algorithms，簡稱 SGA）?；具z傳算法只使用選擇算子、交叉算子和變異算子這三種基本遺傳算子，其遺傳進(jìn)化操作過程簡單，容易理解，是其他一些遺傳算法的雛形和基礎(chǔ)，它不僅給各種遺傳算法提供了一個基本框架，同時也具有一定的應(yīng)用價值。 9 基本遺傳算法描述： 基本遺傳算法只使用選擇算子 ( Selection Operator)、交叉算 子 (Crossover Operator)、變異算子 (Mutation Operator)這三種算子。 基本遺傳算法可以形式化定義為一個八元組： SGA=(C,E,Po,M,φ ,τ ,ψ ,T) C —— 個體的編碼方法 ； E —— 個體適應(yīng)度評價函數(shù) ； Po—— 初始群體 ； M —— 群體大小 ； φ —— 選擇算子 ； τ —— 交叉算子 ； ψ —— 變異算子 ； T —— 遺傳運(yùn)算終止條件 。 遺傳算法的應(yīng)用步驟： 第一步： 確定決策變量及其各種約束條件，即確定出個體的表現(xiàn)型 X和問題的解空間。 第二步： 建立優(yōu)化模型， 即確定出目標(biāo)函數(shù)的類型 (是求目標(biāo)函數(shù)的最大值還是求目標(biāo)函數(shù)的最小值？ )及其數(shù)學(xué)描述形式或量化方法。 第三步：確定表示可行解的染色體編碼方法，也即確定出個體的基因型 X及遺傳算法的搜索空間。 第四步：確定解碼方法，即確定出個體基因型 X到個體表現(xiàn)型 X的對應(yīng)關(guān)系轉(zhuǎn)換方法。 第五步：確定個體適應(yīng)度的量化評價方法，即確定出由目標(biāo)函數(shù)值 f(X)到個體適應(yīng)度F(X)的轉(zhuǎn)換規(guī)則。 第六步：設(shè)計遺傳算子，即確定出選擇運(yùn)算、交叉運(yùn)算、變異運(yùn)算等遺傳算子的具體操作方法。 第七步：確定遺傳算法的有關(guān)運(yùn)行參數(shù)，即確定出遺傳算法的 M、 T、 Pc、 Pm等參數(shù)。 10 遺傳算法構(gòu)造流程 遺傳算法的構(gòu)造過程可以用下圖進(jìn)行描述： 圖 1－ 1 遺傳算法的主要構(gòu)造過程示意圖 11 第二章 遺傳算法的實現(xiàn)技術(shù) 編碼方法 在遺傳算法中如何描述問題的可行解，即把一個問題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法稱為編碼。 編碼是應(yīng)用遺傳算法時要解決的主要問題，也是設(shè)計遺傳算法的一個關(guān)鍵步驟。編碼方法除了決定個體染色體排列形式之外，還決定了個體從搜索空間的基因型變換到解空 間的表現(xiàn)型時的解碼方法，編碼方法也影響到交叉算子、變異算子等遺傳算子的運(yùn)算方法。 針對一個具體問題，如何設(shè)計一個完美的編碼方案一直是遺傳算法的應(yīng)用難點之一，也是遺傳算法的一個重要研究方向。目前還沒有一套既嚴(yán)密有完整的指導(dǎo)理論及評價準(zhǔn)則能夠指導(dǎo)我們設(shè)計編碼方案。 De Jong曾提出了兩條操作性較強(qiáng)的實用編碼原則： 編碼原則一 (有意義積木塊編碼原則 ):應(yīng)使用能易于產(chǎn)生與所求問題相關(guān)的且具有低階，短定義長度的編碼方案。 編碼原則二 (最小字符集編碼原則 ):應(yīng)使用能使問題得到自然表示或描述的具有最小字符集的編碼方案。 迄今為止人們已經(jīng)提出了許多的編碼方法，總的來說，可以分為三類：二進(jìn)制編碼方法，浮點數(shù)編碼方法，符號編碼方法。 二進(jìn)制編碼 二進(jìn)制編碼方法是遺傳算法中最常用的一種編碼方法，它使用的編碼符號集是由二進(jìn)制符號 0和 0組成的二值符號集｛ 0， 1｝，它所構(gòu)成的個體基因型是一個二進(jìn)制編碼符號串。它有如下幾個優(yōu)點： (1)編碼，解碼簡單易行 。 (2)交叉，變異等遺傳操作便于實現(xiàn)。 (3)符合最小字符集編碼原則。 (4)便于利用模式定理對算法進(jìn)行理論分析。 二進(jìn)制編碼符號串的長度與問題所要求的精度有關(guān)。 由于二進(jìn) 制不便于反映所求問題的結(jié)構(gòu)特征，對于一些連續(xù)函數(shù)的優(yōu)化問題等，也由于遺傳運(yùn)算的隨機(jī)特性而使得其局部搜索能力較差，因而人們提出了用格雷碼來對個體進(jìn)行編碼。 12 格雷碼編碼 格雷碼，連續(xù)的兩個整數(shù)所對應(yīng)的編碼值之間只有一個碼位不相同。格雷碼有這樣一個特點：任意兩個整數(shù)的差是這兩個整數(shù)所對應(yīng)的海明距離（ Hamming distance）。這個特點是遺傳算法中使用格雷碼進(jìn)行個體編碼的主要原因。格雷碼編碼方法的主要優(yōu)點是： (1)便于提高遺傳算法的局部搜索能力。 (2)交叉，變異等遺傳操作易于實現(xiàn)。 (3)符合最小字符集編碼原則。 (4)便于用模式定理對算法進(jìn)行理論分析。 假設(shè)一個二進(jìn)制編碼為 B=bnbn1? b2b1，其對應(yīng)的格雷碼為 G=gngn1? g2g1。格雷碼到二進(jìn)制碼的轉(zhuǎn)換公式： 格雷碼編碼方法是二進(jìn)制編碼方法的一種變形，其編碼精度與相同長度二進(jìn)制編碼方法的精度相同。 由于二進(jìn)制編碼存在著連續(xù)函數(shù)離散化時的映射誤差，而且不便于反映所求問題的特定知識，因而人們提出了用符點數(shù)來對個體進(jìn)行編碼。 符點數(shù)編碼 符點數(shù)編碼方法 :指個體的每個基因值用某一范圍內(nèi)的一個浮點數(shù)來表示個 體的編碼長度等于其決策變量的個數(shù)，個體變量的長度等于去決策變量的真實值，所以也叫真值編碼方法．它有以下幾個優(yōu)點： (1)適合于在遺傳算法中表示范圍較大的數(shù)。 (2)適合于精度較高的遺傳算法。 (3)便于較大空間的遺傳搜索。 (4)改善了遺傳算法的復(fù)雜性，提高了運(yùn)算效率。 (5)便于遺傳算法與經(jīng)典優(yōu)化方法的混合使用。 (6)便于設(shè)計針對問題的專門知識的知識型遺傳算子。 (7)便于處理復(fù)雜的決策變量約束條件。 符號編碼方法是指個體染色體編碼串中的基因值取自一個無數(shù)值含義，而只有代碼含義的符號集．它的主要優(yōu)點如下 ： (1)符合有意義積木塊編碼原則。 13 (2)便于在遺傳算法中利用所求解問題的專門知識。 (3)便于遺傳算法與相近似算法之間的混合使用。 但對于使用符號編碼方法的遺傳算法，一般需要認(rèn)真設(shè)計交叉、變異等遺傳運(yùn)算的操作方法，以滿足問題的各種約束要求，這樣才能提高算法的搜索性能。 最后，簡要介紹一下參數(shù)編碼方法。 參數(shù)編碼 參數(shù)編碼方法是對含有多個變量的個體進(jìn)行編碼的方法，包含兩種編碼方法： 多參數(shù)級聯(lián)編碼方法：將各個參數(shù)分別以某種編碼方法進(jìn)行編碼，然后再將它們的編碼按一定順序聯(lián)接在一起就組成了表示全部 參數(shù)的個體編碼。 多參數(shù)交叉編碼方法：將各個參數(shù)中起主要作用的碼位集中在一起。 適應(yīng)度函數(shù) 在研究自然界中生物的遺傳和進(jìn)化現(xiàn)象時，生物學(xué)家使用適應(yīng)度這個術(shù)語來度量某個物種對其生存環(huán)境的適應(yīng)程度。對生存環(huán)境適應(yīng)程度較高的物種將有更多的繁殖機(jī)會；而對生存環(huán)境適應(yīng)度較低的物種，其繁殖的機(jī)會就相對較少，甚至?xí)饾u滅絕。適應(yīng)度較高的個體遺傳到下一代的概率就相對大一些；而適應(yīng)度較低的個體遺傳到下一代的概率就相對較小一些。度量個體適應(yīng)度的函數(shù)就稱為適應(yīng)度函數(shù)。 根據(jù)個體的適應(yīng)值，就可決定在此環(huán)境下的生存能力。個 體適應(yīng)度大小決定該個體被遺傳到下一代群體中的概率。遺傳算法僅使用所求問題的目標(biāo)函數(shù)值就可以得到下一步的有關(guān)搜索信息。目標(biāo)函數(shù)值的使用是通過評價個體適應(yīng)度來體現(xiàn)的。 由于個體適應(yīng)度大小決定該個體被遺傳到下一代群體中的概率。評價個體適應(yīng)度的一般過程： (1)對個體編碼串進(jìn)行解碼處理后，可得到個體的表現(xiàn)型。 (2)由個體的表現(xiàn)型可計算出對