遺傳算法及其在路徑規(guī)劃中的應(yīng)用(編輯修改稿)
2024-09-12 00:26 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 l 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è)體。 假設(shè)在兩個(gè)父代個(gè)體 ， 之間進(jìn)行算數(shù)交叉，則交叉運(yùn)算后所產(chǎn)生出的兩個(gè)新個(gè)體是 tAX tBX11( 1 )( 1 )t t tA A Bt t tB B AX X XX X X????? ? ? ???? ? ???式中 為一參數(shù)，它若是一個(gè)常數(shù)，此時(shí)所進(jìn)行的交叉運(yùn)算稱為 均勻算數(shù)交叉 ；它也可以是一個(gè)由進(jìn)化代數(shù)所決定的變量，此時(shí)所進(jìn)行的交叉運(yùn)算稱為 非均勻算數(shù)交叉 。 ?交叉前 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)行取反操作。如同自然界很少發(fā)生基因突變一樣，變異概率 pm一般都取得比較小。變異的目的是為了增加種群個(gè)體的多樣性，防止丟失一些有用的遺傳模式。 在簡(jiǎn)單遺傳算法中，變異就是將某個(gè)體中某一位的值作取反運(yùn)算。 變異前 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ā)式的。由于遺傳算法沒有利用梯度信息，因此要從數(shù)學(xué)上構(gòu)造比較嚴(yán)格的收斂判據(jù)相當(dāng)困難。常用的收斂判據(jù)有： ① 根據(jù)計(jì)算時(shí)間和所采用計(jì)算機(jī)的性能確定收斂判據(jù)：一般采用指定最大迭代次數(shù)的方法； ② 從解的質(zhì)量方面確定判據(jù)：如果連續(xù)幾代（或幾十代）種群中的最優(yōu)解沒有變化，則認(rèn)為算法收斂；或種群中最優(yōu)個(gè)體的適應(yīng)度與平均適應(yīng)度之差和平均適應(yīng)度的比值小于某一給定值時(shí)，也可以認(rèn)為算法已經(jīng)收斂。 2022年 8月 29日 12時(shí) 13分 北京科技大學(xué)自動(dòng)化學(xué)院控制科學(xué)與工程系 21 （ 8）約束條件的處理 遺傳算法在求解有約束的優(yōu)化問(wèn)題時(shí)，需對(duì)約束條件進(jìn)行必要的處理。處理方式有： ① 直接體現(xiàn)在字符串的編碼中 對(duì)于優(yōu)化問(wèn)題中變量的上、下限約束，可以讓字符串表示的最大值和最小值分別對(duì)應(yīng)于實(shí)際約束變量的上、下限值。設(shè)待優(yōu)化變量 x的變化范圍為 [xmin, xmax]，如用 l 位的二進(jìn)制字符串 y來(lái)表示，則 x、 y之間有如下關(guān)系： )(12 m i nm a xm i n xxyxx l ?????② 判斷舍棄法 在遺傳算法的運(yùn)算過(guò)程中，檢查得到字符串所對(duì)應(yīng)的解是否為可行解。若是，則加入到下一代種群中；否則將其舍棄。 ③ 懲罰函數(shù)法 如果一個(gè)解違反了某個(gè)約束，則視其違反程度給予一定的懲罰，使其具有較小的適應(yīng)度。越限越嚴(yán)重，適應(yīng)度就越小。 2022年 8月 29日 12時(shí) 13分 北京科技大學(xué)自動(dòng)化學(xué)院控制科學(xué)與工程系 22 遺傳算法的特點(diǎn) 目前常規(guī)的優(yōu)化方法主要有 3種類型：解析法、枚舉法和隨機(jī)法。 解析法是優(yōu)化方法中研究最多的一種，它又分為直接法和間接法。 直接法 是一種通過(guò)沿著梯度信息最陡的方向逐漸運(yùn)動(dòng)來(lái)尋找局部極值的方法； 間接法 則是一種通過(guò)使目標(biāo)函數(shù)梯度為零，進(jìn)而通過(guò)求解一組非線性方程來(lái)尋找局部極值的方法。 （ 1）解析法 解析法的主要問(wèn)題在于： （ 1）要求目標(biāo)函數(shù)連續(xù)光滑且可微； （ 2）一般只能找到局部極值而非全局極值，故對(duì)于存在多峰極值的優(yōu)化問(wèn)題有時(shí)顯得無(wú)能為力。 2022年 8月 29日 12時(shí) 13分 北京科技大學(xué)自動(dòng)化學(xué)院控制科學(xué)與工程系 23 隨機(jī)法能夠克服上述兩種方法的缺陷，它在搜索空間中隨機(jī)地漫游并記錄下所找到的最優(yōu)結(jié)果，當(dāng)搜索到一定程度后便終止。當(dāng)然，它所找到的結(jié)果往往也不是最優(yōu)解。實(shí)際上，隨機(jī)法也是枚舉法中的一種。 （ 2）枚舉法 枚舉法能夠克服解析法的兩點(diǎn)不足，它可以找到全局極值且不要求目標(biāo)函數(shù)連續(xù)光滑。但其致命缺點(diǎn)是計(jì)算效率太低，對(duì)于許多實(shí)際問(wèn)題往往會(huì)因?yàn)樗阉骺臻g太大而不可能將所有的情況一一搜索到。 （ 3）隨機(jī)法 2022年 8月 29日 12時(shí) 13分 北京科技大學(xué)自動(dòng)化學(xué)院控制科學(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è)體。如此周而復(fù)始，種群中各個(gè)體的適應(yīng)度不斷提高，直至滿足一定的收斂條件。最后，以種群中適應(yīng)度值最高的個(gè)體作為待優(yōu)化參數(shù)的最優(yōu)解。 （ 4）遺傳算法 遺傳算法也用到了隨機(jī)搜索技術(shù)，但它通過(guò)對(duì)參數(shù)空間的隨機(jī)編碼并用適應(yīng)度函數(shù)作為工具來(lái)引導(dǎo)搜索過(guò)程向著更有效的方向發(fā)展，因而它不同于常規(guī)的隨機(jī)法。 2022年 8月 29日 12時(shí) 13分 北京科技大學(xué)自動(dòng)化學(xué)院控制科學(xué)與工程系 25 與常規(guī)優(yōu)化方法相比，遺傳算法的魯棒性較好，其主要特點(diǎn)在于： ① 遺傳算法對(duì)參數(shù)的編碼進(jìn)行操作，而不是對(duì)參數(shù)本身； ② 遺傳算法從多個(gè)初始點(diǎn)開始操作，而不是從某一個(gè)點(diǎn)開始，這在很大程度上避免了搜索過(guò)程過(guò)早地收斂于局部極值，因此更有可能求得全局極值； ③ 遺傳算法通過(guò)目標(biāo)函數(shù)計(jì)
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1