人工智能及其應用 課件6 遺傳算法

第六章遺傳算法

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

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

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

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

19:139

最常用的染色體選擇技術是輪盤選擇。

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

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

19:13134、突變

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

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

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

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

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

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

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

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

1）確定問題，定義限制和最優(yōu)標準。

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

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

4）構建遺傳操作。

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

電力設備和維護需求

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

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

19:13296.2基本遺傳算法

然后用電力系統(tǒng)的總容量中減去這些值。時間間隔1：150-50=100

時間間隔2：150-35=115

時間間隔3：150-50=100時間間隔4：150-50=100

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

時間間隔2：115-90=25

時間間隔3：100-65=35

時間間隔4：100-70=30

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

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

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

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

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

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

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

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

19:13526.4遺傳算法的改進1．基于預選擇機制的小生境策略只有在子個體的適應度值超過其父個體時，子個體才能代替父個體，進入下一代群體，