遺傳算法理論與應(yīng)用

1、遺傳算法理論與應(yīng)用 遺傳算法理論與應(yīng)用遺傳算法 遺傳算法(genetic algorithms, GA)是人工智能的重要新分支，是基于達爾文進化論，在 是人工智能的重要新分支，是基于達爾文進化論，在微型計算機上模擬生命進化機制而發(fā)展起來的一門新學科。它根據(jù) 微型計算機上模擬生命進化機制而發(fā)展起來的一門新學科。它根據(jù)適者生存、優(yōu)勝劣汰 適者生存、優(yōu)勝劣汰等自然進化規(guī)則來進行搜索計算和問題求解。 自然進化規(guī)則來進行搜索計算和問題求解。遺傳算

2、法是模擬生物在自然環(huán)境中的遺傳和進 遺傳算法是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。 化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。它最早由美國密執(zhí)安大學的 它最早由美國密執(zhí)安大學的 Holland教授提出，起源于 教授提出，起源于 60 年代對自然和人工自適應(yīng)系統(tǒng)的研究。遺傳算法對許多用傳統(tǒng)數(shù)學難 年代對自然和人工自適應(yīng)系統(tǒng)的研究。遺傳算法對許多用傳統(tǒng)數(shù)學難以解決或明顯失效的非常復雜問題，特別是

3、以解決或明顯失效的非常復雜問題，特別是最優(yōu)化問題 最優(yōu)化問題，GA 提供了一個行之有效的新途 提供了一個行之有效的新途徑。 徑。一.遺傳算法的發(fā)展 遺傳算法的發(fā)展遺傳算法起源于對生物系統(tǒng)所進行的計算機模擬研究。早在 遺傳算法起源于對生物系統(tǒng)所進行的計算機模擬研究。早在 20 世紀 世紀 40 年代，就有學 年代，就有學者開始如何利用計算機進行生物模擬的技術(shù)，他們從生物學的角度進行了生物的進化過程 者開始如何利用計算機進行生物模擬的技術(shù)，

4、他們從生物學的角度進行了生物的進化過程模擬、遺傳過程模擬等研究工作。進入 模擬、遺傳過程模擬等研究工作。進入 60 年代后，美國密執(zhí)安大學的 年代后，美國密執(zhí)安大學的 Holland 教授及其學 教授及其學生們受到這種生物模擬技術(shù)的啟發(fā)，創(chuàng)造出了一種基于生物遺傳和進化機制的適合于復雜 生們受到這種生物模擬技術(shù)的啟發(fā)，創(chuàng)造出了一種基于生物遺傳和進化機制的適合于復雜系統(tǒng)優(yōu)化計算的自適應(yīng)概率優(yōu)化技術(shù) 系統(tǒng)優(yōu)化計算的自適應(yīng)概率優(yōu)化技術(shù)——遺傳算

5、法。下面是在遺傳算法的發(fā)展進程中一些 遺傳算法。下面是在遺傳算法的發(fā)展進程中一些關(guān)鍵人物所做出的一些主要貢獻。 關(guān)鍵人物所做出的一些主要貢獻。1.J．H．Holland20 世紀 世紀 60 年代， 年代，Holland 認識到了生物的遺傳和自然進化現(xiàn)象與人工自適應(yīng)系統(tǒng)的相 認識到了生物的遺傳和自然進化現(xiàn)象與人工自適應(yīng)系統(tǒng)的相似關(guān)系，運用生物遺傳和進化的思想來研究自然和人工自適應(yīng)系統(tǒng)的生成以及它們與環(huán)境 似關(guān)系，運用生物遺傳和進化的思想

6、來研究自然和人工自適應(yīng)系統(tǒng)的生成以及它們與環(huán)境的關(guān)系，提出在研究和設(shè)計人工自適應(yīng)系統(tǒng)時，可以借鑒生物遺傳的機制，以群體的方法 的關(guān)系，提出在研究和設(shè)計人工自適應(yīng)系統(tǒng)時，可以借鑒生物遺傳的機制，以群體的方法進行自適應(yīng)搜索，并且充分認識到了交叉、變異等運算策略在自適應(yīng)系統(tǒng)中的重要性。 進行自適應(yīng)搜索，并且充分認識到了交叉、變異等運算策略在自適應(yīng)系統(tǒng)中的重要性。70 年代， 年代，Holland 教授提出了遺傳算法的基本定理 教授提出了遺傳算

7、法的基本定理——模式定理 模式定理(Schema Theorem)，從而奠定了遺傳算法的理論基礎(chǔ)。 從而奠定了遺傳算法的理論基礎(chǔ)。模式定理揭示出了群體中的優(yōu)良個體 模式定理揭示出了群體中的優(yōu)良個體(較好的模式 較好的模式)的樣 的樣本數(shù)將以指數(shù)級規(guī)律增長，因而從理論上保證了遺傳算法是一個可以用來尋找最優(yōu)可行解 本數(shù)將以指數(shù)級規(guī)律增長，因而從理論上保證了遺傳算法是一個可以用來尋找最優(yōu)可行解的優(yōu)化過程。 的優(yōu)化過程。1975 年， 年，Ho

8、lland 出版了第一本系統(tǒng)論述遺傳算法和人工自適應(yīng)系統(tǒng)的專著 出版了第一本系統(tǒng)論述遺傳算法和人工自適應(yīng)系統(tǒng)的專著《自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)性 《自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)性(Adaptation in Natural and Artificial Systems)》 。80 年代， 年代，Holland 教授實現(xiàn)了第一個基于遺傳算法的機器學習系統(tǒng) 教授實現(xiàn)了第一個基于遺傳算法的機器學習系統(tǒng)——分類器系統(tǒng) 分類器系統(tǒng)(Classifi

9、er Systems，簡稱 ，簡稱 CS)，開創(chuàng)了基于遺傳算法的機器學習的新概念，為分類器系統(tǒng) ，開創(chuàng)了基于遺傳算法的機器學習的新概念，為分類器系統(tǒng)構(gòu)造出了一個完整的框架。 構(gòu)造出了一個完整的框架。2.J．D．Bagley1967 年， 年，Holland 的學生 的學生 Bagley 在其博士論文中首次提出了“遺傳算法”一詞，并發(fā) 在其博士論文中首次提出了“遺傳算法”一詞，并發(fā)表了遺傳算法應(yīng)用方面的第一篇論文。他發(fā)展了復制、交叉、變異

10、、顯性、倒位等遺傳算 表了遺傳算法應(yīng)用方面的第一篇論文。他發(fā)展了復制、交叉、變異、顯性、倒位等遺傳算子，在個體編碼上使用了雙倍體的編碼方法。這些都與目前遺傳算法中所使用的算子和方 子，在個體編碼上使用了雙倍體的編碼方法。這些都與目前遺傳算法中所使用的算子和方法相類似。他還敏銳地意識到了在遺傳算法執(zhí)行的不同階段可以使用不同的選擇率，這將 法相類似。他還敏銳地意識到了在遺傳算法執(zhí)行的不同階段可以使用不同的選擇率，這將有利于防止遺傳算法的早熟

11、現(xiàn)象，從而創(chuàng)立了 有利于防止遺傳算法的早熟現(xiàn)象，從而創(chuàng)立了自適應(yīng)遺傳算法 自適應(yīng)遺傳算法的概念。 的概念。3.K．A．De Jong1975 年， 年，De Jong 在其博士論文中結(jié)合模式定理進行了大量的純數(shù)值函數(shù)優(yōu)化計算實 在其博士論文中結(jié)合模式定理進行了大量的純數(shù)值函數(shù)優(yōu)化計算實驗，樹立了遺傳算法的工作框架，得到了一些重要且具有指導意義的結(jié)論。例如，對于規(guī) 驗，樹立了遺傳算法的工作框架，得到了一些重要且具有指導意義的結(jié)論。例如，對

12、于規(guī)模在 模在 50~100 的群體，經(jīng)過 的群體，經(jīng)過 10~20 代的進化，遺傳算法都能以很高的概率找到最優(yōu)或近似最 代的進化，遺傳算法都能以很高的概率找到最優(yōu)或近似最優(yōu)解。他推薦了在大多數(shù)優(yōu)化問題中都較適用的遺傳算法的參數(shù)，還建立了著名的 優(yōu)解。他推薦了在大多數(shù)優(yōu)化問題中都較適用的遺傳算法的參數(shù)，還建立了著名的 De Jong 五函數(shù)測試平臺 五函數(shù)測試平臺，定義了評價遺傳算法性能的在線指標和離線指標。 ，定義了評價遺傳算法性能的

13、在線指標和離線指標。4.D．J．Goldberg（7）遺傳算法具有并行計算的特點，因而可通過大規(guī)模并行計算來提高計算速度。 遺傳算法具有并行計算的特點，因而可通過大規(guī)模并行計算來提高計算速度。三．遺傳算法的應(yīng)用 三．遺傳算法的應(yīng)用遺傳算法提供了一種求解復雜雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領(lǐng) 遺傳算法提供了一種求解復雜雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領(lǐng)域，對問題的種類有很強的魯棒性，所以廣泛應(yīng)用于很多學科。下面

14、是遺傳算法的一些主 域，對問題的種類有很強的魯棒性，所以廣泛應(yīng)用于很多學科。下面是遺傳算法的一些主要應(yīng)用領(lǐng)域： 要應(yīng)用領(lǐng)域：（1）函數(shù)優(yōu)化。 函數(shù)優(yōu)化。函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對遺傳算法進行性能評價 函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對遺傳算法進行性能評價的常用算例。很多人構(gòu)造出了各種各樣的復雜形式的測試函數(shù)， 的常用算例。很多人構(gòu)造出了各種各樣的復雜形式的測試函數(shù)，有連續(xù)函數(shù)也有離散函 有連續(xù)函數(shù)也有離散函數(shù)，有凸函

15、數(shù)也有凹函數(shù)，有低維函數(shù)也有高維函數(shù)，有確定函數(shù)也有隨機函數(shù)，有單峰 數(shù)，有凸函數(shù)也有凹函數(shù)，有低維函數(shù)也有高維函數(shù)，有確定函數(shù)也有隨機函數(shù)，有單峰值函數(shù)也有多峰值函數(shù) 值函數(shù)也有多峰值函數(shù)等。用這些幾何特性各具特色的函數(shù)來評價遺傳算法的性能，更能 等。用這些幾何特性各具特色的函數(shù)來評價遺傳算法的性能，更能反映算法的本質(zhì)效果。而對于一些非線性、多模型、多目標的函數(shù)優(yōu)化問題，用其他優(yōu)化 反映算法的本質(zhì)效果。而對于一些非線性、多模型、多目標

16、的函數(shù)優(yōu)化問題，用其他優(yōu)化方法較難求解，而遺傳算法卻可以方便地得到較好的結(jié)果。 方法較難求解，而遺傳算法卻可以方便地得到較好的結(jié)果。（2）組合優(yōu)化。 組合優(yōu)化。隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴大，有時在 隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴大，有時在目前的計算機上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。對這類復雜問題，人們已 目前的計算機上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。對這類復雜問題，人們已

17、意識到應(yīng)把主要精力放在尋求其 意識到應(yīng)把主要精力放在尋求其滿意解 滿意解上，而遺傳算法是尋求這種 上，而遺傳算法是尋求這種滿意解 滿意解的最佳工具之 的最佳工具之一。實踐證明，遺傳算法對于組合優(yōu)化中的 一。實踐證明，遺傳算法對于組合優(yōu)化中的 NP 完全問題非常有效。例如， 完全問題非常有效。例如，遺傳算法已經(jīng) 遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、圖形劃分問題等方面得到成功的應(yīng)用 在求解旅行商問題、背包問題、裝箱問題、圖形劃

18、分問題等方面得到成功的應(yīng)用。（3）生產(chǎn)調(diào)度問題。 生產(chǎn)調(diào)度問題。生產(chǎn)調(diào)度問題在很多情況下所建立起來的數(shù)學模型難以精確求 生產(chǎn)調(diào)度問題在很多情況下所建立起來的數(shù)學模型難以精確求解，即使經(jīng)過一些簡化之后可以進行求解，也會因簡化得太多而使得求解結(jié)果與實際相差 解，即使經(jīng)過一些簡化之后可以進行求解，也會因簡化得太多而使得求解結(jié)果與實際相差甚遠。而目前在現(xiàn)實生產(chǎn)中也主要是靠一些經(jīng)驗來進行調(diào)度。 甚遠。而目前在現(xiàn)實生產(chǎn)中也主要是靠一些經(jīng)驗來進行調(diào)度

19、?，F(xiàn)在遺傳算法已成為解決復 現(xiàn)在遺傳算法已成為解決復雜調(diào)度問題的有效工具，在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分 雜調(diào)度問題的有效工具，在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用。 配等方面遺傳算法都得到了有效的應(yīng)用。（4）自動控制。 自動控制。在自動控制領(lǐng)域中有很多與優(yōu)化相關(guān)的問題需要求解，遺傳算法已在 在自動控制領(lǐng)域中有很多與優(yōu)化相關(guān)的問題需要求解，遺傳算法已在其中得

20、到了初步的應(yīng)用，并顯示出了良好的效果。例如 其中得到了初步的應(yīng)用，并顯示出了良好的效果。例如用遺傳算法進行航空控制系統(tǒng)的優(yōu) 用遺傳算法進行航空控制系統(tǒng)的優(yōu)化、使用遺傳算法設(shè)計空間交會控制器、基于遺傳算法的模糊控制器的優(yōu)化設(shè)計、基于遺 化、使用遺傳算法設(shè)計空間交會控制器、基于遺傳算法的模糊控制器的優(yōu)化設(shè)計、基于遺傳算法的參數(shù)辨識、基于遺傳算法的模糊控制規(guī)則的學習、利用遺傳算法進行人工神經(jīng)網(wǎng) 傳算法的參數(shù)辨識、基于遺傳算法的模糊控制規(guī)則的學

21、習、利用遺傳算法進行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計和權(quán)值學習等 絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計和權(quán)值學習等，都顯示出了遺傳算法在這些領(lǐng)域中應(yīng)用的可能性。 ，都顯示出了遺傳算法在這些領(lǐng)域中應(yīng)用的可能性。（5）機器人學。 機器人學。機器人是一類復雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就 機器人是一類復雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來自于對人工自適應(yīng)系統(tǒng)的研究，所以機器人學理所當然地成為遺傳算法的一個重要應(yīng)用 來自于對人工自適應(yīng)系統(tǒng)的研究

22、，所以機器人學理所當然地成為遺傳算法的一個重要應(yīng)用領(lǐng)域。例如， 領(lǐng)域。例如，遺傳算法已經(jīng)在移動機器人路徑規(guī)劃、關(guān)節(jié)機器人運動軌跡規(guī)劃、機器人逆 遺傳算法已經(jīng)在移動機器人路徑規(guī)劃、關(guān)節(jié)機器人運動軌跡規(guī)劃、機器人逆運動學求解、細胞機器人的結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方面得到研究和應(yīng)用。 運動學求解、細胞機器人的結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方面得到研究和應(yīng)用。（6）圖像處理。 圖像處理。圖像處理是計算機視覺中的一個重要研究領(lǐng)域。在圖像處理過程中， 圖像處理是

23、計算機視覺中的一個重要研究領(lǐng)域。在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免地會存在一些誤差，這些誤差會影響圖像處理的 如掃描、特征提取、圖像分割等不可避免地會存在一些誤差，這些誤差會影響圖像處理的效果。如何使這些誤差最小是使計算機視覺達到實用化的重要要求。遺傳算法在這些圖像 效果。如何使這些誤差最小是使計算機視覺達到實用化的重要要求。遺傳算法在這些圖像處理中的優(yōu)化計算方面找到了用武之地，目前已在模式識別、圖像恢復、圖像邊緣特

24、征提 處理中的優(yōu)化計算方面找到了用武之地，目前已在模式識別、圖像恢復、圖像邊緣特征提取等方面得到了應(yīng)用。 取等方面得到了應(yīng)用。（7）人工生命。 人工生命。人工生命是用計算機、機械等人工媒體模擬或構(gòu)造出的具有自然生物 人工生命是用計算機、機械等人工媒體模擬或構(gòu)造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。自組織能力和自學能力是人工生命的兩大主要特征。人工生命 系統(tǒng)特有行為的人造系統(tǒng)。自組織能力和自學能力是人工生命的兩大主要特征。人工生命與遺傳

25、算法有著密切的關(guān)系，基于遺傳算法的進化模型是研究人工生命現(xiàn)象的重要基礎(chǔ)理 與遺傳算法有著密切的關(guān)系，基于遺傳算法的進化模型是研究人工生命現(xiàn)象的重要基礎(chǔ)理論。雖然人工生命的研究尚處于啟蒙階段，但遺傳算法已在其進化模型、學習模型、行為 論。雖然人工生命的研究尚處于啟蒙階段，但遺傳算法已在其進化模型、學習模型、行為模型、自組織模型等方面顯示出了初步的應(yīng)用能力，并且必將得到更為深入的應(yīng)用和發(fā) 模型、自組織模型等方面顯示出了初步的應(yīng)用能力，并且必