遺傳算法及其在路徑規(guī)劃中的應(yīng)用-文庫(kù)吧資料
2024-08-29 00:26本頁(yè)面
【正文】 院控制科學(xué)與工程系 24 遺傳算法是基于自然選擇和基因遺傳學(xué)原理的搜索方法，它將 “ 優(yōu)勝劣汰、適者生存 ” 的生物進(jìn)化原理引入到由待優(yōu)化參數(shù)形成的編碼串種群中，按照一定的適應(yīng)度函數(shù)及一系列遺傳操作對(duì)各個(gè)個(gè)體進(jìn)行篩選，使適應(yīng)度值較高的個(gè)體被保留下來(lái)，從而組成新的種群，新種群中包含了上一代的大量信息，并且引入了新的優(yōu)于上一代的個(gè)體。 （ 2）枚舉法 枚舉法能夠克服解析法的兩點(diǎn)不足，它可以找到全局極值且不要求目標(biāo)函數(shù)連續(xù)光滑。當(dāng)然，它所找到的結(jié)果往往也不是最優(yōu)解。 （ 1）解析法 解析法的主要問(wèn)題在于： （ 1）要求目標(biāo)函數(shù)連續(xù)光滑且可微； （ 2）一般只能找到局部極值而非全局極值，故對(duì)于存在多峰極值的優(yōu)化問(wèn)題有時(shí)顯得無(wú)能為力。 解析法是優(yōu)化方法中研究最多的一種，它又分為直接法和間接法。越限越嚴(yán)重，適應(yīng)度就越小。若是，則加入到下一代種群中；否則將其舍棄。處理方式有： ① 直接體現(xiàn)在字符串的編碼中 對(duì)于優(yōu)化問(wèn)題中變量的上、下限約束，可以讓字符串表示的最大值和最小值分別對(duì)應(yīng)于實(shí)際約束變量的上、下限值。常用的收斂判據(jù)有： ① 根據(jù)計(jì)算時(shí)間和所采用計(jì)算機(jī)的性能確定收斂判據(jù)：一般采用指定最大迭代次數(shù)的方法； ② 從解的質(zhì)量方面確定判據(jù)：如果連續(xù)幾代（或幾十代）種群中的最優(yōu)解沒(méi)有變化，則認(rèn)為算法收斂；或種群中最優(yōu)個(gè)體的適應(yīng)度與平均適應(yīng)度之差和平均適應(yīng)度的比值小于某一給定值時(shí)，也可以認(rèn)為算法已經(jīng)收斂。 變異前 1100110111 圖 5 變異操作示意圖 變異后 1100010111 2022年 8月 29日 12時(shí) 13分 北京科技大學(xué)自動(dòng)化學(xué)院控制科學(xué)與工程系 20 （ 7）收斂判據(jù) 常規(guī)的優(yōu)化方法有數(shù)學(xué)上比較嚴(yán)格的收斂判據(jù)，而遺傳算法的收斂判據(jù)通常是啟發(fā)式的。變異的目的是為了增加種群個(gè)體的多樣性，防止丟失一些有用的遺傳模式。 ?交叉前 individual 1 0101100110 template 1001010101 圖 4 均勻交叉 individual 2 0110010001 交叉后 0100110011 0111000100 2022年 8月 29日 12時(shí) 13分 北京科技大學(xué)自動(dòng)化學(xué)院控制科學(xué)與工程系 19 （ 6）變異（ Mutation） 一般的變異操作只作用于采用二進(jìn)制編碼的某單個(gè)個(gè)體，它以一定的變異概率 pm對(duì)個(gè)體的某些位進(jìn)行取反操作。 交叉前 individual 1 11 01011 000 individual 2 10 10110 101 圖 3 兩點(diǎn)交叉 交叉后 11 10110 000 10 01011 101 2022年 8月 29日 12時(shí) 13分 北京科技大學(xué)自動(dòng)化學(xué)院控制科學(xué)與工程系 18 ④ 算數(shù)交叉（ Arithmetic Crossover） 算數(shù)交叉的操作對(duì)象一般是由 浮點(diǎn)數(shù)編碼 所表示的個(gè)體，它通過(guò)兩個(gè)父代個(gè)體的線性組合而產(chǎn)生出兩個(gè)新的個(gè)體。 ③ 均勻交叉（ Uniform Crossover） 其操作過(guò)程是：先選出兩個(gè)父代個(gè)體，之后依據(jù)交叉概率 pc 產(chǎn)生一個(gè)與父代個(gè)體同樣長(zhǎng)度的二進(jìn)制串，這里稱其為 模板（ template）。 ① 單點(diǎn)交叉（ OnePoint Crossover） 對(duì)每一對(duì)相互配對(duì)的個(gè)體，依設(shè)定的交叉概率 pc在其交叉點(diǎn)處相互交換兩個(gè)父代個(gè)體的部分染色體，從而產(chǎn)生出兩個(gè)新的個(gè)體，如下圖所示。一般分兩步實(shí)現(xiàn)：第一步是將新復(fù)制產(chǎn)生的匹配池中的個(gè)體隨機(jī)兩兩配對(duì)；第二步是進(jìn)行交叉繁殖，產(chǎn)生一對(duì)新的個(gè)體。適應(yīng)度可以按序號(hào)線性變化，也可以按某種非線性關(guān)系變化。常用的復(fù)制方法有： ① 賭輪法 ② 兩 兩競(jìng)爭(zhēng)法 從種群中隨機(jī)地選擇兩個(gè)個(gè)體，將其中適應(yīng)度較大的個(gè)體作為被復(fù)制的個(gè)體；若兩個(gè)體適應(yīng)度相同，則任意選擇一個(gè)。適應(yīng)度值高于種群平均適應(yīng)度的個(gè)體在下一代中將有更多的機(jī)會(huì)繁殖一個(gè)或多個(gè)后代，而低于平均適應(yīng)度的個(gè)體則有可能被淘汰掉。這樣，既保證了適應(yīng)度值非負(fù)，又使適應(yīng)度值增大方向和目標(biāo)函數(shù)優(yōu)化方向一致。 m a x m a x( ) ( )()0c J x J x cfx ???? ??當(dāng) 其它 2022年 8月 29日 12時(shí) 13分 北京科技大學(xué)自動(dòng)化學(xué)院控制科學(xué)與工程系 14 ③ 對(duì)于最大化問(wèn)題（如需要），一般采用如下轉(zhuǎn)換形式： 其中， cmin既可以是當(dāng)前代中目標(biāo)函數(shù) J(x) 的最小值，也可以根據(jù)經(jīng)驗(yàn)人為設(shè)定。設(shè)實(shí)際優(yōu)化問(wèn)題的目標(biāo)函數(shù)為 J(x)，遺傳算法的適應(yīng)度函數(shù)為 f(x)，則有： ① 可以將適應(yīng)度函數(shù)表示為實(shí)際優(yōu)化問(wèn)題目標(biāo)函數(shù)的線性形式，即有 bxJaxf ??? )()(其中， a， b是系數(shù)，可根據(jù)具體問(wèn)題的特征及所期望適應(yīng)度的分散程度來(lái)確定。這個(gè)過(guò)程稱為適應(yīng)度轉(zhuǎn)換。在遺傳算法中 要求適應(yīng)度函數(shù)值是非負(fù)的，且任何情況下都希望其值越大越好 ；而實(shí)際優(yōu)化問(wèn)題的目標(biāo)函數(shù)并不一定滿足這個(gè)條件，有的是正的，有的可能為負(fù)，甚至可能是復(fù)數(shù)值。 另外，如果對(duì)于尋優(yōu)問(wèn)題有某些先驗(yàn)知識(shí)，則可先將這些先驗(yàn)知識(shí)轉(zhuǎn)變?yōu)楸仨殱M足的一組約束，然后再在滿足這些約束的解中隨機(jī)地選取個(gè)體以組成初始種群。 （ 3）符號(hào)編碼方式通常在一些專門的應(yīng)用場(chǎng)合使用。 （ 1）采用二進(jìn)制形式編碼，個(gè)體的位數(shù)多，描述得比較細(xì)致，從而加大了搜索范圍；但交叉運(yùn)算的計(jì)算量較大，并且由于大量的具體問(wèn)題本身都是十進(jìn)制的，所以還需對(duì)實(shí)際參數(shù)進(jìn)行編碼和譯碼，從而增加了額外的計(jì)算時(shí)間。因此，如何用適當(dāng)?shù)淖址幋a來(lái)表示問(wèn)題的解成為了遺傳算法應(yīng)用過(guò)程中的首要問(wèn)題。 表 4 交叉操作過(guò)程 標(biāo)號(hào) 復(fù)制后匹配池中的個(gè)體 1 01101 3 2 11000 4 3 11000 1 4 10011 2 總 計(jì) 平均值 最大值 新種群 01000 11001 11101 10010 f (x)=x2 3 5 3 5 8 25 29 18 64 625 841 324 1854 841 配對(duì)對(duì)象 （隨機(jī)選取） 交叉點(diǎn) （隨機(jī)選?。? x值
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1