第4章-遺傳算法.ppt

1、第四章遺傳算法，Contents，算法簡介，1，4.1遺傳算法簡介，遺傳算法是什么？遺傳算法(Genetic Algorithm，GA)是進(jìn)化計(jì)算的一個(gè)分支，是模擬自然界生物進(jìn)化過程的隨機(jī)搜索算法。遺傳算法的來源是什么？是誰提出來的？GA思想源于自然選擇“自然選擇”和“適者生存”的進(jìn)化規(guī)律，通過模擬生物進(jìn)化中的自然選擇和交配變異，探索問題的全局最佳解決方法。美國密歇根大學(xué)教授約翰h霍蘭首次提出。目前廣泛應(yīng)用于各種工程領(lǐng)域的優(yōu)化問題。4.1.1基本原理，遺傳算法，生物進(jìn)化生命從地球出生開始漫長的生物進(jìn)化過程，低水平簡單的生物類型逐漸發(fā)展成高級(jí)復(fù)雜的生物類型。這個(gè)過程已經(jīng)通過對(duì)古生物、胚胎學(xué)、比較

2、解剖學(xué)等的研究證明。生物進(jìn)化的原因自古以來就有多種解釋，其中被廣泛接受的是達(dá)爾文的自然選擇理論。4.1.1的基本原理，自然選擇說，生物要想生存，就必須進(jìn)行生存斗爭。生存斗爭有種內(nèi)斗爭、種間斗爭、生物和武器環(huán)境之間的斗爭三個(gè)方面。在生存斗爭中，具有有利變異的個(gè)體容易生存，留給后代有利變異的機(jī)會(huì)更多，具有不利變異的個(gè)體容易淘汰，產(chǎn)生后代的機(jī)會(huì)也少得多。因此，在生存斗爭中獲勝的個(gè)人對(duì)環(huán)境的適應(yīng)性比較強(qiáng)。達(dá)爾文在生存斗爭中消除赤字生存和不安的這種過程被稱為自然選擇。達(dá)爾文的自然選擇學(xué)說表明遺傳和變異是影響生物進(jìn)化的本質(zhì)因素。4.1.1基本原理，4.1.1基本原理，4.1.1基本原理，生物進(jìn)化過程，基因

3、重組過程，1，也稱為模式定義模式塊(building block)，是描述一系列子集的相似模板。定義1模式：在群體中編碼的某些位置具有相似結(jié)構(gòu)的染色體集。例如：染色體的編碼是由0或1組成的二進(jìn)制序列，模式01*0表示代碼字符串中以01開頭和以0結(jié)尾的相應(yīng)染色體集。4.1.1基本原理、圖案清理、圖案樣例和圖案*1010110與以下兩個(gè)字符串匹配：01010101110 110101110和圖案* 1010110匹配以下四個(gè)字符串：010100110 01010110 110110，4.1.1基本原理，定義兩個(gè)圖案的順序是圖案中出現(xiàn)的“0”和“1”的數(shù)字，并以o(s)記錄。具有給定值的基因數(shù)。例如

4、：模式“0 * * * *”的階數(shù)為1，模式“10*1*”的階數(shù)為3。定義三種模式的長度是陣列中第一個(gè)確定位置和最后一個(gè)確定位置之間出現(xiàn)的距離，記錄為。例如：模式“01 * * * *”的長度為1，模式“0*1”的長度為4。遺傳算法的本質(zhì)是通過選擇、交叉、突變等搜索模式，在群體中指數(shù)增長低順序、定義長度小、平均適應(yīng)值高于群體平均適應(yīng)值的模式。也就是說，隨著進(jìn)化的進(jìn)行，更好的染色體數(shù)迅速增加。模式定理證明了遺傳算法找到最優(yōu)解的可能性。但是，算法不能保證必須找到全局優(yōu)化。4.1.1基本原理，2，構(gòu)造塊假設(shè)：低階、較小定義長度和平均適宜值表示高于組平均適應(yīng)值的模式。積木塊假定在遺傳算法運(yùn)行期間，積木

5、塊受遺傳運(yùn)算符的影響，接近可相互結(jié)合的新的、更好的積木，最終接近全局最優(yōu)解決方案。構(gòu)造塊假設(shè)補(bǔ)充了模式定理，表明遺傳算法具有尋找全局最優(yōu)解的能力。目前的研究不能對(duì)積木假設(shè)是否成立提供嚴(yán)格的判斷和證明，但很多實(shí)驗(yàn)和應(yīng)用為積木假設(shè)提供了支持。，4.1.1基本原理，4.1.2研究進(jìn)展，GA研究內(nèi)容和方向，與GA相關(guān)的重要學(xué)術(shù)雜志和國際會(huì)議，重要學(xué)術(shù)雜志evolutilonary computation IEEE transactions on evolutilonary computation重要國際會(huì)議iii 第一代人口生成，適者生存，解碼后近似最優(yōu)解決方案，4.1.4基本過程，4.2遺傳算法過程

6、，流程結(jié)構(gòu)染色體編碼組初始化自適應(yīng)值評(píng)估選擇運(yùn)算符配對(duì)運(yùn)算符算法流程圖和偽代碼應(yīng)用示例函數(shù)優(yōu)化問題算法的執(zhí)行步驟圖，也稱為簡單遺傳算法的基本遺傳算法(Simple Genetic Algorithm:SGA) 染色體編碼方法：首先要將問題的答案空間編碼，以便用遺傳算法操作。更常用的是二進(jìn)制編碼方法，現(xiàn)在使用非冗馀編碼的情況也越來越多?；具z傳算法的組成部分，染色體編碼，二進(jìn)制編碼方法浮點(diǎn)編碼方法，0000000，1111111，使用生成隨機(jī)數(shù)的方法初始化染色體的每個(gè)一維變量的值。初始化染色體的時(shí)候，要仔細(xì)觀察染色體是否符合優(yōu)化問題的有效解法的定義。如果在進(jìn)化開始的時(shí)候，保證早期群體已經(jīng)是某種程

7、度上的優(yōu)秀群體，那么算法就能有效地提高尋找全局最優(yōu)解決方案的能力。組初始化，評(píng)估函數(shù)用于評(píng)估每條染色體的適應(yīng)性，以區(qū)分優(yōu)劣。評(píng)估函數(shù)在解決函數(shù)優(yōu)化問題時(shí)，經(jīng)常根據(jù)問題的優(yōu)化目標(biāo)來確定，例如，使用問題定義目標(biāo)函數(shù)作為評(píng)估函數(shù)的原型。遺傳算法中適應(yīng)值越大的染色體越優(yōu)秀。因此，對(duì)于求解最大值的幾個(gè)數(shù)值優(yōu)化問題，可以直接應(yīng)用由問題定義的函數(shù)表達(dá)式。但是，對(duì)于其它優(yōu)化問題，定義為問題的目標(biāo)函數(shù)表達(dá)式必須經(jīng)過一定的轉(zhuǎn)換。適應(yīng)值評(píng)估，選擇運(yùn)算符，輪盤選擇算法，fi是個(gè)人的適應(yīng)能力；Fsum是人口的總適應(yīng)度。Pi是單個(gè)I的選擇概率。設(shè)置輪選擇的詳細(xì)說明流程順序匯總組中個(gè)人的適合性、其累計(jì)值、n個(gè)組和最后一個(gè)累

8、計(jì)值Sn。0，生成均勻分布在Sn段的隨機(jī)數(shù)r。如果依次比較Si和r，則第一次出現(xiàn)大于或等于r的Si的相應(yīng)單獨(dú)I將被選擇為復(fù)制對(duì)象。重復(fù)步驟2和3，直到滿足所需的復(fù)制對(duì)象數(shù)。在交配操作符、染色體交配階段，如果每個(gè)染色體的隨機(jī)(0，1)小于Pc，則意味著該染色體可以進(jìn)行交配操作(其中隨機(jī)(0，1)在0，1之間均勻分布的隨機(jī)數(shù))，否則染色體不參與交配。根據(jù)Pc交配的概率，兩個(gè)選定的染色體進(jìn)行交配，交換每個(gè)基因的一部分，產(chǎn)生兩個(gè)新的子代染色體。具體工作是隨機(jī)制作有效的交配位置，以交換染色體在其交配位置的所有基因。交配運(yùn)算符，單點(diǎn)交叉，兩點(diǎn)交叉，染色體的變異作用于基因，對(duì)交配后新群體中染色體的每個(gè)基因，

9、根據(jù)變異概率Pm判定基因是否變異。如果Random(0，1)小于Pm，則更改該基因的值(其中Random(0，1)是在0，1之間均勻分布的隨機(jī)數(shù))。否則，基因?qū)⒈３植蛔?。，變異運(yùn)算符，4，執(zhí)行參數(shù)n:組大小，即組中包含的對(duì)象數(shù)。t:由遺傳算法終止的進(jìn)化代數(shù)。Pc:交叉概率，通常為0.40.99。Pm:可變概率，通常為0.00010.1。遺傳算法流程圖和偽代碼，問題的解決-組攀登，進(jìn)化算法的問題解決過程是持續(xù)攀登過程，登山模擬，搜索空間，隨機(jī)生成初始解決方案，登山模擬，搜索空間，持續(xù)交叉變異和選擇，登山效果，登山模擬，搜索空間，持續(xù)交叉登山的模擬，搜索空間，通過不斷的交叉變異和選擇實(shí)現(xiàn)登山的效果

10、，登山的模擬，搜索空間，最終達(dá)到最佳，4.2.2應(yīng)用案例，示例4.1已知函數(shù)，在這里使用遺傳算法實(shí)現(xiàn)y的，max。執(zhí)行階段、運(yùn)算符選擇參數(shù)設(shè)置動(dòng)態(tài)策略和自適應(yīng)策略混合遺傳算法并行遺傳算法、4.3遺傳算法的改進(jìn)、遺傳算法的諸多優(yōu)點(diǎn)，但是目前存在的問題仍然很多，如早熟現(xiàn)象、接近最優(yōu)解決方案時(shí)收斂速度慢等。很多專家的持續(xù)研究，致力于促進(jìn)遺傳算法的發(fā)展，深入研究編碼方法、控制參數(shù)的確定、選擇和交叉方法，引入提高遺傳算法性能的動(dòng)態(tài)策略和適應(yīng)策略，提出多種變體的遺傳算法(VCGA)，簡單地說，4.3遺傳算法的改進(jìn)，4.3.1運(yùn)算符的選擇，影響算法的搜索能力和執(zhí)行效率。n設(shè)置越大，應(yīng)用一次進(jìn)化的模式就越多，

11、可以確保群體的多樣性，提高算法的搜索能力，但由于組內(nèi)染色體數(shù)較多，只能增加算法計(jì)算量，降低算法的執(zhí)行效率。如果將n設(shè)置得小，計(jì)算量就會(huì)減少，但在每個(gè)進(jìn)化中，減少了組包含更好染色體的能力。n的設(shè)置通常為20100。影響算法的計(jì)算量和交配變異操作的效果。l的設(shè)置與優(yōu)化問題密切相關(guān)，通常由問題定義的解決方案的形式和選擇的編碼方法決定。對(duì)于二進(jìn)制編碼方法，染色體長度l根據(jù)解決方案的值范圍和指定的精度要求選擇大小。對(duì)于浮點(diǎn)編碼方法，染色體的長度l等于問題定義的解決方案的維數(shù)d。Goldberg等公司除了提出染色體長度的特定編碼方法外，還提出了染色體長度不固定的可變長度染色體遺傳算法Messy GA。4.

12、3.2設(shè)定參數(shù)，確定參與交配的進(jìn)化過程人口的平均染色體數(shù)。值通常介于0.4和0.99之間。也可以使用自適應(yīng)方法調(diào)整算法運(yùn)行過程中的交配概率。增加群體進(jìn)化的多樣性，決定進(jìn)化過程中在群體中引起變異的基因的平均數(shù)量。Pm的值不能太大。變異對(duì)發(fā)現(xiàn)的更好的解決方案起一定的破壞作用，因此如果Pm值太大，算法當(dāng)前處于更好的搜索狀態(tài)，則可能會(huì)返回到原始狀態(tài)不好的狀態(tài)。Pm的值通常介于0.001和0.1之間。也可以使用自適應(yīng)方法在算法運(yùn)行過程中調(diào)整Pm值。r取決于使用的染色體編碼系統(tǒng)。對(duì)于二進(jìn)制編碼方法，R=0，1；對(duì)于浮點(diǎn)編碼方法，R等于由優(yōu)化問題定義的每個(gè)一維變量的值范圍。設(shè)置4.3.2參數(shù)，確定算法在應(yīng)用

13、特定問題時(shí)停止工作的時(shí)間，在輸出中發(fā)現(xiàn)的最佳解決方案，以及使用的終止條件。可以使算法在達(dá)到最大進(jìn)化代數(shù)時(shí)停止，最大進(jìn)化代數(shù)通?？梢栽O(shè)置為1001000，該值可以根據(jù)特定問題適當(dāng)?shù)匦薷?。還可以通過檢查找到的當(dāng)前最佳解決方案是否達(dá)到錯(cuò)誤要求來控制算法的停止?；蛘撸绻惴ㄔ陂L期進(jìn)化期間發(fā)現(xiàn)的最佳解決方案沒有得到改善，則算法可能會(huì)停止運(yùn)行。影響算法在人口選擇上，適當(dāng)?shù)脑u(píng)價(jià)函數(shù)要適當(dāng)區(qū)分染色體的優(yōu)劣，確保選擇機(jī)制的有效性，以提高群體的進(jìn)化力。評(píng)價(jià)函數(shù)的設(shè)置與優(yōu)化問題的解決目標(biāo)有關(guān)。評(píng)價(jià)函數(shù)必須滿足更好染色體的適應(yīng)值更大的規(guī)定。要提高選擇的性能，可以稍微修改計(jì)算函數(shù)。當(dāng)前主要評(píng)估函數(shù)修改方法如下：線性變

14、換；動(dòng)力轉(zhuǎn)換；指數(shù)轉(zhuǎn)換等。4.3.2參數(shù)設(shè)置，1，最佳保留策略查找當(dāng)前組的最高級(jí)別的適應(yīng)和最低級(jí)別的對(duì)象，如果當(dāng)前組的最佳對(duì)象的適應(yīng)度最高，則使用當(dāng)前組的最佳對(duì)象作為新的最佳對(duì)象，高于到目前為止最佳對(duì)象的適應(yīng)度。用迄今為止最好的對(duì)象替換當(dāng)前群體中最差的對(duì)象。最優(yōu)保留策略是遺傳算法收斂性的重要保證條件，確保到目前為止得到的最優(yōu)對(duì)象不會(huì)因交叉、變異等操作而受損。通過使特定區(qū)域的最佳對(duì)象快速擴(kuò)散，而不是輕易消除，降低了算法的全局搜索能力。此方法必須與其他選擇操作方法結(jié)合使用，才能獲得良好的效果。4.3.3動(dòng)態(tài)策略和自適應(yīng)策略，2，自適應(yīng)遺傳算法自適應(yīng)遺傳算法(AGA)的交叉概率和變異概率可以根據(jù)自適

15、應(yīng)度自動(dòng)改變。如果群體的個(gè)體適應(yīng)度一致或局部最優(yōu)傾向，則提高交叉概率和變異概率，如果群體適應(yīng)度分布，則降低交叉概率和變異概率。此外，對(duì)于適應(yīng)值高于組的平均適應(yīng)值的對(duì)象，對(duì)應(yīng)于低交叉概率和變異概率，以便相應(yīng)的解決方案保護(hù)到下一代。低于平均自適應(yīng)值的對(duì)象對(duì)應(yīng)于較高的相交概率和變異概率，此解決方案被消除。4.3.3動(dòng)態(tài)策略和自適應(yīng)策略，2，自適應(yīng)遺傳算法，4.3.3動(dòng)態(tài)策略和自適應(yīng)策略，3，生態(tài)位遺傳算法遺傳算法中模擬生態(tài)位的方法主要為：(1)基于預(yù)選的間隙實(shí)施方法Cavicchio 1970年的建議，基本思路：結(jié)果子實(shí)體只有在新創(chuàng)建的子實(shí)體的適應(yīng)性超過父實(shí)體的適應(yīng)性時(shí)，才能替換父實(shí)體以后代的身份繼承，否則父實(shí)體將保留為以下子組：這種方法實(shí)際上只替換了編碼結(jié)構(gòu)相似的部分實(shí)體，可以有效地保持群體的多樣性。4.3.3動(dòng)態(tài)策略和適應(yīng)策略，3，基于小生