遺傳算法最新課件

1、遺傳算法最新遺傳算法遺傳算法Genetic AlgorithmGA遺傳算法最新遺傳算法是什么？遺傳算法是什么？遺傳算法遺傳算法（Genetic Algorithm，GA）是進(jìn)化計算的一個分支，是進(jìn)化計算的一個分支，是一種模擬自然界生物進(jìn)化過程的隨機搜索算法。是一種模擬自然界生物進(jìn)化過程的隨機搜索算法。 遺傳算法的思想來源是怎樣的？遺傳算法的思想來源是怎樣的？它由誰提出的？它由誰提出的？GA思想源于思想源于自然界自然界“自然選擇自然選擇”和和“優(yōu)勝劣汰優(yōu)勝劣汰”的進(jìn)化規(guī)律，的進(jìn)化規(guī)律，通過模擬生物進(jìn)化中的自然選擇和交配變異尋找問題的全局最優(yōu)解。通過模擬生物進(jìn)化中的自然選擇和交配變異尋找問題的全局

2、最優(yōu)解。它最早由美國密歇根大學(xué)教授它最早由美國密歇根大學(xué)教授John H. Holland提出，提出，現(xiàn)在已經(jīng)廣泛應(yīng)用于各種工程領(lǐng)域的優(yōu)化問題之中?，F(xiàn)在已經(jīng)廣泛應(yīng)用于各種工程領(lǐng)域的優(yōu)化問題之中。遺傳算法最新簡介簡介l遺傳算法遺傳算法l借鑒生物界借鑒生物界自然選擇原理自然選擇原理和和自然遺傳機自然遺傳機制制而形成的一種迭代式自適應(yīng)概率性全而形成的一種迭代式自適應(yīng)概率性全局優(yōu)化搜索算法。局優(yōu)化搜索算法。l它模擬自然界中生物進(jìn)化的發(fā)展規(guī)律，它模擬自然界中生物進(jìn)化的發(fā)展規(guī)律，在人工系統(tǒng)中實現(xiàn)待定目標(biāo)的優(yōu)化。在人工系統(tǒng)中實現(xiàn)待定目標(biāo)的優(yōu)化。遺傳算法最新l基本特點基本特點l簡單易懂、通用、魯棒性強、適合簡

3、單易懂、通用、魯棒性強、適合并行處理，可用于解決各種復(fù)雜優(yōu)并行處理，可用于解決各種復(fù)雜優(yōu)化問題化問題l鼻祖鼻祖l美國美國 密歇根密歇根(Michigan)大學(xué)大學(xué) lJohn Holland教授教授遺傳算法最新一一 遺傳算法的基本流程遺傳算法的基本流程二二 模式定理和隱含并行性模式定理和隱含并行性四四 遺傳算法關(guān)鍵參數(shù)和操作設(shè)計遺傳算法關(guān)鍵參數(shù)和操作設(shè)計五五 遺傳算法的改進(jìn)及其并行性遺傳算法的改進(jìn)及其并行性六六 算法的實現(xiàn)及應(yīng)用算法的實現(xiàn)及應(yīng)用三三 收斂性分析收斂性分析目錄遺傳算法最新引言引言在人類歷史上，學(xué)習(xí)和模擬的例子不勝枚舉：在人類歷史上，學(xué)習(xí)和模擬的例子不勝枚舉：模擬飛禽，人類可以翱游

4、太空；模擬飛禽，人類可以翱游太空；模擬游魚，人類可以橫渡海洋；模擬游魚，人類可以橫渡海洋；模擬昆蟲，人類可以縱觀千里；模擬昆蟲，人類可以縱觀千里；模擬大腦，人類創(chuàng)造影響世界發(fā)展的計算機；模擬大腦，人類創(chuàng)造影響世界發(fā)展的計算機； 第一節(jié)第一節(jié) GA的基本流程的基本流程遺傳算法最新 遺傳算法遺傳算法就是一種更為宏觀意義下的模擬，它就是一種更為宏觀意義下的模擬，它模仿的機制是一切生命和智能的產(chǎn)生與進(jìn)化過程模仿的機制是一切生命和智能的產(chǎn)生與進(jìn)化過程.模擬模擬達(dá)爾文達(dá)爾文“優(yōu)勝劣汰、適者生存優(yōu)勝劣汰、適者生存”的原理激的原理激勵好的結(jié)構(gòu)勵好的結(jié)構(gòu)模擬模擬孟德爾孟德爾遺傳變異理論在迭代過程中保持已遺傳變異

5、理論在迭代過程中保持已有結(jié)構(gòu)，同時尋找更好的結(jié)構(gòu)有結(jié)構(gòu)，同時尋找更好的結(jié)構(gòu) 70年代初期由美國年代初期由美國Michigan大學(xué)的大學(xué)的Holland教教授發(fā)展起來的。授發(fā)展起來的。 1975年年Holland的專著的專著Adaptation in natural and Artificial systems出版為標(biāo)志。出版為標(biāo)志。遺傳算法最新 達(dá)爾文進(jìn)化論達(dá)爾文進(jìn)化論現(xiàn)代遺傳學(xué)現(xiàn)代遺傳學(xué)生物模擬技術(shù)生物模擬技術(shù)遺傳算法最新一、一、算法提出依據(jù)l達(dá)爾文達(dá)爾文 (Darwin) 的的進(jìn)化論進(jìn)化論l英國自然學(xué)家，進(jìn)化論的奠基人。英國自然學(xué)家，進(jìn)化論的奠基人。l青年時期在愛丁堡大學(xué)和劍橋大學(xué)學(xué)習(xí)，特

6、青年時期在愛丁堡大學(xué)和劍橋大學(xué)學(xué)習(xí)，特別喜愛博物學(xué)。大學(xué)畢業(yè)時別喜愛博物學(xué)。大學(xué)畢業(yè)時22歲，以博物學(xué)歲，以博物學(xué)者的身份登上英國海軍艦艇貝格爾號者的身份登上英國海軍艦艇貝格爾號(HMS Beagles)，進(jìn)行了，進(jìn)行了5年（年（1831年年1836年）探年）探險航行。險航行。l他觀察了距厄瓜多爾西岸他觀察了距厄瓜多爾西岸950km的加拉帕戈斯的加拉帕戈斯群島上的海龜和地雀。群島上的海龜和地雀。l1859年，達(dá)爾文出版了年，達(dá)爾文出版了物種起源物種起源這一劃這一劃時代的著作。這一著作終結(jié)了神創(chuàng)論關(guān)于上時代的著作。這一著作終結(jié)了神創(chuàng)論關(guān)于上帝創(chuàng)造人類的統(tǒng)治地位，使生物學(xué)開始成為帝創(chuàng)造人類的統(tǒng)治地

7、位，使生物學(xué)開始成為科學(xué)，對人類的思想解放有巨大的意義?？茖W(xué)，對人類的思想解放有巨大的意義。遺傳算法最新l達(dá)爾文達(dá)爾文 (Darwin) 的進(jìn)化論的進(jìn)化論l進(jìn)化論是生物學(xué)最基本的理論之一。生物學(xué)上的所謂進(jìn)化論是生物學(xué)最基本的理論之一。生物學(xué)上的所謂進(jìn)化進(jìn)化或者演化（或者演化（Evolution），舊稱），舊稱“天演天演”，是指生物是指生物在變異、遺傳與自然選擇作用下的演變發(fā)展，物種淘在變異、遺傳與自然選擇作用下的演變發(fā)展，物種淘汰和物種產(chǎn)生過程汰和物種產(chǎn)生過程。地球上原來無生命，大約在。地球上原來無生命，大約在30多多億年前，在一定的條件下，形成了原始生命，其后，億年前，在一定的條件下，形成了

8、原始生命，其后，生物不斷的進(jìn)化，直至今天世界上存在著生物不斷的進(jìn)化，直至今天世界上存在著170多萬個物多萬個物種。種。l達(dá)爾文用達(dá)爾文用自然選擇自然選擇來解釋生物進(jìn)化。自然選擇就是來解釋生物進(jìn)化。自然選擇就是指指生物由于環(huán)境中某些因素的影響而使得有利于一些個生物由于環(huán)境中某些因素的影響而使得有利于一些個體的生存，而不利于另外一些個體生存的演化過程體的生存，而不利于另外一些個體生存的演化過程。l簡而言之簡而言之物競天擇，適者生存物競天擇，適者生存遺傳算法最新l達(dá)爾文的自然選擇說達(dá)爾文的自然選擇說遺傳（遺傳（heredity）：子代和父代具有相：子代和父代具有相 同或相似的性狀，保證物種的穩(wěn)定性；

9、同或相似的性狀，保證物種的穩(wěn)定性；變異（變異（variation）：子代與父代，子代不同個體：子代與父代，子代不同個體之間總有差異，是生命多樣性的根源；之間總有差異，是生命多樣性的根源；生存斗爭和適者生存生存斗爭和適者生存：具有適應(yīng)性變異的個體被：具有適應(yīng)性變異的個體被保留，不具適應(yīng)性變異的個體被淘汰。保留，不具適應(yīng)性變異的個體被淘汰。 自然選擇過程是長期的、緩慢的、連續(xù)的過程。自然選擇過程是長期的、緩慢的、連續(xù)的過程。 遺傳算法最新l孟德爾孟德爾(Mendel) 的的遺傳學(xué)遺傳學(xué)l1822年年7月月22日孟德爾生于奧地利的海因岑多夫（今捷日孟德爾生于奧地利的海因岑多夫（今捷克的海恩塞斯）。他

10、于克的海恩塞斯）。他于1840年畢業(yè)于特羅保的預(yù)科學(xué)年畢業(yè)于特羅保的預(yù)科學(xué)校，進(jìn)入奧爾米茨哲學(xué)院學(xué)習(xí)。校，進(jìn)入奧爾米茨哲學(xué)院學(xué)習(xí)。1843年因家貧而輟學(xué)，年因家貧而輟學(xué)，同年同年10月到奧古斯丁修道院做月到奧古斯丁修道院做修道士修道士。1847年被任命年被任命為為神父神父。1849年受委派到茨納伊姆中學(xué)任希臘文和數(shù)年受委派到茨納伊姆中學(xué)任希臘文和數(shù)學(xué)學(xué)代課教師代課教師。1851年年1853年在維也納大學(xué)學(xué)習(xí)物理、年在維也納大學(xué)學(xué)習(xí)物理、化學(xué)、數(shù)學(xué)、動物學(xué)和植物學(xué)。化學(xué)、數(shù)學(xué)、動物學(xué)和植物學(xué)。1853年，他從維也納年，他從維也納大學(xué)畢業(yè)回修道院。大學(xué)畢業(yè)回修道院。1854年被委派到布呂恩技術(shù)學(xué)校

11、年被委派到布呂恩技術(shù)學(xué)校任物理學(xué)和植物學(xué)的任物理學(xué)和植物學(xué)的代理教師代理教師。并在那里工作了。并在那里工作了14年。年。1884年年1月月6日卒于布呂恩日卒于布呂恩(今捷克的布爾諾今捷克的布爾諾)。l科學(xué)遺傳學(xué)的奠基人科學(xué)遺傳學(xué)的奠基人l代表作代表作 1865植物雜交試驗植物雜交試驗遺傳算法最新l孟德爾孟德爾(Mendel) 的遺傳學(xué)的遺傳學(xué)l遺傳學(xué)遺傳學(xué)是研究基因及它們在生物遺傳中的作用的科學(xué)是研究基因及它們在生物遺傳中的作用的科學(xué)分支分支。遺傳學(xué)最早的應(yīng)用在有歷史記載之初就已經(jīng)出。遺傳學(xué)最早的應(yīng)用在有歷史記載之初就已經(jīng)出現(xiàn)了，即馴養(yǎng)動物及植物的選擇育種。遺傳信息以化現(xiàn)了，即馴養(yǎng)動物及植物的

12、選擇育種。遺傳信息以化學(xué)方法被編碼在學(xué)方法被編碼在DNA（脫氧核糖核酸）中。（脫氧核糖核酸）中。l1865年，孟德爾首先記錄了豌豆某些特性的遺傳模式，年，孟德爾首先記錄了豌豆某些特性的遺傳模式，表明它們遵守簡單的統(tǒng)計學(xué)規(guī)律。由他的統(tǒng)計分析中，表明它們遵守簡單的統(tǒng)計學(xué)規(guī)律。由他的統(tǒng)計分析中，孟德爾定義了一個概念：孟德爾定義了一個概念：遺傳的基本單位遺傳的基本單位等位基等位基因因。他描述的等位基因類于現(xiàn)在的基因。直到孟德爾。他描述的等位基因類于現(xiàn)在的基因。直到孟德爾死后，死后，20世紀(jì)初另外的科學(xué)家重新發(fā)現(xiàn)這個定律之后，世紀(jì)初另外的科學(xué)家重新發(fā)現(xiàn)這個定律之后，孟德爾的工作的重要性才被大家了解。孟德

13、爾的工作的重要性才被大家了解。l改變一個生物的改變一個生物的DNA從而達(dá)到某種目的被稱為從而達(dá)到某種目的被稱為基因工基因工程程。遺傳算法最新l遺傳學(xué)時間表遺傳學(xué)時間表l1859年年 查爾斯查爾斯達(dá)爾文發(fā)表了達(dá)爾文發(fā)表了物種起源物種起源 l1865年年 格雷戈爾格雷戈爾孟德爾發(fā)表文章孟德爾發(fā)表文章植物雜交試驗植物雜交試驗 l1903年年 發(fā)現(xiàn)染色體是發(fā)現(xiàn)染色體是遺傳單位遺傳單位 l1905年年 英國科學(xué)家威廉英國科學(xué)家威廉貝特森在給亞當(dāng)貝特森在給亞當(dāng)塞奇威克的一封信中塞奇威克的一封信中提出了提出了“遺傳學(xué)遺傳學(xué)”這個名詞。這個名詞。 l1927年年 基因的物理變化叫做基因的物理變化叫做基因突變基

14、因突變 l1931年年 交叉互換導(dǎo)致了交叉互換導(dǎo)致了基因重組基因重組 l1944年年 奧斯瓦德奧斯瓦德西奧多西奧多艾弗里，科林艾弗里，科林麥克勞德和麥克林麥克勞德和麥克林麥克麥克卡提分離出卡提分離出遺傳物質(zhì)遺傳物質(zhì)DNA（那時叫做遺傳要素）（那時叫做遺傳要素） l1953年年 詹姆斯詹姆斯沃森和弗朗西斯沃森和弗朗西斯克里克提出了克里克提出了DNA的雙螺旋結(jié)的雙螺旋結(jié)構(gòu)構(gòu) l1958年年 Meselson-Stahl試驗證明試驗證明DNA是半保留復(fù)制是半保留復(fù)制的的 l1961年年 提出三聯(lián)體提出三聯(lián)體遺傳密碼遺傳密碼 l1977年年 DNA測序測序 l2001年年 人類基因組序列草圖人類基因組

15、序列草圖由人類基因組計劃和賽雷拉基因公由人類基因組計劃和賽雷拉基因公司同時完成司同時完成 遺傳算法最新群體群體競爭競爭淘汰的淘汰的群群 體體變異變異子群子群種群種群婚配婚配生物遺傳學(xué)基礎(chǔ)生物遺傳學(xué)基礎(chǔ)遺傳算法最新父代染色體1父代染色體2子代染色體1子代染色體2遺傳算法最新 l遺傳學(xué)基本概念與術(shù)語遺傳學(xué)基本概念與術(shù)語染色體（染色體（chromosome）：遺傳物質(zhì)的載體；：遺傳物質(zhì)的載體；脫氧核糖核酸（脫氧核糖核酸（DNA）：大分子有機聚合物，：大分子有機聚合物，雙螺旋結(jié)構(gòu)；雙螺旋結(jié)構(gòu)；遺傳因子（遺傳因子（gene）：DNA或或RNA長鏈結(jié)構(gòu)中占長鏈結(jié)構(gòu)中占有一定位置的基本遺傳單位；有一定位置的

16、基本遺傳單位； 遺傳算法最新l遺傳算法中常用術(shù)語遺傳算法中常用術(shù)語基因（遺傳因子）基因（遺傳因子）：染色體的一個片段，通常：染色體的一個片段，通常為單個參數(shù)的編碼值。為單個參數(shù)的編碼值。染色體（基因串）染色體（基因串）：攜帶基因信息的數(shù)據(jù)結(jié)構(gòu)，：攜帶基因信息的數(shù)據(jù)結(jié)構(gòu)，簡稱個體，二進(jìn)制位串或整數(shù)數(shù)組。簡稱個體，二進(jìn)制位串或整數(shù)數(shù)組。 遺傳算法最新 l遺傳學(xué)基本概念與術(shù)語遺傳學(xué)基本概念與術(shù)語基因型（基因型（genotype）：遺傳因子組合的模型，染：遺傳因子組合的模型，染色體的內(nèi)部表現(xiàn)；色體的內(nèi)部表現(xiàn)；表現(xiàn)型（表現(xiàn)型（phenotype）：由染色體決定性狀的外：由染色體決定性狀的外部表現(xiàn)，基因型

17、形成的個體；部表現(xiàn)，基因型形成的個體； 1 1 1 1 1 1 1 1 1 1 0 1 1 1 遺傳算法最新l遺傳學(xué)基本概念與術(shù)語遺傳學(xué)基本概念與術(shù)語基因座（基因座（locus）：遺傳基因在染色體中所占據(jù)的：遺傳基因在染色體中所占據(jù)的位置，同一基因座可能有的全部基因稱為等位基位置，同一基因座可能有的全部基因稱為等位基因（因（allele）；）；個體（個體（individual）：指染色體帶有特征的實體；：指染色體帶有特征的實體；種群（種群（population）：個體的集合，該集合內(nèi)個體：個體的集合，該集合內(nèi)個體數(shù)稱為種群的大小；數(shù)稱為種群的大?。环N群大小種群大?。悍N群中個體的數(shù)量，也叫群體規(guī)

18、模。：種群中個體的數(shù)量，也叫群體規(guī)模。 遺傳算法最新l遺傳學(xué)基本概念與術(shù)語遺傳學(xué)基本概念與術(shù)語進(jìn)化（進(jìn)化（evolution）：生物在其延續(xù)生存的過程：生物在其延續(xù)生存的過程中，逐漸適應(yīng)其生存環(huán)境，使得其品質(zhì)不斷得中，逐漸適應(yīng)其生存環(huán)境，使得其品質(zhì)不斷得到改良，這種生命現(xiàn)象稱為進(jìn)化；到改良，這種生命現(xiàn)象稱為進(jìn)化；適應(yīng)度（適應(yīng)度（fitness）：個體性能的數(shù)量值，度量某：個體性能的數(shù)量值，度量某個物種對于生存環(huán)境的適應(yīng)程度。對生存環(huán)境個物種對于生存環(huán)境的適應(yīng)程度。對生存環(huán)境適應(yīng)程度較高的物種將獲得更多的繁殖機會，適應(yīng)程度較高的物種將獲得更多的繁殖機會，而對生存環(huán)境適應(yīng)程度較低的物種，其繁殖機而

19、對生存環(huán)境適應(yīng)程度較低的物種，其繁殖機會就會相對較少，甚至逐漸滅絕會就會相對較少，甚至逐漸滅絕; 遺傳算法最新l遺傳學(xué)基本概念與術(shù)語遺傳學(xué)基本概念與術(shù)語選擇（選擇（selection）：指決定以一定的概率從種群：指決定以一定的概率從種群中選擇若干個體的操作中選擇若干個體的操作 ；復(fù)制（復(fù)制（reproduction）：細(xì)胞在分裂時，遺傳物：細(xì)胞在分裂時，遺傳物質(zhì)質(zhì)DNA通過復(fù)制而轉(zhuǎn)移到新產(chǎn)生的細(xì)胞中，新的通過復(fù)制而轉(zhuǎn)移到新產(chǎn)生的細(xì)胞中，新的細(xì)胞就繼承了舊細(xì)胞的基因細(xì)胞就繼承了舊細(xì)胞的基因;交叉（交叉（crossover）：在兩個染色體的某一相同位：在兩個染色體的某一相同位置處置處DNA被切斷，

20、其前后兩串分別交叉組合形成被切斷，其前后兩串分別交叉組合形成兩個新的染色體。又稱基因重組，俗稱兩個新的染色體。又稱基因重組，俗稱“雜交雜交”; 遺傳算法最新l遺傳學(xué)基本概念與術(shù)語遺傳學(xué)基本概念與術(shù)語變異（變異（mutation）：在細(xì)胞進(jìn)行復(fù)制時可能以很：在細(xì)胞進(jìn)行復(fù)制時可能以很小的概率產(chǎn)生某些復(fù)制差錯，從而使小的概率產(chǎn)生某些復(fù)制差錯，從而使DNA發(fā)生發(fā)生某種變異，產(chǎn)生出新的染色體，這些新的染色某種變異，產(chǎn)生出新的染色體，這些新的染色體表現(xiàn)出新的性狀體表現(xiàn)出新的性狀;編碼（編碼（coding）：表現(xiàn)型到基因型的映射；：表現(xiàn)型到基因型的映射；解碼（解碼（decoding）：從基因型到表現(xiàn)型的映射

21、。：從基因型到表現(xiàn)型的映射。 遺傳算法最新l進(jìn)化論與遺傳學(xué)的融合進(jìn)化論與遺傳學(xué)的融合 19301947年，達(dá)爾文進(jìn)化論與遺傳學(xué)走向融合，年，達(dá)爾文進(jìn)化論與遺傳學(xué)走向融合，Th. Dobzhansky1937年發(fā)表的遺傳學(xué)與物種起年發(fā)表的遺傳學(xué)與物種起源是融合進(jìn)化論與遺傳學(xué)的代表作。源是融合進(jìn)化論與遺傳學(xué)的代表作。l生物進(jìn)化與智能學(xué)的關(guān)系生物進(jìn)化與智能學(xué)的關(guān)系 生物物種作為復(fù)雜系統(tǒng)，具有奇妙的自適應(yīng)、生物物種作為復(fù)雜系統(tǒng)，具有奇妙的自適應(yīng)、自組織和自優(yōu)化能力，這是一種生物在進(jìn)化過自組織和自優(yōu)化能力，這是一種生物在進(jìn)化過程中體現(xiàn)的智能，也是人工系統(tǒng)夢寐以求的功程中體現(xiàn)的智能，也是人工系統(tǒng)夢寐以求的

22、功能。能。 遺傳算法最新l如何借鑒？如何借鑒？l對于一個優(yōu)化問題，一定數(shù)量的候選解（生對于一個優(yōu)化問題，一定數(shù)量的候選解（生命個體）被表示為抽象的數(shù)字串（染色體），命個體）被表示為抽象的數(shù)字串（染色體），通過進(jìn)化向更好的解發(fā)展。通過進(jìn)化向更好的解發(fā)展。l選解一般為二進(jìn)制數(shù)字串（即選解一般為二進(jìn)制數(shù)字串（即0和和1），但也），但也可能有其他表示。一開始，生命個體完全隨可能有其他表示。一開始，生命個體完全隨機產(chǎn)生，之后一代一代的進(jìn)化，在進(jìn)化過程機產(chǎn)生，之后一代一代的進(jìn)化，在進(jìn)化過程中的每一代，每一個個體的適應(yīng)程度被評價，中的每一代，每一個個體的適應(yīng)程度被評價，通過自然選擇和變異產(chǎn)生新的生命群體，該

23、通過自然選擇和變異產(chǎn)生新的生命群體，該群體就是下一代的個體。群體就是下一代的個體。遺傳算法最新l遺傳算法與自然進(jìn)化的比較遺傳算法與自然進(jìn)化的比較自然界自然界染色體染色體基因基因等位基因等位基因(allele)染色體位置染色體位置(locus)基因型基因型(genotype)表現(xiàn)型表現(xiàn)型(phenotype)遺傳算法遺傳算法字符串字符串字符，特征字符，特征特征值特征值字符串位置字符串位置結(jié)構(gòu)結(jié)構(gòu)參數(shù)集，譯碼結(jié)構(gòu)參數(shù)集，譯碼結(jié)構(gòu)遺傳算法最新進(jìn)化過程的三種運算進(jìn)化過程的三種運算選擇選擇：根據(jù)適應(yīng)度，按照一定的規(guī)則或方法，：根據(jù)適應(yīng)度，按照一定的規(guī)則或方法，從第從第t代群體代群體p(t)中選擇優(yōu)良的個

24、體遺傳到下中選擇優(yōu)良的個體遺傳到下一代群體一代群體p(t+1)中。中。交叉交叉：將群體：將群體p(t)內(nèi)各個個體隨機搭配成對，內(nèi)各個個體隨機搭配成對，對每個個體中交換一部分染色體。對每個個體中交換一部分染色體。變異變異：對群體：對群體p(t)中的每個個體改變某個或中的每個個體改變某個或一些值是其他個體的值。一些值是其他個體的值。遺傳算法最新選擇運算選擇運算群體群體p(t)交叉運算交叉運算變異運算變異運算解解 碼碼群體群體p(t+1)解集合解集合個體評價個體評價遺傳空間遺傳空間解解 空空 間間遺傳算法最新生物遺傳概念生物遺傳概念遺傳算法中的作用遺傳算法中的作用適者生存適者生存?zhèn)€體個體(indiv

25、idual)染色體染色體(chromosome)基因基因(gene)適應(yīng)性適應(yīng)性(fitness)群體群體(population)交叉交叉(crossover)變異變異(mutation)種群種群(reproduction)根據(jù)適應(yīng)函數(shù)值選定的一組解根據(jù)適應(yīng)函數(shù)值選定的一組解解解解的編碼解的編碼(字符串，向量等字符串，向量等)解中每一分量特征解中每一分量特征(編碼單元編碼單元)適應(yīng)函數(shù)值適應(yīng)函數(shù)值搜索空間中選定的一組有效解搜索空間中選定的一組有效解算法停止，最優(yōu)值被留住算法停止，最優(yōu)值被留住交換部分基因交換部分基因產(chǎn)生一組新解的過程產(chǎn)生一組新解的過程編碼的某一分量發(fā)生變化編碼的某一分量發(fā)生變化

26、遺傳算法最新例例1 用遺傳算法求解優(yōu)化問題用遺傳算法求解優(yōu)化問題310 ,)(max2xxxf其中其中 為整數(shù)。為整數(shù)。x產(chǎn)生群體產(chǎn)生群體:)(000001x)(110012x)(011113x)(010004x適應(yīng)函數(shù)適應(yīng)函數(shù)2xxfxfitness)()(210)(xfitness2225)(xfitness2315)(xfitness248)(xfitnessjjiixfitnessxfitnessxp)()()(遺傳算法最新交叉交叉)(110012x)(011113x)(010004x)(110012x)(111111y)(010012y)(110003y)(010014y變異變異的第

27、一個基因發(fā)生變異的第一個基因發(fā)生變異)(110014y4y遺傳算法最新二、算法發(fā)展回顧l遺傳算法遺傳算法最開始是產(chǎn)生于最開始是產(chǎn)生于Holland教授和他的同事對教授和他的同事對cellular automata的研究過程中的研究過程中。在二十世紀(jì)八十年代中。在二十世紀(jì)八十年代中期之前，對于遺傳算法的研究還僅限于理論方面，直到在期之前，對于遺傳算法的研究還僅限于理論方面，直到在伊里諾斯大學(xué)召開了第一屆世界遺傳算法大會。隨著計算伊里諾斯大學(xué)召開了第一屆世界遺傳算法大會。隨著計算機計算能力的發(fā)展和實際應(yīng)用需求的增多，遺傳算法逐漸機計算能力的發(fā)展和實際應(yīng)用需求的增多，遺傳算法逐漸進(jìn)入實際應(yīng)用階段。進(jìn)

28、入實際應(yīng)用階段。l1989年，紐約時報作者約翰馬克夫?qū)懥艘黄恼旅枋龅谝荒?，紐約時報作者約翰馬克夫?qū)懥艘黄恼旅枋龅谝粋€商業(yè)用途的遺傳算法個商業(yè)用途的遺傳算法-進(jìn)化者進(jìn)化者(Evolver）。）。l之后，越來越多種類的遺傳算法出現(xiàn)并被用于許多領(lǐng)域中，之后，越來越多種類的遺傳算法出現(xiàn)并被用于許多領(lǐng)域中，財富雜志財富雜志500強企業(yè)中大多數(shù)都用它進(jìn)行時間表安排、數(shù)強企業(yè)中大多數(shù)都用它進(jìn)行時間表安排、數(shù)據(jù)分析、未來趨勢預(yù)測、預(yù)算等很多其他優(yōu)化問題。據(jù)分析、未來趨勢預(yù)測、預(yù)算等很多其他優(yōu)化問題。遺傳算法最新 l產(chǎn)生產(chǎn)生早在早在50年代年代，一些生物學(xué)家開始研究運用數(shù)字計，一些生物學(xué)家開始研究運用數(shù)字計

29、算機模擬生物的自然遺傳與自然進(jìn)化過程；算機模擬生物的自然遺傳與自然進(jìn)化過程；1963年年，德國柏林技術(shù)大學(xué)的，德國柏林技術(shù)大學(xué)的I. Rechenberg和和H. P. Schwefel，做風(fēng)洞實驗時，產(chǎn)生了，做風(fēng)洞實驗時，產(chǎn)生了進(jìn)化策略進(jìn)化策略的的初步思想；初步思想；60年代，年代， L. J. Fogel在設(shè)計有限態(tài)自動機時提出在設(shè)計有限態(tài)自動機時提出進(jìn)化規(guī)劃進(jìn)化規(guī)劃思想。思想。1966年年Fogel等出版基于模擬進(jìn)等出版基于模擬進(jìn)化的人工智能，系統(tǒng)闡述了進(jìn)化規(guī)劃的思想?；娜斯ぶ悄?，系統(tǒng)闡述了進(jìn)化規(guī)劃的思想。 遺傳算法最新l人工進(jìn)化系統(tǒng)人工進(jìn)化系統(tǒng) 早在早在20世紀(jì)世紀(jì)50年代和年代和6

30、0年代，就有計算機科年代，就有計算機科學(xué)家進(jìn)行了學(xué)家進(jìn)行了“人工進(jìn)化系統(tǒng)人工進(jìn)化系統(tǒng)”的研究。的研究。 這些研究大多都是以這些研究大多都是以用計算機來模擬生物系用計算機來模擬生物系統(tǒng)統(tǒng)為主，從生物的角度進(jìn)行進(jìn)化模擬、遺傳模擬為主，從生物的角度進(jìn)行進(jìn)化模擬、遺傳模擬等方面的研究工作。等方面的研究工作。 形成了遺傳算法的雛形形成了遺傳算法的雛形 遺傳算法最新 l產(chǎn)生產(chǎn)生60年代中期，美國年代中期，美國Michigan大學(xué)的大學(xué)的J. H. Holland教授提出借鑒生物自然遺傳的基本原理用于自教授提出借鑒生物自然遺傳的基本原理用于自然然 和人工系統(tǒng)的自適應(yīng)行為研究和串編碼技術(shù)；和人工系統(tǒng)的自適應(yīng)行

31、為研究和串編碼技術(shù)；1967年，他的學(xué)生年，他的學(xué)生J. D. Bagley在博士論文中首在博士論文中首次提出次提出“遺傳算法遺傳算法(Genetic Algorithms)”一詞；一詞；1975年年，Holland出版了著名的出版了著名的“Adaptation in Natural and Artificial Systems”，標(biāo)志，標(biāo)志遺傳算法遺傳算法的誕生的誕生。 遺傳算法最新 l發(fā)展發(fā)展70年代初，年代初，Holland提出了提出了“模式定理模式定理”（Schema Theorem），一般認(rèn)為是），一般認(rèn)為是“遺傳算法的基本定理遺傳算法的基本定理”，從而奠定了遺傳算法研究的理論基礎(chǔ)；

32、從而奠定了遺傳算法研究的理論基礎(chǔ)；1985年，在美國召開了第一屆遺傳算法國際會議，年，在美國召開了第一屆遺傳算法國際會議，并且成立了國際遺傳算法學(xué)會并且成立了國際遺傳算法學(xué)會(ISGA，International Society of Genetic Algorithms)； 遺傳算法最新lJ.H.Holland 20世紀(jì)世紀(jì)60年代年代認(rèn)識到了認(rèn)識到了生物的遺傳和自然進(jìn)化現(xiàn)象生物的遺傳和自然進(jìn)化現(xiàn)象與與人工自適人工自適應(yīng)系統(tǒng)應(yīng)系統(tǒng)的相似關(guān)系，的相似關(guān)系，運用生物遺傳和進(jìn)化的思想來研究自然和人工自運用生物遺傳和進(jìn)化的思想來研究自然和人工自適應(yīng)系統(tǒng)的生成以及它們與環(huán)境的關(guān)系，適應(yīng)系統(tǒng)的生成以及它

33、們與環(huán)境的關(guān)系，提出在研究和設(shè)計人工自適應(yīng)系統(tǒng)時，可以借鑒提出在研究和設(shè)計人工自適應(yīng)系統(tǒng)時，可以借鑒生物遺傳機制，以群體的方法進(jìn)行自適應(yīng)搜索，生物遺傳機制，以群體的方法進(jìn)行自適應(yīng)搜索，充分認(rèn)識到了交叉、變異等充分認(rèn)識到了交叉、變異等運算策略運算策略在自適應(yīng)系在自適應(yīng)系統(tǒng)中的重要性。統(tǒng)中的重要性。 遺傳算法最新 20世紀(jì)世紀(jì)70年代，年代，Holland提出了遺傳算法的提出了遺傳算法的基本定理基本定理-模式定理模式定理(Schema Theorem)，奠定，奠定了遺傳算法的理論基礎(chǔ)。了遺傳算法的理論基礎(chǔ)。 20世紀(jì)世紀(jì)80年代，年代，Holland實現(xiàn)了第一個基于實現(xiàn)了第一個基于遺傳算法的機器學(xué)

34、習(xí)系統(tǒng)遺傳算法的機器學(xué)習(xí)系統(tǒng)-分類器系統(tǒng)分類器系統(tǒng)，開創(chuàng)，開創(chuàng)了基于遺傳算法學(xué)習(xí)的新概念，為分類器系統(tǒng)了基于遺傳算法學(xué)習(xí)的新概念，為分類器系統(tǒng)構(gòu)造出了一個完整的框架。構(gòu)造出了一個完整的框架。 1975年，年，Holland出版了第一本系統(tǒng)論述遺出版了第一本系統(tǒng)論述遺傳算法和人工自適應(yīng)系統(tǒng)的專著傳算法和人工自適應(yīng)系統(tǒng)的專著自然系統(tǒng)和自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)性（人工系統(tǒng)的自適應(yīng)性（Adaptation in Natural and Artificial Systems）。 遺傳算法最新lJ.D.Bagley1967年，年，Holland的學(xué)生的學(xué)生Bagley在其博士論文中首在其博士論文中首次提

35、出了次提出了“遺傳算法遺傳算法”一詞，并發(fā)表了遺傳算法應(yīng)一詞，并發(fā)表了遺傳算法應(yīng)用方面（在博弈中）的第一篇論文。用方面（在博弈中）的第一篇論文。發(fā)展了復(fù)制、交叉、變異、顯性、倒位等遺傳算發(fā)展了復(fù)制、交叉、變異、顯性、倒位等遺傳算子，在個體編碼上使用了雙倍體編碼方法。這些子，在個體編碼上使用了雙倍體編碼方法。這些都與目前遺傳算法中所使用的算子和方法類似。都與目前遺傳算法中所使用的算子和方法類似。意識到了在遺傳算法執(zhí)行的不同階段可以使用不意識到了在遺傳算法執(zhí)行的不同階段可以使用不同的選擇率，這將有利于防止遺傳算法的早熟現(xiàn)同的選擇率，這將有利于防止遺傳算法的早熟現(xiàn)象，從而創(chuàng)立了象，從而創(chuàng)立了自適應(yīng)遺

36、傳算法自適應(yīng)遺傳算法概念。概念。 遺傳算法最新lHolland 自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)性自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)性 第一次系統(tǒng)地論述了遺傳算法的基本理論與第一次系統(tǒng)地論述了遺傳算法的基本理論與方法，提出了遺傳算法的基本定理方法，提出了遺傳算法的基本定理模式定理模式定理（schema theorem），從而奠定了遺傳算法的理），從而奠定了遺傳算法的理論基礎(chǔ)。論基礎(chǔ)。 模式定理揭示了群體中優(yōu)良個體（較好模式）模式定理揭示了群體中優(yōu)良個體（較好模式）的樣本數(shù)將以指數(shù)規(guī)律增長，確認(rèn)了結(jié)構(gòu)重組遺的樣本數(shù)將以指數(shù)規(guī)律增長，確認(rèn)了結(jié)構(gòu)重組遺傳操作對于獲得隱并行性的重要性，從理論上保傳操作對于獲得隱并行

37、性的重要性，從理論上保證了遺傳算法是一個可以尋求最優(yōu)可行解的優(yōu)化證了遺傳算法是一個可以尋求最優(yōu)可行解的優(yōu)化過程。過程。 該書的出版標(biāo)志著遺傳算法得到正式承該書的出版標(biāo)志著遺傳算法得到正式承認(rèn)，認(rèn)， Holland也被視為遺傳算法的創(chuàng)始人。也被視為遺傳算法的創(chuàng)始人。遺傳算法最新lK.A.De Jong 1975年，年，De Jong在其博士論文中結(jié)合模式在其博士論文中結(jié)合模式定理進(jìn)行了大量的定理進(jìn)行了大量的純數(shù)值函數(shù)優(yōu)化的計算實驗純數(shù)值函數(shù)優(yōu)化的計算實驗，將選擇、交叉、變異等遺傳操作進(jìn)一步完善和將選擇、交叉、變異等遺傳操作進(jìn)一步完善和系統(tǒng)化，建立了遺傳算法的系統(tǒng)化，建立了遺傳算法的工作框架工作框

38、架，得到了，得到了一些重要且具有指導(dǎo)意義的結(jié)論。一些重要且具有指導(dǎo)意義的結(jié)論。 他推薦了在大多數(shù)優(yōu)化問題中都比較適用他推薦了在大多數(shù)優(yōu)化問題中都比較適用的遺傳算法參數(shù)，還建立了著名的的遺傳算法參數(shù)，還建立了著名的De Jong 五五函數(shù)測試平臺，定義了評價遺傳算法性能的在函數(shù)測試平臺，定義了評價遺傳算法性能的在線指標(biāo)和離線指標(biāo)。線指標(biāo)和離線指標(biāo)。 遺傳算法最新l發(fā)展發(fā)展1989年，年，Holland的學(xué)生的學(xué)生D. J. Goldherg出版了出版了“Genetic Algorithms in Search, Optimization, and Machine Learning（遺傳算法遺傳算

39、法搜索、優(yōu)搜索、優(yōu)化及機器學(xué)習(xí)化及機器學(xué)習(xí)）”，對遺傳算法及其應(yīng)用作了全，對遺傳算法及其應(yīng)用作了全面而系統(tǒng)的論述。面而系統(tǒng)的論述。 該書系統(tǒng)總結(jié)了遺傳算法的主要研究成果，該書系統(tǒng)總結(jié)了遺傳算法的主要研究成果，全面完整地論述了遺傳算法的基本原理及應(yīng)用。全面完整地論述了遺傳算法的基本原理及應(yīng)用。 遺傳算法最新l發(fā)展發(fā)展1991年，年，L. Davis編輯出版了編輯出版了Handbook of Genetic Algorithms（遺傳算法手冊），遺傳算法手冊），書中書中介紹了遺傳算法在科學(xué)計算、工程技術(shù)和社會介紹了遺傳算法在科學(xué)計算、工程技術(shù)和社會經(jīng)濟(jì)等領(lǐng)域中大量的應(yīng)用實例，該書為推廣和經(jīng)濟(jì)等領(lǐng)域

40、中大量的應(yīng)用實例，該書為推廣和普及遺傳算法的應(yīng)用起到了重要的指導(dǎo)作用。普及遺傳算法的應(yīng)用起到了重要的指導(dǎo)作用。 遺傳算法最新l發(fā)展發(fā)展1992年，年，J.R.KozaGenetic Programming將將遺傳算法應(yīng)用于計算機程序的優(yōu)化設(shè)計及自動遺傳算法應(yīng)用于計算機程序的優(yōu)化設(shè)計及自動生成，提出了遺傳編程的概念。生成，提出了遺傳編程的概念。Koza成功地將成功地將提出的遺傳編程方法應(yīng)用于人工智能、機器學(xué)提出的遺傳編程方法應(yīng)用于人工智能、機器學(xué)習(xí)、符號處理等方面。習(xí)、符號處理等方面。 遺傳算法最新l幾個名詞概念幾個名詞概念 遺傳算法遺傳算法進(jìn)化計算進(jìn)化計算計算智能計算智能人工智能人工智能 遺傳

41、算法最新l幾個名詞概念幾個名詞概念 進(jìn)化計算：進(jìn)化計算： 由于遺傳算法、進(jìn)化規(guī)劃和進(jìn)化策略是不同領(lǐng)由于遺傳算法、進(jìn)化規(guī)劃和進(jìn)化策略是不同領(lǐng)域的研究人員分別獨立提出的，在相當(dāng)長的時期域的研究人員分別獨立提出的，在相當(dāng)長的時期里相互之間沒有正式溝通。直到里相互之間沒有正式溝通。直到90年代，才有所年代，才有所交流。交流。 他們發(fā)現(xiàn)彼此的基本思想具有驚人的相似之處，他們發(fā)現(xiàn)彼此的基本思想具有驚人的相似之處，于是提出將這類方法統(tǒng)稱為于是提出將這類方法統(tǒng)稱為“進(jìn)化計算進(jìn)化計算” ( Evolutionary Computation ) 。 遺傳算法最新l幾個名詞概念幾個名詞概念 計算智能：計算智能： 計

42、算智能主要包括神經(jīng)計算、進(jìn)化計算和模糊計算智能主要包括神經(jīng)計算、進(jìn)化計算和模糊計算等。它們分別從不同的角度模擬人類的智能計算等。它們分別從不同的角度模擬人類的智能活動，以使計算機具有智能?；顒?，以使計算機具有智能。 通常將基于符號處理的傳統(tǒng)人工智能稱為符號通常將基于符號處理的傳統(tǒng)人工智能稱為符號智能，以區(qū)別于正在興起的計算智能。智能，以區(qū)別于正在興起的計算智能。 符號智能的特點是以符號智能的特點是以知識知識為基礎(chǔ)，偏重于為基礎(chǔ)，偏重于邏輯邏輯推理推理，而計算智能則是以，而計算智能則是以數(shù)據(jù)數(shù)據(jù)為基礎(chǔ)，偏重于為基礎(chǔ)，偏重于數(shù)數(shù)值計算值計算。 遺傳算法最新三、算法機理l優(yōu)化問題的優(yōu)化問題的解解被視

43、為被視為個體個體，它表示為一個參數(shù)，它表示為一個參數(shù)列表，叫做染色體或者基因串。染色體一般被列表，叫做染色體或者基因串。染色體一般被表達(dá)為簡單的表達(dá)為簡單的字符串或數(shù)字串字符串或數(shù)字串。l一開始，算法一開始，算法隨機生成一定數(shù)量的個體隨機生成一定數(shù)量的個體，有時，有時操作者也可以對這個隨機產(chǎn)生過程進(jìn)行操作者也可以對這個隨機產(chǎn)生過程進(jìn)行干預(yù)干預(yù)，播下已經(jīng)部分優(yōu)化的種子。在每一代中，每一播下已經(jīng)部分優(yōu)化的種子。在每一代中，每一個個體都被個個體都被評價評價，并通過適應(yīng)度函數(shù)計算并返，并通過適應(yīng)度函數(shù)計算并返回一個回一個適應(yīng)度數(shù)值適應(yīng)度數(shù)值。遺傳算法最新l下一步是下一步是產(chǎn)生下一代個體產(chǎn)生下一代個體并

44、組成群落。這個過并組成群落。這個過程是通過程是通過選擇選擇和繁殖完成的，其中繁殖包括和繁殖完成的，其中繁殖包括雜雜交交和和突變突變。l選擇選擇是根據(jù)新個體的是根據(jù)新個體的適應(yīng)度數(shù)值適應(yīng)度數(shù)值進(jìn)行的，適應(yīng)進(jìn)行的，適應(yīng)度越高，選擇的機會越多，而適應(yīng)度低的，被度越高，選擇的機會越多，而適應(yīng)度低的，被選擇的機會就低。通過這樣的過程，初始的數(shù)選擇的機會就低。通過這樣的過程，初始的數(shù)據(jù)可以達(dá)到一個優(yōu)化的群體。據(jù)可以達(dá)到一個優(yōu)化的群體。遺傳算法最新l之后，被選擇的個體進(jìn)入之后，被選擇的個體進(jìn)入雜交雜交過程。一般的遺過程。一般的遺傳算法都有一個傳算法都有一個雜交率雜交率的參數(shù)，范圍一般是的參數(shù)，范圍一般是0.

45、61，這個雜交率反映兩個被選中的個體進(jìn)行，這個雜交率反映兩個被選中的個體進(jìn)行雜交的概率。雜交的概率。例如例如，雜交率為，雜交率為0.8，則，則80%的的“夫夫妻妻”會生育后代。每兩個個體通過雜交產(chǎn)生兩個會生育后代。每兩個個體通過雜交產(chǎn)生兩個新個體，代替原來的新個體，代替原來的“老老”個體，而不雜交的個個體，而不雜交的個體則保持不變。體則保持不變。雜交父母的染色體相互交錯，雜交父母的染色體相互交錯，從而產(chǎn)生兩個新的染色體從而產(chǎn)生兩個新的染色體，第一個個體前半段，第一個個體前半段是父親的染色體，后半段是母親的，第二個個是父親的染色體，后半段是母親的，第二個個體則正好相反。不過這里的半段不是真正的一

46、體則正好相反。不過這里的半段不是真正的一半，這個位置叫做半，這個位置叫做雜交點雜交點，也是，也是隨機產(chǎn)生隨機產(chǎn)生的，的，可以是染色體的任意位置?？梢允侨旧w的任意位置。遺傳算法最新l再下一步是再下一步是變異變異，通過變異產(chǎn)生新的，通過變異產(chǎn)生新的“子子”個體。個體。一般遺傳算法都有一個固定的變異常數(shù)，通常一般遺傳算法都有一個固定的變異常數(shù)，通常是是0.01或者更小，這代表變異發(fā)生的概率。根或者更小，這代表變異發(fā)生的概率。根據(jù)這個概率，新個體的染色體據(jù)這個概率，新個體的染色體隨機的變異隨機的變異，通，通常就是改變?nèi)旧w的一個字節(jié)（常就是改變?nèi)旧w的一個字節(jié)（0變到變到1，或者，或者1變到變到0）

47、。）。遺傳算法最新l經(jīng)過這一系列的過程（選擇、雜交和變異），經(jīng)過這一系列的過程（選擇、雜交和變異），產(chǎn)生的新一代個體不同于初始的一代，并產(chǎn)生的新一代個體不同于初始的一代，并一代一代一代向增加整體適應(yīng)度的方向發(fā)展一代向增加整體適應(yīng)度的方向發(fā)展，因為最好，因為最好的個體總是更多的被選擇去產(chǎn)生下一代，而適的個體總是更多的被選擇去產(chǎn)生下一代，而適應(yīng)度低的個體逐漸被淘汰掉。這樣的過程不斷應(yīng)度低的個體逐漸被淘汰掉。這樣的過程不斷的重復(fù)：的重復(fù)：每個個體被評價，計算出適應(yīng)度，兩每個個體被評價，計算出適應(yīng)度，兩個個體雜交，然后變異，產(chǎn)生第三代個個體雜交，然后變異，產(chǎn)生第三代。周而復(fù)。周而復(fù)始，直到始，直到終止

48、條件終止條件滿足為止。滿足為止。遺傳算法最新l終止條件有以下幾種：終止條件有以下幾種：l進(jìn)化次數(shù)限制；進(jìn)化次數(shù)限制； l計算耗費的資源限制（例如計算時間、計算計算耗費的資源限制（例如計算時間、計算占用的內(nèi)存等）；占用的內(nèi)存等）； l一個個體已經(jīng)滿足最小值的條件，即最小值一個個體已經(jīng)滿足最小值的條件，即最小值已經(jīng)找到；已經(jīng)找到； l適應(yīng)度已經(jīng)達(dá)到飽和，繼續(xù)進(jìn)化不會造成適適應(yīng)度已經(jīng)達(dá)到飽和，繼續(xù)進(jìn)化不會造成適應(yīng)度更好的個體；應(yīng)度更好的個體； l人為干預(yù)；人為干預(yù)； l以及以上兩種或更多種的組合。以及以上兩種或更多種的組合。 遺傳算法最新Step1 隨機產(chǎn)生一組初始個體構(gòu)成初始種群隨機產(chǎn)生一組初始個

49、體構(gòu)成初始種群,并評并評價每一個個體的適配值價每一個個體的適配值(fitness value);Step2 判斷算法收斂準(zhǔn)則是否滿足。若滿足則輸出判斷算法收斂準(zhǔn)則是否滿足。若滿足則輸出搜索結(jié)果；否則執(zhí)行以下步驟搜索結(jié)果；否則執(zhí)行以下步驟;Step3 根據(jù)適配值大小以一定方式進(jìn)行復(fù)制操作根據(jù)適配值大小以一定方式進(jìn)行復(fù)制操作;Step6 返回返回Step2.四、標(biāo)準(zhǔn)遺傳算法的主要步驟四、標(biāo)準(zhǔn)遺傳算法的主要步驟Step4 按交叉概率按交叉概率 執(zhí)行交叉操作執(zhí)行交叉操作;cpStep5 按變異概率按變異概率 執(zhí)行變異操作執(zhí)行變異操作;mp遺傳算法最新算法基本流程開始開始隨機產(chǎn)生初始種群并隨機產(chǎn)生初始種

50、群并計算各個體的適配值計算各個體的適配值算法收斂準(zhǔn)算法收斂準(zhǔn)則滿足否？則滿足否？輸出搜索結(jié)果輸出搜索結(jié)果Y執(zhí)行復(fù)制操作執(zhí)行復(fù)制操作交叉概率交叉概率滿足否滿足否?執(zhí)行交叉操作執(zhí)行交叉操作變異概率變異概率滿足否？滿足否？執(zhí)行變異操作執(zhí)行變異操作YYNNN遺傳算法最新遺傳算法流程圖和偽代碼遺傳算法最新遺傳算法基本要素l編碼編碼：固定長度的二進(jìn)制符號串：固定長度的二進(jìn)制符號串l初始種群的產(chǎn)生初始種群的產(chǎn)生：若干初始解組成的初始群體：若干初始解組成的初始群體l適值度函數(shù)的設(shè)定適值度函數(shù)的設(shè)定：區(qū)分群中個體好壞的標(biāo)準(zhǔn)：區(qū)分群中個體好壞的標(biāo)準(zhǔn)l遺傳算子遺傳算子：選擇運算；交叉運算；變異運算：選擇運算；交叉運

51、算；變異運算l終止條件終止條件：進(jìn)化結(jié)束的條件。如最大進(jìn)化代：進(jìn)化結(jié)束的條件。如最大進(jìn)化代 數(shù)或最優(yōu)解所需滿足的精度。數(shù)或最優(yōu)解所需滿足的精度。l運行參數(shù)運行參數(shù)：群體規(guī)模、交叉概率、變異概率：群體規(guī)模、交叉概率、變異概率遺傳算法最新五、五、SGA結(jié)構(gòu)結(jié)構(gòu)l標(biāo)準(zhǔn)遺傳算法標(biāo)準(zhǔn)遺傳算法(Simple Genetic Algorithms,簡稱簡稱SGA)l是一種統(tǒng)一的最基本的遺傳算法，它只使用是一種統(tǒng)一的最基本的遺傳算法，它只使用選擇、交叉、變異選擇、交叉、變異這三種基本遺傳算子，其這三種基本遺傳算子，其遺傳進(jìn)化操作過程簡單，容易理解，是其他遺傳進(jìn)化操作過程簡單，容易理解，是其他一些遺傳算法的雛形

52、和基礎(chǔ)，它不僅給各種一些遺傳算法的雛形和基礎(chǔ)，它不僅給各種遺傳算法提供了一個基本框架，同時也具有遺傳算法提供了一個基本框架，同時也具有一定的應(yīng)用價值。一定的應(yīng)用價值。 l又叫又叫基本遺傳算法基本遺傳算法或或簡單遺傳算法。簡單遺傳算法。遺傳算法最新l構(gòu)成要素構(gòu)成要素 染色體編碼方法染色體編碼方法。標(biāo)準(zhǔn)遺傳算法使用固定長度。標(biāo)準(zhǔn)遺傳算法使用固定長度的的二進(jìn)制二進(jìn)制符號串來表示群體中的個體，其等位符號串來表示群體中的個體，其等位基因是由二值符號集基因是由二值符號集0，1所組成的。初始群所組成的。初始群體中各個個體的基因值可用均勻分布的隨機數(shù)體中各個個體的基因值可用均勻分布的隨機數(shù)來生成。來生成。 遺

53、傳算法最新個體適應(yīng)度評價個體適應(yīng)度評價。標(biāo)準(zhǔn)遺傳算法。標(biāo)準(zhǔn)遺傳算法按與個體適應(yīng)按與個體適應(yīng)度成正比的概率度成正比的概率來決定當(dāng)前群體中每個個體遺來決定當(dāng)前群體中每個個體遺傳到下一代群體中的機會多少。為正確計算這傳到下一代群體中的機會多少。為正確計算這個概率，這里要求所有個體的個概率，這里要求所有個體的適應(yīng)度必須為正適應(yīng)度必須為正數(shù)或零數(shù)或零。遺傳算子遺傳算子。標(biāo)準(zhǔn)遺傳算法使用下述三種遺傳算。標(biāo)準(zhǔn)遺傳算法使用下述三種遺傳算子：子：選擇運算使用比例選擇算子選擇運算使用比例選擇算子，交叉運算使交叉運算使用單點交叉算子用單點交叉算子，變異運算使用基本位變異算變異運算使用基本位變異算子或均勻變異算子子或

54、均勻變異算子。 遺傳算法最新運行參數(shù)運行參數(shù)。標(biāo)準(zhǔn)遺傳算法有下述。標(biāo)準(zhǔn)遺傳算法有下述4個運行參數(shù)需要個運行參數(shù)需要提前設(shè)定：提前設(shè)定：群體大小群體大小M，即群體中所含個體數(shù)目，一般取為，即群體中所含個體數(shù)目，一般取為20100；遺傳運算的終止進(jìn)化代數(shù)遺傳運算的終止進(jìn)化代數(shù)T，一般取為，一般取為100500； 交叉概率交叉概率Pc，一般取為，一般取為0.40.99； 變異概率變異概率Pm，一般取為，一般取為0.00010.1。 遺傳算法最新形式化定義形式化定義 算法可定義為一個算法可定義為一個8元組：元組： ),(0TMPECSGAC-個體的編碼方法；個體的編碼方法；E-個體適應(yīng)度評價函數(shù)；個體

55、適應(yīng)度評價函數(shù)；P0-初始群體；初始群體；M-群體大?。蝗后w大??；-選擇算子；選擇算子； -交叉算子；交叉算子； -變異算子變異算子T-遺傳運算終止條件。遺傳運算終止條件。 遺傳算法最新例例1 用遺傳算法求解優(yōu)化問題用遺傳算法求解優(yōu)化問題310 ,)(max2xxxf其中其中 為整數(shù)。為整數(shù)。x解解: (1)確定初始種群確定初始種群 參數(shù)編碼參數(shù)編碼 將整數(shù)將整數(shù) x* 0,1,31作為參數(shù)，采用二進(jìn)制作為參數(shù)，采用二進(jìn)制進(jìn)行編碼：進(jìn)行編碼：X=000000， x=31 11111 隨機生成隨機生成例如例如: 01001； 11001； 01000； 10011。遺傳算法最新(2)選擇選擇 根

56、據(jù)根據(jù)“適者生存適者生存”的自然選擇原理的自然選擇原理,從初始種群中選從初始種群中選擇生命力強的個體擇生命力強的個體(適者適者)產(chǎn)生新的種群產(chǎn)生新的種群 確定適應(yīng)度函數(shù)確定適應(yīng)度函數(shù) 適應(yīng)度函數(shù)取為非負(fù)函數(shù)適應(yīng)度函數(shù)取為非負(fù)函數(shù),且適應(yīng)度增大的方向?qū)η疫m應(yīng)度增大的方向?qū)?yīng)于目標(biāo)函數(shù)的優(yōu)化方向應(yīng)于目標(biāo)函數(shù)的優(yōu)化方向 本例取適應(yīng)度函數(shù)本例取適應(yīng)度函數(shù) fitness(X)=x 計算適應(yīng)度和選擇率計算適應(yīng)度和選擇率 將初始種群的個體解碼為將初始種群的個體解碼為X,并計算適應(yīng)度并計算適應(yīng)度f(X)及及選擇率選擇率f/,其中其中為適應(yīng)度之和為適應(yīng)度之和.遺傳算法最新 隨機選擇適者個體隨機選擇適者個體 采

57、用采用輪盤輪盤法，對初始種群進(jìn)行選擇，使得最優(yōu)法，對初始種群進(jìn)行選擇，使得最優(yōu)秀的個體獲得最多的生存繁殖機會。秀的個體獲得最多的生存繁殖機會。遺傳算法最新(3)(3)交叉交叉 將選擇出的個體存入交配池中，用隨機方法配對將選擇出的個體存入交配池中，用隨機方法配對交叉，以產(chǎn)生新一代的個體交叉，以產(chǎn)生新一代的個體 隨機選擇配對；隨機選擇配對； 隨機選擇交叉點；隨機選擇交叉點； 采用單點交叉，產(chǎn)生新的種群采用單點交叉，產(chǎn)生新的種群遺傳算法最新(4) (4) 變異變異 在交叉過程中，可能丟失一些重要的遺傳信在交叉過程中，可能丟失一些重要的遺傳信息息( (特定位置的特定位置的1 1與與0 )0 )，因而產(chǎn)生變異。為了獲，因而產(chǎn)生變異。為了獲得新的遺傳信息，則需引入適度的變異。得新的遺傳信息，則需引入適度的變異。 遺傳算法最新1 是否有其他形式的候選解？是否有其他形式的候選解？2 如何選取交叉概率、變異概率？如何選取交叉概率、變異概率？3 是否有適配值的其他替代形式？是否有適配值的其他替代形式？4 交叉及變異點的如何選擇？交叉及變異點的如何選擇？5 如何利用更多的信息？如何利用更多的信息？6 終止準(zhǔn)則？終止準(zhǔn)則？Problem遺傳算法最新1 以優(yōu)化變量的遺傳編碼為運算及搜索對象以優(yōu)化變量的遺傳編碼為運算及搜索對象;