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

1遺傳算法原理及基本特點(diǎn)

1.1算法原理

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

1.2遺傳算法的優(yōu)點(diǎn)

遺傳算法充分運(yùn)用大自然的遺傳和進(jìn)化的思想，完全不同于其他搜索方式，其明顯的優(yōu)點(diǎn)如下：

（1）快速隨機(jī)的搜索能力。遺傳算法本身具有很強(qiáng)的自適應(yīng)和智能性。在搜索過(guò)程中，消除了基本的障礙，即需要能夠先對(duì)問題的全部特點(diǎn)進(jìn)行描述。搜索使用概率機(jī)制進(jìn)行迭代，具有很高的隨機(jī)性。同時(shí)，它不受優(yōu)化函數(shù)的約束，也沒有對(duì)優(yōu)化函數(shù)的依賴性。

（2）搜索技術(shù)從群體出發(fā)，具有很好的并行性，可以同時(shí)進(jìn)行多個(gè)個(gè)體的比較，可以降低對(duì)硬件的要求，從而減少巨額開支。

（3）搜索使用評(píng)價(jià)函數(shù)啟發(fā)，過(guò)程相對(duì)簡(jiǎn)單。算法具有很好的擴(kuò)展性，在實(shí)際應(yīng)用過(guò)程中，容易與其他算法結(jié)合提升效率。算法簡(jiǎn)單易懂，能夠較好地應(yīng)用到實(shí)際操作中。

2路面特性與油耗關(guān)系

2.1汽車油耗影響因素

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

2.2速度與油耗的關(guān)系

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

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

3.1個(gè)體編碼及初始化

個(gè)體主要用于表示汽車在行進(jìn)過(guò)程中的一條路線。小汽車由起點(diǎn)A經(jīng)過(guò)途中所示范路線前行最終到達(dá)位置B，即為一個(gè)個(gè)體。個(gè)體以坐標(biāo)的形式可以表現(xiàn)為：{（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）}。其中前兩位數(shù)分表代表橫向和縱向值，第三位數(shù)代表著這段路程所能行駛的最大速度。初始化種群是由一定數(shù)目的個(gè)體組成，在小汽車運(yùn)行的區(qū)間即A到B點(diǎn)之間，用隨機(jī)選擇、自由、不定的連續(xù)路徑鏈接A和B。在初始化的時(shí)候，要確保選擇進(jìn)來(lái)的路徑是能夠通行的道路，且無(wú)死胡同，并且每個(gè)個(gè)體的長(zhǎng)度盡可能地大于全路徑的30%，再經(jīng)過(guò)一系列的插入、刪除操作，最終得到最低油耗路徑。

3.2適應(yīng)函數(shù)

個(gè)體的自適應(yīng)函數(shù)直接關(guān)系到遺傳算法的計(jì)算時(shí)間和工作效率。在設(shè)計(jì)過(guò)程中，要盡可能確保能夠找到一條最低油耗路徑，且該路線不會(huì)進(jìn)入死胡同或者死循環(huán)。

3.3遺傳算子

（1）繁殖算子。根據(jù)適應(yīng)函數(shù)和個(gè)體適應(yīng)度大小，使個(gè)體能夠按照一定的概率向下繁殖。

（2）交叉變異算子。交叉指的是將兩個(gè)父代的部分結(jié)構(gòu)進(jìn)行替換重組的操作，在這里主要選擇重合點(diǎn)混合交叉的方式。即隨機(jī)選取兩個(gè)個(gè)體，在兩個(gè)個(gè)體中，選擇序號(hào)相同的道路進(jìn)行交叉操作。變異則為在起點(diǎn)A和終點(diǎn)B之間隨機(jī)選擇一個(gè)序號(hào)作為變異點(diǎn)進(jìn)行變異操作。

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

3.4汽車前進(jìn)路徑規(guī)劃算法路程

（1）個(gè)體編碼，對(duì)所涉及問題的可能解進(jìn)行染色體編碼。選擇操作主要使用選擇重合點(diǎn)混合交叉的方式。即隨機(jī)選取兩個(gè)個(gè)體，在兩個(gè)個(gè)體中，選擇序號(hào)相同的道路進(jìn)行交叉操作；

（2）計(jì)算種群上每個(gè)個(gè)體的適應(yīng)度；

（3）按由個(gè)體適應(yīng)值所制定的規(guī)則選擇進(jìn)入下一代的個(gè)體；

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

（5）若經(jīng)過(guò)交叉及突變并沒有生產(chǎn)某種停止條件，則轉(zhuǎn)入到2），否則繼續(xù)進(jìn)入下一步；

（6）輸出種群適應(yīng)度最優(yōu)的染色體作為問題最優(yōu)解或最終解。

作者：周文彬羅瑩單位：江西師范大學(xué)軟件學(xué)院江西中醫(yī)藥大學(xué)現(xiàn)代中藥制劑教育部重點(diǎn)實(shí)驗(yàn)室