遺傳算法Contents算法簡(jiǎn)介

1基本流程2改進(jìn)研究3相關(guān)應(yīng)用44.1遺傳算法簡(jiǎn)介遺傳算法是什么？遺傳算法（GeneticAlgorithm，GA）是進(jìn)化計(jì)算的一個(gè)分支，是一種模擬自然界生物進(jìn)化過(guò)程的隨機(jī)搜索算法。遺傳算法的思想來(lái)源是怎樣的？它由誰(shuí)提出的？GA思想源于自然界“自然選擇”和“優(yōu)勝劣汰”的進(jìn)化規(guī)律，通過(guò)模擬生物進(jìn)化中的自然選擇和交配變異尋找問(wèn)題的全局最優(yōu)解。它最早由美國(guó)密歇根大學(xué)教授JohnH.Holland提出，現(xiàn)在已經(jīng)廣泛應(yīng)用于各種工程領(lǐng)域的優(yōu)化問(wèn)題之中。4.1.1基本原理遺傳算法

達(dá)爾文進(jìn)化論現(xiàn)代遺傳學(xué)生物模擬技術(shù)4.1.1

基本原理生物遺傳進(jìn)化群體種群染色體基因適應(yīng)能力交配變異進(jìn)化結(jié)束遺傳算法搜索空間的一組有效解選擇得到的新群體可行解的編碼串染色體的一個(gè)編碼單元染色體的適應(yīng)值染色體交換部分基因得到新染色體染色體某些基因的數(shù)值改變算法結(jié)束生物遺傳進(jìn)化過(guò)程遺傳算法類(lèi)比關(guān)系4.1.1

基本原理生物進(jìn)化過(guò)程遺傳基因重組過(guò)程4.1.1

基本原理模式定理模式指群體中編碼的某些位置具有相似結(jié)構(gòu)的染色體集合

模式的定義長(zhǎng)度指模式中第一個(gè)具有確定取值的基因到最后一個(gè)具有確定取值的基因的距離

模式的階指模式中具有確定取值的基因個(gè)數(shù)Holland的模式定理提出，遺傳算法的實(shí)質(zhì)是通過(guò)選擇、交配和變異算子對(duì)模式進(jìn)行搜索，低階、定義長(zhǎng)度較小且平均適應(yīng)值高于群體平均適應(yīng)值的模式在群體中的比例將呈指數(shù)級(jí)增長(zhǎng)。即隨著進(jìn)化的不斷進(jìn)行，較優(yōu)染色體的個(gè)數(shù)將快速增加。4.1.1

基本原理積木塊假設(shè)積木塊指低階、定義長(zhǎng)度較小且平均適應(yīng)值高于群體平均適應(yīng)值的模式積木塊假設(shè)認(rèn)為在遺傳算法運(yùn)行過(guò)程中，積木塊在遺傳算子的影響下能夠相互結(jié)合，產(chǎn)生新的更加優(yōu)秀的積木塊，最終接近全局最優(yōu)解。4.1.2

研究進(jìn)展GA研究?jī)?nèi)容與方向

算法性能研究混合算法研究并行算法研究算法應(yīng)用研究與GA相關(guān)的重要學(xué)術(shù)期刊與國(guó)際會(huì)議重要學(xué)術(shù)期刊EvolutionaryComputationIEEETransactionsonEvolutionaryComputation……重要國(guó)際會(huì)議InternationalConferenceonGeneticAlgorithmACMGeneticandEvolutionaryComputationConferenceWorkshoponFoundationsofGeneticAlgorithmsandClassifierSystemsGeneticProgrammingConferenceInternationalWorkshoponArtificialLife……

4.2遺傳算法的流程流程結(jié)構(gòu)染色體編碼群體初始化適應(yīng)值評(píng)價(jià)選擇算子交配算子變異算子算法流程圖和偽代碼應(yīng)用舉例函數(shù)優(yōu)化問(wèn)題算法的執(zhí)行步驟示意圖染色體編碼二進(jìn)制編碼方法（BinaryRepresentation）浮點(diǎn)數(shù)編碼方法（FloatPointRepresentation）0000…00001111…1111一般情況下，遺傳算法在群體初始化階段采用的是隨機(jī)數(shù)初始化方法。采用生成隨機(jī)數(shù)的方法，對(duì)染色體的每一維變量進(jìn)行初始化賦值。初始化染色體時(shí)必須注意染色體是否滿(mǎn)足優(yōu)化問(wèn)題對(duì)有效解的定義。如果在進(jìn)化開(kāi)始時(shí)保證初始群體已經(jīng)是一定程度上的優(yōu)良群體的話(huà)，將能夠有效提高算法找到全局最優(yōu)解的能力。群體初始化評(píng)估函數(shù)用于評(píng)估各個(gè)染色體的適應(yīng)值，進(jìn)而區(qū)分優(yōu)劣。評(píng)估函數(shù)常常根據(jù)問(wèn)題的優(yōu)化目標(biāo)來(lái)確定，比如在求解函數(shù)優(yōu)化問(wèn)題時(shí)，問(wèn)題定義的目標(biāo)函數(shù)可以作為評(píng)估函數(shù)的原型。在遺傳算法中，規(guī)定適應(yīng)值越大的染色體越優(yōu)。因此對(duì)于一些求解最大值的數(shù)值優(yōu)化問(wèn)題，我們可以直接套用問(wèn)題定義的函數(shù)表達(dá)式。但是對(duì)于其他優(yōu)化問(wèn)題，問(wèn)題定義的目標(biāo)函數(shù)表達(dá)式必須經(jīng)過(guò)一定的變換。適應(yīng)值評(píng)價(jià)選擇算子輪盤(pán)賭選擇算法交配算子在染色體交配階段，每個(gè)染色體能否進(jìn)行交配由交配概率Pc（一般取值為0.4到0.99之間）決定，其具體過(guò)程為：對(duì)于每個(gè)染色體，如果Random(0,1)小于Pc則表示該染色體可進(jìn)行交配操作（其中Random(0,1)為[0,1]間均勻分布的隨機(jī)數(shù)），否則染色體不參與交配直接復(fù)制到新種群中。每?jī)蓚€(gè)按照Pc交配概率選擇出來(lái)的染色體進(jìn)行交配，經(jīng)過(guò)交換各自的部分基因，產(chǎn)生兩個(gè)新的子代染色體。具體操作是隨機(jī)產(chǎn)生一個(gè)有效的交配位置，染色體交換位于該交配位置后的所有基因。交配算子染色體的變異作用于基因之上，對(duì)于交配后新種群中染色體的每一位基因，根據(jù)變異概率Pm判斷該基因是否進(jìn)行變異。如果Random(0,1)小于Pm，則改變?cè)摶虻娜≈担ㄆ渲蠷andom(0,1)為[0,1]間均勻分布的隨機(jī)數(shù)）。否則該基因不發(fā)生變異，保持不變。變異算子遺傳算法流程圖和偽代碼4.2.2應(yīng)用舉例例4.1

已知函數(shù)，

其中，用遺傳算法求解y的

最大值。運(yùn)行步驟算子選擇參數(shù)設(shè)置混合遺傳算法并行遺傳算法4.3遺傳算法的改進(jìn)確定性采樣排擠模型最佳個(gè)體保存模型4.3.1算子選擇適應(yīng)值比例模型排序模型隨機(jī)錦標(biāo)賽模型無(wú)回放余數(shù)隨機(jī)采樣期望值模型選擇算子交配算子單性孢子交配算子邊重組交配算子循環(huán)交配算子順序交配算子部分匹配交配算子多點(diǎn)交配算子算術(shù)交配算子均勻交配算子兩點(diǎn)交配算子邊集合交配算子變異算子非均勻變異算子高斯變異算子邊界變異算子群體規(guī)模N

染色體長(zhǎng)度L

影響算法的搜索能力和運(yùn)行效率。若N設(shè)置較大，一次進(jìn)化所覆蓋的模式較多，可以保證群體的多樣性，從而提高算法的搜索能力，但是由于群體中染色體的個(gè)數(shù)較多，勢(shì)必增加算法的計(jì)算量，降低了算法的運(yùn)行效率。若N設(shè)置較小，雖然降低了計(jì)算量，但是同時(shí)降低了每次進(jìn)化中群體包含更多較好染色體的能力。N的設(shè)置一般為20~100。影響算法的計(jì)算量和交配變異操作的效果。L的設(shè)置跟優(yōu)化問(wèn)題密切相關(guān)，一般由問(wèn)題定義的解的形式和選擇的編碼方法決定。對(duì)于二進(jìn)制編碼方法，染色體的長(zhǎng)度L根據(jù)解的取值范圍和規(guī)定精度要求選擇大小。對(duì)于浮點(diǎn)數(shù)編碼方法，染色體的長(zhǎng)度L

跟問(wèn)題定義的解的維數(shù)D相同。除了染色體長(zhǎng)度一定的編碼方法，Goldberg等人還提出了一種變長(zhǎng)度染色體遺傳算法MessyGA，其染色體的長(zhǎng)度并不是固定的。4.3.2參數(shù)設(shè)置交配概率Pc

變異概率Pm

決定了進(jìn)化過(guò)程種群參加交配的染色體平均數(shù)目。取值一般為0.4至0.99。也可采用自適應(yīng)方法調(diào)整算法運(yùn)行過(guò)程中的交配概率。增加群體進(jìn)化的多樣性，決定了進(jìn)化過(guò)程中群體發(fā)生變異的基因平均個(gè)數(shù)。Pm的值不宜過(guò)大。因?yàn)樽儺悓?duì)已找到的較優(yōu)解具有一定的破壞作用，如果Pm的值太大，可能會(huì)導(dǎo)致算法目前處于的較好的搜索狀態(tài)倒退回原來(lái)較差的情況。Pm的取值一般為0.001至0.1之間。也可采用自適應(yīng)方法調(diào)整算法運(yùn)行過(guò)程中的Pm值。R視采用的染色體編碼方案而定。對(duì)于二進(jìn)制編碼方法，R={0,1}，而對(duì)于浮點(diǎn)數(shù)編碼方法，R與優(yōu)化問(wèn)題定義的解每一維變量的取值范圍相同。基因取值范圍R

4.3.2參數(shù)設(shè)置終止條件決定算法何時(shí)停止運(yùn)行，輸出找到的最優(yōu)解，采用何種終止條件，跟具體問(wèn)題的應(yīng)用有關(guān)。可以使算法在達(dá)到最大進(jìn)化代數(shù)時(shí)停止，最大進(jìn)化代數(shù)一般可設(shè)置為100~1000，根據(jù)具體問(wèn)題可對(duì)該建議值作相應(yīng)的修改。也可以通過(guò)考察找到的當(dāng)前最優(yōu)解是否達(dá)到誤差要求來(lái)控制算法的停止。或者是算法在持續(xù)很長(zhǎng)的一段進(jìn)化時(shí)間內(nèi)所找到的最優(yōu)解沒(méi)有得到改善時(shí)，算法可以停止。適應(yīng)值評(píng)價(jià)影響算法對(duì)種群的選擇，恰當(dāng)?shù)脑u(píng)估函數(shù)應(yīng)該能夠?qū)θ旧w的優(yōu)劣做出合適的區(qū)分，保證選擇機(jī)制的有效性，從而提高群體的進(jìn)化能力。評(píng)估函數(shù)的設(shè)置同優(yōu)化問(wèn)題的求解目標(biāo)有關(guān)。評(píng)估函數(shù)應(yīng)滿(mǎn)足較優(yōu)染色體的適應(yīng)值較大的規(guī)定。為了更好地提高選擇的效能，可以對(duì)評(píng)估函數(shù)做出一定的修正。目前主要的評(píng)估函數(shù)修正方法有：線(xiàn)性變換；乘冪變換；指數(shù)變換等。4.3.2參數(shù)設(shè)置4.3.3混合遺傳算法爬山法模擬退火算法最速下降法其它……局部搜索算法遺傳算法4.3.3混合遺傳算法并行組合模擬退火算法并行模擬退火遺傳算法貪婪遺傳算法遺傳比率切割算法遺傳爬山法引入局部改善操作的混合遺傳算法免疫遺傳算法并行計(jì)算單指令流多數(shù)據(jù)流計(jì)算機(jī)多指令流多數(shù)據(jù)流計(jì)算機(jī)并行計(jì)算網(wǎng)絡(luò)串行計(jì)算單