基本遺傳算法c.ppt

1、遺傳算法,主要內(nèi)容,概述 基本遺傳算法 遺傳算法的數(shù)學(xué)理論 應(yīng)用舉例,概述,遺傳算法（Genetic Algorithms）是基于生物進(jìn)化理論的原理發(fā)展起來的一種廣為應(yīng)用的、高效的隨機(jī)搜索與優(yōu)化的方法。 1975年美國霍蘭(Holland)教授發(fā)表了第一本比較系統(tǒng)論述遺傳算法的專著自然系統(tǒng)與人工系統(tǒng)中的適應(yīng)性(Adaptation in Natural and Artificial Systems)。該書系統(tǒng)地闡述了遺傳算法的基本理論和方法。,概述,遺傳算法，從數(shù)學(xué)角度看，是一種概率性搜索算法；從工程學(xué)角度看，它是一種自適應(yīng)的迭代尋優(yōu)過程。它從某一隨機(jī)產(chǎn)生的或者特定的初始群體出發(fā)，按照一定得操

2、作規(guī)則，不斷的迭代計(jì)算，并根據(jù)每一個(gè)個(gè)體的適應(yīng)度，保留優(yōu)良品種，淘汰次品，引導(dǎo)搜索過程向最優(yōu)解逼近。 遺傳算法的主要特點(diǎn)是直接對結(jié)構(gòu)對象進(jìn)行操作；具有內(nèi)在的隱并行性和較好的全局尋優(yōu)能力；采用概率化得尋優(yōu)方法。,基本遺傳算法,基本遺傳算法（simple genetic algorithms, SGA）只使用選擇算子、交叉算子和變異算子這三種基本遺傳算子。其遺傳進(jìn)化操作簡單，容易理解，是其他遺傳算法的雛形和基礎(chǔ)。 基本遺傳算法的構(gòu)成要素主要有：染色體編碼，個(gè)體適應(yīng)度評價(jià)，遺傳算子以及遺傳參數(shù)設(shè)置等。,基本遺傳算法的構(gòu)成要素,1、染色體編碼方法 基本遺傳算法使用固定長度的二進(jìn)制符號串來表示群體中的個(gè)

3、體，其等位基因是由二值符號集0,1所組成。初始種群眾各個(gè)個(gè)體的基因值可用均勻分布的隨機(jī)數(shù)來生成。如： X = 001011011001110010 就可表示一個(gè)個(gè)體，該個(gè)體的染色體長度是 n = 18。,基本遺傳算法的構(gòu)成要素,2、適應(yīng)度函數(shù) 基本遺傳算法按與個(gè)體適應(yīng)度成正比的概率來決定當(dāng)前群體中每個(gè)個(gè)體遺傳到下一代群體中的機(jī)會(huì)多少。為正確計(jì)算這個(gè)概率，這里要求所有個(gè)體的適應(yīng)度必須為正或零。這樣，根據(jù)不同種類的問題，必須預(yù)先確定好由目標(biāo)函數(shù)到個(gè)體適應(yīng)度之間的轉(zhuǎn)換規(guī)則，特別是要預(yù)先確定好當(dāng)目標(biāo)函數(shù)值為負(fù)數(shù)時(shí)的處理方法。,基本遺傳算法的構(gòu)成要素,3、遺傳算子 基本遺傳算法使用下述三種遺傳算子： （

4、1）選擇算子 按照某種策略從父代中挑選個(gè)體進(jìn)入中間群體，如使用比例選擇。 （2）交叉算子 隨機(jī)地從中間群體中抽取兩個(gè)個(gè)體，并按照某種交叉策略使兩個(gè)個(gè)體相互交換部分染色體碼串，從而形成兩個(gè)新的個(gè)體。如使用單點(diǎn)交叉。 （3）變異算子 按照一定的概率，改變?nèi)旧w中某些基因的值。 （4）基本遺傳算法的運(yùn)行參數(shù),選擇算子-比例選擇方法,比例選擇算法是一種回放式隨機(jī)采樣的方法。其基本思想是：各個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比。 設(shè)某一代的群體大小為n，某一個(gè)體得適應(yīng)度值為 ，那么它被選中的概率為：,選擇算子-比例選擇方法,將每個(gè)串的選取概率畫在一張輪盤上。 每轉(zhuǎn)動(dòng)一次輪盤，指針落入串i所占區(qū)域的概率

5、為 ，當(dāng) 比較大時(shí)，串i被選取的概率就比較大。當(dāng)某一個(gè)體被選中時(shí)，它就完全復(fù)制產(chǎn)生下一代。,交叉算子,交叉算子有一點(diǎn)交叉、二點(diǎn)交叉、多點(diǎn)交叉和均勻交叉。 一點(diǎn)交叉如下進(jìn)行： （1）在染色體中隨機(jī)選擇一個(gè)點(diǎn)作為交叉點(diǎn)； （2）第一個(gè)父輩的交叉點(diǎn)前的串和第二個(gè)父輩交叉點(diǎn)后的串組成一個(gè)新的染色體，第二個(gè)父輩的交叉點(diǎn)前的串和第一個(gè)父輩交叉點(diǎn)后的串組成另一個(gè)新的染色體。例如，下面兩個(gè)進(jìn)行交叉： 11010 01100101101 yxyyx yxxyyyxyxxy 形成新的串11010yxxyyyxyxxy和yxyyx01100101101 替代生成他們的父輩串放入中間群體。,變異算子,對于基本遺傳算法

6、中二進(jìn)制編碼符號串所表示的個(gè)體，若需要進(jìn)行變異操作的某一基因值為0，則變異操作將該基因值變?yōu)?；反之，若原有基因值為1，則變異操作將其變?yōu)?。 基本位變異算子的具體執(zhí)行過程： （1）對個(gè)體的每一個(gè)基因座，依變異概率 指定其為變異點(diǎn)； （2）對每一個(gè)指定的變異點(diǎn)，對其基因值做取反運(yùn)算或用其他等位基因來代替，從而產(chǎn)生出一個(gè)新的個(gè)體。,基本遺傳算法的運(yùn)行參數(shù),M：群體大小，即群體中所含個(gè)體的數(shù)量，一般取為 20 100 。 T： 遺傳運(yùn)算的終止進(jìn)化代數(shù)， 一般取為 100 500。 ：交叉概率，一般取為 0.40.9. ：變異概率，一般取為 0.0001 0.1. 注：這4個(gè)運(yùn)行參數(shù)對遺傳算法的求解

7、結(jié)果和求解效率都有一定的影響，但目前尚無合理選擇它們的理論依據(jù)。在遺傳算法的實(shí)際應(yīng)用中，往往需要經(jīng)過多次試算后才能確定出這些參數(shù)合理的取值大小或取值范圍。,基本遺傳算法,一般遺傳算法的主要步驟如下： （1）隨機(jī)產(chǎn)生一個(gè)由確定長度的特征字符串組成的初始種群。 （2）對該字符串種群迭代地執(zhí)行下面的步驟：和步驟，直到滿足停止準(zhǔn)則為止： 計(jì)算種群中每個(gè)個(gè)體字符串的適應(yīng)值。 應(yīng)用復(fù)制、交叉和變異等遺傳算子產(chǎn)生下一代種群。 （3）把在后代中出現(xiàn)的最好的個(gè)體字符串指定為遺傳算法的執(zhí)行結(jié)果，這個(gè)結(jié)果可以表示問題的一個(gè)解。,基本遺傳算法,根據(jù)遺傳算法思想，可以給出如圖的基本遺傳算法流程圖 其中GEN是當(dāng)前進(jìn)化代

8、數(shù)；M是算法執(zhí)行的最大次數(shù)。,基本遺傳算法,基本遺傳算法可以定義為一個(gè)八元組：,遺傳算法的數(shù)學(xué)理論,模式理論 定義：基于三值字符集0、1、*所產(chǎn)生的能描述具有某些結(jié)構(gòu)相似的0、1字符串集的字符串稱作模式。 以長度為5的字符串為例，模式*0001描述了在位置2、3、4、5具有形式“0001”的所有字符串，即00001，10001；又比如模式*1*0，描述了所有在位置2為“1”及位置5為“0”的字符串。由此可以看出，模式的概念為我們提供了一種簡單地用于描述在某些位置上具有結(jié)構(gòu)相似性的0、1字符串集合的方法。這里需要強(qiáng)調(diào)的是，“*”只是一個(gè)描述符，而并非遺傳算法中實(shí)際的運(yùn)算符號，它是為描述方便而引入

9、的符號。通過模式，而將多個(gè)不同的串聯(lián)系起來。,遺傳算法的數(shù)學(xué)理論,模式階：模式H中有確定值的基因位個(gè)數(shù)稱作該模式的模式階（schema order），記作O(H)。 例如，模式011*1*的階數(shù)為4，而模式0*的階數(shù)為1。顯然一個(gè)模式的階越高，其所代表的集合所包含的個(gè)體數(shù)目越少，因而確定性越高。 模式定義長度：模式H中的第一個(gè)確定位置和最后一個(gè)確定位置間的距離稱作該模式的定義長度（defining length），記作(H)。 比如模式011*1*的定義距為4，而模式0*的定義距為0。,遺傳算法的數(shù)學(xué)理論,M（H,t）表示在t時(shí)刻群體中包含模式H的字符串的個(gè)數(shù)。f（H,t）表示當(dāng)前群體當(dāng)中包含

10、模式H的個(gè)體的評估函數(shù)的平均值。 表示當(dāng)前群體的平均的評估函數(shù)值。中間群體中包含模式H的字符串個(gè)數(shù)可表示為：,遺傳算法的數(shù)學(xué)理論,設(shè)遺傳算法的交叉概率和變異概率分別為 和 ，L為個(gè)體基因鏈碼的長度，模式定理的表示方法如下： 由定理知，在選擇、交叉和變異算子的作用下，具有低階、短的定義長度，并且平均適應(yīng)度高于群體平均適應(yīng)度的模式將按指數(shù)級增長。,遺傳算法的數(shù)學(xué)理論,由前面的模式定理可知，具有低階、短定義距以及平均適應(yīng)度高于群體適應(yīng)度的模式在后代中將以指數(shù)級增長。這類模式在遺傳算法中非常重要，我們稱之為“積木”或“基因塊”(building block)。如同搭“積木”一樣，這些“好” 的模式在遺

11、傳操作下相互拼接、結(jié)合，產(chǎn)生適應(yīng)度更高的個(gè)體，從而找到更優(yōu)的可行解。這正是“積木假說” （building block hypothesis）所揭示的內(nèi)容。 積木塊假設(shè)：低階、短定義長度、高平均適應(yīng)度的模式在遺傳算子作用下，相互結(jié)合，能生成高階、長定義長度、高平均適應(yīng)度的模式，可最終生成全局最優(yōu)解。,應(yīng)用舉例,應(yīng)用步驟 第一步：確定決策變量及其各種約束條件，即確定出個(gè)體的表現(xiàn)型 X 和問題的解空間。 第二步：建立優(yōu)化模型，即確定出目標(biāo)函數(shù)的類型（是求目標(biāo)函數(shù)最大值還是求目標(biāo)函數(shù)的最小值）及其數(shù)學(xué)描述形式或量化方法。 第三步：確定表示可行劫的染色體編碼方法，也即確定出個(gè)體的基因型 X 及遺傳算法的搜索空間。 第四步：確定解碼方法，即確定出由個(gè)體基因型 X 到個(gè)體表現(xiàn)型X的對應(yīng)關(guān)系或轉(zhuǎn)換方法。,應(yīng)用舉例,第五步：確定個(gè)體適應(yīng)度的量化評價(jià)方法，即確定出由目標(biāo)函數(shù)值 f(x) 到個(gè)體適應(yīng)度 f(x)的轉(zhuǎn)換規(guī)則。 第六步：設(shè)計(jì)遺傳算子，即確定出選擇運(yùn)算、交叉運(yùn)算、變異運(yùn)算等遺傳算子的具體操作方法。 第七步：確定遺傳算法的有關(guān)運(yùn)行參數(shù)，即確定出遺傳算法的N,T , , 等參數(shù)。 由上述構(gòu)造步驟可以看出，可行解的編碼方法、遺傳算子的設(shè)計(jì)是構(gòu)造遺傳算法是需要考慮的兩個(gè)主要問題，也是設(shè)計(jì)遺傳算法時(shí)的兩個(gè)關(guān)