現如今智能啟發式算法很普遍,用處也很多,遺傳算法、模拟退火、蟻群算法、粒子群算法等都是常用的幾個智能算法,借用之前做的數模題目的例子,大緻記錄一下遺傳算法的Matlab實作。
題目具體分析就不闡述了,核心要求是給出由理想起始點倒車入庫的泊車政策,包括車速、前輪轉角、後輪行駛距離。
假設我現在已經得到了一個比較好的倒車起始點,且在最終到達車庫門前的過程中方向盤不動。遺傳算法求解過程:
由于該模型方程較複雜且限制條件為非線性的,直接用求解面臨這許多困難,故考慮用啟發式算法中常用的遺傳算法求解。遺傳算法不需要給出優化變量的初始值,隻需要給出優化變量的範圍就可以進行高效并行的全局搜尋。并且遺傳算法不需要目标函數的導數梯度等資訊,按照适應度的值就可以進行搜尋最優值。本文研究的泊車問題無法給出的優化參數的初始值,僅能給出優化變量的範圍,并且無法提供目标函數的梯度資訊,是以采用遺傳算法進行參數優化。
垂直泊車的遺傳算法優化過程如下:
第一步:确定轉彎半徑範圍
當停車點确定後,由于前輪轉向角不同使得開出的路徑不一樣,但由于角度不直覺且不友善運算,根據阿克曼模型,使用對應的轉彎半徑 作為決策變量。對于小型車,其最大轉向角一般為33.5-39.6°之間,取轉向角為36°,進而确定了轉彎半徑要大于3785mm。
第二步:産生初始種群并編碼
決策變量 為一定區間内的浮點數,不宜采用二進制編碼,由于 為一定範圍内的浮點數,是以采用實數編碼效果更好。具體做法是在 的取值範圍内,随機選擇 個染色體,作為初始種群。
第三步:等效距離的選擇與計算[
為了求解最優的路徑,我們把從理想倒車點到停車位置處所經過的距離的計算式作為适應度函數,算出的适應度稱為等效距離。在産生種群的過程中,難免會得出一些不滿足限制條件的解。工程中常用懲罰政策來解決遺傳算法中具有非線性限制的問題,懲罰政策的本質是通過懲罰不可行解,将有限制的問題轉化為無限制的問題,即通過增加懲罰項來改變适應度。帶有懲罰項的适應度函數有兩種。
在加法形式下的适應度函數中,本文将懲罰項定義為一很大的常數 ,以此排除不滿足限制條件的值,則适應度函數為:
第四步:對個體進行選擇
采用轉盤算法對染色體進行選擇,按如下公式計算出種群中每個染色體被選中的機率:
輪盤每轉動一次選中一個個體,若個體的等效距離越小,則被選中的機率越大,由此選中那些路徑較小的個體,使得種群的平均路徑長度不斷減小。
第五步:交叉操作
首先選取對應的交叉機率 。選取交叉機率為0.7, 的值太大,群體更新的速度太快,高适應度的個體很快被破壞。而 的值太小則可能導緻搜尋阻滞。随機選取兩個個體 和 ,交叉公式為:
第六步:變異操作
變異的基因多少是按照變異率 決定的,變異率 很低難以增加種群的多樣性, 太高GA 的搜尋就變成了随機搜尋,是以,一般取 =0.001~0.1。本文取 =0.01。
第七步:進化終止
進化的終止條件是進化代數到達最大值,進化代數的選擇視具體情況而定,一般取T=100-500,經過重複多次試驗,本文取100。
結果的分析
輸入坐标對模型進行測試,一般的,倒車方式為直接倒行時,輸入變量為理想起始點的坐标。當倒車方式為兩段式垂直泊車時,需要再添加一個車身與水準線夾角的變量 。
a.直接倒行 b.兩段式
運作程式,開始時輸入倒車起始點,但基于理想起始點的限制,不是任意的點都可以得出解的,比如某些死角點不可能直接倒進車庫中,或者不同的理想點對應不同的倒車方式,是以在分析大量實驗資料後,我們大緻給出了輸入坐标的範圍。
給出程式運作過程中,各代的平均值和最佳值曲線。由曲線可以看出,遺傳算法收斂程度高,每一代種群平均等效距離的下降速度快,且得出最優路徑時間快,完全保持在100代以内達到最優結果。
a.直接倒行 b.兩段式
程式運作完畢後,給出最優的路徑,并在指令視窗顯示出題目需要的幾個參數的具體值,并畫出最優路徑[9]。
a.直接倒行 b.兩段式
圖13 最優路徑顯示
論文下載下傳,想要了解的朋友可以看看,水準有限,請勿噴=。=