智能優(yōu)化算法-遺傳算法_第1頁
智能優(yōu)化算法-遺傳算法_第2頁
智能優(yōu)化算法-遺傳算法_第3頁
智能優(yōu)化算法-遺傳算法_第4頁
智能優(yōu)化算法-遺傳算法_第5頁
已閱讀5頁,還剩11頁未讀 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

智能優(yōu)化算法--遺傳算法

什么是智能優(yōu)化算法?

智能優(yōu)化算法是一種啟發(fā)式優(yōu)化算法,通過程序來模擬自然界已知的進化方法來進行優(yōu)化的方法,比如模擬生物進化的遺傳算法,模擬自然選擇進行篩選,逐步歸向最大值,包括遺傳算法、蟻群算法、禁忌搜索算法、模擬退火算法、粒子群算法等?!ぶ悄軆?yōu)化算法一般是針對具體問題設計相關的算法,理論要求弱,技術性強。一般,我們會把智能算法與最優(yōu)化算法進行比較,相比之下,智能算法速度快,應用性強。遺傳算法(GA)

遺傳算法(GeneticAlgorithm)是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型,是一種通過模擬自然進化過程搜索最優(yōu)解的方法,是一類借鑒生物界的進化規(guī)律(適者生存,優(yōu)勝劣汰遺傳機制)演化而來的隨機化搜索方法。它是由美國的J.Holland教授1975年首先提出,其主要特點是直接對結構對象進行操作,不存在求導和函數連續(xù)性的限定;具有內在的隱并行性和更好的全局尋優(yōu)能力;采用概率化的尋優(yōu)方法,能自動獲取和指導優(yōu)化的搜索空間,自適應地調整搜索方向,不需要確定的規(guī)則。遺傳算法的操作算法(1)復制或選擇算子:將父代的個體原封不動地傳遞到子代,在復制過程中,每個個體是按照適應度值的大小決定其能否被復制到下一代的概率,復制算子可使群體中的優(yōu)秀個體數目逐漸增加,使進化過程向更優(yōu)解的方向發(fā)展,反映了自然界中優(yōu)勝劣汰的法則.:(3)變異算子:復制和交叉算子只能在現有基因型的排列組合內尋找最優(yōu),而不能產生新的基因型,變異算子可使基因型發(fā)生變化,從而擴大尋優(yōu)范圍。(2)交叉算子:上面的復制算子只能在現有群體中尋找最優(yōu),而不能產生與父代不同的個體,交叉算子可使同一代的某對個體間,按一定的概率交換其中的部分基因,從而產生新的基因組合,可望獲得比父代更好的個體。遺傳算法優(yōu)化

遺傳算法具有很強的魯棒性,而且所需的領域知識少,應用范圍廣泛,但它具有一個根本的缺點——過早收斂。由于遺傳算法中選擇及交叉等算子的作用,使得一些優(yōu)秀的基因片段過早丟失,從而限制搜索范圍,使得搜索只能在局部內找到最優(yōu)值,而不能得到滿意的全局最優(yōu)值。優(yōu)化方向:1)對選擇,交叉和變異算子的改進2)改進控制參數;種群規(guī)模,交叉概率Pc,變異概率Pm1自適應參數調整令fmax代表某一代種群中最優(yōu)個體的擬合度,令F代表此代種群平均的擬合度,則Δ=fmax-F,諾Δ越小,表示種群個體擬合度差別較小,達到局部最優(yōu)和過早收斂可能性越大;反之,Δ越大,個體特性分散,擬合度差別較大。Pc和Pm參數由Δ決定,且

pc=k1/(fmax-F)(1)

pm=k2/(fmax-F)(2)在調整過程中,當種群趨于收斂時,提高Pc和Pm,破壞當前的穩(wěn)定性,克服過早收斂;當種群個體發(fā)散時,降低Pc和Pm,增加開發(fā)能力,使個體趨于收斂。但,當已收斂到全局最優(yōu)時,此時誤判別函數,從而使得Pc和Pm增大,最優(yōu)個體遭到破壞的概率也增大,使得GA性能下降。

在克服過早收斂和避免優(yōu)秀個體被破壞之間選擇折衷方案:

pc=k1(fmax-f′)/(fmax-F),f′≥

F

(3)

pc=k3,f′<F

(4)

pm=k2(fmax-f)/(fmax-F),f≥F

(5)

pm=k4,f<F

(6)f為變異個體的擬合度,f′為兩個交叉?zhèn)€體中擬合度大的k1,k2,k3,k4≤1.0,并為常數

對于k3,k4由于此時f′<F或f<F,即個體擬合度小于平均擬合度,說明個體特性差,因此增大Pc和Pm,易使差的個體破壞的可能性增大,因此,k3,k4的值應大一些,而k1,k2可依據實際情況而定2

多種群進化

將原種群按特性劃分為幾個子種群,每個子種群有各自的特點具有不同的Pc和Pm,不同的種群規(guī)模,具有不同的進化策略和算子,個體的特性分布也不同。這樣通過不同子種群之間的進化,可以選取和保留每個種群的優(yōu)秀個體,避免單種群進化產生的過早收斂現象,同時又可以保持優(yōu)秀個體的進化穩(wěn)定性。另外為了使每個種群進化的靈活性,在Pc和Pm的設置時,不再像以前那樣將它們設為常值,而是根據種屬的實際情況,使其自動調整參數值。遺傳算法的應用基于遺傳算法的移動機器人動態(tài)避障路徑規(guī)劃方法動態(tài)路徑的規(guī)劃要求:路徑在路邊之內、能動態(tài)避障和路徑最短(1)路徑在路邊之內路邊約束限制了解空間的范圍,即各個y;值只能在路邊約束范圍內取值,各個點的y值取值范圍的確定方法如下:在圖2中,首先計算出各個x;位置與x軸垂直的各直線與路兩邊折線相交的兩個y坐標值,然后再分別向路中心收縮一定量,收縮量的確定是按照機器人中心必須遠離路邊的安全距離確定的,顯然安全距離應大于移動機器人的最大半徑,設確定的yi的取值范圍是(y,l,y2)因此路邊約束的適應度函數flt1可表達為式中i為路徑上的所有點上式表明只要各個路徑點在離路邊的安全距離之內,則適應度為1,否則為0,這樣確定是比較符合實際情況的.(2)能動態(tài)避障

動態(tài)避障是比較關鍵的一個約束條件,假設障礙物的個數、障礙物的位置和速度信息可由機器視覺和激光雷達確定;在局部動態(tài)路徑的規(guī)劃過程中,假設移動機器人以當前的速度行走,各障礙物也以當前測定的速度做勻速直線運動,因為控制周期一般小于500m、,此外,路徑跟蹤控制算法會自動控制機器人行走速度的變化,因此在路徑規(guī)劃過程中,可以不考慮機器人和障礙物行走速度的變化.動態(tài)避障的基本條件是,對于某一路徑,組成路徑的各點與各障礙物之間的最小距離必須大于機器人與障礙物的半徑之和.可得動態(tài)避障的適度函數fit2為Dmin為于任意一條路徑,路徑上與障礙物的最短距離(3)路徑最短路徑最短的適應度函數確定如下:最后綜合得到遺傳算法的綜合適應度函數為最后綜合得到遺傳算法的綜合適應度函數為該綜合適應度函數把三個約束條件有機融合在一起,計算簡單,且能避免三項加權求和引起的優(yōu)化不穩(wěn)定問題復制算子:同傳統(tǒng)復制算子一樣,即采用與適應度成比例的概率來選擇個體.為了保證最優(yōu)個體在進化過程中不被破壞,新一代群體中適應度最小的個體可以直接用上一代的適應度最大的個體取代交叉算子:與傳統(tǒng)的交叉算子類似,交換的位置和交換的點數是隨機確定的.變異算子:其作用是在個體結構一定的前提下,加人隨機擾動,以尋找最優(yōu)解,本文采取加人零均值高斯白噪聲的方法.

此外,為提高初始種群的優(yōu)良性能,在隨機產生初始種群的過程中,加人初選評估程序,即對隨機產生的初始種群考察其路邊約束和動態(tài)避障的適應度值,由此保證初始種群中滿足路邊約束和動態(tài)避障條件的個體數目大于一定的數量,這樣可保證遺傳算法快速、穩(wěn)定地找到全局最優(yōu)解.參考文獻1《基于克服過早收斂的自適應并行遺傳算法》——周遠暉,陸玉昌,石純一2《基于遺傳算法的移動機器人動態(tài)避障路徑規(guī)劃方法》——李慶中顧偉康葉秀清PPT模板下載:/moban/行業(yè)PPT模板:/hangye/節(jié)日PPT模板:/jieri/PPT素材下載:/sucai/PPT背景圖片:/beijing/PPT圖表下載:/tubiao/優(yōu)秀PPT下載:/xiazai/PPT教

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論