數值分析方法主編

李冬果李林高磊首都醫科大學生物醫學工程學院智能醫學工程學學系面向“四新”人才培養普通高等教育系列教材第八章智能優化算法基礎第一節最優化問題和隨機算法第二節禁忌搜索算法第三節模擬退火方法第四節遺傳算法第五節粒子群算法

目錄/Contents

8.4遺傳算法在自然界中，生命為了適應環境變化，而產生了進化機制。即通過遺傳和隨機突變產生下一代，在自然選擇下，適應環境的個體和它們的遺傳特性得以存活。遺傳算法（Geneticalgorithm,GA）是一種群體算法，它通過模擬一個種群在自然選擇作用下的繁衍，突變，和選擇過程，在可能的解空間中進行搜索得到最優結果的一個過程。遺傳算法最早于1975年由J.Holland等人提出。8.4.1算法原理遺傳算法模擬了生物進化過程，真核生物的主要遺傳物質是脫氧核糖核酸（DNA），在生物細胞中，DNA與組蛋白組成了染色體，是細胞中可被觀察到的遺傳信息載體。遺傳信息的基本單位被稱為基因，它是DNA的片段，一條染色體上可以包含很多個不同的基因，而生物體表現出的形狀則由這些基因的組合決定。在生物進化過程中，染色體的親代與子代之間存在著復制，交叉，變異和選擇的基本階段。復制使子代保持了親代的主要信息，是遺傳性狀得到保持的基本機制。而同源染色體的交叉，即兩個染色體的某些部分進行互換，和染色體上部分基因發生隨機的變異，則是子代產生不同于親代性狀的兩種機制。最后，在自然選擇的作用下，不適應環境的子代被淘汰，而適應環境的子代則被保留下來。在數學家看來，遺傳過程就是一個優化過程。出于簡化的目的，每個個體被視為一條染色體，也就是優化問題的潛在解，而該解所對應的優化目標函數就是對該個體適應環境水平的評價，算法基于此可以進行選擇。而復制、交叉和變異，是由父代個體獲得子代個體的方式，可以分別對應著不同的運算過程。由此，遺傳算法被開發出來。8.4.2算法設計遺傳算法是對群體遺傳過程的模擬，生物遺傳過程中的各階段，都被對應于優化算法的不同運算程序。主要包括，遺傳編碼，適應度函數，交叉操作，變異操作，個體選擇等。（1）遺傳編碼遺傳算法使用“染色體”作為運算的基礎，因此，需要把實際優化問題中的潛在解映射為一條“染色體”，這個過程稱為編碼(encoding)，而相反的過程，則稱為解碼(decoding)。針對不同的問題，遺傳算法可以有不同的編碼方式，如二進制編碼，自然數編碼，實數編碼和樹型編碼等。在實際應用中，二進制編碼最最簡單，也最常用，為方便起見，后續內容均以二進制編碼為例。

（3）交叉操作模擬生物遺傳過程中，兩個同源染色體交叉交換部分染色體產生新個體的過程，遺傳算法定義了交叉操作。在遺傳算法中，一般在親代群體中隨機匹配兩條染色體，然后進行交叉運算。交叉過程，一般是隨機選定一個或多個交叉點，然后再依次交換兩條染色體在交叉點后的部分。

如上例中，如果只有一個交叉點，稱為單點交叉，而有兩個或更多交叉點的方法稱為兩點交叉或多點交叉。交叉的意義在于生成與親代不同的子代，在算法中，是否交叉，在何位置交叉以及有幾個交叉點經常都是通過概率的方式決定的。交叉概率大，則算法能夠產生更多的新解，搜索范圍隨之擴大，從而保持了群體的多樣性，避免陷入局部最優。但相應地增加了運算量，浪費運算資源。（4）變異操作在生物遺傳過程中，基因可能發生突變，DNA序列上某個位點可能被替換為不同的堿基。在遺傳算法當中，則將變異操作理解為“染色體”某個位置發生改變，對二進制編碼而言，意味著在某個位置發生0-1的互補運算，即字符0被替換為1，或者1被替換為0。一般情況下，是否發生變異也需要按照一個給定的變異概率參數來決定，通過(0,1)上的隨機數與給定的變異概率相比較，來決定是否發生變異。這個概率參數如果設的過小，則搜索空間被限制，反之如果變異概率過大，則子代與親代的區別可能過大，從而失去了對親代“優良性狀”的繼承。（5）選擇操作親代通過交叉、變異操作生成的子代合在一起組成了新的候選群落，這個群落并非每個個體都能夠產生子代，需要通過一個選擇過程來從這個群落中挑選出環境適應度更高的個體，使其成為下一次遺傳過程的親代。為了避免陷入局部最優值，選擇操作不會直接根據適應度函數值來進行排序篩選，而是需要通過某種方法引入一個隨機狀態，使適應度高的個體更可能被選擇，但適應度低的個體也有被選中的機會。為了達到這一效果，數學家開發了很多算法。

8.4.3算法實現根據上述內容，遺傳算法的主要步驟如下：步驟1

根據編碼方法，輸入指定規模初始群體，定義適應度函數；步驟2

為群體中每個個體計算適應度值；步驟3

通過選擇操作，從群體中選出親代群體；步驟4

在親代群體中隨機配對，按概率選定交叉點進行交叉操作以產生新個體；步驟5

對新個體進行變異操作；步驟6

重復執行步驟2到步驟5，直到算法終止條件得到滿足。在遺傳算法的過程中，有些細節需要加以注意：

（1）精英保留策略。為了保證算法結果收斂于全局最優解，在選擇過程中還要增加一個精英保留策略，即每次產生下一代的過程中，需保留一個適應度最高的個體，將其直接復制到下一代中。經過基于馬爾可夫鏈的相關理論分析，證明如果不在算法中采用精英保留策略，算法將不能收斂到全局最優解。

（2）算法的終止條件。遺傳算法的終止條件可以設為群體趨于穩定，即各染色體變化很小，但由于遺傳算法的特性，這個條件有時不易達到