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

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

2、過程搜索最優(yōu)解的方法，是一類借鑒生物界的進(jìn)化規(guī)律（適者生存，優(yōu)勝劣汰遺傳機(jī)制）演化而來的隨機(jī)化搜索方法。它是由美國的J.Holland教授1975年首先提出，其主要特點(diǎn)是直接對結(jié)構(gòu)對象進(jìn)行操作，不存在求導(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ù)目逐漸增加,使進(jìn)化過程向更優(yōu)解的方向發(fā)展,反映了自然界中優(yōu)

3、勝劣汰的法則.:（3）變異算子：復(fù)制和交叉算子只能在現(xiàn)有基因型的排列組合內(nèi)尋找最優(yōu)，而不能產(chǎn)生新的基因型，變異算子可使基因型發(fā)生變化，從而擴(kuò)大尋優(yōu)范圍。(2)交叉算子：上面的復(fù)制算子只能在現(xiàn)有群體中尋找最優(yōu)，而不能產(chǎn)生與父代不同的個體，交叉算子可使同一代的某對個體間，按一定的概率交換其中的部分基因，從而產(chǎn)生新的基因組合，可望獲得比父代更好的個體。遺傳算法優(yōu)化 遺傳算法具有很強(qiáng)的魯棒性，而且所需的領(lǐng)域知識少，應(yīng)用范圍廣泛，但它具有一個根本的缺點(diǎn)過早收斂。由于遺傳算法中選擇及交叉等算子的作用，使得一些優(yōu)秀的基因片段過早丟失，從而限制搜索范圍，使得搜索只能在局部內(nèi)找到最優(yōu)值，而不能得到滿意的全局最優(yōu)

4、值。優(yōu)化方向：1） 對選擇，交叉和變異算子的改進(jìn)2）改進(jìn)控制參數(shù)；種群規(guī)模，交叉概率Pc，變異概率Pm1 自適應(yīng)參數(shù)調(diào)整令fmax代表某一代種群中最優(yōu)個體的擬合度，令F代表此代種群平均的擬合度，則 = f max-F，諾越小，表示種群個體擬合度差別較小，達(dá)到局部最優(yōu)和過早收斂可能性越大；反之，越大，個體特性分散，擬合度差別較大。Pc和Pm參數(shù)由決定，且 p c = k 1 /( f max - F) ( 1) p m = k 2 /( f max - F) ( 2)在調(diào)整過程中，當(dāng)種群趨于收斂時，提高Pc和Pm，破壞當(dāng)前的穩(wěn)定性，克服過早收斂；當(dāng)種群個體發(fā)散時，降低Pc和Pm，增加開發(fā)能力，使

5、個體趨于收斂。但，當(dāng)已收斂到全局最優(yōu)時，此時誤判別函數(shù)，從而使得Pc和Pm增大，最優(yōu)個體遭到破壞的概率也增大，使得GA性能下降。 在克服過早收斂和避免優(yōu)秀個體被破壞之間選擇折衷方案： p c = k 1( f max - f) /( f max - F) , f F (3) p c = k 3 , f F ( 4) p m = k 2 ( f max - f ) /( f max - F) , f F ( 5) p m = k 4 , f F ( 6)f為變異個體的擬合度，f為兩個交叉?zhèn)€體中擬合度大的k1，k2，k3，k4 1.0，并為常數(shù) 對于k3，k4由于此時f F或 f F，即個體擬合度

6、小于平均擬合度，說明個體特性差，因此增大Pc和Pm，易使差的個體破壞的可能性增大，因此，k3,k4的值應(yīng)大一些，而k1,k2可依據(jù)實(shí)際情況而定2 多種群進(jìn)化 將原種群按特性劃分為幾個子種群，每個子種群有各自的特點(diǎn)具有不同的Pc和Pm，不同的種群規(guī)模，具有不同的進(jìn)化策略和算子，個體的特性分布也不同。這樣通過不同子種群之間的進(jìn)化，可以選取和保留每個種群的優(yōu)秀個體，避免單種群進(jìn)化產(chǎn)生的過早收斂現(xiàn)象，同時又可以保持優(yōu)秀個體的進(jìn)化穩(wěn)定性。另外為了使每個種群進(jìn)化的靈活性，在Pc和Pm的設(shè)置時，不再像以前那樣將它們設(shè)為常值，而是根據(jù)種屬的實(shí)際情況，使其自動調(diào)整參數(shù)值。遺傳算法的應(yīng)用基于遺傳算法的移動機(jī)器人動

7、態(tài)避障路徑規(guī)劃方法動態(tài)路徑的規(guī)劃要求：路徑在路邊之內(nèi)、能動態(tài)避障和路徑最短(1)路徑在路邊之內(nèi)路邊約束限制了解空間的范圍路邊約束限制了解空間的范圍, ,即各個即各個y;y;值只能在路邊約束范圍內(nèi)取值值只能在路邊約束范圍內(nèi)取值, ,各個點(diǎn)的各個點(diǎn)的y y值取值范圍的確定方法如下值取值范圍的確定方法如下: :在圖在圖2 2中中, ,首先計算出各個首先計算出各個x;x;位置與位置與x x軸垂直的各直線軸垂直的各直線與路兩邊折線相交的兩個與路兩邊折線相交的兩個y y坐標(biāo)值坐標(biāo)值, ,然后再分別向路中心收縮一定量然后再分別向路中心收縮一定量, ,收縮量的確定收縮量的確定是按照機(jī)器人中心必須遠(yuǎn)離路邊的安全

8、距離確定的是按照機(jī)器人中心必須遠(yuǎn)離路邊的安全距離確定的, ,顯然安全距離應(yīng)大于移動機(jī)器顯然安全距離應(yīng)大于移動機(jī)器人的最大半徑人的最大半徑, ,設(shè)確定的設(shè)確定的yiyi的取值范圍是的取值范圍是(y,l,(y,l,y2)y2)因此路邊約束的適應(yīng)度函數(shù)因此路邊約束的適應(yīng)度函數(shù)flt1flt1可表達(dá)為可表達(dá)為式中式中i i為路徑上的所有點(diǎn)上式表明只要各個路徑為路徑上的所有點(diǎn)上式表明只要各個路徑點(diǎn)在離路邊的安全距離之內(nèi)點(diǎn)在離路邊的安全距離之內(nèi), ,則適應(yīng)度為則適應(yīng)度為1,1,否則否則為為0,0,這樣確定是比較符合實(shí)際情況的這樣確定是比較符合實(shí)際情況的. .(2)能動態(tài)避障 動態(tài)避障是比較關(guān)鍵的一個約束條

9、件動態(tài)避障是比較關(guān)鍵的一個約束條件, ,假設(shè)障礙物的個數(shù)、障礙物的位置假設(shè)障礙物的個數(shù)、障礙物的位置和速度信息可由機(jī)器視覺和激光雷達(dá)確定和速度信息可由機(jī)器視覺和激光雷達(dá)確定; ;在局部動態(tài)路徑的規(guī)劃過程中在局部動態(tài)路徑的規(guī)劃過程中, ,假假設(shè)移動機(jī)器人以當(dāng)前的速度行走設(shè)移動機(jī)器人以當(dāng)前的速度行走, ,各障礙物也以當(dāng)前測定的速度做勻速直線各障礙物也以當(dāng)前測定的速度做勻速直線運(yùn)動運(yùn)動, ,因?yàn)榭刂浦芷谝话阈∮谝驗(yàn)榭刂浦芷谝话阈∮?00m500m、, ,此外此外, ,路徑跟蹤控制算法會自動控制機(jī)路徑跟蹤控制算法會自動控制機(jī)器人行走速度的變化器人行走速度的變化, ,因此在路徑規(guī)劃過程中因此在路徑規(guī)劃過

10、程中, ,可以不考慮機(jī)器人和障礙物行可以不考慮機(jī)器人和障礙物行走速度的變化走速度的變化. .動態(tài)避障的基本條件是動態(tài)避障的基本條件是, ,對于某一路徑對于某一路徑, ,組成路徑的各點(diǎn)與各組成路徑的各點(diǎn)與各障礙物之間的最小距離必須大于機(jī)器人與障礙物的半徑之和障礙物之間的最小距離必須大于機(jī)器人與障礙物的半徑之和. .可得動態(tài)避障的適度函數(shù)fit2為Dmin為于任 意 一 條路徑,路徑上與障礙物的最短距離（3）路徑最短路徑最短的適應(yīng)度函數(shù)確定如下：路徑最短的適應(yīng)度函數(shù)確定如下：最后綜合得到遺傳算法的綜合適應(yīng)度函數(shù)為最后綜合得到遺傳算法的綜合適應(yīng)度函數(shù)為最后綜合得到遺傳算法的綜合適應(yīng)度函數(shù)為該綜合適應(yīng)

11、度函數(shù)把三個約束最后綜合得到遺傳算法的綜合適應(yīng)度函數(shù)為該綜合適應(yīng)度函數(shù)把三個約束條件有機(jī)融合在一起條件有機(jī)融合在一起, ,計算簡單計算簡單, ,且能避免三項加權(quán)求和引起的優(yōu)化不穩(wěn)定且能避免三項加權(quán)求和引起的優(yōu)化不穩(wěn)定問題問題復(fù)制算子復(fù)制算子: :同傳統(tǒng)復(fù)制算子一樣同傳統(tǒng)復(fù)制算子一樣, ,即采用與適應(yīng)度成比例的概率來選擇個體即采用與適應(yīng)度成比例的概率來選擇個體. .為了為了保證最優(yōu)個體在進(jìn)化過程中不被破壞保證最優(yōu)個體在進(jìn)化過程中不被破壞, ,新一代群體中適應(yīng)度最小的個體可以直接新一代群體中適應(yīng)度最小的個體可以直接用上一代的適應(yīng)度最大的個體取代用上一代的適應(yīng)度最大的個體取代交叉算子交叉算子: :與

12、傳統(tǒng)的交叉算子類似與傳統(tǒng)的交叉算子類似, ,交換的位置和交換的點(diǎn)數(shù)是隨機(jī)確定的交換的位置和交換的點(diǎn)數(shù)是隨機(jī)確定的. .變異算子變異算子: :其作用是在個體結(jié)構(gòu)一定的前提下其作用是在個體結(jié)構(gòu)一定的前提下, ,加人隨機(jī)擾動加人隨機(jī)擾動, ,以尋找最優(yōu)解以尋找最優(yōu)解, ,本本文采取加人零均值高斯白噪聲的方法文采取加人零均值高斯白噪聲的方法. . 此外此外, ,為提高初始種群的優(yōu)良性能為提高初始種群的優(yōu)良性能, ,在隨機(jī)產(chǎn)生初始種群的過程中在隨機(jī)產(chǎn)生初始種群的過程中, ,加人初選加人初選評估程序評估程序, ,即對隨機(jī)產(chǎn)生的初始種群考察其路邊約束和動態(tài)避障的適應(yīng)度值即對隨機(jī)產(chǎn)生的初始種群考察其路邊約束和動態(tài)避障的適應(yīng)度值, ,由由此保證初始種群中滿足路邊約束和動態(tài)避障條件的個體數(shù)目大于一定的數(shù)量此保證初始種群中滿足路邊約束和動態(tài)避障條件的個體數(shù)目大于一定的數(shù)量, ,這這樣可保證遺傳算法快速、穩(wěn)定地找到全局最優(yōu)解樣可保證遺傳算法快速、穩(wěn)定地找到全