改進(jìn)果蠅優(yōu)化算法及其在月球探測中的應(yīng)用

改進(jìn)果蠅優(yōu)化算法及其在月球探測中的應(yīng)用

1基于改進(jìn)果蠅優(yōu)化算法的球磨算法月亮勘探檢驗器是一種能夠在月亮表面移動、進(jìn)行近距離勘探的探測器，可以有效擴(kuò)大探測范圍。探測巡視器要適應(yīng)探測環(huán)境,需要找到從起始位置到目標(biāo)位置的安全路徑,即進(jìn)行路徑規(guī)劃。路徑規(guī)劃分為基于地圖的全局路徑規(guī)劃和基于傳感器的局部路徑規(guī)劃。路徑規(guī)劃的算法正在不斷的發(fā)展和完善中。文獻(xiàn)將人工勢場的思想引入到蟻群算法中,構(gòu)建并加入了權(quán)重可調(diào)的引力概率函數(shù)作為啟發(fā)因子,使新的算法在較快的收斂速度下仍能得到全局較優(yōu)解;文獻(xiàn)針對粒子群算法在路徑規(guī)劃中易造成不收斂的問題,去掉了速度更新中的速度慣性因子,同時引入經(jīng)典遺傳算法中的變異因子以增強(qiáng)算法的全局尋優(yōu)能力;文獻(xiàn)以多組螞蟻為研究對象,采用最近鄰居搜索策略和趨近導(dǎo)向函數(shù)相互協(xié)作完成全局最優(yōu)路徑的搜索。由此可見,路徑規(guī)劃方法在全局路徑規(guī)劃中已能得到令人滿意的結(jié)果,但在未知環(huán)境中,由于環(huán)境信息的時刻變化,對巡視器的實時性提出了更高的要求,即要求規(guī)劃算法的復(fù)雜度(時間需求、存儲需求等)能滿足月面巡視器的運動需要。用于路徑規(guī)劃的方法很多,群智能算法是其中的一大類,主要有遺傳算法、蟻群算法、魚群算法、免疫算法、粒子群算法,雖然這些算法各有優(yōu)點,但它們共同的不足是實時性不好,不適于解決動態(tài)規(guī)劃問題。果蠅算法也是一種群智能算法,于2011年由Wen-TsaoPan提出,之后部分學(xué)者對其算法尋優(yōu)特性與其他群智能算法進(jìn)行了比較,發(fā)現(xiàn)果蠅算法具有算法簡單、參數(shù)少、易調(diào)節(jié)、計算量小、尋優(yōu)精度高的特點,具有良好的實時性。針對月球探測巡視器動態(tài)路徑規(guī)劃的實時性問題,本文提出基于改進(jìn)果蠅優(yōu)化算法(FruitFlyOptimizationAlgorithm,FOA)的月球探測巡視器路徑規(guī)劃方法,即針對其易于陷入局部最優(yōu)的穩(wěn)定性問題,對FOA的味道濃度判定值進(jìn)行改進(jìn)。同時,考慮到月球探測巡視器在沿規(guī)劃路徑進(jìn)行月面巡視的過程中,有可能遇到未知障礙物的情況,提出了動態(tài)環(huán)境下月球巡視器遇到未知靜態(tài)障礙物的避障策略。2搜索食物foaWen-TsaoPan從果蠅的覓食行為得到啟發(fā),提出了尋求全局優(yōu)化的新方法。果蠅本身在感官知覺上優(yōu)于其他物種,其嗅覺器官能夠很好地搜集漂浮在空氣中的各種氣味,甚至能嗅到40km外的食物源。果蠅飛近食物后亦可使用敏銳的視覺發(fā)現(xiàn)食物與同伴聚集的位置,并往該方向飛去,如圖1所示。依照果蠅搜索食物的特性,可將FOA歸納為以下幾個重要步驟:1)隨機(jī)初始果蠅群體位置X,Y。2)分配果蠅個體利用嗅覺搜尋食物隨機(jī)方向與距離:3)估計果蠅與原點的距離D,再計算味道濃度判定值S,S為距離D的倒數(shù):4)味道濃度判定值代入味道濃度判定函數(shù)(FitnessFunction)以求出該果蠅個體位置味道濃度smell:5)找出果蠅群體中味道濃度最大的果蠅:6)保留最佳味道濃度值與X、Y坐標(biāo),此時果蠅群體利用視覺向該位置飛去:7)進(jìn)入迭代尋優(yōu),重復(fù)步驟2)~5),并判斷味道濃度是否優(yōu)于前一迭代味道濃度,若是則進(jìn)行步驟6)。3路徑長度規(guī)劃如圖2所示,將全局地圖進(jìn)行等柵格大小劃分,I為起始點,G為目標(biāo)點。果蠅以給定的速度沿柵格邊飛行,圖2中粗實線為飛行路徑,P1、P2、P3為路徑導(dǎo)航點,將起點I視為P0,終點G視為P4,則整個路徑長度路徑規(guī)劃問題即是對Pj的位置進(jìn)行優(yōu)化選擇,保證連線PjPj+1不與障礙物相交并使LP最小。4改進(jìn)的算法matlab由上可知,利用FOA進(jìn)行路徑規(guī)劃時,需要對參數(shù)進(jìn)行必要的設(shè)置。考慮到FOA的參數(shù)設(shè)置是導(dǎo)致算法是否會陷入局部最優(yōu)的關(guān)鍵,本文提出基于改進(jìn)參數(shù)設(shè)置方法的改進(jìn)FOA,其對算法的改進(jìn)包括:第一,由于路徑規(guī)劃問題的起始點與目標(biāo)點均是已知的,因而第2節(jié)中步驟1)果蠅群體的初始位置及食物源位置可以設(shè)為是已知的;第二,月球車具有一定的越障能力,步驟2)需要給予果蠅一定的越障能力并設(shè)置允許的行進(jìn)代價值范圍;第三,一般情況下,起始點和目標(biāo)點相距較遠(yuǎn),這樣步驟3)中D的取值范圍會很大,為此當(dāng)計算味道濃度判定值S時,S的取值范圍會很小,因而將其代入味道濃度判定函數(shù)時,很可能引起早熟收斂并陷入局部最優(yōu)。針對此問題,本文提出將D直接代入味道濃度判定函數(shù),計算與目標(biāo)點距離差。因此不需將S代入味道濃度判定函數(shù),從而不易陷入局部最優(yōu),提高了算法的穩(wěn)定性,并可使果蠅群體向已知食物源飛行;第四,步驟2)中果蠅搜索步長明顯會影響算法收斂速度,當(dāng)對實時性要求很高時,可以增大步長,提高收斂速度。綜上,改進(jìn)后的算法Matlab程序步驟如下:2)分配果蠅個體利用嗅覺搜尋食物隨機(jī)方向與距離,并去除邊界點和沒有移動的果蠅,賦予果蠅避障能力。end其中,X(i)>100‖X(i)<1、Y(i)>100‖Y(i)<1為超過地圖邊界的點(地圖大小100×100個柵格);score(X(i),Y(i))>40衡量果蠅的越障能力,即行進(jìn)代價值大于40的柵格果蠅無法飛行。3)估計果蠅與原點的距離。4)代入味道濃度判定函數(shù)(FitnessFunction)以求出該果蠅個體位置味道濃度smell:smell(i)=140.0071-D(i)其中,140.0071是起始點與食物源的距離。5)找出果蠅群體中味道濃度最小的果蠅:[bestsmellbestindex]=min(smell)。7)進(jìn)入迭代尋優(yōu),重復(fù)步驟2)~5),并判斷味道濃度是否優(yōu)于前一迭代味道濃度,若是則進(jìn)行步驟6)。終止條件為搜索一定迭代次數(shù)的果蠅,本文設(shè)迭代次數(shù)500,種群規(guī)模200。5未發(fā)現(xiàn)大型有機(jī)械環(huán)境,導(dǎo)致路徑規(guī)劃路徑無線性化如果月球環(huán)境中存在全局地圖上沒有表示的未知靜態(tài)障礙物,巡視器在之前規(guī)劃出的全局路徑上行走時,需要用傳感器探測其視野內(nèi)的環(huán)境信息,提取出存在的未知靜態(tài)障礙物的位置信息。設(shè)L為全局路徑規(guī)劃的路徑坐標(biāo)集合,t時刻探測到障礙物,提取的障礙物坐標(biāo)集合為X,若X∩L≠?表示原規(guī)劃路徑(圖2中實折線)上出現(xiàn)了未知障礙物。未知障礙物避障策略如圖3所示。避障策略為:測出障礙物與全局路徑在行進(jìn)方向上第一個交點為P1;確定障礙物左右端點位置,選擇距離當(dāng)前位置更近的端點為避障路徑端點P2,做P2與L中P1點之后路徑坐標(biāo)點P3的連線,使得P2P3與原全局地圖的已知障礙物(圖3中灰色矩形)邊沿出現(xiàn)交點。PP2P3即為避障路徑,選擇避障路徑時距離障礙物可留有一定余量。6模擬與分析6.1月面數(shù)字地形的建立月球表面總體上可以分為月海和高地兩大地理單元,分布有大小不一的巖石和撞擊坑。根據(jù)以往獲得的月面地形信息,擬合得到其數(shù)學(xué)模型。本文以平緩月海為例建立月面數(shù)字地形(見圖4),綜合巡視器工作能力和體積水平,確定研究區(qū)域為100m×100m。然后分析其可通行性,得到可通行性代價地圖。6.2pso算法仿真由表1可以看出,果蠅優(yōu)化算法和粒子群優(yōu)化算法是尋優(yōu)性能較為相近且實時性較好的群智能算法,因此,將兩者進(jìn)行對比分析,尋找更適合月球車路徑規(guī)劃的算法。(1)FOA路徑規(guī)劃利用FOA優(yōu)化算法進(jìn)行仿真時,設(shè)定初始位置(1,1,0),目標(biāo)點(100,100,0),種群規(guī)模200,迭代次數(shù)500。規(guī)劃路徑結(jié)果如圖5(a)所示,迭代次數(shù)如圖5(b)所示。運算時間為3.39s。(2)PSO算法路徑規(guī)劃PSO是基于粒子群的算法,它是將速度慣性因子ω設(shè)置為0,c1=1,c2=2,vjmax=0.1×(Δdjmax-Δdjmin),同時為了防止路徑搜索到局部最優(yōu),在種群中取5%的比例粒子反方向搜索,并設(shè)定相同的初始位置(1,1,0),目標(biāo)點(100,100,0),種群規(guī)模200,迭代次數(shù)500,賦予相同的越障能力。規(guī)劃路徑結(jié)果如圖6(a)所示,迭代次數(shù)如圖6(b)所示。運算時間為5.71s。(3)結(jié)果分析FOA和PSO路徑規(guī)劃仿真結(jié)果對比如表2所示。當(dāng)種群數(shù)目、越障能力、步長等初始條件相同時,FOA比PSO算法運算時間更短,迭代次數(shù)更少,說明FOA具有更好的實時性;且仿真過程中,FOA沒有陷入局部最優(yōu),滿足月球車路徑規(guī)劃穩(wěn)定性的要求。6.3不同步長的仿真結(jié)果第4節(jié)中改進(jìn)后的算法步驟2)中,X(i)=X+round(2*h*rand()-1*h),Y(i)=Y+round(2*h*rand()-1*h),h是步長。圖5是h=1的仿真結(jié)果,圖7是改變步長為h=3的仿真結(jié)果。運算時間為2.31s。由此可見,當(dāng)對于實時性要求很高時,可以增大步長,提高收斂速度。從圖7(b)可以看出,增大步長后收斂速度更快,迭代次數(shù)更少,但圖5(a)中規(guī)劃路徑長度157.9327m,圖7(a)中規(guī)劃路徑長度165.7503m,改變步長規(guī)劃出的路徑?jīng)]有原路徑短、光滑。6.4單位和義和單位躲避未知障礙物的放大仿真結(jié)果如圖8所示,坐標(biāo)軸定義和單位與圖7(a)相同。傳感器發(fā)現(xiàn)全局路徑L被未知障礙物阻斷,運用避障策略得到避障路徑(圖7中繞過山峰的路徑),之后沿著原有路徑繼續(xù)前進(jìn)。7仿真結(jié)果與分析考慮到目前群智能算法搜索速度慢及易于陷入局部最優(yōu)的問題,結(jié)合探測任務(wù)對路徑規(guī)劃的實時性提出的更高要求。本文提出一種基于改進(jìn)FOA的月球巡視器動態(tài)路徑規(guī)劃方法,并將改進(jìn)FOA與粒子群優(yōu)化算法的路徑規(guī)劃尋優(yōu)特性進(jìn)行了仿真對比分析。仿真結(jié)果表明,改進(jìn)的FOA能快速找到最優(yōu)解,