張砦-遺傳算法在多目標(biāo)優(yōu)化中的應(yīng)用-文庫吧資料
2025-01-05 17:27本頁面
【正文】 即使經(jīng)過一些簡化之后可以進(jìn)行求解，也會(huì)因簡化得太多而使得求解結(jié)果與實(shí)際相差甚遠(yuǎn)。實(shí)踐證明，遺傳算法對(duì)于組合優(yōu)化中的 NP完全問題非常有效。 (2) 組合優(yōu)化 隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴(kuò)大，有時(shí)在目前的計(jì)算機(jī)上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。下面是遺傳算法的一些主要應(yīng)用領(lǐng)域： (1) 函數(shù)優(yōu)化 函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對(duì)遺傳算法進(jìn)行性能評(píng)價(jià)的常用算例。 遺傳算法研究的主要問題 (1)局部最優(yōu) (2)收斂速度問題 (3)正確性問題 (4)算法的實(shí)現(xiàn)性問題 改進(jìn)：編碼方式、遺傳算子、控制參數(shù)。 (4)變異概率對(duì)收斂性的影響 變異操作是對(duì)種群模式的擾動(dòng)，有利于增加種群的多樣性 。 (3)交叉概率對(duì)收斂性的影響 交叉操作用于個(gè)體對(duì)，產(chǎn)生新的個(gè)體，實(shí)質(zhì)上是在解空間中進(jìn)行有效搜索。 (2)選擇操作對(duì)收斂性的影響 選擇操作使高適應(yīng)度個(gè)體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。與算法收斂性有關(guān)的因素主要包括種群規(guī)模、選擇操作、交叉概率和變異概率。通過這些遺傳操作，模式逐步向較好的方向進(jìn)化，最終得到問題的最優(yōu)解。M? Gen=Gen+1 輸出結(jié)果 終止 Y N Y Y Y N N N pc pm 算法流程圖 遺傳算法的特點(diǎn) （ 1）群體搜索，易于并行化處理； （ 2）不是盲目窮舉，而是啟發(fā)式搜索； （ 3）適應(yīng)度函數(shù)不受連續(xù)、可微等條件的約束，適用范圍很廣。M ? j = pm Ⅱ. 對(duì)每一個(gè)指定的變異點(diǎn)，對(duì)其基因值做取反運(yùn)算或用其它等位基因值來代替，從而產(chǎn)生出一個(gè)新的個(gè)體。 對(duì)于基本遺傳算法中用二進(jìn)制編碼符號(hào)串所表示的個(gè)體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為 0，則變異操作將該基因值變?yōu)?1，反之，若原有基因值為 1，則變異操作將其變?yōu)?0。 Ⅲ. 對(duì)每一對(duì)相互配對(duì)的個(gè)體，依設(shè)定的 交叉概率 pc在其交叉點(diǎn)處相互交換兩個(gè)個(gè)體的部分染色體，從而產(chǎn)生出兩個(gè)新的個(gè)體。 單點(diǎn)交叉算子 的具體計(jì)算過程如下： Ⅰ. 對(duì)群體中的個(gè)體進(jìn)行兩兩 隨機(jī) 配對(duì)。交換是遺傳算法產(chǎn)生新個(gè)體的主要手段。但是，適應(yīng)度小的個(gè)體也有可能被選中，以便增加下一代群體的多樣性。 比例選擇算子： 指個(gè)體被選中并遺傳到下一代群體中的概率與該個(gè)體的適應(yīng)度大小成正比。 1 i=l Umax ? umin 2l ? 1 = + 70352?(+3)/(2181) = ? = Umax ? umin 2l ? 1 得： （ 2） 個(gè)體適應(yīng)度評(píng)價(jià) (1) 當(dāng)優(yōu)化目標(biāo)是求函數(shù)最大值，并且目標(biāo)函數(shù)總?cè)≌禃r(shí)，可以直接設(shè)定個(gè)體的適應(yīng)度 F(X)就等于相應(yīng)的目標(biāo)函數(shù)值 f(X)，即： F(X)＝ f(X) (2) 對(duì)于求目標(biāo)函數(shù)最小值的優(yōu)化問題 ，理論上只需簡單地對(duì)其增加一個(gè)負(fù)號(hào)就可將其轉(zhuǎn)化為求目標(biāo)函數(shù)最大值的優(yōu)化問題，即： min f(X)＝ max (f(X)) 但實(shí)際優(yōu)化問題中的目標(biāo)函數(shù)值有正也有負(fù)，優(yōu)化目標(biāo)有求函數(shù)最大值，也有求函數(shù)最小值，顯然上面兩式保證不了所有情況下個(gè)體的適應(yīng)度都是非負(fù)數(shù)這個(gè)要求。 如： 010001001011010000 解碼： x = umin + ( ? bi 2i1 ) 在遺傳算法的實(shí)際應(yīng)用中，往往需要經(jīng)過多次試算后才能確定出這些參數(shù)合理的取值大小或取值范圍。 (4) 基本遺傳算法的運(yùn)行參數(shù) 基本遺傳算法有下述 4個(gè)運(yùn)行參數(shù)需要提前設(shè)定： ? M：群體大小，即群體中所含個(gè)體的數(shù)量，一般取 20100。這樣，根據(jù)不同種類的問題，必須預(yù)先確定好由目標(biāo)函數(shù)值到個(gè)體適應(yīng)度之間的轉(zhuǎn)換規(guī)則，特別是要預(yù)先確定好當(dāng)目標(biāo)函數(shù)值為負(fù)數(shù)時(shí)的處理方法。 (2) 個(gè)體適應(yīng)度評(píng)價(jià) 基本遺傳算法 按與個(gè)體適應(yīng)度成正比的概率來決定當(dāng)前群體中每個(gè)個(gè)體遺傳到下一代群體中的機(jī)會(huì)多少。初始群體中各個(gè)個(gè)體的基因值用均勻分布的隨機(jī)數(shù)來生成。同年，《 Advances in Geic Programming》，匯集許多研究工作者有關(guān)應(yīng)用遺傳規(guī)劃的經(jīng)驗(yàn)和技術(shù)。 ? 1992年， Koza出版專著《 Geic Programming:on the Programming of Computer by Means of Natural Selection》，該書全面介紹了遺傳規(guī)劃的原理及應(yīng)用實(shí)例，表明遺傳規(guī)劃己成為進(jìn)化算法的一個(gè)重要分支。 ? 1996年 《遺傳算法 + 數(shù)據(jù)結(jié)構(gòu) = 進(jìn)化程序》深入討論了遺傳算法的各種專門問題。 (3) 發(fā)展期 (90年代以后 ) 90年代，遺傳算法不斷地向廣度和深度發(fā)展。 ? 1985年，在美國舉行第一屆遺傳算法國際學(xué)術(shù)會(huì)議(International Conference on Geic Algorithms，簡稱ICGA），與會(huì)者交流運(yùn)用遺傳算法的經(jīng)驗(yàn)。 ? 1985年，作為 Holland的學(xué)生， 《 Geic Algorithms—— in Search， Optimization and Machine Learning》
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1