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

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

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

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

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

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

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

pm=k2/(fmax-F)(2)在調(diào)整過程中，當(dāng)種群趨于收斂時，提高Pc和Pm，破壞當(dāng)前的穩(wěn)定性，克服過早收斂；當(dāng)種群個體發(fā)散時，降低Pc和Pm，增加開發(fā)能力，使個體趨于收斂。但，當(dāng)已收斂到全局最優(yōu)時，此時誤判別函數(shù)，從而使得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，并為常數(shù)

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

多種群進化

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

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

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