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

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

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

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

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

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

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

7、法的基本定理——模式定理 模式定理(Schema Theorem)，從而奠定了遺傳算法的理論基礎(chǔ)。 從而奠定了遺傳算法的理論基礎(chǔ)。模式定理揭示出了群體中的優(yōu)良個(gè)體 模式定理揭示出了群體中的優(yōu)良個(gè)體(較好的模式 較好的模式)的樣 的樣本數(shù)將以指數(shù)級(jí)規(guī)律增長(zhǎng)，因而從理論上保證了遺傳算法是一個(gè)可以用來(lái)尋找最優(yōu)可行解 本數(shù)將以指數(shù)級(jí)規(guī)律增長(zhǎng)，因而從理論上保證了遺傳算法是一個(gè)可以用來(lái)尋找最優(yōu)可行解的優(yōu)化過(guò)程。 的優(yōu)化過(guò)程。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 教授實(shí)現(xiàn)了第一個(gè)基于遺傳算法的機(jī)器學(xué)習(xí)系統(tǒng) 教授實(shí)現(xiàn)了第一個(gè)基于遺傳算法的機(jī)器學(xué)習(xí)系統(tǒng)——分類器系統(tǒng) 分類器系統(tǒng)(Classifi

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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