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

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

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

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

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

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

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

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

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

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為變異個(gè)體的擬合度，f′為兩個(gè)交叉?zhèn)€體中擬合度大的k1，k2，k3，k4≤1.0，并為常數(shù)

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

多種群進(jìn)化

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

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

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