1、第10章 遺傳算法10.1 遺傳算法的基本原理1 遺傳算法簡稱GA（Genetic Algorithms）是1962年由美國Michigan大學的Holland教授提出的模擬自然界遺傳機制和生物進化論而成的一種并行隨機搜索最優化方法。 遺傳算法是以達爾文的自然選擇學說為基礎發展起來的。自然選擇學說包括以下三個方面：2（1）遺傳：這是生物的普遍特征，親代把生物信息交給子代，子代總是和親代具有相同或相似的性狀。生物有了這個特征，物種才能穩定存在。（2）變異：親代和子代之間以及子代的不同個體之間的差異，稱為變異。變異是隨機發生的，變異的選擇和積累是生命多樣性的根源。（3）生存斗爭和適者生存：具有適應

2、性變異的個體被保留下來，不具有適應性變異的個體被淘汰，通過一代代的生存環境的選擇作用，性狀逐漸逐漸與祖先有所不同，演變為新的物種。3 遺傳算法將“優勝劣汰，適者生存”的生物進化原理引入優化參數形成的編碼串聯群體中，按所選擇的適應度函數并通過遺傳中的復制、交叉及變異對個體進行篩選，使適適應度高的個體被保留下來，組成新的群體，新的群體既繼承了上一代的信息，又優于上一代。這樣周而復始，群體中個體適應度不斷提高，直到滿足一定的條件。遺傳算法的算法簡單，可并行處理，并能到全局最優解。4遺傳算法的基本操作為：（1）復制（Reproduction Operator） 復制是從一個舊種群中選擇生命力強的個體位

3、串產生新種群的過程。具有高適應度的位串更有可能在下一代中產生一個或多個子孫。 復制操作可以通過隨機方法來實現。首先產生01之間均勻分布的隨機數，若某串的復制概率為40%，則當產生的隨機數在0.401.0之間時，該串被復制，否則被淘汰。5（2）交叉（Crossover Operator） 復制操作能從舊種群中選擇出優秀者，但不能創造新的染色體。而交叉模擬了生物進化過程中的繁殖現象，通過兩個染色體的交換組合，來產生新的優良品種。 交叉的過程為：在匹配池中任選兩個染色體，隨機選擇一點或多點交換點位置；交換雙親染色體交換點右邊的部分，即可得到兩個新的染色體數字串。6 交杈體現了自然界中信息交換的思想。

4、交叉有一點交叉、多點交叉、還有一致交叉、順序交叉和周期交叉。一點交叉是最基本的方法，應用較廣。它是指染色體切斷點有一處，例：7（3）變異(Mutation Operator) 變異運算用來模擬生物在自然的遺傳環境中由于各種偶然因素引起的基因突變，它以很小的概率隨機地改變遺傳基因（表示染色體的符號串的某一位）的值。在染色體以二進制編碼的系統中，它隨機地將染色體的某一個基因由1變為0，或由0變為1。8 若只有選擇和交叉，而沒有變異，則無法在初始基因組合以外的空間進行搜索，使進化過程在早期就陷入局部解而進入終止過程，從而影響解的質量。為了在盡可能大的空間中獲得質量較高的優化解，必須采用變異操作。91

5、0.2 遺傳算法的特點 （1）遺傳算法是對參數的編碼進行操作，而非對參數本身，這就是使得我們在優化計算過程中可以借鑒生物學中染色體和基因等概念，模仿自然界中生物的遺傳和進化等機理；（2）遺傳算法同時使用多個搜索點的搜索信息。傳統的優化方法往往是從解空間的單個初始點開始最優解的迭代搜索過程，單個搜索點所提供的信息不多，搜索效率不高，有時甚至使搜索過程局限于局部最優解而停滯不前。10 遺傳算法從由很多個體組成的一個初始群體開始最優解的搜索過程，而不是從一個單一的個體開始搜索，這是遺傳算法所特有的一種隱含并行性，因此遺傳算法的搜索效率較高。（3）遺傳算法直接以目標函數作為搜索信息。傳統的優化算法不僅

6、需要利用目標函數值，而且需要目標函數的導數值等輔助信息才能確定搜索方向。而遺傳算法僅使用由目標函數值變換來的適應度函數值，就可以確定進一步的搜索方向和搜索范圍，無需目標函數的導數值等其他一些輔助信息。11 遺傳算法可應用于目標函數無法求導數或導數不存在的函數的優化問題，以及組合優化問題等。（4）遺傳算法使用概率搜索技術。遺傳算法的選擇、交叉、變異等運算都是以一種概率的方式來進行的，因而遺傳算法的搜索過程具有很好的靈活性。隨著進化過程的進行，遺傳算法新的群體會更多地產生出許多新的優良的個體。12（5）遺傳算法在解空間進行高效啟發式搜索，而非盲目地窮舉或完全隨機搜索；（6）遺傳算法對于待尋優的函數

7、基本無限制，它既不要求函數連續，也不要求函數可微，既可以是數學解析式所表示的顯函數，又可以是映射矩陣甚至是神經網絡的隱函數，因而應用范圍較廣；（7）遺傳算法具有并行計算的特點，因而可通過大規模并行計算來提高計算速度，適合大規模復雜問題的優化。 1310.3 遺傳算法的發展及應用10.3.1 遺傳算法的發展 遺傳算法起源于對生物系統所進行的計算機模擬研究。早在20世紀40年代，就有學者開始研究如何利用計算機進行生物模擬的技術，他們從生物學的角度進行了生物的進化過程模擬、遺傳過程模擬等研究工作。進入20世紀60年代，美國密執安大學的Holland教授及其學生們受到這種生物模擬技術的啟發，創造出一種

8、基于生物遺傳和進化機制的適合于復雜系統優化計算的自適應概率優化技術遺傳算法。14 以下是在遺傳算法發展進程中一些關鍵人物所做出的主要貢獻：（1）J.H.Holland 20世紀70年代初，Holland教授提出了遺傳算法的基本定理模式定理，從而奠定了遺傳算法的理論基礎。模式定理揭示了群體中優良個體（較好的模式）的樣本數將以指數級規律增長，從理論上保證了遺傳算法用于尋求最優可行解的優化過程。1975年，Holland出版了第一本系統論述遺傳算法和人工自適應系統的專著自然系統和人工系統的自適應性。20世紀80年代，Holland教授實現了第一個基于遺傳算法的機器學習系統分類器系統，開創了基于遺傳算

9、法的機器學習的新概念。15（2）J.D.Bagley 1967年，Holland的學生Bagley在其博士論文中首次提出了“遺傳算法”一詞，并發表了遺傳算法應用方面的第一篇論文。他發展了復制、交叉、變異、顯性、倒位等遺傳算子，在個體編碼上使用了雙倍體的編碼方法。在遺傳算法的不同階段采用了不同的概率，從而創立了自適應遺傳算法的概念。16（3）K.A.De Jong 1975年，De Jong博士在其博士論文中結合模式定理進行了大量純數值函數優化計算實驗，樹立了遺傳算法的工作框架。他推薦了在大多數優化問題中都較適用的遺傳算法的參數，建立了著名的De Jong五函數測試平臺，定義了評價遺傳算法性能的

10、在線指標和離線指標。（4）D.J.Goldberg 1989年，Goldberg出版了專著搜索、優化和機器學習中的遺傳算法，該書全面地論述了遺傳算法的基本原理及其應用，奠定了現代遺傳算法的科學基礎。17（5）L.Davis 1991年，Davis編輯出版了遺傳算法手冊一書，為推廣和普及遺傳算法的應用起到了重要的指導作用。（6）J.R.Koza 1992年，Koza將遺傳算法應用于計算機程序的優化設計及自動生成，提出了遺傳編程的概念，并成功地將遺傳編程的方法應用于人工智能、機器學習和符號處理等方面。1810.3.1 遺傳算法的應用（1）函數優化。 函數優化是遺傳算法的經典應用領域，也是遺傳算法進

11、行性能評價的常用算例。尤其是對非線性、多模型、多目標的函數優化問題，采用其他優化方法較難求解，而遺傳算法卻可以得到較好的結果。（2）組合優化。 隨著問題的增大，組合優化問題的搜索空間也急劇擴大，采用傳統的優化方法很難得到最優解。遺傳算法是尋求這種滿意解的最佳工具。例如，遺傳算法已經在求解旅行商問題、背包問題、裝箱問題、圖形劃分問題等方面得到成功的應用。19（3）生產調度問題 在很多情況下，采用建立數學模型的方法難以對生產調度問題進行精確求解。在現實生產中多采用一些經驗進行調度。遺傳算法是解決復雜調度問題的有效工具，在單件生產車間調度、流水線生產車間調度、生產規劃、任務分配等方面遺傳算法都得到了

12、有效的應用。20（4）自動控制。 在自動控制領域中有很多與優化相關的問題需要求解，遺傳算法已經在其中得到了初步的應用。例如，利用遺傳算法進行控制器參數的優化、基于遺傳算法的模糊控制規則的學習、基于遺傳算法的參數辨識、基于遺傳算法的神經網絡結構的優化和權值學習等。21（5）機器人 例如，遺傳算法已經在移動機器人路徑規劃、關節機器人運動軌跡規劃、機器人結構優化和行為協調等方面得到研究和應用。（6）圖像處理 遺傳算法可用于圖像處理過程中的掃描、特征提取、圖像分割等的優化計算。目前遺傳算法已經在模式識別、圖像恢復、圖像邊緣特征提取等方面得到了應用。22（7）人工生命 人工生命是用計算機、機械等人工媒體

13、模擬或構造出的具有生物系統特有行為的人造系統。人工生命與遺傳算法有著密切的聯系，基于遺傳算法的進化模型是研究人工生命現象的重要基礎理論。遺傳算法為人工生命的研究提供了一個有效的工具。（8）遺傳編程 遺傳算法已成功地應用于人工智能、機器學習等領域的編程。23（9）機器學習 基于遺傳算法的機器學習在很多領域都得到了應用。例如，采用遺傳算法實現模糊控制規則的優化，可以改進模糊系統的性能；遺傳算法可用于神經網絡連接權的調整和結構的優化；采用遺傳算法設計的分類器系統可用于學習式多機器人路徑規劃。2410.4.1 遺傳算法的構成要素（1）染色體編碼方法 基本遺傳算法使用固定長度的二進制符號來表示群體中的個

14、體，其等位基因是由二值符號集0,1所組成。初始個體基因值可用均勻分布的隨機值生成，如就可表示一個個體，該個體的染色體長度是18。10.4 遺傳算法的優化設計25（2）個體適應度評價：基本遺傳算法與個體適應度成正比的概率來決定當前群體中每個個體遺傳到下一代群體中的概率多少。為正確計算這個概率，要求所有個體的適應度必須為正數或零。因此，必須先確定由目標函數值J到個體適應度f之間的轉換規則。26（3）遺傳算子：基本遺傳算法使用下述三種遺傳算子： 選擇運算:使用比例選擇算子； 交叉運算:使用單點交叉算子； 變異運算:使用基本位變異算子或均勻變異算子。27（4）基本遺傳算法的運行參數 有下述4個運行參數

15、需要提前設定：M：群體大小，即群體中所含個體的數量，一般取為20100；G：遺傳算法的終止進化代數，一般取為100500；Pc：交叉概率，一般取為0.40.99；Pm：變異概率，一般取為0.00010.1。28 對于一個需要進行優化的實際問題，一般可按下述步驟構造遺傳算法：第一步：確定決策變量及各種約束條件，即確定出個體的表現型X和問題的解空間；第二步：建立優化模型，即確定出目標函數的類型及數學描述形式或量化方法；10.4.2 遺傳算法的應用步驟29第三步：確定表示可行解的染色體編碼方法，即確定出個體的基因型x及遺傳算法的搜索空間；第四步：確定解碼方法，即確定出由個體基因型x到個體表現型X的對

16、應關系或轉換方法；第五步：確定個體適應度的量化評價方法，即確定出由目標函數值到個體適應度的轉換規則；第六步：設計遺傳算子，即確定選擇運算、交叉運算、變異運算等遺傳算子的具體操作方法。第七步：確定遺傳算法的有關運行參數，即M,G,Pc,Pm等參數。30以上操作過程可以用圖10-1來表示。 圖10-1 遺傳算法流程圖 31利用遺傳算法求Rosenbrock函數的極大值10.5 遺傳算法求函數極值3210.5.1 二進制編碼遺傳算法求函數極大值 求解該問題遺傳算法的構造過程：（1）確定決策變量和約束條件；（2）建立優化模型；（3）確定編碼方法 33 用長度為10位的二進制編碼串來分別表示兩個決策變量

17、x1,x2。10位二進制編碼串可以表示從0到1023之間的1024個不同的數，故將x1,x2的定義域離散化為1023個均等的區域，包括兩個端點在內共有1024個不同的離散點。 從離散點-2.048到離散點2.048 ，分別對應于從0000000000(0)到1111111111(1023)之間的二進制編碼。34 將x1,x2分別表示的兩個10位長的二進制編碼串連接在一起，組成一個20位長的二進制編碼串，它就構成了這個函數優化問題的染色體編碼方法。使用這種編碼方法，解空間和遺傳算法的搜索空間就具有一一對應的關系。例如： 表示一個個體的基因型，其中前10位表示x1，后10位表示x2。35（4）確定

18、解碼方法：解碼時需要將20位長的二進制編碼串切斷為兩個10位長的二進制編碼串，然后分別將它們轉換為對應的十進制整數代碼，分別記為y1和y2。 依據個體編碼方法和對定義域的離散化方法可知，將代碼y轉換為變量x的解碼公式為 例如，對個體36 它由兩個代碼所組成 上述兩個代碼經過解碼后，可得到兩個實際的值（5）確定個體評價方法：由于Rosenbrock函數的值域總是非負的，并且優化目標是求函數的最大值，故可將個體的適應度直接取為對應的目標函數值，即37選個體適應度的倒數作為目標函數（6）設計遺傳算子：選擇運算使用比例選擇算子，交叉運算使用單點交叉算子，變異運算使用基本位變異算子。（7）確定遺傳算法的

19、運行參數：群體大小M=80，終止進化代數G=100，交叉概率Pc=0.60，變異概率Pm=0.10。 上述七個步驟構成了用于求函數極大值的優化計算基本遺傳算法。38 采用上述方法進行仿真，經過100步迭代，最佳樣本為即當 時，Rosenbrock函數具有極大值，極大值為3905.9。仿真程序：chap5_1.m 39 遺傳算法的優化過程是目標函數J和適應度函數F的變化過程。 由仿真結果可知，隨著進化過程的進行，群體中適應度較低的一些個體被逐漸淘汰掉，而適應度較高的一些個體會越來越多，并且它們都集中在所求問題的最優點附近，從而搜索到問題的最優解。4010.5.2 實數編碼遺傳算法求函數極大值求解

20、該問題遺傳算法的構造過程：（1）確定決策變量和約束條件；（2）建立優化模型；（3）確定編碼方法：用2個實數分別表示兩個決策變量，分別將的定義域離散化為從離散點-2.048到離散點2.048的Size個實數。41（4）確定個體評價方法： 個體的適應度直接取為對應的目標函數值，即 選個體適應度的倒數作為目標函數 42（5）設計遺傳算子：選擇運算使用比例選擇算子，交叉運算使用單點交叉算子，變異運算使用基本位變異算子。（6）確定遺傳算法的運行參數：群體大小M=500，終止進化代數G=200，交叉概率Pc=0.90，采用自適應變異概率即變異概率與適應度有關，適應度越小，變異概率越大。 43 上述六個步驟

21、構成了用于求函數Rosenbrock極大值的優化計算的實數編碼遺傳算法。 十進制編碼求函數Rosenbrock極大值。仿真程序見chap10_2.m。 仿真程序經過200步迭代，最佳樣本為即當 ， 時，函數具有極大值，極大值為3880.3。4410.6 基于遺傳算法優化的RBF網絡逼近10.6.1 遺傳算法優化原理 在7.3節的RBF網絡逼近算法中，網絡權值、高斯函數的中心矢量和基寬向量的初值難以確定，如果這些參數選擇不當，會造成逼近精度的下降甚至RBF網絡的發散。采用遺傳算法可實現RBF網絡參數的優化。45 為獲取滿意的逼近精度，采用誤差絕對值指標作為參數選擇的最小目標函數。 式中， 為逼近

22、的總步驟， 為第 步RBF網絡的逼近誤差。 在應用遺傳算法時，為了避免參數選取范圍過大，可以先按經驗選取一組參數，然后再在這組參數的周圍利用遺傳算法進行設計，從而大大減少初始尋優的盲目性，節約計算量。4610.6.2 仿真實例 使用RBF網絡逼近下列對象： 在RBF網絡中，網絡輸入信號為2個，即和 ，網絡初始權值及高斯函數參數初始值通過遺傳算法優化而得。47 遺傳算法優化程序為chap10_3a.m，取逼近總步驟為，每一步的逼近誤差由chap10_3b.m求得。采用二進制編碼方式，用長度為10位的二進制編碼串來分別表示向量b、c和w中的每個值。 48 遺傳算法優化中，取樣本個數為Size=30

23、，交叉概率為Pc=0.60，采用自適應變異概率，即適應度越小，變異概率越大，取變異概率為 取用于優化的RBF網絡結構為2-3-1，網絡權值wj的取值范圍為-1,+1，高斯函數基寬向量的取值范圍為0.1,3.0，高斯函數中心矢量的取值范圍為-3,+3。取則共有12個參數需要優化。49 經過150代遺傳算法進化，優化后的結果為：p=2.7732，2.6343，2.2630，1.8680，-0.0616，-0.7126，-0.3959，2.2669， -1.4047，-0.3099，0.7478，-0.3353。 則RBF網絡高斯基函數參數的初始值及權值的初始值為:50 RBF網絡遺傳算法優化程序包

24、括三部分，即遺傳算法優化程序chap10_3a.m、RBF網絡逼近函數程序chap10_3b.m和RBF網絡逼近測試程序chap10_3c.m。51 10.7 基于遺傳算法的伺服系統靜態摩擦參數辨識 摩擦分為靜摩擦和動摩擦，它們之間的區別就是看兩個物體之間的接觸面有沒有相對位移，分為三種情況：如果沒有相對位移，也沒有位移的趨勢，則是沒有摩擦力；如果沒有相對位移，但是有位移的趨勢，則為靜摩擦力；如果有相對位移，則為動摩擦。 摩擦現象是一種復雜的、非線性的、具有不確定性的自然現象。在高精度、超低速伺服系統中，由于非線性摩擦環節的存在，使系統的動態及靜態性能受到很大程度的影響，主要表現為低速時出現爬

25、行現象，穩態時有較大的靜差或出現極限環振蕩。克服這一問題的有效方法是進行摩擦辨識，從而進行有效的補償。52 10.7.1 伺服系統的靜態摩擦模型 基于SISO的伺服系統可描述為 （10.7）其中 為轉動慣量， 為轉角， 為控制輸入力矩，F為摩擦力矩。 許多伺服系統在低速情況下存在靜摩擦現象。靜摩擦力矩與轉速之間的穩態對應關系為： （10.8）其中 、 、 、 為靜態摩擦參數， 為庫侖摩擦， 為靜摩擦， 為粘性摩擦系數， 為切換速度。53 伺服系統在正反轉動速度方向運行時，其靜態摩擦力矩的靜態參數通常為不同的值。當 時，靜態參數的值為 、 、 、 ；當 ，靜態參數的值為 、 、 、 ，表示如下：

26、 (10.9) 由上式所確定的轉速-摩擦力矩曲線稱為Stribeck曲線。對于摩擦模型中的靜態參數，通過恒速跟蹤實驗可以得到Stribeck曲線，再由Stribeck曲線，采用遺傳算法可辨識出靜態參數22。54 恒速跟蹤實驗為在線條件下運行，工程上很容易實現，而遺傳算法是在離線情況下運行，因而本方法具有較強的實際工程價值。 10.7.2 靜摩擦模型Stribeck曲線的獲取 在靜態摩擦條件下， ，由式（10.7）可知， 。由于u可測得，采用一組恒速跟蹤，可獲得一組相應的控制輸入信號和靜態摩擦力矩，從而獲得Stribeck曲線。 具體方法為：取閉環系統的一組恒定轉速序列 作為速度指令信號，通過采

27、用PD控制律，實現被控對象精確的速度跟蹤，得到相應的控制力矩序列 ，從而獲得一組相應的靜態摩擦力矩序列。 PD控制律為： （10.10）55 10.7.3 基于遺傳算法的靜態摩擦參數辨識 取待辨識靜態摩擦參數向量為個體，遺傳算法的每步迭代得到靜態摩擦參數的辨識值為： ， （10.11） 其中M為種群規模。 由下式可得到相應的摩擦力矩辨識值： （10.12）56 辨識誤差為： ，其中值根據所建立的Stribeck曲線得到。 取目標函數為： （10.13）選擇個體適應度函數如下： 或 ， （10.14）57 采用十進制浮點編碼格式，選擇操作采取保存最優個體的隨機采樣選擇方法，交叉操作采用均勻交叉算

28、子，交叉概率 ，變異操作采用高斯變異算子，變異概率隨進化代數自適應調整，即， 其中 g當前遺傳代數。 遺傳算法的步驟如下： Step 1. 置進化代數計數器為 ，隨機產生初始化種群 ；Step 2. 計算個體適應度 ， ；Step 3. 判斷是否達到最大進化代數，若是，則算法終止，否則，轉step 4；Step 4. 經過選擇操作，產生新一代種群 ；Step 5. 以概率 進行交叉操作；Step 6. 以概率 進行個體變異操作；Step 7. ，轉step 2；58 一旦辨識得到的參數估計值，便可以設計摩擦力矩的補償環節，實現對系統的摩擦進行補償，基于摩擦力矩補償的控制系統描述為： （10.1

29、5） 10.7.4 仿真實例 被控對象為（10.7）式，取 ，控制律取PD控制。參數辨識的仿真分以下兩步實現。 仿真之一：Stribeck曲線的測試 恒速跟蹤時，為靜態摩擦，實際系統的摩擦模型取（10.9）式，被控對象為帶有靜態摩擦模型式（10.7）的實際對象，取 ， ， ， ， ， ， ， 。取速度信號 作為指令信號，共41個速度指令信號。針對每個指令信號，采用PD控制律，取 ， 。仿真結果如圖10-8至10-10所示。仿真結束后，將所得到的靜摩擦力矩估計值保存在文件Fi_中。59圖10-8 恒速斜波跟蹤（速度指令為1.0時） 60圖10-9 Stribeck曲線的實際值與測試值的比較 61

30、圖10-10 Stribeck曲線的辨識誤差62 仿真之二：遺傳算法的靜態摩擦參數辨識 首先將仿真之一“Stribeck曲線設計”所得到的摩擦力矩估計值 從文件Fi_中調入，作為實際系統的靜摩擦力矩的估計值。 恒速跟蹤時為靜態摩擦。取速度信號 作為指令信號，共41個速度指令信號。針對每個指令信號，采用PD控制律，取 ， 。 在遺傳算法仿真中，取種群規模，最大遺傳代數 。參數搜索范圍為 ， ， ， ， 靜態摩擦模型取（10.9）式，將遺傳算法設計所得到了靜摩擦力矩與實際摩擦力矩比較得到目標函數值。當運行到最大遺傳代數 時，目標函數值為 。 63遺傳算法的辨識過程及辨識曲線如圖10-11和10-1

31、2所示，實際值與辨識值比較的仿真結果如表10-1所示。 表10-1 靜態摩擦參數實際值與辨識值的比較64圖10-11 目標函數值變化曲線局部放大圖65圖10-12 辨識Stribeck曲線與實際 Stribeck曲線66 10.7.5 基于摩擦模型補償的伺服系統控制 為了驗證基于遺傳算法的伺服系統靜態摩擦參數辨識的效果，將PD控制與基于靜態摩擦模型補償的PD控制進行比較，采用低速正弦信號 作為位置指令。在PD控制中，取 ， 。采用手動轉換開關實現兩種控制方法的切換，一種為只采用PD控制，另一種為基于摩擦補償的PD控制，仿真結果如圖10-13和10-14所示。在圖10-13中，由于存在靜摩擦，造

32、成了位置跟蹤出現了“平頂”現象。67圖10-13 未加補償的PD控制位置跟蹤68圖10-14 基于摩擦補償的PD控制位置跟蹤69 10.8 基于遺傳算法的TSP問題優化 在第8.5節已經對旅行商問題進行了描述。遺傳算法由于其全局搜索的特點，在解決TSP問題中有明顯的優勢。 10.8.1 TSP問題的編碼 設 是由城市i和城市j之間的距離組成的距離矩陣，旅行商問題就是求出一條通過所有城市且每個城市只通過一次的具有最短距離的回路。70 在旅行商問題的各種求解方法中，描述旅行路線的方法主要有如下兩種：（1）巡回旅行路線經過的連接兩個城市的路線的順序排列；（2）巡回旅行路線所經過的各個城市的順序排列。

33、大多數求解旅行商問題的遺傳算法是以后者為描述方法的，它們大多采用所遍歷城市的順序來表示各個個體的編碼串，其等位基因為N個整數值或N個記號。 以城市的遍歷次序作為遺傳算法的編碼，目標函數取路徑長度。在群體初始化、交叉操作和變異操作中考慮TSP問題的合法性約束條件（即對所有的城市做到不重不漏）。71 10.8.2 TSP問題的遺傳算法設計 采用遺傳算法進行路徑優化，分為以下幾步： 第一步：參數編碼和初始群體設定 一般來說遺傳算法對解空間的編碼大多采用二進制編碼形式，但對于TSP一類排序問題，采用對訪問城市序列進行排列組合的方法編碼，即某個巡回路徑的染色體個體是該巡回路徑的城市序列。 針對TSP問題

34、，編碼規則通常是N取進制編碼，即每個基因僅從1到N的整數里面取一個值，每個個體的長度為N，N為城市總數。定義一個s行t列的pop矩陣來表示群體，t為城市個數N+1，即N+1，s為樣本中個體數目。針對30個城市的TSP問題，t取值31， 72 即矩陣每一行的前30個元素表示經過的城市編號，最后一個元素表示經過這些城市要走的距離。 參數編碼和初始群體設定程序為：pop=zeros(s,t);for i=1:s pop(i,1:t-1)=randperm(t-1);end 第二步：計算路徑長度的函數設計 在TSP的求解中，用距離的總和作為適應度函數，來衡量求解結果是否最優。將POP矩陣中每一行表示經過的距離的最后一個元素作為路徑長度。73 兩個城市m和n間的距離為： （10.16） 用于計算路徑長度的程序為chap10_1dis.m。 通過樣本的路徑長度可以得到目標函數和自適應度函數。根據t的定義，兩兩城市組合數共有t-2組，則目標函數為： （10.17） 自適應度函數取目標函數的倒數，即： （10.18）74 第三步：計算