遺傳算法的電子地圖研究范文

本站小編為你精心準備了遺傳算法的電子地圖研究參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

1遺傳算法原理及基本特點

1.1算法原理

遺傳算法最早是由美國Michigan大學的Holland教授于1969年提出的，它主要是通過模擬大自然的淘汰生產法則和生物的進化過程形成的計算模型，在后期經過Dejong、Gol-dberg等學科專家歸納總結，形成一種全新的全局的優化搜索算法。在使用遺傳算法的過程中，問題的每個可能的解都會被編碼成一個“染色體”，稱為染色體或者個體，若干個個體構成了種群。在初始種群產生后，通過適度函數給每個個體一個數值評價，按照適者生存和優勝劣汰的原理，淘汰適應度低的個體，并選擇適應度較高的個體參加遺傳操作。在遺傳操作中，部分個體經過交叉和變異進行再組合生成新一代的種群。這個種群就像自然界進化一樣，越往后的子代相對于初始種群能夠更加適應新的環境，這樣朝著最優解的方向不斷進化最終得到更優解。

1.2遺傳算法的優點

遺傳算法充分運用大自然的遺傳和進化的思想，完全不同于其他搜索方式，其明顯的優點如下：

（1）快速隨機的搜索能力。遺傳算法本身具有很強的自適應和智能性。在搜索過程中，消除了基本的障礙，即需要能夠先對問題的全部特點進行描述。搜索使用概率機制進行迭代，具有很高的隨機性。同時，它不受優化函數的約束，也沒有對優化函數的依賴性。

（2）搜索技術從群體出發，具有很好的并行性，可以同時進行多個個體的比較，可以降低對硬件的要求，從而減少巨額開支。

（3）搜索使用評價函數啟發，過程相對簡單。算法具有很好的擴展性，在實際應用過程中，容易與其他算法結合提升效率。算法簡單易懂，能夠較好地應用到實際操作中。

2路面特性與油耗關系

2.1汽車油耗影響因素

汽車在行駛過程中的油耗不僅關系到成本，同時也關系到綠色出行。汽車燃油經濟性指標，是指汽車在一定標準的情況下，以最低能耗完成行駛定量路程的能力。在汽車的行駛過程中，能夠影響汽車油耗的因素相對較多，主要有以下幾類：汽車本身的性能，如汽車動力和傳動系統，包括發動機、變速箱、車型、車重、輪胎等多種汽車內在因素，往往汽車越重，排量越大的汽車相對耗油量較高。駕駛技術的因素，作為司機在行車過程中，能否在合適的時候換擋（以手動擋為例），或者在行車過程中的一些良好的操作如紅燈前空擋滑行、輕踩油門啟動等，會直接影響汽車油耗。路面環境對汽車行駛影響。在道路上由于多種因素造成汽車在道路上緩慢行駛，如：堵車、路面情況復雜、發生交通事故等，這些會直接影響汽車在行進中燃油是否能夠充分燃燒，燃油不能重復燃燒的后果是不僅耗油還會污染環境。從全局來看，提高燃油的經濟性無外乎就是：一是提升燃油燃燒效率，二是降低負荷。而本文所研究的是在汽車重量一定的情況下，如何降低油耗，所以接下來會重點分析速度與燃油效率的關系。

2.2速度與油耗的關系

世界銀行的HDM-3研究表明，在外國，部分公路在反復維修后，道路表面平整度減小，但是汽車的油耗反而更低。其重要原因是，在公路維修過后，道路的平整度相對減小，司機通過減速的方法來提升適應度，最終因車速的降低而使得在行駛過程中的空氣阻力減小，進而減少耗油量。通過實踐證明，汽車在行駛過程中，速度與油耗之間的關系呈U字形拋物線。即在起步階段，油耗隨著速度的提升不斷下降，當速度提升到一定值后，汽車遇到的空氣阻力不斷增大，油耗隨著速度的提升不斷上升。

3基于遺傳算法的最低油耗電子地圖尋徑

3.1個體編碼及初始化

個體主要用于表示汽車在行進過程中的一條路線。小汽車由起點A經過途中所示范路線前行最終到達位置B，即為一個個體。個體以坐標的形式可以表現為：{（0，0，x）（0,1,x）（0,2,x）（0,3,x）（2,2,x）（3,3,x）（3,4,x）（3,0,x）（5,5,x）（6,7,x）}。其中前兩位數分表代表橫向和縱向值，第三位數代表著這段路程所能行駛的最大速度。初始化種群是由一定數目的個體組成，在小汽車運行的區間即A到B點之間，用隨機選擇、自由、不定的連續路徑鏈接A和B。在初始化的時候，要確保選擇進來的路徑是能夠通行的道路，且無死胡同，并且每個個體的長度盡可能地大于全路徑的30%，再經過一系列的插入、刪除操作，最終得到最低油耗路徑。

3.2適應函數

個體的自適應函數直接關系到遺傳算法的計算時間和工作效率。在設計過程中，要盡可能確保能夠找到一條最低油耗路徑，且該路線不會進入死胡同或者死循環。

3.3遺傳算子

（1）繁殖算子。根據適應函數和個體適應度大小，使個體能夠按照一定的概率向下繁殖。

（2）交叉變異算子。交叉指的是將兩個父代的部分結構進行替換重組的操作，在這里主要選擇重合點混合交叉的方式。即隨機選取兩個個體，在兩個個體中，選擇序號相同的道路進行交叉操作。變異則為在起點A和終點B之間隨機選擇一個序號作為變異點進行變異操作。

（3）刪除、插入算子。定義汽車的運行方向時，主要是四個方向，分別是：前，后，左，右。為了盡可能地保證路徑選擇的合理性，以向前的方向及最低油耗值作為最優路線。所以汽車在行進過程中，反方向或者油耗過高的路線都會被刪除，從而確保最低油耗路徑的生成。插入算子主要是為了保持種群個體所對應路徑的連續性。

3.4汽車前進路徑規劃算法路程

（1）個體編碼，對所涉及問題的可能解進行染色體編碼。選擇操作主要使用選擇重合點混合交叉的方式。即隨機選取兩個個體，在兩個個體中，選擇序號相同的道路進行交叉操作；

（2）計算種群上每個個體的適應度；

（3）按由個體適應值所制定的規則選擇進入下一代的個體；

（4）按概率PC和Pm進行交叉操作和突變操作，生成新鮮的群體；

（5）若經過交叉及突變并沒有生產某種停止條件，則轉入到2），否則繼續進入下一步；

（6）輸出種群適應度最優的染色體作為問題最優解或最終解。

作者：周文彬羅瑩單位：江西師范大學軟件學院江西中醫藥大學現代中藥制劑教育部重點實驗室