[發(fā)明專利]無序經(jīng)過必經(jīng)點的最短路徑獲取方法及裝置

在審

• 申請?zhí)枺?/td>: 201710099326.8
• 申請日: 2017-02-23
• 公開（公告）號: CN106845630A
• 公開（公告）日: 2017-06-13
• 發(fā)明（設(shè)計）人: 王志超
• 申請（專利權(quán)）人: 中國人民解放軍國防科學(xué)技術(shù)大學(xué)
• 主分類號: G06N3/00
• 分類號: G06N3/00;G06N3/12
• 代理公司: 長沙市護航專利代理事務(wù)所(特殊普通合伙)43220
• 代理人: 莫曉齊

1.一種無序經(jīng)過必經(jīng)點的最短路徑獲取方法，用于獲取經(jīng)過K個必經(jīng)點的N條最短路徑，其中K、N均是大于1的整數(shù)，其特征在于，包括以下步驟：

步驟S1：計算只經(jīng)過非必經(jīng)點的起點到任意必經(jīng)點，任意必經(jīng)點到終點以及兩兩必經(jīng)點之間的最短路徑長度以及路徑；

步驟S2：初始化UN個種群個體，個體長度為K，填充為各個必經(jīng)點的序號，其中UN是大于N的整數(shù)；

步驟S3：計算種群中每個個體的路徑以及路徑長度，依據(jù)路徑長度對種群進行排序并取N條最佳路徑；

步驟S4：從種群中取一定比例的個體，按照交叉變異規(guī)則進行生成，產(chǎn)生新一代可行解作為新的種群；

步驟S5：在迭代次數(shù)達到預(yù)設(shè)次數(shù)時，輸出N個最優(yōu)解。

2.根據(jù)權(quán)利要求1所述的無序經(jīng)過必經(jīng)點的最短路徑獲取方法，其特征在于，所述步驟S1之前還包括以下步驟：

初始化網(wǎng)絡(luò)以去掉沒有入度或出度的中間點；

縮減網(wǎng)絡(luò)矩陣，減少矩陣維度，降低時間復(fù)雜度。

3.根據(jù)權(quán)利要求1所述的無序經(jīng)過必經(jīng)點的最短路徑獲取方法，其特征在于，所述步驟S1具體包括：

步驟S11：將要求取的路徑抽象為從節(jié)點a到節(jié)點b，其中a是起點或者必經(jīng)點，b是必經(jīng)點或者終點；

步驟S12：將除了a和b之外所有必經(jīng)點的出度清空；

步驟S13：使用最短路徑算法求取a到b的路徑及路徑長度。

4.根據(jù)權(quán)利要求1所述的無序經(jīng)過必經(jīng)點的最短路徑獲取方法，其特征在于，所述步驟S3中計算種群中每個個體的路徑及路徑長度具體包括：

步驟S31：設(shè)置經(jīng)過的非必經(jīng)點集合；

步驟S32：針對每個個體，生成隨機序列作為路徑搜索順序；

步驟S33：依據(jù)搜索順序，查詢當(dāng)前點與下一必經(jīng)點之間的最短路徑，如果經(jīng)過的非必經(jīng)點都不在非必經(jīng)點集合內(nèi)，則當(dāng)前點即為此路徑中的非必經(jīng)點；

步驟S34：否則，將網(wǎng)絡(luò)中涉及到的非必經(jīng)點集合內(nèi)的非必經(jīng)點出度清空，獲得新的路徑中的非必經(jīng)點；

步驟S35：將各段路徑長度加起來即可得到當(dāng)前個體路徑。

5.根據(jù)權(quán)利要求1-4任一項所述的無序經(jīng)過必經(jīng)點的最短路徑獲取方法，其特征在于，所述步驟S4中采用三交叉啟發(fā)交叉，進行啟發(fā)式生成，以生成更優(yōu)的一代種群。

6.一種無序經(jīng)過必經(jīng)點的最短路徑獲取裝置，用于獲取經(jīng)過K個必經(jīng)點的N條最短路徑，其中K、N均是大于1的整數(shù)，其特征在于，包括：

第一計算模塊，用于計算只經(jīng)過非必經(jīng)點的起點到任意必經(jīng)點，任意必經(jīng)點到終點以及兩兩必經(jīng)點之間的最短路徑長度以及路徑；

第一初始化模塊，用于初始化UN個種群個體，個體長度為K，填充為各個必經(jīng)點的序號，其中UN是大于N的整數(shù)；

第二計算模塊，用于計算種群中每個個體的路徑以及路徑長度，依據(jù)路徑長度對種群進行排序并取N條最佳路徑；

種群生成模塊，用于從種群中取一定比例的個體，按照交叉變異規(guī)則進行生成，產(chǎn)生新一代可行解作為新的種群；

輸出模塊，用于在迭代次數(shù)達到預(yù)設(shè)次數(shù)時，輸出N個最優(yōu)解。

7.根據(jù)權(quán)利要求6所述的無序經(jīng)過必經(jīng)點的最短路徑獲取裝置，其特征在于，還包括：

第二初始化模塊，用于初始化網(wǎng)絡(luò)以去掉沒有入度或出度的中間點，縮減網(wǎng)絡(luò)矩陣，減少矩陣維度，降低時間復(fù)雜度。

8.根據(jù)權(quán)利要求6所述的無序經(jīng)過必經(jīng)點的最短路徑獲取裝置，其特征在于，所述第一計算模塊包括：

抽象單元，用于將要求取的路徑抽象為從節(jié)點a到節(jié)點b，其中a是起點或者必經(jīng)點，b是必經(jīng)點或者終點；

第一出度單元，用于將除了a和b之外所有必經(jīng)點的出度清空；

求取單元，用于使用最短路徑算法求取a到b的路徑及路徑長度。