2.2　遺傳算法理論

2.2.1　遺傳算法的生物學基礎

自然選擇學說認為適者生存，生物要存活下去，就必須進行生存斗爭。生存斗爭包括種內斗爭、種間斗爭以及生物跟環境之間的斗爭三個方面。在生存斗爭中，具有有利變異的個體容易存活下來，并且有更多的機會將有利變異傳給后代；具有不利變異的個體就容易被淘汰，產生后代的機會也將少得多。因此，凡是在生存斗爭中獲勝的個體都是對環境適應性比較強的個體。達爾文把這種在生存斗爭中適者生存、不適者淘汰的過程叫作自然選擇。

達爾文的自然選擇學說表明，遺傳和變異是決定生物進化的內在因素。遺傳是指父代與子代之間，在性狀上存在的相似現象；變異是指父代與子代之間，以及子代的個體之間，在性狀上存在的差異現象。在生物體內，遺傳和變異的關系十分密切。一個生物體的遺傳性狀往往會發生變異，而變異的性狀有的可以遺傳。遺傳能使生物的性狀不斷地傳送給后代，因此保持了物種的特性；變異能夠使生物的性狀發生改變，從而適應新的環境而不斷地向前發展。

生物的各項生命活動都有它的物質基礎，生物的遺傳與變異也是這樣。根據現代細胞學和遺傳學的研究可知：遺傳物質的主要載體是染色體，而染色體由基因組成；基因是有遺傳效應的片段，它儲存著遺傳信息，可以被準確地復制，也能夠發生突變。生物體自身通過對基因的復制和交叉，使其性狀的遺傳得到選擇和控制。同時，通過基因重組、基因變異和染色體在結構和數目上的變異產生豐富多彩的變異現象。生物的遺傳特性，使生物界的物種能夠保持相對的穩定；生物的變異特性，使生物個體產生新的性狀，以至形成了新的物種，推動了生物的進化和發展。

由于生物在繁殖中可能發生基因交叉和變異，引起了生物性狀的連續微弱改變，為外界環境的定向選擇提供了物質條件和基礎，使生物的進化成為可能。人們正是通過對環境的選擇、基因的交叉和變異這一生物演化的迭代過程的模仿，才提出了能夠用于求解最優化問題的強魯棒性和自適應性的遺傳算法［7］。生物遺傳和進化的規律有：

（1）生物的所有遺傳信息都包含在其染色體中，染色體決定了生物的性狀。染色體是由基因及其有規律的排列所構成的。

（2）生物的繁殖過程是由其基因的復制過程來完成的。同源染色體的交叉或變異會產生新的物種，使生物呈現新的性狀。

（3）對環境適應能力強的基因或染色體，比適應能力差的基因或染色體有更多的機會遺傳到下一代。

2.2.2　遺傳算法理論基礎

模式定理

模式定義：模式是描述種群中在位串的某些確定位置上具有相似性的位串子集的相似性模板。

不失一般性，考慮二值字符集｛0，1｝，由此可以產生通常的0、1字符串。增加一個符號“*”，稱作“通配符”，即“*”既可以當作“0”，也可以當作“1”。這樣，二值字符集｛0，1｝就擴展為三值字符集｛0，1，*｝，由此可以產生諸如0110，0 * 1 1 * *，* * 0 1 * 0之類的字符串。

基于三值字符集｛0，1，*｝所產生的能描述具有某些結構相似性的0、1字符串集的字符串，稱作模式。這里需要強調的是，“*”只是一個描述符，而并非遺傳算法中實際的運算符號，它僅僅是為了描述上的方便而引入的符號。

模式的概念可以簡明地描述為具有相似結構特點的個體編碼字符串。在引入了模式概念之后，遺傳算法的本質是對模式所進行的一系列運算，即通過選擇操作將當前群體中的優良模式遺傳到下一代群體中，通過交叉操作進行模式的重組，通過變異操作進行模式的突變。通過這些遺傳運算，一些較差的模式逐步被淘汰，而一些較好的模式逐步被遺傳和進化，最終就可以得到問題的最優解。

多個字符串中隱含著多個不同的模式。確切地說，長度為L的字符串，隱含著2L個不同的模式，而不同的模式所匹配的字符串的個數是不同的。為了反映這種確定性的差異，引入模式階概念。

模式階定義：模式H中確定位置的個數稱作該模式的模式階，記作O（H）。

比如，模式011*1*的階數為4，而模式0*****的階數為1。顯然，一個模式的階數越高，其樣本數就越少，因而其確定性就越高。但是，模式階并不能反映模式的所有性質；即使具有同階的模式，在遺傳操作下，也會有不同的性質。為此，引入定義距的概念。

定義距定義：在模式H中第一個確定位置和最后一個確定位置之間的距離稱作該模式的定義距，記作D（H）。

模式定理：在遺傳算法選擇、交叉和變異算子的作用下，具有低階、短定義距，并且其平均適應度高于群體平均適應度的模式在子代中將呈指數級增長［8］。

模式定理又稱為遺傳算法的基本定理。模式定理闡述了遺傳算法的理論基礎，說明了模式的增加規律，同時也對遺傳算法的應用提供了指導。根據模式定理，隨著遺傳算法的一代一代地進行，那些定義距短的、位數少的、高適應度的模式將越來越多，因而可期望最后得到的位串的性能越來越得到改善，并最終趨向全局的最優點。

模式的思路提供了一種簡單而有效的方法，使得能夠在有限字符表的基礎上討論有限長位串的嚴謹定義的相似性；而模式定理從理論上保證了遺傳算法是一個可以用來尋求最優可行解的優化過程。

積木塊假設

模式定理說明了具有某種結構特征的模式在遺傳進化過程中其樣本數目將呈指數級增長。這種模式定義為積木塊，它在遺傳算法中非常重要。

積木塊定義：具有低階、短定義距以及高平均適應度的模式稱作積木塊。

之所以稱之為積木塊，是由于遺傳算法的求解過程并不是在搜索空間中逐一地測試各個基因的枚舉組合，而是通過一些較好的模式，像搭積木一樣，將它們拼接在一起，從而逐漸地構造出適應度越來越高的個體編碼串。

模式定理說明了積木塊的樣本數呈指數級增長，亦即說明了用遺傳算法尋求最優樣本的可能性，但它并未指明遺傳算法一定能夠尋求到最優樣本；而積木塊假設說明了遺傳算法的這種能力。

積木塊假設：個體的積木塊通過選擇、交叉、變異等遺傳算子的作用，能夠相互結合在一起，形成高階、長距、高平均適應度的個體編碼串［9，10］。

積木塊假設說明了用遺傳算法求解各類問題的基本思想，即通過基因塊之間的相互拼接能夠產生出問題的更好的解，最終生成全局最優解。

從遺傳算法的模式定理得到：具有高適應度、低階、短定義矩的模式的數量會在種群的進化中呈指數級增長，從而保證了算法獲得最優解的一個必要條件。而另一方面，積木塊假設則指出：遺傳算法有能力使優秀的模式向著更優的方向進化，即遺傳算法有能力搜索到全局最優解。

2.2.3　遺傳算法的基本概念

簡單而言，遺傳算法使用群體搜索技術，將種群代表一組問題解，通過對當前種群施加選擇、交叉和變異等一系列遺傳操作來產生新一代的種群，并逐步使種群進化到包含近似最優解的狀態。由于遺傳算法是自然遺傳學與計算機科學相互滲透而形成的計算方法，所以遺傳算法中經常會使用一些有關自然進化的基礎術語［11］，其中的術語對應關系如表2.1所示。

群體和個體

群體是生物進化過程中的一個集團，表示可行解集。

個體是組成群體的單個生物體，表示可行解。

染色體和基因

染色體是包含生物體所有遺傳信息的化合物，表示可行解的編碼。

基因是控制生物體某種性狀（即遺傳信息）的基本單位，表示可行解編碼的分量。

遺傳編碼

遺傳編碼將優化變量轉化為基因的組合表示形式，優化變量的編碼機制有二進制編碼、十進制編碼（實數編碼）等。

二進制編碼

這里介紹一下二進制編碼的原理和實現。例如，求實數區間［0，4］上函數f（x）的最大值，傳統的方法是不斷調整自變量x本身的值，直到獲得函數最大值；遺傳算法則不對參數本身進行調整，而是首先將參數進行編碼，形成位串，再對位串進行進化操作。在這里，假設使用二進制編碼形式，我們可以由長度為6的位串表示變量x，即從“000000”到“111111”，并將中間的取值映射到實數區間［0，4］內。由于從整數上來看，6位長度的二進制編碼位串可以表示0～63，所以對應［0，4］的區間，每個相鄰值之間的階躍值為4/63≈0.0635，這個就是編碼精度。一般來說，編碼精度越高，所得到的解的質量也越高，意味著解更為優良；但同時，由于遺傳操作所需的計算量也更大，因此算法的耗時將更長。因而在解決實際問題時，編碼位數需要適當選擇。

實數編碼

基于二進制編碼的個體盡管操作方便，計算簡單，但也存在著一些難以克服的困難而無法滿足所有問題的要求。例如，對于高維、連續優化問題，由于從一個連續量離散化為一個二進制量本身存在誤差，使得算法很難求得精確解。而要提高解的精度又必須加長編碼串的長度，造成解空間擴大，算法效率下降。同時，二進制編碼也不利于反映所求問題的特定信息，對問題信息和知識利用得不充分也會阻礙算法效率的進一步提高。為了解決二進制編碼產生的問題，人們在解決一些數值優化問題（尤其是高維、連續優化問題）時，經常采用實數編碼方式。實數編碼的優點是計算精確度高，便于和經典連續優化算法結合，適用于數值優化問題；但其缺點是適用范圍有限，只能用于連續變量問題。

適應度

適應度即生物群體中個體適應生存環境的能力。在遺傳算法中，用來評價個體優劣的數學函數，稱為個體的適應度函數。

遺傳算法在進化搜索中基本上不用外部信息，僅以適應度函數為依據。它的目標函數不受連續可微的約束，且定義域可以為任意集合。對適應度函數的唯一要求是，針對輸入可計算出能進行比較的結果。這一特點使得遺傳算法應用范圍很廣。在具體應用中，適應度函數的設計要結合求解問題本身的要求而定。適應度函數評估是選擇操作的依據，適應度函數設計直接影響到遺傳算法的性能。常見的適應度函數構造方法主要有：目標函數映射成適應度函數，基于序的適應度函數等。

遺傳操作

遺傳操作是優選強勢個體的“選擇”、個體間交換基因產生新個體的“交叉”、個體基因信息突變而產生新個體的“變異”這三種變換的統稱。在生物進化過程中，一個群體中生物特性的保持是通過遺傳來繼承的。生物的遺傳主要是通過選擇、交叉、變異三個過程把當前父代群體的遺傳信息遺傳到下一代（子代）成員。與此對應，遺傳算法中最優解的搜索過程也模仿生物的這個進化過程，使用所謂的遺傳算子來實現，即選擇算子、交叉算子、變異算子。

（1）選擇算子：根據個體的適應度，按照一定的規則或方法，從第t代群體P（t）中選擇出一些優良的個體遺傳到下一代群體P（t+1）中。

其中，“輪盤賭”選擇法是遺傳算法中最早提出的一種選擇方法，由Holland提出，因為它簡單實用，所以被廣泛采用。它是一種基于比例的選擇，利用各個個體適應度所占比例的大小來決定其子代保留的可能性。若某個個體i的適應度為fi，種群大小為NP，則它被選取的概率表示為

個體適應度越大，則其被選擇的機會也越大；反之亦然。為了選擇交叉個體，需要進行多輪選擇。每一輪產生一個［0，1］內的均勻隨機數，將該隨機數作為選擇指針來確定被選個體。

（2）交叉算子：將群體P（t）中選中的各個個體隨機搭配，對每一對個體，以某一概率（交叉概率Pc）交換它們之間的部分染色體。通過交叉，遺傳算法的搜索能力得以飛躍提高。

交叉操作一般分為以下幾個步驟：首先，從交配池中隨機取出要交配的一對個體；然后，根據位串長度L，對要交配的一對個體，隨機選取［1，L-1］中的一個或多個整數k作為交叉位置；最后，根據交叉概率Pc實施交叉操作，配對個體在交叉位置處，相互交換各自的部分基因，從而形成新的一對個體。

（3）變異算子：對群體中的每個個體，以某一概率（變異概率Pm）將某一個或某一些基因座上的基因值改變為其他的等位基因值。根據個體編碼方式的不同，變異方式有：實值變異、二進制變異。對于二進制的變異，對相應的基因值取反；對于實值的變異，對相應的基因值用取值范圍內的其他隨機值替代。

變異操作的一般步驟為：首先，對種群中所有個體按事先設定的變異概率判斷是否進行變異；然后，對進行變異的個體隨機選擇變異位進行變異。

2.2.4　標準遺傳算法

標準遺傳算法（Standard Genetic Algorithm，SGA）是由美國J.H.Holland教授與他的同事和學生于1975年研究出的遺傳算法理論和方法［1］。20世紀60年代中期，Holland提出了位串編碼技術。這種編碼既適用于變異操作，又適用于交叉操作，并強調將交叉作為主要的遺傳操作。隨后，他將該算法應用到自然和人工系統的自適應行為的研究中。Holland早期有關遺傳算法的許多概念一直沿用至今，遺傳算法通用的編碼技術和簡單有效的遺傳操作為其后來的成功應用和廣泛應用奠定了基礎。

標準遺傳算法又稱為經典遺傳算法，它的優化變量由二進制編碼來描述，多個優化變量的二進制編碼串接在一起組成染色體，這種編碼既適用于交叉操作，又適用于變異操作。在創建初始群體時，代表個體的二進制串是在一定字長的限制下隨機產生的。交叉算子作用在按交叉概率選中的兩個染色體上，隨機選中交叉位置，將兩個染色體上對應于這些位置上的二進制數值進行交換，生成兩個新的個體；而變異算子作用在按變異概率隨機選中的個體上，一般是隨機選定變異位，將該位的二進制值取反，生成一個新的個體。

2.2.5　遺傳算法的特點

遺傳算法是模擬生物在自然環境中的遺傳和進化的過程而形成的一種并行、高效、全局搜索的方法，它主要有以下特點：

（1）遺傳算法以決策變量的編碼作為運算對象。這種對決策變量的編碼處理方式，使得在優化計算過程中可以借鑒生物學中染色體和基因等概念，模仿自然界中生物的遺傳和進化等的機理，方便地應用遺傳操作算子。特別是對一些只有代碼概念而無數值概念或很難有數值概念的優化問題，編碼處理方式更顯示出了其獨特的優越性。

（2）遺傳算法直接以目標函數值作為搜索信息。它僅使用由目標函數值變換來的適應度函數值，就可確定進一步的搜索方向和搜索范圍，而不需要目標函數的導數值等其他一些輔助信息。實際應用中很多函數無法或很難求導，甚至根本不存在導數，對于這類目標函數的優化和組合優化問題，遺傳算法就顯示了其高度的優越性，因為它避開了函數求導這個障礙。

（3）遺傳算法同時使用多個搜索點的搜索信息。遺傳算法對最優解的搜索過程，是從一個由很多個體所組成的初始群體開始的，而不是從單一的個體開始的。對這個群體所進行的選擇、交叉、變異等運算，產生出新一代的群體，其中包括了很多群體信息。這些信息可以避免搜索一些不必搜索的點，相當于搜索了更多的點，這是遺傳算法所特有的一種隱含并行性。

（4）遺傳算法是一種基于概率的搜索技術。遺傳算法屬于自適應概率搜索技術，其選擇、交叉、變異等運算都是以一種概率的方式來進行的，從而增加了其搜索過程的靈活性。雖然這種概率特性也會使群體中產生一些適應度不高的個體，但隨著進化過程的進行，新的群體中總會更多地產生出優良的個體。與其他一些算法相比，遺傳算法的魯棒性使得參數對其搜索效果的影響盡可能小。

（5）遺傳算法具有自組織、自適應和自學習等特性。當遺傳算法利用進化過程獲得信息自行組織搜索時，適應度大的個體具有較高的生存概率，并獲得更適應環境的基因結構。同時，遺傳算法具有可擴展性，易于同別的算法相結合，生成綜合雙方優勢的混合算法。

2.2.6　遺傳算法的改進方向

標準遺傳算法的主要本質特征，在于群體搜索策略和簡單的遺傳算子，這使得遺傳算法獲得了強大的全局最優解搜索能力、問題域的獨立性、信息處理的并行性、應用的魯棒性和操作的簡明性，從而成為一種具有良好適應性和可規模化的求解方法。但大量的實踐和研究表明，標準遺傳算法存在局部搜索能力差和“早熟”等缺陷，不能保證算法收斂。

在現有的許多文獻中出現了針對標準遺傳算法的各種改進算法，并取得了一定的成效［12-15］。它們主要集中在對遺傳算法的性能有重大影響的6個方面：編碼機制、選擇策略、交叉算子、變異算子、特殊算子和參數設計（包括群體規模、交叉概率、變異概率）等。

此外，遺傳算法與差分進化算法、免疫算法、蟻群算法、粒子群算法、模擬退火算法、禁忌搜索算法、神經網絡算法和量子計算等結合起來所構成的各種混合遺傳算法，可以綜合遺傳算法和其他算法的優點，提高運行效率和求解質量。