歐麗珍，楊 旭，李新夢，羅雪山

（國防科技大學，長沙 410073）

0 引言

真實軍事作戰(zhàn)中，是否懂地形、能否充分發(fā)揮地形的作用是影響作戰(zhàn)勝負的關鍵因素之一。軍事地形學是軍隊院校必修課程之一，包含理論教學和實踐教學兩個部分，其中，軍事地形學實踐教學又稱為軍事定向越野或定向越野，其主要目的在于培養(yǎng)學員識圖、用圖以及軍事標圖等技能。因此，定向越野逐步成為了一項常態(tài)化的軍事訓練科目。

定向越野是一種利用指北針以及地圖或地形圖等指向工具，根據(jù)一定的比賽規(guī)則在野外行進至終點，最終得分高者獲勝。定向越野路線設計是通過在合適的地圖或地形圖上設計起點、檢查點以及終點，規(guī)劃定向比賽過程，從而獲得盡可能公正的賽道的過程。但在實際比賽中，往往只知道起點及檢查候選點，在規(guī)劃路徑時，需要自行確定終點及必經(jīng)檢查點，其中，必經(jīng)檢查點是指所有賽道都經(jīng)過的檢查點，用于提供水以及醫(yī)療物資等。定向越野運動在軍校學生的訓練中具有重要意義，這項運動不僅考驗參與者的體能、意志，同時也將考察識圖技能、方向辨認等。定向越野比賽要求的空間較大，通常選擇森林、公園、校園以及山地等，往往包含一些未知地理地形等，因此，這也將鍛煉參賽選手應對突發(fā)情況的能力。

實現(xiàn)多路徑定向越野比賽路徑自動化設計有利于促進軍事定向越野運動的發(fā)展，提升參與者自身的綜合素質(zhì)。目前關于越野賽道的研究集中于單路徑最優(yōu)，這對于多路徑定向越野比賽并不適用，多路徑定向越野賽道設計更加注重賽道之間的均衡，而非最短或是最優(yōu)單路徑，據(jù)此，構(gòu)建多路徑定向越野模型框架，有利于減少路徑設計成本，促進定向越野運動發(fā)展。

1 背景介紹

多路徑定向越野比賽通常安排若干條比賽賽道，所有路線的起點和終點相同，每條賽道可安排一個或多個選手，同一賽道的選手間隔一定時間出發(fā)，不同路線的首發(fā)參賽選手同時出發(fā)。良好的賽道設計需保證賽道的公平性及參賽選手的良好參賽體驗。根據(jù)以往的賽道設計經(jīng)驗，結(jié)合實際需求，本文設計以下約束。

規(guī)則1：不同路徑的長度盡可能均勻，為簡化模型，通常假設參賽選手在各打卡點之間沿直線前進；

規(guī)則2：不同路徑的總打卡難度盡可能均勻，打卡難度通常用完成該任務的平均時長代替；

規(guī)則3：不同路徑的爬高量盡可能均勻，其中，爬高量是指若后一個打卡點的Z 坐標比前一打卡點高，則兩者之間的差值稱為爬高量；

規(guī)則4：避免包含較多的重復路段，即“尾隨路段”，防止參賽選手之間有意或無意地相互交流與協(xié)助；相鄰或相近檢查點打卡順序應當盡可能連續(xù)，且路線盡可能短；

規(guī)則5：路徑檢查點數(shù)量大于等于一個定值D，且通常包含d 個公共檢查點；

規(guī)則6：同時抵達（時間間隔小于1 min）同一檢查點的隊伍數(shù)小于等于p，以保證參賽隊伍良好的參賽體驗感；

規(guī)則7：需保證參賽選手以平均速度v行進，參賽選手平均完成時間不小于t且不大于t，保證選手充分體驗比賽且不至于過度消耗。

規(guī)則8：終點通常設立在任務難度較低的點。

其中，規(guī)則1～規(guī)則3 是為了保證各賽道盡可能均勻，減少賽道差異對比賽的影響，規(guī)則4～規(guī)則5 則是為了保障比賽的順利進行；規(guī)則6～規(guī)則8 則是為了保證比賽選手的參與體驗。

賽道基本類型包含閉合路線、半閉合路線、開放路線、交叉路線、星型路線1 以及星型路線2 共6種形式，如圖1 所示。

圖1 越野賽道基本路線類型

因此，若需設計閉合路線，則終點的候選集應當包含起點。

2 模型建立

約束4：規(guī)則4 要求避免包含較多重復路段，且同一路線中打卡順序應盡可能連續(xù)，路線長度盡可能短。

重復路徑表示在兩個最短路徑序列中，兩個相同節(jié)點相鄰出現(xiàn)，因本題路徑為相同起點和相同終點，因此，不考慮逆向路徑的可能，即不考慮兩條路徑同時存在節(jié)點A →節(jié)點B 和節(jié)點B→節(jié)點A 的情況。據(jù)此我們構(gòu)建一個新的路徑序列矩陣M。

綜上所述，多路徑規(guī)劃的目標為各路徑長度、難度以及爬高量的方差盡可能小。其中，約束1～約束3 將用于路徑初始化及后續(xù)生成；約束4～約束6主要用于挑選合適路徑。

3 Dijkstra 改進遺傳算法基本原理

3.1 模型介紹

遺傳算法（genetic algorithm，GA）具有魯棒性、適應能力強等優(yōu)點。近年來，遺傳算法已成功應用于工業(yè)、金融以及交通運輸?shù)阮I域，在路徑優(yōu)化領域取得了較大發(fā)展，因此，本文選用遺傳算法對模型進行求解。但傳統(tǒng)的遺傳算法僅能獲取一組無序的節(jié)點序列，而無法給出最短路徑。Dijkstra算法是圖論中求最短路徑的著名算法，本質(zhì)上為貪心算法的實現(xiàn)，目的是尋找起點到各點距離獲取最短路徑。因此，可以利用Dijkstra 算法對遺傳算法的結(jié)果進行最短路徑排序。

基于Dijkstra 改進遺傳算法包括8 個步驟：1）編碼；2）初始化種群；3）利用Dijkstra 算法對種群進行排序；4）對種群個體適應度進行評估；5）按照優(yōu)勝劣汰和適者生存的原理選擇個體；6）模擬自然遺傳學進行染色體交叉和變異；7）Dijkstra 算法對新產(chǎn)生的種群進行修正、評估；8）逐步迭代，直至滿足停止條件，求取最終解?；玖鞒倘鐖D2 所示。

圖2 Dijkstra 改進遺傳算法流程

3.2 模型相關設定

3.2.1 編碼

編碼是指DNA 中遺傳信息在一個長鏈上按一定的模式排列，即可以看成表現(xiàn)型到基因型的映射。遺傳算法的編碼主要包括二進制編碼、格雷碼編碼、實數(shù)編碼、符號編碼4 種。其中，二進制編碼具有操作簡單，容易計算等優(yōu)勢，因而常被采用。

3.2.2 初始化種群

隨機生成由n 個個體組成的種群，即可行解集合，通過模擬優(yōu)勝劣汰的自然法則對這些種群進行重新選擇，獲取優(yōu)秀的種群及個體。

3.2.3 最短路徑獲取

在多路徑規(guī)劃問題求解中，依據(jù)約束1～約束3初始化種群后，需經(jīng)過Dijkstra 算法對各節(jié)點進行排序以獲取最短路徑。

3.2.4 適應度函數(shù)選擇

適應度函數(shù)通常是用于區(qū)分種群中個體好壞的標準，在多路徑優(yōu)化算法中，可以選用約束4～約束6 進行選擇，計算方便快捷，同時不會出現(xiàn)由于異常個體或者差異不大的個體造成選擇結(jié)果不理想的狀況。

3.2.5 交叉和變異

交叉是指在遺傳學中，父母雙方的基因可能在某一個位置相互交換；變異則是模擬生物進化過程中小概率基因突變事件。通過交叉和變異產(chǎn)生新的個體（調(diào)整節(jié)點順序），重新進行評價、選擇、雜交和變異，直至抵達終止條件。終止條件由目標函數(shù)確定。

3.3 場景需求與模型應用

1）若路徑條數(shù)為定值，則直接輸入N 的值即可。

2）調(diào)整約束4～約束6 可以適應不同的場景，若無相關需求，則可刪除相應的約束；若模型無可行解，可自行調(diào)整參數(shù)p，t，t的數(shù)值。

3）若路徑條數(shù)未知，但希望賽道容納盡可能多的人，則可增加一個目標函數(shù)，即在滿足約束的前提下，讓路徑數(shù)量盡可能多。

4）若無法獲取高程數(shù)據(jù)（Z 坐標值）、或是高程數(shù)據(jù)差異較?。ㄈ缙皆龋?，則去掉約束3，將長度改為二維歐式距離公式計算即可。

5）若需對參賽選手進行分配安排，則可通過增加關于選手的約束即可，模型整體框架不變。

4 實驗分析

為驗證模型的可行性，本文采用一次真實定向越野比賽數(shù)據(jù)進行驗證分析。

模型目標函數(shù)為容納盡可能多的參賽選手，其中，p=5，t=2，t=3，v=6。其中，各節(jié)點難度值w={1，2，3，4}，最終試驗結(jié)果如表1 所示。從表1 可知，路徑條數(shù)為6 時，難度方差、長度方差、爬坡方差以及完成時間方差綜合較小，且人數(shù)相對較多。

表1 試驗結(jié)果展示（部分）

圖3 數(shù)據(jù)概覽（紅色△表示起點，紅色×表示低難度節(jié)點，即終點候選集，中間節(jié)點用灰色○表示）

5 結(jié)論

本文利用基于Dijkstra 改進遺傳算法對模型進行求解，并利用實際數(shù)據(jù)進行驗證。結(jié)果表明，本文提出的多路徑多目標規(guī)劃模型可以通過不同的參數(shù)設定和約束調(diào)整，滿足多種場景需求，具有廣闊的應用前景。同時，多路徑多目標規(guī)劃模型可應用于多靜點多路徑探查任務，如偵察任務等。