第2章　遺傳算法

2.1　引言

前已述及，遺傳算法（Genetic Algorithm，GA）是模擬生物在自然環境中的遺傳和進化的過程，從而形成的自適應全局優化搜索算法。它借用了生物遺傳學的觀點，通過自然選擇、遺傳和變異等作用機制，實現各個個體適應性的提高。遺傳算法最早由美國的J.H.Holland教授提出［1］，起源于20世紀60年代人們對自然和人工自適應系統的研究；70年代，K.A.De Jong基于遺傳算法的思想，在計算機上進行了大量的純數值函數優化計算試驗［2］；80年代，遺傳算法由D.E.Goldberg在一系列研究工作的基礎上歸納總結而成［3］。

20世紀90年代以后，遺傳算法作為一種高效、實用、魯棒性強的優化技術，發展極為迅速，在機器學習、模式識別、神經網絡、控制系統優化及社會科學等不同領域得到廣泛應用，引起了許多學者的廣泛關注。進入21世紀，以不確定性、非線性、時間不可逆為內涵的復雜性科學成為一個研究熱點。遺傳算法因能有效地求解NP（Non-deterministic Polynomial）問題以及非線性、多峰函數優化和多目標優化問題，得到了眾多學科學者的高度重視，同時這也極大地推動了遺傳算法理論研究和實際應用的不斷深入與發展。目前，在世界范圍內已掀起關于遺傳算法的研究與應用熱潮［4-6］。

遺傳算法借鑒了達爾文的進化論和孟德爾的遺傳學說。其本質是一種并行、高效、全局搜索的方法，它能在搜索過程中自動獲取和積累有關搜索空間的知識，并自適應地控制搜索過程以求得最優解。遺傳算法操作：使用“適者生存”的原則，在潛在的解決方案種群中逐次產生一個近似最優的方案。在遺傳算法的每一代中，根據個體在問題域中的適應度值和從自然遺傳學中借鑒來的再造方法進行個體選擇，產生一個新的近似解。這個過程導致種群中個體的進化，得到的新個體比原個體更能適應環境，就像自然界中的改造一樣［7］。

同傳統的優化算法相比，遺傳算法具有對參數的編碼進行操作、不需要推導和附加信息、尋優規則非確定性、自組織性、自適應性和自學習性等特點。當染色體結合時，雙親的遺傳基因的結合使得子女保持父母的特征；當染色體結合后，隨機的變異會造成子代同父代的不同。