基于改進(jìn)遺傳算法的艦船路徑規(guī)劃

1、14522009,30(6)計(jì)算機(jī)工程與設(shè)計(jì)ComputerEngineeringandDesign人工智能0引言艦船路徑規(guī)劃對(duì)于艦船實(shí)現(xiàn)自動(dòng)化航行和航線優(yōu)化具有重要的意義，要求在復(fù)雜的海上環(huán)境中，根據(jù)已知的地理信息數(shù)據(jù)，尋找出一條從起點(diǎn)到終點(diǎn)的最安全且航程最短的航線。傳統(tǒng)的圖搜索法、柵格法、人工勢場法等都有一定局限性1。由于遺傳算法在解決非線性問題上具有良好的適用性，已成為路徑規(guī)劃中使用較多的一種方法，被廣泛的應(yīng)用于機(jī)器人、飛行器的路徑規(guī)劃1-3。但是標(biāo)準(zhǔn)的遺傳算法本身也存在著一些缺陷，如早熟、局部最優(yōu)解、占據(jù)較大的存儲(chǔ)空間和運(yùn)算時(shí)間，并且在實(shí)際應(yīng)用中缺乏對(duì)特定知識(shí)的利用2，保證不了對(duì)路徑規(guī)

2、劃的計(jì)算效率和可靠性要求。為了提高路徑規(guī)劃問題的求解質(zhì)量和求解效率，本文提出了一種用于艦船路徑規(guī)劃的改進(jìn)遺傳算法，使用簡單的編碼方式，有效降低了遺傳算法的搜索空間；根據(jù)艦船航行的特點(diǎn)設(shè)計(jì)了交叉算子、插入算子、刪除算子和平滑算子。最后通過計(jì)算機(jī)仿真證明了改進(jìn)后的遺傳算法對(duì)于搜索效率和收斂速度都有顯著的提高，并能保證收斂到全局最優(yōu)解，克服了標(biāo)準(zhǔn)遺傳算法的缺點(diǎn)。1應(yīng)用于艦船路徑規(guī)劃的改進(jìn)遺傳算法在本文的艦船路徑規(guī)劃中，目標(biāo)是在一幅障礙物分布已知的二維地圖上尋找一條最優(yōu)路徑使到達(dá)目標(biāo)點(diǎn)距離最短，同時(shí)盡可能地最大化與障礙物的距離。為了簡化討論，艦船被作為一個(gè)質(zhì)點(diǎn)來考慮，而障礙物的邊界向外擴(kuò)張艦船的最大安

3、全距離。1.1路徑編碼編碼長度是影響遺傳算法收斂速度的重要因素之一，因此應(yīng)當(dāng)盡量使用簡單的遺傳編碼4。艦船航行路徑可以看作由起點(diǎn)和終點(diǎn)及一系列中間點(diǎn)組成的路徑，其結(jié)構(gòu)為(x0，y0)(x1，y1)(xi，yi)(xn，yn)式中：(x0，y0)起點(diǎn)，(xn，yn)終點(diǎn)，(xi，yi)起點(diǎn)和終點(diǎn)之間的一系列中間點(diǎn)，稱之為轉(zhuǎn)向點(diǎn)，i=1，2，n唐琳，蔡德榮，黃猛：基于改進(jìn)遺傳算法的艦船路徑規(guī)劃2009,30(6)145311,10圖1路徑編碼平分成x1，x2，xn-1，則路徑點(diǎn)可以簡化為一維的y軸坐標(biāo)編碼形式，表示為y1，y2，yn，在遺傳操作中，只需要對(duì)y軸坐標(biāo)進(jìn)行優(yōu)化即可，可以大大的提高算法的

4、速度。1.2種群初始化執(zhí)行遺傳算法的最優(yōu)航線設(shè)計(jì)，必須對(duì)種群進(jìn)行初始化，由于初始路徑是隨機(jī)產(chǎn)生的，各轉(zhuǎn)向點(diǎn)坐標(biāo)可能分布在整個(gè)規(guī)劃區(qū)域范圍內(nèi)，包括可行和不可行的，這樣增加了搜索的范圍，由于對(duì)原坐標(biāo)進(jìn)行了映射，也就是說每個(gè)轉(zhuǎn)向點(diǎn)的橫坐標(biāo)是已知的，即x1，x2，xn-1已知，只需要在這些位置的垂直線上隨機(jī)選取y坐標(biāo)即可。另外，根據(jù)規(guī)劃環(huán)境的復(fù)雜度不同，最優(yōu)航線中轉(zhuǎn)向點(diǎn)的個(gè)數(shù)也是不確定的，一般來說，環(huán)境越復(fù)雜轉(zhuǎn)向點(diǎn)就越多，因此算法采用變長編碼技術(shù)，通過對(duì)染色體進(jìn)行刪除、插入等操作，能夠確定合適的轉(zhuǎn)向點(diǎn)個(gè)數(shù)，使路徑達(dá)到最優(yōu)。但是轉(zhuǎn)向點(diǎn)數(shù)目太多會(huì)占用太多資源，使運(yùn)算速度變慢，因此，在運(yùn)算過程中，設(shè)定一個(gè)最

5、大轉(zhuǎn)向點(diǎn)Nmax，種群中每個(gè)個(gè)體的最大長度n滿足：2nNmax。1.3適應(yīng)度函數(shù)艦船的路徑規(guī)劃，具體說就是要在起點(diǎn)和終點(diǎn)之間找出一條最短的可行路徑，約束條件是不與障礙物相交，同時(shí)還受自身體積的限制，艦船在航行中的轉(zhuǎn)角不能太大，本文算法以3個(gè)條件來作為規(guī)劃路徑的可行性評(píng)價(jià)函數(shù)，即路徑總長度、安全性、和各轉(zhuǎn)向點(diǎn)拐角平均大小，對(duì)于不可行的路徑對(duì)其適應(yīng)度進(jìn)行懲罰，使它的適應(yīng)度差于可行路徑。(1)路徑安全性評(píng)價(jià)：為了防止艦船與障礙物碰撞，應(yīng)盡量使其與障礙物保持一定的安全距離，假設(shè)艦船的安全半徑為r，艦船與障礙物的距離為d，安全性的評(píng)價(jià)函數(shù)可以式(1)來表示=1(3)d(pi-1pi)是轉(zhuǎn)向點(diǎn)pi-1與p

6、i之間的長度，如果pi-1與pi之間的路徑不可行，則使用懲罰函數(shù)法對(duì)其適應(yīng)度進(jìn)行懲罰，懲罰函數(shù)定義如下,=01=1(4)式中：ci的定義見式(2)，=1(5)評(píng)價(jià)路徑好壞是求路徑長度最短的問題，通過懲罰因子，可以使不可行路徑的變長，從而降低它的適應(yīng)值。(3)路徑平滑度：艦船的幾何外形特點(diǎn)決定了其在航行過程中不能以大的拐角進(jìn)行轉(zhuǎn)向，因此整條行駛路徑應(yīng)平緩而光滑，即每一轉(zhuǎn)向點(diǎn)處的拐角值應(yīng)盡可能小。這里假設(shè)拐角最大值不能超過×=i(i=2，3，nii中大于或等于/2時(shí)，對(duì)適應(yīng)度進(jìn)行懲罰。當(dāng)n=2時(shí)，路徑為起始點(diǎn)與終止點(diǎn)的連線。若其可行，則M值為0，可以看出M值越小路徑的平滑度越好。得到了以

7、上3個(gè)條件的評(píng)價(jià)函數(shù)，就可以獲得整條路徑的適應(yīng)度函數(shù)。采用各項(xiàng)評(píng)價(jià)函數(shù)加權(quán)求和是常用的確定適應(yīng)度函數(shù)的方法4-6，因?yàn)楦鱾€(gè)加權(quán)系數(shù)不是恒定不變的，而是隨著路徑和障礙物的情況變化而變化，這種情況下各個(gè)加權(quán)系數(shù)就很難調(diào)整和確定。因此，在確定適應(yīng)度函數(shù)時(shí)，盡量使適應(yīng)度函數(shù)的項(xiàng)數(shù)最少，但又必須把路徑規(guī)劃的3個(gè)條件融合在遺傳優(yōu)化過程中。這里采用評(píng)價(jià)函數(shù)相乘的形式，如式(7)所示f=S/(M*L)(7)以f作為選擇操作的依據(jù)，路徑的長度和平均拐角越小，其適應(yīng)度越好。1.4遺傳算子(1)選擇算子：使用錦標(biāo)賽選擇法和精英保留法相結(jié)合的選擇策略，錦標(biāo)賽選擇法在選擇時(shí)先隨機(jī)的在群體中選擇K個(gè)個(gè)體進(jìn)行比較，適應(yīng)度最

8、好的個(gè)體將被選擇作為生成下一代的父體，參數(shù)K稱為競賽規(guī)模。這種選擇方式能使種群中適應(yīng)度好的個(gè)體具有較大的“生存”機(jī)會(huì)。同時(shí)，由于它只使用適應(yīng)度的相對(duì)值作為選擇的標(biāo)準(zhǔn)，而與適應(yīng)度的數(shù)值大小不成直接比例，從而避免了超級(jí)個(gè)體的影響，在一定程度上避免了過早收斂和停滯現(xiàn)象的發(fā)生。精英保留法即當(dāng)前種群中適應(yīng)度最好的個(gè)體不參加遺傳操作，直接復(fù)制到下一代，替換經(jīng)交叉和變異操作產(chǎn)生的子種群中適應(yīng)度最差的個(gè)體，其優(yōu)點(diǎn)是在搜索過程中某一代的最優(yōu)個(gè)體可不被遺傳操作所破壞，這樣可以保證遺傳算法以概率收斂到最優(yōu)解。經(jīng)驗(yàn)證明，保留占種群總體25數(shù)量的個(gè)體，效果最為理想7。(2)交叉算子：采用單點(diǎn)交叉法，在兩個(gè)父體上分別隨機(jī)

9、選取一個(gè)交叉點(diǎn)(起點(diǎn)和終點(diǎn)除外)，交換兩個(gè)體在各自交叉點(diǎn)之后的染色體?？紤]到規(guī)劃路徑的長度可變，為了防止交叉操作后出現(xiàn)過于繁瑣或簡單的路徑，對(duì)生成的新個(gè)體長度進(jìn)行限制，即最大長度不能超過Nmax，并且不能產(chǎn)生回路，若不符合要求，重親獲取兩個(gè)父個(gè)體的交叉點(diǎn)。(3)插入算子：設(shè)計(jì)了兩種插入算子，第一種是有針對(duì)性14542009,30(6)計(jì)算機(jī)工程與設(shè)計(jì)ComputerEngineeringandDesign的，即在連線穿過障礙物的兩個(gè)轉(zhuǎn)向點(diǎn)之間插入一個(gè)或多個(gè)轉(zhuǎn)向點(diǎn)，使產(chǎn)生的路徑避開障礙物，如圖2(a)所示，第二種是一般意義上的插入，以一定的概率插入一個(gè)隨機(jī)產(chǎn)生的轉(zhuǎn)向點(diǎn)，如圖2(b)所示。圖2中虛

10、線部分為變異后的路徑1,21(4)擾動(dòng)算子：同樣設(shè)計(jì)了兩種擾動(dòng)算子，第一種只選取路徑不可行的轉(zhuǎn)向點(diǎn)來進(jìn)行小范圍的調(diào)整，使其路徑可行，如圖2(c)所示；第二種是不管路徑是否可行，任意選取一個(gè)位置，以概率pm對(duì)其轉(zhuǎn)向點(diǎn)坐標(biāo)進(jìn)行調(diào)整，在進(jìn)化初期，不可行解數(shù)量較多，調(diào)整的范圍大一些，進(jìn)化后期調(diào)整范圍逐漸縮小，如圖2(d)所示。(5)刪除算子：建立一個(gè)存儲(chǔ)空間REC，在一條路徑中，如果點(diǎn)(xi-1，yi-1)與點(diǎn)(xi，yi)的連線經(jīng)過障礙物，但(xi-1，yi-1)與(xi+1，yi+1)的連線不經(jīng)過障礙物，則將點(diǎn)(xi，yi)添加到REC中。如果REC不為空，則從中隨機(jī)選取一點(diǎn)刪除(如圖2(e)所示

11、)，否則，在路徑中任意選取一個(gè)路徑點(diǎn)以概率pd進(jìn)行刪除，如圖2(f)所示。(6)平滑算子：平滑算子只對(duì)可行路徑中最大的拐角進(jìn)行操作。如圖2(g)所示，刪除拐角(a)(b)(c)圖3各種環(huán)境下的仿真結(jié)果俞駿，劉以安：模糊模式識(shí)別在潛艇威脅等級(jí)判斷中的應(yīng)用表2待識(shí)別對(duì)象*2009,30(6)1457用價(jià)值。,參考文獻(xiàn):1234567崔國桓,于德新.非聲探潛技術(shù)現(xiàn)狀及其對(duì)抗措施J.火力與指揮控制,2007,32(12):10-13.姚敏.計(jì)算機(jī)模糊信息處理技術(shù)M.上海:上?？茖W(xué)技術(shù)文獻(xiàn)出版社,1999.何新貴.模糊知識(shí)處理的理論與技術(shù)M.北京:國防工業(yè)出版社,1998.徐宗本,張講社,鄭亞林.計(jì)算智

12、能中的仿生學(xué):理論與算法M.北京:科學(xué)出版社,2003.王曉君,魏書華.模糊理論在基于特征向量的模式識(shí)別中的應(yīng)用J.計(jì)算機(jī)工程與應(yīng)用,2007,43(10):81-83.龐慶華.基于灰色理論的軟件系統(tǒng)人機(jī)界面綜合評(píng)價(jià)模型J.計(jì)算機(jī)工程,2007,33(18):59-61.YuXueFeng,ChenShouYu.Afuzzydecisionmakingmodelformulti-objectivesystemsanditspropertiesC.HangZhou,China:Proceedingofthe5thWorldCongressonIntelligentControlandAutoma

13、tion,2004:2505-2508.89艾芳菊.基于多維加權(quán)貼近度方法的方案優(yōu)選J.微計(jì)算機(jī)應(yīng)用,2007,28(6):566-570.YoungWhanPark,HyunsungPark,SehunRhee,etal.RealtimeestimationofCO2laserweldqualityforautomotiveindustryJ.OpticsandLaserTechnology,2002,34(2):135-142.LA1A2A3A4A5wjJgF0.08為極度威脅，則在該海域內(nèi)存在潛艇的可能性非常大，應(yīng)該采取相應(yīng)的反潛措施。從實(shí)驗(yàn)可以看出，利用模糊識(shí)別中的擇近原則對(duì)多種探測技

14、術(shù)的特征值進(jìn)行融合計(jì)算，提取最大的貼近度作為輸出，可以有效地提高潛艇探測的精度和效率，從而提高反潛作戰(zhàn)的效率。4結(jié)束語隨著潛艇降噪技術(shù)的發(fā)展，出現(xiàn)了多種非聲探測技術(shù)。針對(duì)單一探測技術(shù)的不準(zhǔn)確性，本文運(yùn)用了模糊模式識(shí)別技術(shù)，將多個(gè)非聲探測技術(shù)的特征值進(jìn)行模糊模式識(shí)別，利用其中的擇近原則選擇貼近度最大的模式作為輸出，有效地克服了單一探測技術(shù)的不確定因素，提高了潛艇探測的準(zhǔn)確性和可靠性。該方法在計(jì)算機(jī)上用Matlab語言進(jìn)行了實(shí)驗(yàn)，計(jì)算結(jié)果令人滿意。該方法豐富了模糊識(shí)別理論，拓寬了其應(yīng)用范圍，對(duì)于現(xiàn)代反潛作戰(zhàn)具有較高的理論參考價(jià)值和工程應(yīng)(上接第1454頁)表1環(huán)境(a)運(yùn)行結(jié)果對(duì)比標(biāo)準(zhǔn)遺傳算法路徑

15、長度進(jìn)化代數(shù)610.3290本文遺傳算法610.3225單，不能完全適應(yīng)種群的變化情況，如何讓算法根據(jù)種群進(jìn)化情況自動(dòng)調(diào)整和優(yōu)化這些參數(shù)，還需進(jìn)一步的研究和改進(jìn)。參考文獻(xiàn):1234劉國棟,謝宏斌,李春光.動(dòng)態(tài)環(huán)境中基于遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃的方法J.機(jī)器人,2003,25(4):327-330.唐國新,陳雄,袁楊.基于改進(jìn)遺傳算法的機(jī)器人路徑規(guī)劃J.計(jì)算機(jī)工程與設(shè)計(jì),2007,28(18):4446-4449.李思海,白存儒.基于遺傳算法的飛行器航跡規(guī)劃研究J.華東交通大學(xué)學(xué)報(bào),2007,24(4):147-150.NoboruN,HideoT.Pathplanningofanagric

16、ulturalmobilerobotbyneuralnetworkandgeneticalgorithmJ.ComputersandElec-tronicsinAgriculture,1997,18:187-204.56陳華華,郭曄,杜歆,等.基于改進(jìn)型遺傳算法的動(dòng)態(tài)避障路徑規(guī)劃方法J.傳感技術(shù)學(xué)報(bào),2006,19(2):520-524.WoonggieH,SeungminB,TaeyongK.GeneticalgorithmbasedpathplanninganddynamicobstacleavoidanceofmobilerobotsC.IEEEInternationalConferenceonComputationalCyberne-ticsandSimulation,1997:2747-2751.78MatBuckland.游戲編程中的人工智能技術(shù)M.吳祖增,沙鷹,譯.北京:清華大學(xué)出版社,2006:110-111.王小平,曹立明.遺傳算法理論、應(yīng)用與軟件實(shí)現(xiàn)M.西安:西安交通大學(xué)出版社,2002:46-47.表2環(huán)境(b)運(yùn)行結(jié)果對(duì)比標(biāo)準(zhǔn)遺傳算法本文遺傳算法860.7340路徑長度進(jìn)化代數(shù)942.25160從表1和表2中可以看出，不管是運(yùn)行時(shí)間還是收斂的路徑長度，本文的算法都要優(yōu)于標(biāo)準(zhǔn)遺