遺傳算法及其在路徑規(guī)劃中的應(yīng)用(已改無錯(cuò)字)
2022-09-13 00:26:17 本頁面
【正文】 算適應(yīng)度，它不需要其它的推導(dǎo)運(yùn)算和附加信息，因而對(duì)問題的依賴性??； ④ 遺傳算法使用概率的操作規(guī)則，而不是確定性的規(guī)則； ⑤ 遺傳算法在解空間中采用啟發(fā)式搜索，而不是盲目的枚舉或完全隨機(jī)的搜索，因而搜索的效率高； ⑥ 遺傳算法對(duì)于待尋優(yōu)的問題基本沒有限制，既可以是數(shù)學(xué)解析式所表示的顯函數(shù)，也可以是映射矩陣或神經(jīng)網(wǎng)絡(luò)表示的隱函數(shù)，同時(shí)也不要求待優(yōu)化函數(shù)連續(xù)、可微； 2022年 8月 29日 12時(shí) 13分 北京科技大學(xué)自動(dòng)化學(xué)院控制科學(xué)與工程系 26 ⑦ 遺傳算法所具有的隱含并行性的特點(diǎn)，使其可以通過大規(guī)模并行搜索來提高計(jì)算速度； ⑧ 遺傳算法適合復(fù)雜的、高度非線性問題的優(yōu)化。 遺傳算法的研究熱點(diǎn) （ 1）編碼方式的確定； （ 2）專用遺傳算子的設(shè)計(jì)； （ 3）控制參數(shù)的選擇； ① 種群規(guī)模： N = 20~100； ② 交叉概率： pc = ~； ③ 變異概率： pm = ~。 李擎 、張偉、尹怡欣、王志良．一種新的調(diào)節(jié)交叉和變異概率的自適應(yīng)算法． 控制與決策， 2022年 1月第 23卷第 1期： 79～ 83 2022年 8月 29日 12時(shí) 13分 北京科技大學(xué)自動(dòng)化學(xué)院控制科學(xué)與工程系 27 2 遺傳算法的應(yīng)用實(shí)例 —— 車載導(dǎo)航系統(tǒng)路徑規(guī)劃算法的設(shè)計(jì) 問題簡(jiǎn)介 所謂車載導(dǎo)航系統(tǒng)路徑規(guī)劃，就是在電子地圖中找到一條從起點(diǎn)到終點(diǎn)在距離（或時(shí)間）上最短的路徑。 下圖為一個(gè)路徑規(guī)劃用仿真地圖，其上共有 15個(gè)節(jié)點(diǎn)， 24條弧。弧下的數(shù)據(jù)表示路徑的長(zhǎng)度（單位：公里），弧上的數(shù)據(jù)則表示該路段車輛行駛的速度（單位：米 /秒）。 在實(shí)際電子地圖中，節(jié)點(diǎn)相當(dāng)于道路的交叉點(diǎn)，弧相當(dāng)于實(shí)際道路。 2022年 8月 29日 12時(shí) 13分 北京科技大學(xué)自動(dòng)化學(xué)院控制科學(xué)與工程系 28 Y X D P N L O M F C B G K H I J A E 圖 6 路徑規(guī)劃用仿真地圖 2022年 8月 29日 12時(shí) 13分 北京科技大學(xué)自動(dòng)化學(xué)院控制科學(xué)與工程系 29 遺傳算法的具體應(yīng)用 （ 1）路徑的表示方法 這里采用 符號(hào)編碼方式 表示實(shí)際路網(wǎng)中的路徑。 對(duì)于圖 6中一條從 A點(diǎn)到 P點(diǎn)的路徑，采用符號(hào)編碼方式得到的個(gè)體為 A、 B、 E、 H、 L、 O、 P。 圖 7 仿真地圖中的一條路徑 A B E H L O P 2022年 8月 29日 12時(shí) 13分 北京科技大學(xué)自動(dòng)化學(xué)院控制科學(xué)與工程系 30 （ 2）初始路徑的產(chǎn)生 ① 傳統(tǒng)遺傳算法 隨機(jī)生成初始路徑，會(huì)產(chǎn)生斷路或環(huán)路。 ② 改進(jìn)遺傳算法 （ a）克服斷路的思路 從起始點(diǎn)出發(fā)，隨機(jī)選取與起始點(diǎn)直接相連的一個(gè)點(diǎn)作為下一個(gè)節(jié)點(diǎn)，如此反復(fù)直到找到終點(diǎn)為止。 在路徑的產(chǎn)生過程中為了避免出現(xiàn)環(huán)路，規(guī)定在一條路徑中當(dāng)一個(gè)路徑節(jié)點(diǎn)被選中以后，則給該節(jié)點(diǎn)一個(gè)標(biāo)記，只有沒有標(biāo)記的節(jié)點(diǎn)才能被選作新的路徑節(jié)點(diǎn)，每條初始路徑選擇完畢后標(biāo)記全部刷新。 （ b）克服環(huán)路的思路 2022年 8月 29日 12時(shí) 13分 北京科技大學(xué)自動(dòng)化學(xué)院控制科學(xué)與工程系 31 （ 3）適應(yīng)度函數(shù)的確定 ① 距離最短優(yōu)化原則下的適應(yīng)度函數(shù) ② 時(shí)間最優(yōu)優(yōu)化原則下的適應(yīng)度函數(shù) 1()iijFx x? ?1()iijijFxxv??ix其中， 為第 i個(gè)染色體（路徑）； 為第 i條路徑第 j段的路徑長(zhǎng)度。 ijxijv其中， 仍為第 i條路徑第 j段的路徑長(zhǎng)度； 為第 i條路徑第 j段的行駛速度。 ijx2022年 8月 29日 12時(shí) 13分 北京科技大學(xué)自動(dòng)化學(xué)院控制科學(xué)與工程系 32 不能象傳統(tǒng)遺傳算法那樣隨機(jī)進(jìn)行一點(diǎn)、兩點(diǎn)或多點(diǎn)交叉操作，因?yàn)檫@樣很容易產(chǎn)生斷路或環(huán)路。 這里只允許使用在重復(fù)節(jié)點(diǎn)位置交叉且只進(jìn)行一點(diǎn)交叉的操作方式，具體實(shí)現(xiàn)步驟如下： （ 5）交叉操作 （ 4）復(fù)制（選擇）操作 采用賭輪法進(jìn)行復(fù)制操作。 ① 隨機(jī)選取兩個(gè)個(gè)體作為待交叉?zhèn)€體； ② 找出兩個(gè)待交叉?zhèn)€體的共同節(jié)點(diǎn)（起點(diǎn)和終點(diǎn)除外）的集合； ③ 從共同節(jié)點(diǎn)的集合中隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為交叉節(jié)點(diǎn)； ④ 檢查兩個(gè)待交叉?zhèn)€體在交叉節(jié)點(diǎn)之前或之后的內(nèi)容是否相同。如相同，則取消本次交叉操作；否則，兩者交換交叉點(diǎn)之前（或之后）的內(nèi)容形成兩個(gè)新個(gè)體。 2022年 8月 29日 12時(shí) 13分 北京科技大學(xué)自動(dòng)化學(xué)院控制科學(xué)與工程系 33 下面將結(jié)合仿真地圖舉例說明交叉操作是如何實(shí)現(xiàn)的。 ① 設(shè)選取的兩個(gè)待交叉樣本為 A、 B、 E、 I、 L、 O、 P和 A、C、 E、 H、 L、 N、 P； ② 兩者重復(fù)節(jié)點(diǎn)的集合為 {E、 L}； ③ 隨機(jī)選擇 E作為交叉節(jié)點(diǎn)； ④ 檢查發(fā)現(xiàn)兩者待交叉樣本在 E點(diǎn)之前和之后的內(nèi)容均不相同，因此可以進(jìn)行此次交叉操作，交叉后的新個(gè)體為： A、 B、 E、 H、 L、 N、 P A、 C、 E、 I、 L、 O、 P 和 2022年 8月 29日 12時(shí) 13分 北京科技大學(xué)自動(dòng)化學(xué)院控制科學(xué)與工程系 34 圖 8 交叉操作示意圖 P L O C B H I A E N 2022年 8月 29日 12時(shí) 13分 北京科技大學(xué)自動(dòng)化學(xué)院控制科學(xué)與工程系 35 （ 6）變異操作 不能采用傳統(tǒng)遺傳算法中隨機(jī)選擇變異點(diǎn)的做法，因?yàn)檫@樣同樣容易產(chǎn)生斷路或環(huán)路。 這里采用的變異操作，其基本步驟如下： ① 隨機(jī)選取一個(gè)個(gè)體作為待變異個(gè)體； ② 在待變異個(gè)體中隨機(jī)選擇一個(gè)節(jié)點(diǎn)（起點(diǎn)和終點(diǎn)除外）作為待變異節(jié)點(diǎn)； ③ 找到和該待變異節(jié)點(diǎn)直接相連的節(jié)點(diǎn)集合（該集
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1