基于Dijkstra 改進(jìn)遺傳算法的定向越野賽道設(shè)計(jì)*

歐麗珍，楊 旭，李新夢(mèng)，羅雪山

（國(guó)防科技大學(xué)，長(zhǎng)沙 410073）

0 引言

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

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

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

1 背景介紹

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

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

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

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

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

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

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

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

規(guī)則8：終點(diǎn)通常設(shè)立在任務(wù)難度較低的點(diǎn)。

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

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

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

因此，若需設(shè)計(jì)閉合路線，則終點(diǎn)的候選集應(yīng)當(dāng)包含起點(diǎn)。

2 模型建立

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

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

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

3 Dijkstra 改進(jìn)遺傳算法基本原理

3.1 模型介紹

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

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

圖2 Dijkstra 改進(jìn)遺傳算法流程

3.2 模型相關(guān)設(shè)定

3.2.1 編碼

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

3.2.2 初始化種群

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

3.2.3 最短路徑獲取

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

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

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

3.2.5 交叉和變異

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

3.3 場(chǎng)景需求與模型應(yīng)用

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

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

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

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

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

4 實(shí)驗(yàn)分析

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

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

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

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

5 結(jié)論

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