數(shù)學建模競賽優(yōu)秀選2004-2019年

題 智能飛行器航跡規(guī)劃模 要利用搜索算法和遺傳算法求解出最優(yōu)的智能飛行器航行軌跡方案。最短原則，使用貪心算法初始化解，再使用搜索算法，優(yōu)化初始解，在120次迭代后得到較優(yōu)解，運行時間為70.64s，改善情況為6.55%1求解出的最佳航行軌跡方案為：A→503→69→237→115→338→457→555→436→B，經(jīng)過誤差校正點數(shù)8個，航案為：A→163→114→8→309→305→123→45→160→92→93→61→292→B，經(jīng)過誤差校該算法針對兩組數(shù)據(jù)最優(yōu)解的點數(shù)均為最優(yōu)AB直線距離增加4.41%和6.11%，驗證了算法的有效性。考Dubins從A到B的向過，設計了飛行器轉向約束，根據(jù)優(yōu)先級盡可能短的航跡長度>盡可能少的誤差校正點，在此基礎上改進問題一的雙目標優(yōu)化模型，建立了帶多約束條件的航跡長度最小化和誤差校正點數(shù)最小化的雙目標優(yōu)化模型規(guī)范函數(shù)進行無量綱化處理并通過線性法將該模型轉化為單目標優(yōu)化模型貪心算法集中和分散機制，出用改進搜索算法優(yōu)化初解一定度解了搜算法優(yōu)問存的，步搜法索量斂在120次迭代后得到較優(yōu)解，運行時間為74.41，改善情況為6.79%1求解出的最佳航行軌跡方案為：→503→69→237→233→598→561→448→485→，經(jīng)過誤差校正點數(shù)8個，航跡長度為104960m，比AB直線距離增加了4.47%，比問題一最優(yōu)方案距離增加了0.02%；對數(shù)據(jù)集2求解出的最佳航行軌跡方案為：A→163→114→8→309→305→123→45→160→92→93→61→292→B，經(jīng)過誤差校正點數(shù)12個，航跡長度為10941mB.18%0.06%時間復雜度低于O(n2)。本文通過深度優(yōu)先搜索策略進行遍歷，驗證兩組數(shù)據(jù)最優(yōu)解的校812該算法針對兩組數(shù)據(jù)最優(yōu)解的點數(shù)均為最優(yōu)B4.47%6.18%0.02%.6%，驗證了算法的有效性。針對問題三，由于無法確保智能飛行器能夠成功抵達目的地，因此需盡量降低失敗概率，同時使航跡長度盡可能小，經(jīng)過的校正點個數(shù)盡可能少。為此本文考慮了飛行器成功到達目的地的多種約束條件，建立了帶多約束條件概率最小化、航跡長度最小化和誤差校正點數(shù)最小化的多目標優(yōu)化模型規(guī)范函數(shù)進行無量綱化處理并通線性法將該模型轉化為單目標模型，再使貪心算法求解初始化解，將搜索算法與遺傳算法結合，提出并使用遺傳混合搜索算法優(yōu)化初始解在120次迭代后得到較優(yōu)解，運行時間為87.86，改善情況為6.13%。對數(shù)據(jù)集1求解出的最佳航行軌跡方案為：57→1→8→3767→319→504848→0→62→B，經(jīng)過誤差校正點數(shù)12個，航跡長度為108439m，比AB直線距離增加了7.93%，成功抵達終點概率100%；對數(shù)據(jù)集2求解出的最佳航行軌跡方案為：A→169→322→100→→B，經(jīng)過誤差校正點數(shù)19個，航跡長度為147271m，比AB直線距離增加了42.91%，成功抵達終點概率65.01%。該算法時間復雜度T(n)O(n4/)（為種群數(shù)量）。本文通過深度優(yōu)先搜索策略進行遍歷，驗證1219，該算法針對兩組數(shù)據(jù)最優(yōu)解的點數(shù)均為最優(yōu)AB7.93%和 問題重 問題背 需要解決的問 問題分 問題一分 問題二分 問題三分 模型假 符號說 問題一：模型建立與求 模型建 模型求 雙目標轉化為單目 基于單目標規(guī)劃的搜索算 求解結果及分 模型評 算法的有效性和復雜 靈敏度分 問題二：模型建立與求 模型建 模型求 雙目標轉化為單目 基于單目標規(guī)劃的改進型搜索算 求解結果及分 模型評 算法的有效性和復雜 靈敏度分 問題三：模型建立與求 模型建 模型求 多目標轉化為單目 基于單目標規(guī)劃的遺傳搜索算 求解結果及分 模型評 算法的有效性和復雜 靈敏度分 模型的評 模型的優(yōu) 模型的缺 參考文 附 問題重問題背景中，在和民用領域的使用上都得到了顯著增加[1]。智能飛行器的飛行航線快速規(guī)劃在航行任務策劃中起著作用，其目的是確定由出發(fā)地到目的地的最優(yōu)航線。由于智能飛前提下，例如圖1所示的智能飛行器航行規(guī)劃區(qū)域，研究了如何自動快速計算得到智能飛其垂直定位誤差和水平定位誤差分別增加一個單位。只有在保證飛行器到達目的地時，即時的垂直定位誤差和水平定位誤差都小于個單位的條件下，進行航線規(guī)劃。為滿足限制條件1，需對飛行器的垂直定位誤差和水平定位誤差進行垂直和水平的校位誤差和水平定位誤差的（即校正），從而在實時校正的同時進行航線規(guī)劃。垂直校正條件：垂直定位誤差小于1，水平定位誤差小于21，水平定位誤差小于2飛行器轉彎時所能達到的最小半徑為200m需要解決的問題在本文中，我們需要根據(jù)附1和附2所給數(shù)據(jù)集結合上述限制條件建立一個從出發(fā)模型結合1和附2所給的兩個數(shù)據(jù)集，設計算法分別規(guī)劃出各自條件下的飛行器航行一問的基礎上，同時考慮限制條件（8）問題分基礎上，進一步將飛行器的路線進行平滑和優(yōu)化。為解決該問題，一般用到的算法有A*算法、Dijkstra算法、粒子群算法、遺傳算法等[2~5]。這些算法各有優(yōu)劣，有些傳統(tǒng)算法得制條件具體分析，考慮了多種約束條件，采用了搜索算法和遺傳算法，針對實際應用問題一分析前提：1，滿足垂直校正條件下的最大垂直定位誤差125，最大水平定位誤差225；滿足水平校正條件下的最大垂直定位120，最大水平定位誤差225B點時，垂直定位誤差和水平定位誤差都小于30；單位飛行距離下，垂直定位誤差和水平定位誤差所增加的單位定位誤差0.001。針對附件2，滿足垂直校正條件下的最大垂直定位誤差120，最大水平定位誤差210115220B點時，垂直定位誤差和水平定位誤差都小于20；單位飛行距離下，垂直定位誤差和水平定位誤差所增加的單位定位誤差0.001。條件：根據(jù)上述問題背景，按照（1）~（7）12所提問題二分析前提：1，滿足垂直校正條件下的最大垂直定位誤差125，最大水平定位誤差225120，最大水平定位誤差225B垂直定位誤差和水平定位誤差都小于30；單位飛行距離下，垂直定位誤差和水平定位誤差120，最大水平定位誤差210；滿足水平校正條件下的最大垂直定位誤差115，最大水平定位誤差220；到達目的地B點時，垂直定位誤差和水平定位誤差都小于 20；單位飛行距離下，垂直定位誤差和水平定位誤差所增加的單位定位誤0.001條件：根據(jù)問題背景，按照（1）~（8）12所提供的數(shù)據(jù)分別進行航線規(guī)劃。與問題一不同的是，問題二是在額外考慮限制條件（8）的前提下進行模型的建立。限制條件（8）涉及了三維飛行空間中的轉彎問題，由于飛行器轉彎（1）（7）限制條件下實時定位誤差校正約束。問題三分析前提：1，滿足垂直校正條件下的最大垂直定位誤差125，最大水平定位誤差225120，最大水平定位誤差225B垂直定位誤差和水平定位誤差都小于30；單位飛行距離下，垂直定位誤差和水平定位誤差120，最大水平定位誤差210；滿足水平校正條件下的最大垂直定位誤差115，最大水平定位誤差220B點時，垂直定位誤差和水平定位誤差都小于200.001正點后，定位誤差取原誤差（校正前）和5的較小值。條件：根據(jù)問題背景，與問題相同，按照（1）~（7）限制條件的要求對附件并且使得所規(guī)劃的航跡到達目的地的校正成功概率最大化，由此建立多目標航跡規(guī)劃函數(shù)。模型假符號說符 符號說 P(x,y,

i點與j點的歐氏距離Ph(x,y 距飛行器當前位置最近的水平校正點坐Pv(x,y 距飛行器當前位置最近的垂直校正點坐 i段飛行器正常飛行（無需校正） 變 問題一：模型建立與求模型建立短航跡-少校正次數(shù)雙目標規(guī)劃模型優(yōu)化目標：（1）飛行器從出發(fā)地A航行至目的地B的航線距離盡可能短；（2）經(jīng)過校Distance，即飛行器從出發(fā)地A航行至終點B所經(jīng)過的總路程；定義經(jīng)過校正區(qū)域進行校正的次數(shù)Times。minz2

(5-(5-終點）j xij 同時，使用向量x[x(1x(2x(k)...]記錄每一次的決策，其中x(k)表示第k N xiji0jNTimesi0j其中dijij

(5-約束條件：（1）飛行器垂直校正條件：垂直定位誤差v小于1，水平定位誤差h于2；（2）飛行器水平校正條件：垂直定位誤差v1，水平定位誤差h小于2；（3）飛行器到達目的地前，垂直誤差和水平誤差都應小于。在探討約束條件前，定義校正器類型變量Ti

第i個校正點是垂直校正點

(5-兩種情況的約束條件匯總如下表5-1：情到達校正點時的誤差約束條件hd0jx0hvd0jx0vhd0jx0hvd0jx0vk (1T)0 0 d0jx0j(1Ti) T 0 0 d0jx0jTi校正點。兩種情況的約束條件匯總如下表5-2：情到達校正點時的誤差約束條件上一次經(jīng)過d(k)x(k) h2水平校正點d(k)x(k)d(k1)x(k1) v選擇水平校正點d(k)x(k)d(k1)x(k1) h2上一次經(jīng)過垂直校正點d(k)x(k) v上一次經(jīng)過d(k)x(k)d(k1)x(k1) h2選擇垂直水平校正點d(k)x(k) v校正點上一次經(jīng)過d(k)x(k) h2垂直校正點d(k)x(k)d(k1)x(k1) v

k k k kxij(1Ti)+ Tidkxk(1T)+dk1xk1(1T)

ijk

(5-

xijTi Ti 1，這樣可以確保每個校正點最多經(jīng)過一 其次需要約束起點到終點是一條通路。本文使用向量x[x(1),x(2),...x(k)...] 的點x(k)(i,j)縱坐標與第k+1次選擇的點x(k)(i,j)橫坐標相等，即j kj

xijjkiki,j0,1,2,...N

(5-Nminz1Distancexiji0jNminz2Timesi0jk (1T) 0j 0j Ti) T 0j 0j Ti) T 0 0 d0jx0jTik dkxk(1T)+dk1xk dkxk(1T)+dk1xk1(1T) k k k k

xijTi TidkxkTdk1xk1(1T) xij j jkiki,j0,1,2,...N1,2,1,2,,dkikjk模型求解雙目標轉化為單目在本問題由最小化航跡變量Distance和最小化經(jīng)過矯正區(qū)域進行校正的次數(shù)建立了兩個目標函數(shù)，選取兩個值0i1(i1,2)，作為這兩個目標的線 系數(shù)，22且i1 z1min z2min maxzmin maxzmin 100，zminz1

(1z2z) min

(1z2z) k (1T) 0j 0j Ti) T 0j 0j Ti) T 0 0 d0jx0jTik dkxk(1T)+dk1xk1 ii

k

k

k1

k

xijTi Ti1 dkxkTdk1xk1(1T) xij j jkiki,j0,1,2,...N1,2,1,2,,dkikjk基于單目標規(guī)劃的搜索算陷入局部最優(yōu)，搜索算法采用了一種靈活的技術，其基本思想是在搜索過程中將近期的歷史搜索存放在表中，防止算法重復搜索，即之前搜索過的區(qū)域不會在迂回搜隨著迭代的不斷進行，表將不斷進行更新，當?shù)?jīng)過一定的次數(shù)之后，原先進入表的移動便會從表中移除。解的編碼與更新是如何編碼與更新的，這里設N6，即總誤差校正點數(shù)量為6，如圖5-1所示。編號 編號 編號 編號 編號 編號5-1進行誤差校正），i候選集的構造

i,k(jki10個距離目標誤差校正點 如圖5-2所示候選集產(chǎn)生算法Step3：選取前10個距目標誤差校正點最近的誤差校正點Step5：將可插入分量集合記為候選集，選擇時按選擇法進行選擇始始垂水Y按Y按束搜其基本思想是在搜索過程中將近期的歷史搜索存放在表中，防止算法重復搜索，循環(huán)和局部最優(yōu)解。其時表的管理，表分為對象和長度。其中，對象是導致解變化的重要因素。在本問題中，移動作為對象。在期內i,

i,k(jk)和i,ki,j(jk)都將被 如圖5-3所示：

（N為誤差校正點的數(shù)量）表示表長度。該算法nnnN更新T圖5-3搜索算法流初始化解N（N為誤差校正點的數(shù)量）的該集合中選出離B點最近的點作為目的地，并將對應的編號標記為1同時將該點作為出發(fā)點。反復進行上述操作直到無人機可以直接飛到B點。具體流程如下，該流如圖5-4貪心算法Step1：將A點作為出發(fā)Step3：從該集合中選出離B點最近的點，作為目的地；返回Step2。是是否5-4目標解的迭代5-37~888求解結果及分析（1）航跡規(guī)劃和誤差校正點數(shù)A50369237155338457555436B，航跡長度為 1000100010001000B5-513D行軌跡沿著AB方向上下穿梭，安排較為合理，航行軌跡長度為算法最優(yōu)解，航跡長度增加了4.41%。分數(shù)據(jù)集1其他解果，參考下表5-5：校正點個數(shù)航跡路徑航跡長度7無無895-55-7可以觀察到，在我們選取的部分結果中，校正點個數(shù)為7個時，無法從這個角度說明本文求解出的8個校正點，航跡長度104898m為算法的最優(yōu)解。A163114830930512345160929361292B，航跡長度為109342m，誤差校正點12點。 0010800100010001000100010B5-823D結合數(shù)據(jù)表5-6，由上柱狀圖表5-9可以直觀地看出，飛行器到達垂直校正點時，垂直誤航行軌跡沿著AB方向上下穿梭，安排較為合理，航行軌跡長度為算法最優(yōu)解，航跡長度109342m，僅使用12個誤差校正點，AB直線距離為103045m，航跡長度僅比AB直線距離增加了6.11%。分數(shù)據(jù)集2其他解果，參考下表5-7：校正點個數(shù)航跡路徑航跡長度無無5-105-75-10可以觀察到，在我們選取的部分結果中，校正點個數(shù)為11個時，無可以從這個角度說明本文求解出的12個校正點，航跡長度109342m為算法的最優(yōu)解。模型評估算法的有效性和復雜度雙目標規(guī)劃問題的最主要特點是各個目標間的性和不可度量性。目標間的性心算法來獲取較好的初始解，這大大減少了算法后續(xù)尋找最優(yōu)解的時間。同時搜索算最優(yōu)解，從而實現(xiàn)全局優(yōu)化。結果表明搜索算法在飛行器航跡規(guī)劃這一NP-hard的求正點數(shù)也會比我們的多；比這個校正點數(shù)少的，距離肯定大于該算法求出的路徑。搜索算法各操作時間復雜度見下表5-4：表5-4搜索算法各操作時間復雜kkn判斷nl（n為問題規(guī)模，l為表長度解除搜索算法時間復雜度為O(Max_GEN(n2nl，在程序運行過程中，找到最優(yōu)解的時間數(shù)據(jù)集166.78s，數(shù)據(jù)集254.23s。靈敏度分析本文在設計算法時，引入了一個全局搜索常量k，用于在當前時間搜索距離飛行器當kkk的值甚至出現(xiàn)“繞圈”的情況。因此，本文設計了對算法中k值的靈敏度分析，盡可能選取一個合適的k值，使結果趨向最優(yōu)解。k10k10時，航跡長度開始增大。 再分析數(shù)2：如下5-11和下5-12所示，可以觀察到，當k5時，航跡長度k10時，航跡長度在整體上最??；當k10時，航跡長度開始增大。 k取值偏小時，航跡路徑規(guī)劃不合理，會漏掉較多優(yōu)良的校正點，航跡長度顯著偏大；當k取值在10附近時，則不會遺漏附近優(yōu)良的校正點，航跡路徑規(guī)劃合問題二：模型建立與求模型建立短航跡-少校正次數(shù)-圓弧式轉向雙目標規(guī)劃模型優(yōu)化目標：（1）飛行器從出發(fā)地A航行至目的地B的航線距離盡可能短；（2）經(jīng)過校Distance，即飛行器從出發(fā)地A航行至終點B所經(jīng)過的總路程；定義經(jīng)過校正區(qū)域進行校正的次數(shù)Times。minz3minz4

(6-(6-終點）j xij 同時，使用向量x[x(1x(2x(k)...]記錄每一次的決策，其中x(k)表示第k N xiji0jNTimesi0j其中dijij

(6-約束條件：（1）飛行器垂直校正條件：垂直定位誤差v小于1，水平定位誤差h小轉彎半徑為200米。Dubins曲線是在滿足曲率約束和規(guī)定起點、終點的速度方向（切線）的條件下，連接初速度vSE時以速度vE駛離，DubinsSE情況 情況情況

情況DD 起點S終點D空間位置S器飛行方向始終是前進的（飛行方向與位置至終點方向夾角小于90度），因此設定每次進行轉向的弧度小于（不會向后飛行）6-4所示： 垂直X-Y坐標軸。飛行器首先需要在X-Y平面上轉向至D點在X-Y方向的投影點，然后D在空間種不同的位置情況，PT1，T1T2T2

PD與v共線，則飛行器不需要轉向，因此PT1T1T2PD與v共面，則飛行器僅需要完成一次轉向，因此T1T2為PD與vT2D0一般而言飛行器在三中從第i校正點飛行至第j校正點，其飛行路程總是可以用兩段圓弧和一段直線來描述。因此可以將dij表述為：dijl1l2

(6-l1l2PT1，T1T2所代表的圓弧，y表

分析完轉向情況，在探討約束條件前，定義校正器類型變量Ti Ti 兩種情況的約束條件匯總如下表6-1：情到達校正點時的誤差約束條件hd0jx0hvd0jx0vhd0jx0hvd0jx0vk (1T)0 0 d0jx0j(1Ti) T 0 0 d0jx0jTi校正點。兩種情況的約束條件匯總如下表6-2：情到達校正點時的誤差約束條件上一次經(jīng)過水d(k)x(k) h2平校正點d(k)x(k)d(k1)x(k1) v選擇水平校正點d(k)x(k)d(k1)x(k1) h2上一次經(jīng)過垂直校正點d(k)x(k) v上一次經(jīng)過水d(k)x(k)d(k1)x(k1) h2選擇垂直平校正點d(k)x(k) v校正點上一次經(jīng)過垂d(k)x(k) h2直校正點d(k)x(k)d(k1)x(k1) v

k k k ki i

(1T)+

Tidkxk(1T)+dk1xk1(1T)

ijk

xijTi Ti 6-5 其次需要約束起點到終點是一條通路。本文使用向量x[x(1),x(2),...x(k)...]記 的點x(k)(i,j)縱坐標與第k+1次選擇的點x(k)(i,j)橫坐標相等，即j kj

xijjkiki,j0,1,2,...N

(6-Nminz1Distancexiji0jNminz2Timesi0jk (1T) 0j 0j Ti) Td 0j 0j Ti) T 0 0 d0jx0jTik dkxk(1T)+dk1 dkxk(1T)+dk1xk1(1T)

k k k k

xijTi TidkxkTdk1xk1(1T) xij j jkiki,j0,1,2,...N,,,,, dklklk 模型求解雙目標轉化為單目在本問題由最小化航跡變量Distance和最小化經(jīng)過矯正區(qū)域進行校正的次數(shù)建立了兩個目標函數(shù)，選取兩個值0i1(i1,2)，作為這兩個目標的線性22量綱化處理。此時目標函數(shù)分別通過函數(shù)z3minz3，z4minz4 maxzmin maxzmin 100，這樣k

minz(1z2z)z zzminz(1z2z)z

(6- (1T) 0j 0j Ti) Td0 0j 0j Ti) T 0 0 d0jx0jTik dkxk(1T)+dk1xk dkxk(1T)+dk1xk1(1T)ii

k

k

k

ijk

(6-

xijTi Ti1dkxkTdk1xk1(1T) xij j jkiki,j0,1,2,...N,,,,, dklklk 基于單目標規(guī)劃的改進型搜索算藐視準則在搜索算法中，可能會出現(xiàn)候選集全部被，或者存在一個優(yōu)于“bestsofar”狀態(tài)的候選解，此時可以通過準則將某些狀態(tài)解禁來實現(xiàn)更高效率的優(yōu)化?；谀繕撕瘮?shù)值的原則：某個候選解的目標函數(shù)值優(yōu)于“bestsofar”則解禁當前狀態(tài)和新的“bestsofar”狀態(tài)。前該對象對應的候選集的目標函數(shù)值優(yōu)于當前解，則對其解禁。在本問題中，我們選擇基于目標函數(shù)值的準則，除此之外，我們還引入了另外的法則：如果一個互換操作在相當長的一段時間內沒有被選中，那么不管它當前的屬性改進長長度是算法中的一個關鍵因素：如果長度值取小了，則在搜索過程中容易出現(xiàn)重復搜索；如果長度值太大，又可能會一些有益的移動操作，導致求解質 改進搜索算法（ImprovedTabuSearch,

n,1.1n（n為誤差校正與其他啟發(fā)式算法類似，搜索算法在求解優(yōu)化問題時，存在著，即所求為了進一步提高搜索算法的搜索質量和收斂速度，引入了集中和和分散機制，提出了一種改進搜索算法(ITS)。ITS的主要思想是，當搜索過程停滯時，及時對保留的局部優(yōu)化解中的優(yōu)良（成為精英）進行重組，構造出新的可行解，在此基礎上再開展進一步搜索。具體而言，ITS由集中搜索和精英重組兩個步驟經(jīng)過多次迭代完成。在集中搜索階段，采用問題一的搜索算法，實現(xiàn)對重點區(qū)域的集中搜索；在精英重組階段，開開體解的優(yōu)劣程度排序。在主循環(huán)的每一次迭代中，集中搜索輸出集中優(yōu)化結果 ，并根1更新EQ。若EQ中 數(shù)已達到s，只有當1優(yōu)于隊尾 EQ[s]時，才用1替EQ[s]，并對EQ重新排序集中搜索集中搜索采用問題一 搜索算法， 長度在區(qū)間0.9n,1.1n（n為誤差精英重組個已有的可行解（ ）中通過重組產(chǎn)生一個新的可行解。在交叉過程中， 的目標解的迭代9~888求解結果及分析 10001000100000B6-713D6-46-10可以直觀地看出，飛行器到達垂直校正點時，垂AB方向上下穿梭，安排較為合理，航行軌跡長度為算法最優(yōu)解，航跡跡長度（折線，104935m）0.02%8個誤差校正點，AB直線距離為100465m，航跡長度僅比AB直線距離增加了4.47%。109342m，航跡長度（添加轉彎半徑約束后）109411m0.06%；同時，僅經(jīng)過12個誤差校正點。 0010800100010001000100010B6-923D6-56-10可以直觀地看出，飛行器到達垂直校正點時，垂AB方向上下穿梭，安排較為合理，航行軌跡長度為算法最優(yōu)解，航跡跡長度（折線，109342m）0.06%12個誤差校正點，AB直線距離為103045m，航跡長度僅比AB直線距離增加了6.17%。模型評估算法的有效性和復雜度引入線性系數(shù)，使復雜的多目標規(guī)劃模型求解轉換為單目標規(guī)劃模型，極大降低了問題的求解難度。該算法在問題一算法的基礎上加入了藐視準則，使一些區(qū)域中的一些進了長度，使長度的設置更加合理；引入了集中和分散機制，提出了一種改進禁忌搜索算法（ITS），一定程度上解決了搜索算法在求解優(yōu)化問題時存在著的停滯現(xiàn)象，進一步提高了搜索算法的搜索質量和收斂速度。結果表明改進搜索算法在飛改進搜索算法的時間復雜度低于O(Max_GEN(n2nl))，在程序運行過程中，找到最優(yōu)解的時間數(shù)據(jù)集163.69s，數(shù)據(jù)集250.42s。靈敏度分析并使用改進搜索算法優(yōu)化初始解。在設計算法時，引入精英隊列長度s參數(shù)。精英隊列EQ的長度為s，長度太小會導致解集太小，不利于跳出發(fā)生的搜索區(qū)域；長度太大會導致程序占用的內存較大，運行時間較長，容易引起內部，不利于算法收斂。因s能夠盡可能提升算法的收斂性能和有效性。故對進行精英隊列長度s靈敏度分析。分別取s[10,15,20,25,30,35,40]，設置迭代次數(shù)為60，通過改進搜索算法得出目迭代次 s取 目標函數(shù) 運行時s取值過大，雖然目標函數(shù)整體較小，但時間開銷較大；若s取值過校，時間開銷大，但目標函數(shù)收斂性能較差。因此，本文選定s取值為25。問題三：模型建立與求模型建立低失敗概率-短航跡-少校正次數(shù)多目標規(guī)劃模型優(yōu)化目標：（1）AB的成功概率盡可能大，即可轉化pDistance，即飛行器從出發(fā)地A航行至終點B所經(jīng)過的總路程；定義經(jīng)過矯正區(qū)域進行校正的次數(shù)minz5pminz7Times

(7-(7-(7-終點）j xij 同時，使用向量x[x(1x(2x(k)...]記錄每一次的決策，其中x(k)表示第k N xiji0jNTimesi0j其中dijij

(7-約束條件：（1）飛行器垂直校正條件：垂直定位誤差v小于1，水平定位誤差h小在探討約束條件前，定義校正器類型變量TiT

(7-定義理想校正器判別變量

Qi

兩種情況的約束條件匯總如下表7-1：情到達校正點時的誤差約束條件hd0jx0hvd0jx0vhd0jx0hvd0jx0vk (1T)0 0 d0jx0j(1Ti) T 0 0 d0jx0jTiik>1時，會選擇一個合適的水平校正點或垂直校7-2和表7-3：情到達校正點時的誤差約束條件d(k)x(k) h2d(k)x(k)d(k1)x(k1) vd(k)x(k)d(k1)x(k1) h2d(k)x(k) vd(k)x(k)d(k1)x(k1) h2d(k)x(k) vd(k)x(k) h2d(k)x(k)d(k1)x(k1) v情到達校正點時的誤差約束條件d(k)x(k) h2d(k)x(k)d(k1)x(k1) v點d(k)x(k)d(k1)x(k1) h2d(k)x(k) v點hd(k)x(k)d(k1)x(k1) h2d(k)x(k) vd(k)x(k) h2vd(k)x(k)d(k1)x(k1) v點k 1Qdkxk(1T)+dk1xk1TQdkxk(1T)+dk 1Qdkxk(1T)+dk1xk1(1T)Qdkxk(1T)+dk1xk1(1T)+5

T

1QdkxkTdk1xk1(1T)QdkxkTdk1xk1(1T)+5 (7- 其次需要約束起點到終點是一條通路。本文使用向量x[x(1),x(2),...x(k)...]記 的點x(k)(i,j)縱坐標與第k+1次選擇的點x(k)(i,j)橫坐標相等，即j kj

xijjkiki,j0,1,2,...N

(7-可能出現(xiàn)校正失敗的情況，其分布律如下表7-1：7-1 設 變量i

(7-7-4各種情況i校驗失敗點類型后續(xù)校驗點安排順序到達下一個同類校驗點時的誤差條id(k)x(k) d(k)x(k)d(k1)x(kd(k)x(k)d(k1)x(k1) d(k)x(k) hd(k)x(k)d(k1)x(k1) d(k)x(k) d(k)x(k) vd(k)x(k)d(k1)x(k1) 0 k 1Qdkxk(1T)+dk1xk1TQdkxk(1T)+dk1xk1T5 i 1Qdkxk(1T)+dk1xk1(1T)Qdkxk(1T)+dk1xk1(1T)+5i1 1QdkxkT TQ T T5

1QidijxijTi (1Ti)QidijxijTi (1Ti)+52(7-校正成 校正失

(1ps)(1i p1(1p)(1n11

(7- k

x(1T)

minz5Nminz6Distancexiji0jNminz7Timesi0j0j 0j i) T0j 0j i) T 0 0 d0jx0jTi k 1Qdkxk(1T)+dk1xk1TQdkxk(1T)+dk1xk1T5 1Qdkxk(1T)+dk1xk1(1T)Qdkxk(1T)+dk1xk1(1T)+5

ijk

k k k k1QidijxijTi TiQidijxijTi T5i1QdkxkTdk1xk1(1T)QdkxkTdk1xk1(1T)+5

xij

jiki,j0,1,2,...N1,2,1,2,k

kk

i p11(1ps)(1i

k 1Qdkxk(1T)+dk1xk1TQdkxk(1T)+dk1xk1T5 i 1Qdkxk(1T)+dk1xk1(1T)Qdkxk(1T)+dk1xk1(1T)+5 1 k k k k k k k k 1Qi

xijTi TiQidijxijTi T5i 1QdkxkTdk1xk1(1T)QdkxkTdk1xk1(1T)+5 (7-模型求解多目標轉化為單目Times建立了三個目標函數(shù)，選取三個值0i1(i1,2,3)目標的線 系數(shù)，并且i1。由于本問題中三個目標函數(shù)的量綱不同，因此需i歸一化目標函數(shù)，對其進行無量綱化處理。此時目標函數(shù)分別通過函數(shù)z6min ， z7min 567 maxz6min maxz7min67100，這樣迭代時zminz(1p2z+3z)z

(7-kdx(1T)0j 0j i) T0j 0j i) T 0 0 k

minz(1p2z+3z)z z 1Qdkxk(1T)+dk1xk1TQdkxk(1T)+dk 1Qdkxk(1T)+dk1xk1(1T)Qdkxk(1T)+dk1xk1(1T)+5

ik1

k1

k1Qi

k k kxijTi TiQidijxijTi T5i1QdkxkTdk1xk1(1T)QdkxkTdk1xk1(1T)+5

xij

iki,j0,1,2,...N1,2,1,2,dijkikjk p11(1ps)(1i

k 1Qdkxk(1T)+dk1xk1TQdkxk(1T)+dk1xk1T5 i 1Qdkxk(1T)+dk1xk1(1T)Qdkxk(1T)+dk1xk1(1T)+5 1 k k k k k k k k 1Qi

xijTi TiQidijxijTi T5i 1QdkxkTdk1xk1(1T)QdkxkTdk1xk1(1T)+5

(7-基于單目標規(guī)劃的遺傳搜索算法缺陷使傳統(tǒng)遺傳算法難以收斂到全局最優(yōu)解。搜索算法是從局部搜索發(fā)展而來的，是一種全局逐步尋優(yōu)算法。搜索法的基本思想是在搜索過程中將近期的歷史搜索存放在表中，有效避免了算法陷入循環(huán)和局部最優(yōu)解。搜索算法中的蔑視準則可以使算基于上述說明，在本問題中將局部搜索能力強的搜索算法與遺傳算法結合，得到遺傳搜索算法。搜索作為遺傳算法的選擇操作可以得到每一代的最優(yōu)，并且通過遺傳算法中的變異算子可以提高算法中解空間的多樣性。下面為遺傳搜索算法步驟，該流見圖7-2：遺傳搜索算法步Step1：通過貪心算法得到初最優(yōu)的m個構成搜索候選集； 加加表表N圖7-2遺傳搜索算法流目標解的迭代~求解結果及分析率，結合航跡長度、校正點個數(shù)建立了多目標優(yōu)化模型，并設計了遺傳搜索算法，求解出給定數(shù)據(jù)集1和數(shù)據(jù)集2的最優(yōu)航行軌跡及成功抵達終點的概率。數(shù)據(jù)集1最終得到的航跡規(guī)劃路線為A5784178023760733194450448485302612終點概率100%。失?。?，因此本文選取了其中一種校正情況，匯總于下表7-6中： 5555.0000005B結合數(shù)據(jù)表7-6，由下柱狀圖表7-4和餅圖7-5可以直觀地看出，飛行器到達垂直校正AB方向上下穿梭，安排較為合理，航行軌跡長度為算法最優(yōu)解，航跡長度108439m，使用12個誤差校正點，且成功抵達終點概率100%。AB直線距離為100465m，航跡長度僅比AB直線距離增加了7.93%。分數(shù)據(jù)集1其他解果，參考下表7-7：校正點個數(shù)航跡路徑航跡長度失敗概率[0,285,162,55,234,42,316,379,284,273,370,[0,285,162,55,234,192,70,312,198,513,277,[0,578,417,80,237,607,33,450,448,397,[0,578,417,80,237,607,89,403,3,501,[0,285,162,55,234,42,316,538,556,424,555,436,18,[0,285,162,55,234,42,316,312,96,476,520,59,425,數(shù)據(jù)集2最終得到的航跡規(guī)劃路線為：A16932210013719419029625024382442113212793013828799326終點概率65.01%。失?。?，因此本文選取了其中一種校正情況，匯總于下表7-8中： 000005000000050000B結合數(shù)據(jù)表7-8，由下柱狀圖表7-8和餅圖7-9可以直觀地看出，飛行器到達垂直校正AB方向上下穿梭，安排較為合理，航行軌跡長度為算法最優(yōu)解，航跡長度147271m，使用19個誤差校正點，且成功抵達終點概率65.01%。AB直線距離為103045m，航跡長度比AB直線距離增加了42.91%。分數(shù)據(jù)集2其他解果，參考下表7-9：校正點個數(shù)航跡路徑航跡長度失敗概率無無[0,285,162,55,234,42,316,379,284,273,370,[0,285,162,55,234,192,70,312,198,513,277,[0,184,163,114,251,137,194,296,250,243,73,82,44,211,279,301,38,110,99,[0,184,163,114,251,137,194,296,250,243,73,249,274,12,279,301,38,110,99,[0,184,163,114,251,137,194,296,250,243,167,82,207,44,321,279,301,38,287,99,[0,285,162,55,234,42,316,312,96,476,520,59,425,7-97-10可以觀察到，在我們選取的部分結果中，校正點個數(shù)為19時，航跡角度說明本文求解出的19個校正點，航跡長度147271m為算法的最優(yōu)解。模型評估算法的有效性和復雜度大降低了問題的求解難度。本問題將局部搜索能力強的搜索算法與遺傳算法結合，提出了遺傳搜索算法。搜索作為遺傳算法的選擇操作可以得到每一代的最優(yōu)， 型可以證明遺傳搜索算法是以概率1收斂到全局最優(yōu)解的。結果表明遺傳 間復雜度為T(n)O(n4170.69s，數(shù)據(jù)集2為54.42s。靈敏度分析在部署遺傳搜索算法時，交叉率Pc和變異率Pm是需要手動設置的參數(shù)，且交叉率Pc和變異率Pm是影響算法效率的重要因是到目前為止仍然沒有一種合理選擇交叉率Pc 為此，本文在算法設計時，研究了(Pc,Pm 對結果的影響。取交叉P(0.4,0.5,0.6,0.70.8)P104,103,102,101)。根據(jù)交叉率和變異率 )

模型的評價模型的優(yōu)點對目標函數(shù)引入飛行器飛行失敗概率和變量，分析了導致飛行器飛行失敗的原因，并在問題一的基礎上，將變量轉化為模型的約束條件?；幚砗蛥⒖純?yōu)先級順序，引入了線性系數(shù)，使復雜的多目標規(guī)劃模型求解轉換為單模型的缺點參考文Z.LiandR.Han,"UnmannedAerialVehicleThree-dimensionalTrajectorynningBasedonAntColonyAlgorithm,"201837thControlConference(CCC),Wuhan,2018,pp.Sun,Liguo,Li,Shidan,Wang,Desheng.”Flightroutenningforterrainnavigationusingmulti-fractaltheory”.JournalofTsinghuaUniversity,2011.Qu,Dongcai,Yu,Dehai,Feng,Yuguang.”O(jiān)nflightroutenningmethodoftheterrainavoidancesystem”.2014IEEEGuidance,NavigationandControlConference,CGNCC2014,2015,pp.492-496.Sun,Tsung-Ying;Huo,Chih-Li;Tsai,Shang-Jeng.”O(jiān)ptimalUAVflightpathnningusingskeletonizationandParticleSwarmOptimizer”.2008IEEECongressonEvolutionaryComputation,CEC2008,2008,pp.1183-1188,,,etal.基于遺傳算法的多約束三維航跡規(guī)劃方法研究[C]//第二十七屆中國控制會議集.2008.季.搜索算法[J].電腦知識與技術,2009,5(27):7748-ClassificationoftheDubinsset.Shkel,A.M.1;Lumelsky,V.附問題一代碼importopenpyxlimportsysimportrandomimportosdata_path=os.path.join('..','..','2019年中國數(shù)學建模競賽F題\附件1：數(shù)據(jù)集1-終#excel文件,#獲取指定的表單point_list=[]forrowinpoint_list.append([row[1].value,row[2].value,row[3].value,row[4].value,row[5].value])point_num=len(point_list)defget_distance(start_index,end_index):x1,y1,z1=point_list[start_index][0:3]x2,y2,z2=return((x1-x2)**2+(y1-y2)**2+(z1-z2)**2)**0.5defjudge_z(start_index,end_index=point_num-1):x1,y1,z1=point_list[start_index][0:3]x2,y2,z2=point_list[end_index][0:3]ifabs(z1-z2)>5000:returnreturnend_point_type=point_list[end_index][3]distance=get_distance(start_index,delta_error=distance*end_point_horizontal_error=horizontal_error+delta_errorend_point_vertical_error=vertical_error+delta_errorififend_indexpoint_num1:#下一個點不是終點ifend_point_type==0:#水平ifend_point_horizontal_error<=beta2andend_point_vertical_error<=beta1:is_pass=Trueis_pass=elifend_point_type1:# is_pass=

is_pass=ifend_point_horizontal_error<=thetaandend_point_vertical_error<=theta:is_pass=True

is_pass=after_end_point_vertical_error=end_point_vertical_errorififend_point_type==0:after_end_point_horizontal_error=0elifend_point_type==1:after_end_point_vertical_error=0 after_end_point_horizontal_error,after_end_point_vertical_errordefranked_list=sorted(point_index_list,key=lambdaindex_list:get_distance(index_list[0],returndistance=0foriinrange(len(index_list)-start_index=index_list[i]distance=distance+get_distance(start_index,end_index)returndistanceorder=[]temp_all_distance=temp_order=[]deffind_path(start_index=0,horizontal_error=0,vertical_error=0):globaltemp_all_distanceglobalorder,temp_ordercandidate_list=[]forindexinrange(point_num):ifindex!=start_index: after_end_point_horizontal_error,after_end_point_vertical_error=judge(start_index,index,horizontal_error,vertical_error)ifis_passandget_distance(start_index,point_num-1)>iflen(candidate_list)==0:candidate_list.sort(key=lambdaindex_list:get_distance(index_list,point_num-1))#random.shuffle(candidate_list)iflen(candidate_list)>=5:forcandidateinifcandidate==point_num-1:ifall_distance<temp_all_distance:temp_order=order.copy()print('\n'+'small',order,all_distance)iflen(order)>13: after_end_point_horizontal_error,after_end_point_vertical_error=judge(start_index,candidate,horizontal_error,find_path(candidate,after_end_point_horizontal_error,importopenpyxlimportsysimportosdata_path=os.path.join('..','..','2019年中國數(shù)學建模競賽F題\附件1：數(shù)據(jù)集1-終#excel文件,#獲取指定的表單sheet=wb['data1']point_list=[]forrowinpoint_list.append([row[1].value,row[2].value,row[3].value,row[4].value,row[5].value])point_num=x1,y1,z1=point_list[start_index][0:3]x2,y2,z2=point_list[end_index][0:3]ifabs(z1-z2)>5000:returnreturndefget_distance(start_index,end_index):x1,y1,z1=point_list[start_index][0:3]x2,y2,z2=return((x1-x2)**2+(y1-y2)**2+(z1-end_point_type=point_list[end_index][3]distance=get_distance(start_index,delta_error=distance*end_point_horizontal_error=horizontal_error+delta_errorend_point_vertical_error=vertical_error+delta_errorififend_indexpoint_num1:#下一個點不是終點ifend_point_type==0:#水平ifend_point_horizontal_error<=beta2andend_point_vertical_error<=beta1:is_pass=Trueis_pass=elifend_point_type1:# is_pass=

is_pass=ifend_point_horizontal_error<=thetaandend_point_vertical_error<=theta:is_pass=True

is_pass=after_end_point_vertical_error=end_point_vertical_errorififend_point_type==0:after_end_point_horizontal_error=0elifend_point_type==1:after_end_point_vertical_error=0 after_end_point_horizontal_error,after_end_point_vertical_error_path_list=[0,503,294,91,282,33,315,403,594,501,path_list=[[i,0,0,0,0]foriindistance=foriinrange(len(path_list)-1):start_index=end_index=path_list[i+ after_end_point_horizontal_error,after_end_point_vertical_error=judge(start_index,end_index,path_list[i][3],path_list[i][4])if after_end_point_horizontal_error,after_end_point_vertical_errordistance=distance+get_distance(start_index,end_index)foriinpath_list:print(i,問題二代碼importopenpyxlimportsysimportrandomimportosdata_path=os.path.join('..','..','2019年中國數(shù)學建模競賽F題\附件1：數(shù)據(jù)集1-終#excel文件,#獲取指定的表單point_list=[]forrowinpoint_list.append([row[1].value,row[2].value,row[3].value,row[4].value,row[5].value])point_num=len(point_list)defget_distance(start_index,end_index):x1,y1,z1=point_list[start_index][0:3]x2,y2,z2=return((x1-x2)**2+(y1-y2)**2+(z1-z2)**2)**0.5defjudge_z(start_index,end_index=point_num-1):x1,y1,z1=point_list[start_index][0:3]x2,y2,z2=point_list[end_index][0:3]ifabs(z1-z2)>5000:returnreturnend_point_type=point_list[end_index][3]distance=get_distance(start_index,end_index)delta_error=distance*sigmaend_point_horizontal_error=horizontal_error+delta_errorend_point_vertical_error=vertical_error+delta_errorififend_indexpoint_num1:#下一個點不是終點ifend_point_type==0:#水平ifend_point_horizontal_error<=beta2andend_point_vertical_error<=beta1:is_pass=Trueis_pass=elifend_point_type1:# is_pass=

is_pass=ifend_point_horizontal_error<=thetaandend_point_vertical_error<=theta:is_pass=True

is_pass=after_end_point_vertical_error=end_point_vertical_errorififend_point_type==0:after_end_point_horizontal_error=0elifend_point_type==1:after_end_point_vertical_error=0 defrank_distance(point_index_list):ranked_list=sorted(point_index_list,key=lambdaindex_list:get_distance(index_list[0],returndistance=0foriinrange(len(index_list)-1):start_index=index_list[i]distance=distance+get_distance(start_index,end_index)returndistanceorder=[]temp_order=[]deffind_path(start_index=0,horizontal_error=0,vertical_error=0):globaltemp_all_distanceglobalorder,temp_ordercandidate_list=[]forindexinrange(point_num):ifindex!=start_index: after_end_point_horizontal_error,after_end_point_vertical_error=judge(start_index,index,horizontal_error,verti