遺傳算法及其在路徑規(guī)劃中的應(yīng)用(參考版)
2024-08-27 00:26本頁面
【正文】 實際規(guī)劃問題經(jīng)常是動、靜態(tài)障礙物并存。 根據(jù)規(guī)劃空間中的障礙物信息是否全部已知，移動機(jī)器人路徑規(guī)劃可以分為 全局（離線）規(guī)劃 和 局部（在線）規(guī)劃 兩種情況；按照規(guī)劃空間中障礙物的運(yùn)動形式不同，移動機(jī)器人路徑規(guī)劃又可以分為 靜態(tài)規(guī)劃 和 動態(tài)規(guī)劃 兩種情形。 下面也結(jié)合仿真地圖舉例說明刪除操作的具體實現(xiàn)方法。 ① 選擇待變異個體為 A、 C、 E、 I、 L、 O、 P； ⑤ 經(jīng)過檢查發(fā)現(xiàn) C和 B不直接相連，所以取消此次變異操作；接著選取 F作為變異后節(jié)點，檢查發(fā)現(xiàn) C和 F、 F和 I直接相連，故可進(jìn)行此次變異操作，變異后的新個體為 ② 隨機(jī)選取 E作為待變異節(jié)點； ③ 與 E直接相連的節(jié)點集合為 {B、 F、 H}； ④ 隨機(jī)選取 B作為變異后節(jié)點； A、 C、 F、 I、 L、 O、 P 2022年 8月 29日 12時 13分 北京科技大學(xué)自動化學(xué)院控制科學(xué)與工程系 37 P L O F C B H I A E 圖 9 變異操作示意圖 2022年 8月 29日 12時 13分 北京科技大學(xué)自動化學(xué)院控制科學(xué)與工程系 38 （ 7）刪除操作 刪除操作的具體步驟如下： ① 隨機(jī)選擇一個個體； ② 檢查該個體中任意兩個不相鄰節(jié)點（包括起點和終點）之間是否直接相連。若直接相連，則用變異后節(jié)點替代待變異節(jié)點完成變異過程；否則，放棄此次操作，回到第④步，直至將節(jié)點集合中的所有節(jié)點全部選遍。 ① 設(shè)選取的兩個待交叉樣本為 A、 B、 E、 I、 L、 O、 P和 A、C、 E、 H、 L、 N、 P； ② 兩者重復(fù)節(jié)點的集合為 {E、 L}； ③ 隨機(jī)選擇 E作為交叉節(jié)點； ④ 檢查發(fā)現(xiàn)兩者待交叉樣本在 E點之前和之后的內(nèi)容均不相同，因此可以進(jìn)行此次交叉操作，交叉后的新個體為： A、 B、 E、 H、 L、 N、 P A、 C、 E、 I、 L、 O、 P 和 2022年 8月 29日 12時 13分 北京科技大學(xué)自動化學(xué)院控制科學(xué)與工程系 34 圖 8 交叉操作示意圖 P L O C B H I A E N 2022年 8月 29日 12時 13分 北京科技大學(xué)自動化學(xué)院控制科學(xué)與工程系 35 （ 6）變異操作 不能采用傳統(tǒng)遺傳算法中隨機(jī)選擇變異點的做法，因為這樣同樣容易產(chǎn)生斷路或環(huán)路。如相同，則取消本次交叉操作；否則，兩者交換交叉點之前（或之后）的內(nèi)容形成兩個新個體。 這里只允許使用在重復(fù)節(jié)點位置交叉且只進(jìn)行一點交叉的操作方式，具體實現(xiàn)步驟如下： （ 5）交叉操作 （ 4）復(fù)制（選擇）操作 采用賭輪法進(jìn)行復(fù)制操作。 ijxijv其中， 仍為第 i條路徑第 j段的路徑長度； 為第 i條路徑第 j段的行駛速度。 在路徑的產(chǎn)生過程中為了避免出現(xiàn)環(huán)路，規(guī)定在一條路徑中當(dāng)一個路徑節(jié)點被選中以后，則給該節(jié)點一個標(biāo)記，只有沒有標(biāo)記的節(jié)點才能被選作新的路徑節(jié)點，每條初始路徑選擇完畢后標(biāo)記全部刷新。 圖 7 仿真地圖中的一條路徑 A B E H L O P 2022年 8月 29日 12時 13分 北京科技大學(xué)自動化學(xué)院控制科學(xué)與工程系 30 （ 2）初始路徑的產(chǎn)生 ① 傳統(tǒng)遺傳算法 隨機(jī)生成初始路徑，會產(chǎn)生斷路或環(huán)路。 2022年 8月 29日 12時 13分 北京科技大學(xué)自動化學(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時 13分 北京科技大學(xué)自動化學(xué)院控制科學(xué)與工程系 29 遺傳算法的具體應(yīng)用 （ 1）路徑的表示方法 這里采用 符號編碼方式 表示實際路網(wǎng)中的路徑?；∠碌臄?shù)據(jù)表示路徑的長度（單位：公里），弧上的數(shù)據(jù)則表示該路段車輛行駛的速度（單位：米 /秒）。 李擎 、張偉、尹怡欣、王志良．一種新的調(diào)節(jié)交叉和變異概率的自適應(yīng)算法． 控制與決策， 2022年 1月第 23卷第 1期： 79～ 83 2022年 8月 29日 12時 13分 北京科技大學(xué)自動化學(xué)院控制科學(xué)與工程系 27 2 遺傳算法的應(yīng)用實例 —— 車載導(dǎo)航系統(tǒng)路徑規(guī)劃算法的設(shè)計 問題簡介 所謂車載導(dǎo)航系統(tǒng)路徑規(guī)劃，就是在電子地圖中找到一條從起點到終點在距離（或時間）上最短的路徑。 2022年 8月 29日 12時 13分 北京科技大學(xué)自動化學(xué)院控制科學(xué)與工程系 25 與常規(guī)優(yōu)化方法相比，遺傳算法的魯棒性較好，其主要特點在于： ① 遺傳算法對參數(shù)的編碼進(jìn)行操作，而不是對參數(shù)本身； ② 遺傳算法從多個初始點開始操作，而不是從某一個點開始，這在很大程度上避免了搜索過程過早地收斂于局部極值，因此更有可能求得全局極值； ③ 遺傳算法通過目標(biāo)函數(shù)計算適應(yīng)度，它不需要其它的推導(dǎo)運(yùn)算和附加信息，因而對問題的依賴性?。? ④ 遺傳算法使用概率的操作規(guī)則，而不是確定性的規(guī)則； ⑤ 遺傳算法在解空間中采用啟發(fā)式搜索，而不是盲目的枚舉或完全隨機(jī)的搜索，因而搜索的效率高； ⑥ 遺傳算法對于待尋優(yōu)的問題基本沒有限制，既可以是數(shù)學(xué)解析式所表示的顯函數(shù)，也可以是映射矩陣或神經(jīng)網(wǎng)絡(luò)表示的隱函數(shù)，同時也不要求待優(yōu)化函數(shù)連續(xù)、可微； 2022年 8月 29日 12時 13分 北京科技大學(xué)自動化學(xué)院控制科學(xué)與工程系 26 ⑦ 遺傳算法所具有的隱含并行性的特點，使其可以通過大規(guī)模并行搜索來提高計算速度； ⑧ 遺傳算法適合復(fù)雜的、高度非線性問題的優(yōu)化。最后，以種群中適應(yīng)度值最高的個體作為待優(yōu)化參數(shù)的最優(yōu)解。 （ 3）隨機(jī)法 2022年 8月 29日 12時 13分 北京科技大學(xué)自動化學(xué)
試題試卷相關(guān)推薦
鄂ICP備17016276號-1