人工智能及其應(yīng)用 課件6 遺傳算法

第六章遺傳算法

遺傳算法概述基本遺傳算法遺傳算法數(shù)學(xué)基礎(chǔ)遺傳算法的改進(jìn)19:1316.1遺傳算法概述1、簡介遺傳算法(GeneticAlgorithms,GA)是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法.

遺傳算法吸取了自然生物系統(tǒng)“適者生存”的進(jìn)化理論，將達(dá)爾文的進(jìn)化理論引入人工系統(tǒng)串結(jié)構(gòu)的改造中，使得串結(jié)構(gòu)及其攜帶的信息發(fā)生有組織的而又是隨機(jī)的變換和組合，并使該過程按物種進(jìn)化規(guī)律來操作運(yùn)行，設(shè)法使物種的優(yōu)良品質(zhì)在組合中加以保留，從而不斷產(chǎn)生出更佳的個(gè)體后代。19:1326.1遺傳算法概述2、發(fā)展簡史20世紀(jì)50年代，生物學(xué)家Fraser試圖通過計(jì)算的方法來模擬生物界“遺傳與選擇”的進(jìn)化過程。20世紀(jì)60年代，1975年Holland教授出版了遺傳算法歷史上的經(jīng)典著作《AdaptationinNaturalandArtificialSystems》，首次提出遺傳算法的概念。20世紀(jì)80年代，迅速發(fā)展，1989年，Holland的學(xué)生Goldberg出版了《GeneticAlgorithmsinSearch,OptimizationandMachineLearning》

一書，為這一領(lǐng)域奠定了堅(jiān)實(shí)的科學(xué)基礎(chǔ)。20世紀(jì)90年代，隨著計(jì)算機(jī)技術(shù)的發(fā)展，遺傳算法在各個(gè)領(lǐng)域得到了廣泛的應(yīng)用。不同領(lǐng)域的專家、學(xué)者根據(jù)各自的實(shí)際問題，構(gòu)造出了多種能很好地解決行業(yè)問題新的遺傳算法。19:1336.1遺傳算法概述3、遺傳算法的特點(diǎn)全局性并行性和高效性魯棒性普適性和易擴(kuò)性簡明性19:1346.2基本遺傳算法一、基本原理1、基本術(shù)語染色體：遺傳物質(zhì)的主要載體，指多個(gè)遺傳因子的集合。個(gè)體：指染色體帶有特征的實(shí)體稱個(gè)體種群：染色體帶有特征個(gè)體的集合稱為群體，該集合內(nèi)的個(gè)體數(shù)稱為群體的大小。編碼：從表現(xiàn)型到遺傳子型的映射稱為編碼適應(yīng)度：各個(gè)個(gè)體對各自適應(yīng)環(huán)境的程度稱為適應(yīng)度。選擇：指決定以一定的概率從群體中選擇若干對個(gè)體的操作稱為選擇。交叉：把兩個(gè)染色體換組的操作稱為交叉，又稱重組。變異：讓遺傳因子以一定的概率變化的操作稱為變異解碼：從遺傳子型到表現(xiàn)型的映射稱為解碼19:1356.2基本遺傳算法2、基本原理與流程19:1366.2基本遺傳算法19:1371.用固定長度的染色體表示問題變量域，選擇染色體種群數(shù)量為N，交叉概率為pc,突變概率為pm。2.定義適應(yīng)性函數(shù)來衡量問題域上單個(gè)染色體的性能或適應(yīng)性。適應(yīng)性函數(shù)是在繁殖過程中選擇成對染色體的基礎(chǔ)。3.隨機(jī)產(chǎn)生一個(gè)大小為N的染色體種群：4.計(jì)算每個(gè)染色體的適應(yīng)性：5.在當(dāng)前種群中選擇一對染色體。適應(yīng)性高的染色體被選中的概率高于適應(yīng)性低的染色體。遺傳算法的基本操作6.通過執(zhí)行遺傳操作——交叉和突變產(chǎn)生一對后代染色體。7.將后代染色體放入新種群中。8.重復(fù)步驟5，直到新染色體種群的大小等于初始種群的大小N為止。9.用新（后代）染色體種群取代初始（雙親）染色體種群。10.回到步驟4，重復(fù)這個(gè)過程直到滿足中止條件為止。19:138例6.1尋找函數(shù)（15x-x2）在x的范圍為0-15時(shí)的最大值，假設(shè)x僅取整數(shù)值。解：假設(shè)染色體種群的大小為6，交叉概率為pc為0.7,突變概率為pm為0.001。適應(yīng)性函數(shù)為

表6-1染色體隨機(jī)產(chǎn)生的初始種群

19:139

最常用的染色體選擇技術(shù)是輪盤選擇。

圖6.2適應(yīng)性函數(shù)和染色體位置圖6.3輪盤選擇19:1310

在本例中，初始種群有6個(gè)染色體，因此，輪盤應(yīng)旋轉(zhuǎn)6次。第一對可能選擇x6和x2為雙親，第二對可能選擇x1和x5，最后一對可能是x2和x5。19:1311交叉操作如何進(jìn)行首先，交叉操作隨機(jī)選擇交叉點(diǎn)（親代染色體的“斷裂”點(diǎn)），并交換染色體交叉點(diǎn)后的部分，從而產(chǎn)生兩個(gè)新的子代染色體。如果兩個(gè)染色體沒有交叉，那么就克隆自己，子代是親代染色體的精確拷貝。19:1312

19:13134、突變

以很小的概率隨機(jī)地改變遺傳基因的值，模擬生物在自然環(huán)境中，由于某種偶然因素引起的基因突變。假設(shè)只有復(fù)制和交叉，沒有變異操作，就無法在初始基因族組以外的空間進(jìn)行搜索，可能使進(jìn)化過程較早陷入局部解而失去某種特殊的進(jìn)化途徑。對于二進(jìn)制編碼表示的染色體數(shù)字符串中，隨機(jī)地將染色體的某一個(gè)基因，即染色體的數(shù)字符串的某一位的數(shù)值由1變成0，或由0變成1。19:1314

突變的概率比較小，通常取千分之一二，但突變操作增加了基因類型的多樣性，使搜索能在盡可能大的空間進(jìn)行，得到更優(yōu)化的解。假設(shè)變異概率為0.001，則對于種群總共有20個(gè)基因位，期望的變異串位數(shù)為20X0.001=0.02位，所以這里沒有基因位數(shù)值的改變。19:13156.2基本遺傳算法二、遺傳算法的設(shè)計(jì)與實(shí)現(xiàn)1、編碼利用遺傳算法進(jìn)行問題求解時(shí),首先確定問題的目標(biāo)函數(shù)和變量,然后對其進(jìn)行編碼。這樣做主要是因?yàn)樵谶z傳算法中,問題的解是用數(shù)字串來表示的，而遺傳操作算子也是直接對串進(jìn)行操作的。編碼方式常用的有二進(jìn)制編碼和浮點(diǎn)數(shù)編碼。19:13166.2基本遺傳算法2、適應(yīng)度函數(shù)在生物的遺傳和進(jìn)化過程中，對生物環(huán)境適應(yīng)程度較高的物種將有更多的繁殖機(jī)會。遺傳算法中也使用這個(gè)概念來度量群體中各個(gè)個(gè)體在優(yōu)化計(jì)算中有可能達(dá)到或有助于找到最佳解的尋優(yōu)過程。適應(yīng)度較高的個(gè)體遺傳到下一代的概率就較大，而適應(yīng)度較低的個(gè)體遺傳到下一代的概率就相對小一些。度量個(gè)體適應(yīng)度的函數(shù)稱為適應(yīng)度函數(shù)（FitnessFunction）。19:13176.2基本遺傳算法3.遺傳算子(1)選擇運(yùn)算(selection)

選擇是從群體中挑選優(yōu)良個(gè)體并淘汰劣質(zhì)個(gè)體的操作過程。它建立在適應(yīng)度評估的基礎(chǔ)上，個(gè)體適應(yīng)度越大，被選中的可能性就越大，它的子代保留到配對庫(matingpool)中的個(gè)數(shù)就越多。常用選擇方法:輪盤賭方法、排序選擇法、最佳個(gè)體保存法。

19:13186.2基本遺傳算法(2)交叉運(yùn)算(crossover)

在遺傳操作中的，交叉操作因其全局搜索能力而成為主要算子，其作用在于它不僅使原種群中優(yōu)良個(gè)體的特性能夠在一定程度上保持，而且其探索新的基因空間的能力使得種群中的個(gè)體具有多樣性。它是GA獲取新優(yōu)良個(gè)體的最重要手段。交叉是指把兩個(gè)父串個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作。交叉運(yùn)算分為兩類，一類為二進(jìn)制交叉，另一類為浮點(diǎn)數(shù)交叉。

19:13196.2基本遺傳算法(3)變異運(yùn)算(mutation)

遺傳算法中使用變異算子使得遺傳算法具有局部的隨機(jī)搜索能力,能找到更精確的值.并配合交叉操作以維持種群的多樣性，防止出現(xiàn)過早收斂。兩類變異運(yùn)算：二進(jìn)制變異運(yùn)算，浮點(diǎn)數(shù)的變異運(yùn)算。19:13206.2基本遺傳算法三、遺傳算法運(yùn)行參數(shù)的選擇1、種群規(guī)模種群規(guī)模過小，容易使算法陷入局部最優(yōu)解；種群規(guī)模過大，增加了算法的計(jì)算量，從而減緩了算法的進(jìn)化速度。一般來說對種群的大小是針對一個(gè)具體的問題而言的，種群的規(guī)模與以下影響因素有關(guān)：(1)問題的內(nèi)在規(guī)律。如果在問題空間內(nèi)目標(biāo)函數(shù)的極值點(diǎn)越多，所要求的種群規(guī)模越大；如果問題空間內(nèi)目標(biāo)函數(shù)的變化越平滑，所要求的種群規(guī)模越小。(2)問題空間的范圍。問題空問的取值范圍越大，要求的種群規(guī)模也越大。(3)交叉率、變異率的選擇。交叉率和變異率較大時(shí)，要求的種群規(guī)模較?。环粗?，較大。19:13216.2基本遺傳算法2、交叉率交叉率是最主要的遺傳運(yùn)算，遺傳算法的性能在很大程度上取決于所采用的交叉算子的性能和交叉率的大小。交叉率是指各代中交叉產(chǎn)生的后代數(shù)與種群規(guī)模之比。交叉運(yùn)算產(chǎn)生新個(gè)體，不斷拓展搜索空間，較高的交叉率可以搜索更大的解空間，從而降低停在非優(yōu)解的機(jī)會；但是交叉率太高，會因搜索不必要的解空間而耗費(fèi)大量的計(jì)算時(shí)間。常用的交叉率的取值范圍為0.4~0.7。19:13226.2基本遺傳算法3、變異率變異率也是遺傳操作中的重要參數(shù)，它直接影響到算法的收斂性和最終解的性能。變異率是指種群中變異的基因數(shù)占總基因數(shù)的百分比。變異率控制了新基因引入的比例。在實(shí)際操作的過程中，算法常用變異率的數(shù)量級范圍為0.1~0.001?；蛘咴谶M(jìn)化初期選擇一個(gè)較大的值，而在進(jìn)化后期變異概率隨之減小。19:13236.2基本遺傳算法4.進(jìn)化終止條件進(jìn)化計(jì)算的終止可以從兩方面進(jìn)行控制：預(yù)先設(shè)定進(jìn)化代數(shù)或者以種群的進(jìn)化程度進(jìn)行控制。種群的進(jìn)化程度是指種群的當(dāng)前代最大適應(yīng)值與種群的平均適應(yīng)值的比例關(guān)系。

19:13246.2基本遺傳算法四、實(shí)例：用遺傳算法來維護(hù)計(jì)劃開發(fā)遺傳算法的典型過程通常包含下面幾個(gè)步驟：

1）確定問題，定義限制和最優(yōu)標(biāo)準(zhǔn)。

2）用染色體來表示問題域。

3）定義適應(yīng)性函數(shù)來評估染色體的性能。

4）構(gòu)建遺傳操作。

5）運(yùn)行遺傳算法，調(diào)整其參數(shù)。19:13256.2基本遺傳算法步驟1、確定問題，定義限制和最優(yōu)標(biāo)準(zhǔn)。19:13266.2基本遺傳算法

電力設(shè)備和維護(hù)需求

19:13276.2基本遺傳算法19:1328步驟2、用染色體來表示問題域。我們的任務(wù)是將完整的計(jì)劃表示為固定長度的染色體。在本例中，用4位來表示一個(gè)基因。然后，為每個(gè)設(shè)備產(chǎn)生基因池：

遺傳算法通過從基因池中隨機(jī)選擇基因來填滿7個(gè)基因的染色體來創(chuàng)建初始染色體種群。6.2基本遺傳算法步驟3、定義適應(yīng)性函數(shù)來評估染色體的性能。染色體的評估從求每個(gè)時(shí)間間隔上計(jì)劃維護(hù)的設(shè)備的總和開始：

19:13296.2基本遺傳算法

然后用電力系統(tǒng)的總?cè)萘恐袦p去這些值。時(shí)間間隔1：150-50=100

時(shí)間間隔2：150-35=115

時(shí)間間隔3：150-50=100時(shí)間間隔4：150-50=100

然后，減去每個(gè)時(shí)間間隔內(nèi)預(yù)期的最大負(fù)載，就可以得到各自的凈儲備：時(shí)間間隔1：100-80=20

時(shí)間間隔2：115-90=25

時(shí)間間隔3：100-65=35

時(shí)間間隔4：100-70=30

染色體的適應(yīng)性由凈儲備的最低值確定，本例為20。19:13306.2基本遺傳算法步驟4、構(gòu)建遺傳操作。

19:13316.2基本遺傳算法步驟5、運(yùn)行遺傳算法，調(diào)整其參數(shù)。

19:13326.2基本遺傳算法19:13336.2基本遺傳算法

19:133419:13356.3遺傳算法的數(shù)學(xué)基礎(chǔ)一、模式定理1、模式的定義由編碼串的結(jié)構(gòu)形式變化表明，模式是一個(gè)字符串集在某些位置上的相似性。對于二進(jìn)制編碼方式，個(gè)體是由二值編碼串集{0,1}所組成，由此產(chǎn)生了常見的0,1編碼串，再加入一個(gè)通配符“*”，其含義即可表示為0也可表示為1。這樣就將二值字符串?dāng)U展成了三值字符串{0,1,*}，由此可以產(chǎn)生00110、01*11、*01**等編碼串。模式：描述基因串集中相似類基因串的模板，該類基因串中某些特征位結(jié)構(gòu)相同，稱為“模式”。通俗地講，基于三值字符集{0,1,*}所產(chǎn)生的一類能夠描述在某些位置上具有結(jié)構(gòu)相似性的0，1編碼串集的編碼，稱為模式。19:13366.3遺傳算法的數(shù)學(xué)基礎(chǔ)模式階(schemaorder)：模式H中確定位置的個(gè)數(shù),稱為該模式的階，記作O(H)。例如，在二進(jìn)制編碼中，一個(gè)模式的階就是所有0和1的數(shù)目。模式H=**1*0*的階數(shù)為2，記為O(H)＝2；，模式H=1**10*的階數(shù)為3，記為O(H)＝3；顯然一個(gè)模式的階越高，其樣本數(shù)就越少，其確定性也越高。定義長度(DefiningLength)：模式H中第一個(gè)確定位和最后一個(gè)確定位置的距離稱作該模式的定義長度。例如：模式H=**1*0*的定義長度為2，記為δ(H)=2，這是因?yàn)榈谝粋€(gè)確定位置為3，最后一個(gè)確定位置為5，他們之間的距離δ(H)=5-3=2。若模式H=1*****僅有一個(gè)確定位置，根據(jù)概念該模式的定義長度為0。19:13376.3遺傳算法的數(shù)學(xué)基礎(chǔ)2、選擇對模式的影響選擇操作能使模式的數(shù)量以指數(shù)形式增減，但由于選擇操作只能將某些高適應(yīng)度的個(gè)體復(fù)制，低適應(yīng)度的個(gè)體淘汰，它并不能產(chǎn)生新的模式結(jié)構(gòu)，因而選擇操作對性能的改進(jìn)是有限的。

19:13386.3遺傳算法的數(shù)學(xué)基礎(chǔ)3、交叉對模式的影響交叉操作是基因串之間的有組織而又是隨機(jī)的信息交換，它在創(chuàng)造新結(jié)構(gòu)的同時(shí)，應(yīng)盡可能少的破壞復(fù)制過程所選擇的高適應(yīng)度模式。在選擇和交叉操作共同作用下，模式數(shù)量的增長或減少，取決于其模式的平均適應(yīng)度的高低和定義長度的長短，平均適應(yīng)度越大，定義長度越小，則H的數(shù)量就越多。19:13396.3遺傳算法的數(shù)學(xué)基礎(chǔ)4、變異對模式的影響19:13406.3遺傳算法的數(shù)學(xué)基礎(chǔ)5、模式定理在遺傳算子選擇、交叉和變異的作用下，具有低階、短定義長度以及平均適應(yīng)度高于群體平均適應(yīng)度的模式，將在子代中呈指數(shù)級地增長。模式定理是遺傳算法的理論基礎(chǔ)，適用于二進(jìn)制編碼，對其他編碼方式未必成立。

19:13416.3遺傳算法的數(shù)學(xué)基礎(chǔ)二、積木塊假設(shè)由模式定理可知，具有低階、短定義長度以及平均適應(yīng)度高于群體平均適應(yīng)度的模式，在子代中將呈指數(shù)級增長。這類模式在遺傳算法中非常重要，稱之為積木塊(BuildingBlock)。積木塊假設(shè)(BuildingBlockHypothesis)：低階、短定義長度、高平均適應(yīng)度的模式在遺傳算子作用下，相互結(jié)合，能生成高階、長定義長度、高平均適應(yīng)度的模式，可最終生成全局最優(yōu)解。

19:13426.4遺傳算法的改進(jìn)一、早熟現(xiàn)象在遺傳算法進(jìn)化的過程中，在某些時(shí)候會出現(xiàn)以下情況:(1）當(dāng)群體中出現(xiàn)個(gè)別或極少數(shù)適應(yīng)度值相當(dāng)高的個(gè)體時(shí),由于選擇機(jī)制就有可能導(dǎo)致這些個(gè)體在群體中迅速繁殖，經(jīng)過少數(shù)幾次迭代后就占滿了群體的位置,這樣GA的求解過程就結(jié)束了，但這樣很有可能是收斂到局部最優(yōu)解，即遺傳算法的不成熟收斂；（2）當(dāng)群體中個(gè)體適應(yīng)度彼此非常接近時(shí)，便失去了種群的多樣性，這些個(gè)體進(jìn)行交配的機(jī)會相等，而且交叉后得到的新個(gè)體也不會有多大變化，這樣搜索過程也不能有效地進(jìn)行，從而使進(jìn)化過程陷于停頓的狀態(tài),。這兩種情況統(tǒng)稱“早熟”現(xiàn)象。19:13436.4遺傳算法的改進(jìn)二、自適應(yīng)遺傳算法自適應(yīng)遺傳算法是指個(gè)體的交叉和變異率由個(gè)體在當(dāng)前種群中的優(yōu)良程度來自適應(yīng)決定，并隨遺傳代數(shù)的變化而變化。動態(tài)自適應(yīng)技術(shù)在進(jìn)化過程中通過調(diào)整遺傳控制參數(shù)可以克服早熟現(xiàn)象，在進(jìn)化早期，群體中個(gè)體的差異較大，所以選擇操作和交叉操作的作用比較明顯，進(jìn)化速度也較快；但在進(jìn)化的后期，由于選擇問題和固定交叉、變異的問題使得種群中個(gè)體的近親繁殖而造成的種群失去了多樣性，其適應(yīng)度值也比較接近，產(chǎn)生早熟現(xiàn)象。19:13446.4遺傳算法的改進(jìn)1．指數(shù)形式實(shí)現(xiàn)交叉和變異指數(shù)形式的交叉和變異是指在進(jìn)化過程中，交叉率和變異率隨指數(shù)形式變化。交叉率對遺傳代數(shù)影響較大，這是因?yàn)樵诘跗冢粨Q率選擇得大一些可以造成足夠的擾動，從而增強(qiáng)遺傳算法的搜索能力，而在迭代后期，交換率選得小一些可以避免破壞優(yōu)良基因，從而加快收斂速度?？紤]到交換率隨遺傳代數(shù)變化下降的關(guān)系，可將算式可表示為

19:13456.4遺傳算法的改進(jìn)19:13466.4遺傳算法的改進(jìn)19:13476.4遺傳算法的改進(jìn)2．平均適應(yīng)度形式實(shí)現(xiàn)交叉和變異以平均適應(yīng)度形式的交叉和變異是指在進(jìn)化過程中，交叉率和變異率隨該帶的平均適應(yīng)度變化而變化。平均適應(yīng)度在一定意義上反映整個(gè)種群的變化趨勢，因此可以平均適應(yīng)度形式判定種群中的交叉和變異率，即系統(tǒng)自適應(yīng)產(chǎn)生的交叉和變異率必須同這一代的平均適應(yīng)度相關(guān)聯(lián)，如下式所示19:13486.4遺傳算法的改進(jìn)19:13496.4遺傳算法的改進(jìn)19:13506.4遺傳算法的改進(jìn)19:13516.4遺傳算法的改進(jìn)三、小生境技術(shù)在遺傳進(jìn)化過程中，尤其是對于一些多峰值函數(shù)的優(yōu)化計(jì)算時(shí)，在尋優(yōu)過程中往往都會找一些局部最優(yōu)解并徘徊其中，很難跳出。使得進(jìn)化后期大量個(gè)體收斂于該局部優(yōu)化解從而陷入早熟的現(xiàn)象。為此，小生境技術(shù)的引入也是為了實(shí)現(xiàn)尋優(yōu)過程的全局最優(yōu)。幾種小生境策略：

19:13526.4遺傳算法的改進(jìn)1．基于預(yù)選擇機(jī)制的小生境策略只有在子個(gè)體的適應(yīng)度值超過其父個(gè)體時(shí)，子個(gè)體才能代替父個(gè)體，進(jìn)入下一代群體，