周 睿，何利文，唐澄澄，侯小宇，陸錢春

(1.南京郵電大學(xué)，江蘇 南京 210003；2.中興通訊股份有限公司，江蘇 南京 210012)

1 概 述

網(wǎng)絡(luò)的穩(wěn)定性是網(wǎng)絡(luò)正常運(yùn)行的重要前提，減少網(wǎng)絡(luò)變更對(duì)生產(chǎn)生活的影響就變得至關(guān)重要，這同時(shí)還會(huì)減少相關(guān)設(shè)備和協(xié)議的巨大安裝成本。想在傳統(tǒng)網(wǎng)絡(luò)上有所創(chuàng)新變得困難，幾乎沒有什么辦法來嘗試新的網(wǎng)絡(luò)協(xié)議，因此人們普遍認(rèn)為網(wǎng)絡(luò)設(shè)施已經(jīng)變得僵化了[1]。但是隨著移動(dòng)設(shè)備和內(nèi)容的爆炸式增長(zhǎng)、服務(wù)器虛擬化，以及云計(jì)算的出現(xiàn)推動(dòng)了網(wǎng)絡(luò)的進(jìn)一步發(fā)展，行業(yè)開始重新審視傳統(tǒng)的網(wǎng)絡(luò)架構(gòu)。傳統(tǒng)網(wǎng)絡(luò)結(jié)構(gòu)是分層的，由分布式排列的交換機(jī)和路由器構(gòu)成，這種設(shè)計(jì)在客戶機(jī)-服務(wù)器計(jì)算時(shí)是占主導(dǎo)地位的，但是這樣的靜態(tài)架構(gòu)不適合今天的企業(yè)數(shù)據(jù)中心、校園網(wǎng)、運(yùn)營(yíng)商環(huán)境的計(jì)算和存儲(chǔ)需求[2]。近年來，SDN(software defined networking，軟件定義網(wǎng)絡(luò))的提出，為目前出現(xiàn)的這些網(wǎng)絡(luò)問題找到了新的方向。不同于傳統(tǒng)的網(wǎng)絡(luò)，SDN控制器將網(wǎng)絡(luò)設(shè)備的數(shù)據(jù)平面和控制平面分離，使用一個(gè)集中的控制器來決定網(wǎng)絡(luò)中所有轉(zhuǎn)發(fā)組件的行為[3]。并且為相關(guān)的網(wǎng)絡(luò)應(yīng)用提供可編程的接口，利用軟件的方式對(duì)整個(gè)網(wǎng)絡(luò)的資源進(jìn)行控制，革命性地改變了現(xiàn)有的網(wǎng)絡(luò)架構(gòu)[4]。

在傳統(tǒng)的網(wǎng)絡(luò)體系架構(gòu)中，路由協(xié)議改進(jìn)非常困難，這主要是由于設(shè)備更新?lián)Q代以及網(wǎng)絡(luò)自身的復(fù)雜性比較高，同時(shí)也會(huì)帶來非常巨大的開銷等[5]。傳統(tǒng)的QoS體系結(jié)構(gòu)(基于分布式控制平面)被證明是過于靜態(tài)的，無法獲得更廣泛的應(yīng)用[6]。SDN的出現(xiàn)直接降低了新型網(wǎng)絡(luò)開發(fā)的成本，其倡導(dǎo)控制轉(zhuǎn)發(fā)分離、網(wǎng)絡(luò)能力接口的開放、軟硬件解耦和網(wǎng)絡(luò)功能的虛擬化，這將會(huì)推動(dòng)網(wǎng)絡(luò)架構(gòu)向軟件化、集約化、智能化和開放化的目標(biāo)網(wǎng)絡(luò)架構(gòu)演進(jìn)[7]。

它的關(guān)鍵技術(shù)包括控制和轉(zhuǎn)發(fā)解耦、實(shí)現(xiàn)控制集中化和網(wǎng)絡(luò)能力開放化這幾個(gè)方面,一個(gè)SDN控制器可以對(duì)轉(zhuǎn)發(fā)平面多臺(tái)設(shè)備進(jìn)行通信，同時(shí)提供了一系列的開放編程接口，這樣對(duì)網(wǎng)絡(luò)業(yè)務(wù)的加載和控制更加靈活[8]。以往的路由算法通常是由分布式實(shí)現(xiàn)，即交換機(jī)需要生成并維護(hù)轉(zhuǎn)發(fā)表，實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)的集中配置與管理，而在SDN網(wǎng)絡(luò)中，數(shù)據(jù)轉(zhuǎn)發(fā)由控制器集中管理[9]，因此，只需要通過控制器來設(shè)計(jì)與數(shù)據(jù)轉(zhuǎn)發(fā)有關(guān)的程序。在具有全局的網(wǎng)絡(luò)狀態(tài)和應(yīng)用需求的情況下，可以在一個(gè)集中的系統(tǒng)中執(zhí)行得更高效[10]，SDN控制器的出現(xiàn)大大簡(jiǎn)化了路由創(chuàng)新的門檻。

網(wǎng)絡(luò)資源的中心化讓以前的分布式算法控制路由轉(zhuǎn)發(fā)成了歷史，這也是造成網(wǎng)絡(luò)低效的原因之一?，F(xiàn)在通過中心控制器可以高效地管理數(shù)據(jù)轉(zhuǎn)發(fā)，讓網(wǎng)絡(luò)流量更加可控，可以直接使用Dijkstra算法[11]來計(jì)算最短路，達(dá)到最佳路由。然而，SDN控制器支持的最短路徑算法無法較好地部署三層路由技術(shù)，還有就是Dijkstra算法的時(shí)間復(fù)雜度并不低，隨著網(wǎng)絡(luò)結(jié)點(diǎn)的增加，CPU的消耗越來越高，網(wǎng)絡(luò)尋址的效率也會(huì)降低。SDN現(xiàn)在最常見的應(yīng)用是在IDC網(wǎng)絡(luò)中，這種網(wǎng)絡(luò)通常會(huì)有成千上萬個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，因此，提出一種效率更高的算法是極具意義的。與此同時(shí)，網(wǎng)絡(luò)服務(wù)提供商需要根據(jù)客戶的SLA(服務(wù)等級(jí)協(xié)議)為其定制特定級(jí)別的高質(zhì)量網(wǎng)絡(luò)服務(wù)，即需要滿足如帶寬、時(shí)延、嚴(yán)格下一跳等等條件[12]。Qos需求路由問題可以理解為尋找滿足多個(gè)約束條件的可行路徑問題，這是屬于NP難問題，通常無法在多項(xiàng)式時(shí)間內(nèi)求解[13]。所以文中采用基于啟發(fā)式算法的遺傳算法來解決這個(gè)問題。

遺傳算法(genetic algorithm，GA)是由J.H.Holland等于20世紀(jì)70年代提出并發(fā)展起來的[14]，也是啟發(fā)式算法的一種，還是一種具有全局搜索能力的直接、并行、隨機(jī)的優(yōu)化方法。它通過模仿生物的進(jìn)化，遵循進(jìn)化的主要原則，本質(zhì)上是先通過隨機(jī)方式選出初始種群，根據(jù)特定的評(píng)定標(biāo)準(zhǔn)，通過選擇、交叉、變異的遺傳算子的優(yōu)化作用，優(yōu)選出性能最佳的一系列個(gè)體[15]。因?yàn)檫z傳算法具有很強(qiáng)的全局尋優(yōu)能力和適應(yīng)性，被廣泛地應(yīng)用于路徑規(guī)劃問題。所以這里采用多目標(biāo)約束遺傳算法解決多約束路由問題，既能一次計(jì)算產(chǎn)生多條可選路徑路由，也可以根據(jù)業(yè)務(wù)的需求動(dòng)態(tài)調(diào)整路由計(jì)算的參數(shù)，來得到所需要的路徑。

文中提出的遺傳算法是在已有物理拓?fù)錉顟B(tài)下根據(jù)具體的業(yè)務(wù)標(biāo)準(zhǔn)需求的多目標(biāo)約束遺傳算法，可以在并行的情況下自適應(yīng)地計(jì)算出符合路徑約束條件的若干條可用路徑，保證每個(gè)業(yè)務(wù)都有充足的備用路徑可供調(diào)整。對(duì)該算法的主要思想和流程進(jìn)行了介紹，然后對(duì)算法展開了詳細(xì)描述，最后對(duì)算法在給定的網(wǎng)絡(luò)環(huán)境下的性能進(jìn)行了分析，驗(yàn)證該算法對(duì)SDN路徑增強(qiáng)問題的有效性。

2 SDN網(wǎng)絡(luò)約束

2.1 網(wǎng)絡(luò)模型及問題描述

即如果兩節(jié)點(diǎn)之間有鏈路連通，則矩陣對(duì)應(yīng)的元素為1，否則為0。同理，鏈路帶寬容量矩陣用B={bi,j},vi,vj∈V,ek=(vi,vj)∈E表示，其中bi,j表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間鏈路的帶寬容量大??；時(shí)延矩陣D={dij},vi,vj∈V,ek=(vi,vj)∈E,dij表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的鏈路時(shí)延的值，cij表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的鏈路開銷的值。

2.2 約束優(yōu)化模型

假定兩個(gè)節(jié)點(diǎn)vi,vj之間有一條不帶環(huán)的通路路徑，記為：path=(vi,vj)，如果路徑path經(jīng)過鏈路ek，那么ek∈path,否則ek?path。文中路徑是由染色體個(gè)體的形式表示的，即每個(gè)染色體代表一條路徑，有x1,x2,…,xn，這里使用變長(zhǎng)的實(shí)數(shù)編碼的方式，以s和d為其起始節(jié)點(diǎn)，每個(gè)個(gè)體所表示的路徑經(jīng)過的節(jié)點(diǎn)數(shù)量是不定的。多約束路由問題中的多約束條件可以表述為:

(1)

(2)

(3)

(4)

?(xij=1)bi,j·xi,j>BandWidth

(5)

(6)

其中，xij表示路徑x中對(duì)應(yīng)的鏈路有效因子，當(dāng)(vi,vj)屬于x時(shí)，xij=1，否則xij=0。Cost、Delay、Hop、Bandwidth分別是SDN路由中要求的額定開銷、時(shí)延、跳數(shù)和帶寬的可變參數(shù)，在這里一般表示為常數(shù)。

3 改進(jìn)的多目標(biāo)約束的遺傳算法

3.1 路徑編碼

根據(jù)網(wǎng)絡(luò)拓?fù)渎窂降奶攸c(diǎn)，采用鏈?zhǔn)阶冮L(zhǎng)實(shí)數(shù)編碼的方式，如：源節(jié)點(diǎn)是0.0，目的節(jié)點(diǎn)是120.3，路徑依次經(jīng)過節(jié)點(diǎn)0.0、3.5、50.9、70,3、62.8、109.5、120.4，那么路徑編碼就是0.0→50.9→70.3→62.8→109.5→120.4。這樣的編碼和解碼的過程相對(duì)來講比較簡(jiǎn)單，代表每一個(gè)節(jié)點(diǎn)的實(shí)數(shù)根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量會(huì)做相應(yīng)的調(diào)整，隨著網(wǎng)絡(luò)規(guī)模的變化相應(yīng)地改變小數(shù)位的位數(shù)，如圖1所示。

圖1 網(wǎng)絡(luò)拓?fù)?/p>

3.2 種群初始化

遺傳算法需要通過初始種群的生成的篩選滿足路徑規(guī)劃類約束條件。這里引入了He L在用混合遺傳算法解決電信網(wǎng)絡(luò)備用路由的研究中提出的SPA算法(最短路徑優(yōu)先)[16]，并且根據(jù)約束條件進(jìn)行改進(jìn)，在原有隨機(jī)路徑選擇生成的過程中滿足相應(yīng)的約束條件。算法流程如下：

(1)從源節(jié)點(diǎn)開始；

(2)尋找所有與源節(jié)點(diǎn)相連接的節(jié)點(diǎn)，記錄這些節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)；

(3)檢查這些當(dāng)前節(jié)點(diǎn)中是否有目的節(jié)點(diǎn)；

(4)如果有，則記錄源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的鏈路，計(jì)算完成，否則，繼續(xù)計(jì)算；

(5)繼續(xù)查找與當(dāng)前節(jié)點(diǎn)相連的節(jié)點(diǎn)，作為當(dāng)前節(jié)點(diǎn)；

(6)查看這些節(jié)點(diǎn)是否有源節(jié)點(diǎn)，如果有則將其從列表中刪除；

(7)重復(fù)步驟3，直到找到最短路徑為止。

約束條件為：嚴(yán)格下一跳和松散下一跳；排除某個(gè)節(jié)點(diǎn)；親和力屬性的處理。

改進(jìn)的SPA算法：

(1)從源節(jié)點(diǎn)開始；

(2)尋找所有與源節(jié)點(diǎn)相連接的節(jié)點(diǎn)，記錄這些節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)集合；

(3)檢查當(dāng)前節(jié)點(diǎn)是否有目的節(jié)點(diǎn)；

(4)如果有，則記錄源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的鏈路，計(jì)算完成，否則繼續(xù)計(jì)算；

(5)檢查當(dāng)前節(jié)點(diǎn)中有無需要排除的節(jié)點(diǎn)，如果有則從當(dāng)前節(jié)點(diǎn)中刪除，繼續(xù)計(jì)算；

(6)檢查當(dāng)前節(jié)點(diǎn)集合中有無嚴(yán)格下一跳或者松散下一跳的節(jié)點(diǎn)，如果集合中有下一跳節(jié)點(diǎn)就走上去，否則繼續(xù)計(jì)算；

(7)檢查與當(dāng)前節(jié)點(diǎn)集合中節(jié)點(diǎn)連接的所有鏈路上的親和力屬性有無滿足當(dāng)前業(yè)務(wù)的親和力屬性，如果有就走該鏈路，否則繼續(xù)計(jì)算；

(8)繼續(xù)查找與當(dāng)前節(jié)點(diǎn)相連的節(jié)點(diǎn)，作為當(dāng)前節(jié)點(diǎn)；

(9)查看這些節(jié)點(diǎn)是否有源節(jié)點(diǎn)，如果有則將其從列表中刪除；

(10)重復(fù)步驟3，直到找到可行的路徑為止。

3.3 個(gè)體選擇

個(gè)體選擇概率取決于種群中個(gè)體的適應(yīng)度及其分布，為了簡(jiǎn)單有效地控制選擇壓力并且使得個(gè)體有更好的魯棒性，選擇使用輪盤賭的方法。解決路徑規(guī)劃的優(yōu)化問題必須要先解決問題模型中的約束條件問題，包括一些等式和不等式的約束條件，在遺傳算法中對(duì)約束條件的處理會(huì)帶來一些額外的參數(shù)。首先要將所有的等式約束條件轉(zhuǎn)化成不等式約束條件，這樣就只處理不等式約束條件即可。文中采用靜態(tài)懲罰函數(shù)法來處理不等式約束條件，適應(yīng)度函數(shù)定義為：

(7)

3.4 交叉運(yùn)算

交叉運(yùn)算產(chǎn)生子代，子代繼承父代的基本特征，主要包括兩個(gè)內(nèi)容：第一是對(duì)種群中的個(gè)體進(jìn)行隨機(jī)配對(duì)并按照設(shè)定的交叉概率Pm來確定需要交叉的個(gè)體對(duì)；第二是設(shè)定個(gè)體的交叉點(diǎn)，然后對(duì)個(gè)體的部分片段相互交換。交叉算子的設(shè)計(jì)與編碼方式有關(guān)，在最優(yōu)路徑規(guī)劃問題中有幾種代表性的交叉算子，如：順序交叉、類OX交叉等。這些交叉算子在產(chǎn)生新個(gè)體的過程中沒有目的性,對(duì)于實(shí)數(shù)編碼的最優(yōu)規(guī)劃問題,這些交叉可能破壞親代的較優(yōu)基因,從而使交叉算子的搜索能力大大降低?；诖?，文中擬用在重復(fù)節(jié)點(diǎn)位置交叉且只進(jìn)行一點(diǎn)交叉的操作方式，具體實(shí)現(xiàn)步驟如下：

·隨機(jī)選取兩個(gè)個(gè)體作為帶交叉?zhèn)€體；

·找到兩個(gè)帶交叉?zhèn)€體的共同點(diǎn)(源節(jié)點(diǎn)和目的節(jié)點(diǎn)除外)的集合；

·從共同節(jié)點(diǎn)的集合中隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為交叉節(jié)點(diǎn)；

·檢查兩個(gè)帶交叉?zhèn)€體在交叉節(jié)點(diǎn)之前和之后的內(nèi)容是否相同。如果相同，則取消此次的交叉操作。

具體的操作過程如下：

(1)設(shè)選取的兩個(gè)待交叉樣本為0.0，3.5，50.9，70.3，62.8，109.5，120.4和0.0，23.1，50.9，25.6，62.8，98.5，120.4，如圖2所示；

(2)兩者重復(fù)節(jié)點(diǎn)為{50.9，62.8}；

(3)隨機(jī)選擇節(jié)點(diǎn)50.9作為交叉節(jié)點(diǎn)；

(4)檢查發(fā)現(xiàn)兩者帶交叉樣本在節(jié)點(diǎn)50.9之前和之后的內(nèi)容均不相同，因此可以進(jìn)行此次操作，交叉之后會(huì)產(chǎn)生新的個(gè)體：

0.0,3.5,50.9,25.6,62.8,98.5,120.4

0.0,23.1,50.9,70.3,62.8,109.5,120.4

圖2 交叉操作

3.5 變異操作

變異操作是對(duì)個(gè)體的某些基因值做變動(dòng)。目的有兩個(gè)，第一使遺傳算法具有局部的隨機(jī)搜索能力,當(dāng)經(jīng)過交叉操作群體已接近最優(yōu)解時(shí),利用變異算子可以加速向最優(yōu)解收斂;第二是使遺傳算法可維持群體的多樣性,以防止早熟現(xiàn)象。變異算子的設(shè)計(jì)也與編碼方法有關(guān),對(duì)于實(shí)數(shù)編碼的TSP問題，可采用逆轉(zhuǎn)變異、對(duì)換變異和插入變異等。逆轉(zhuǎn)變異,也稱倒位變異,是指在個(gè)體編碼中隨機(jī)選擇兩點(diǎn),再將這兩點(diǎn)內(nèi)的字串按反序插入到原位置中。倒位變異考慮了與原邊的鄰接關(guān)系,能將巡回路線上的優(yōu)良基因性能較好地遺傳到下一代,提高尋優(yōu)速度。基于此，該項(xiàng)目具體實(shí)現(xiàn)步驟如下：

(1)隨機(jī)選取一個(gè)個(gè)體作為待變異個(gè)體；

(2)在待變異個(gè)體中隨機(jī)選擇一個(gè)節(jié)點(diǎn)(起點(diǎn)和終點(diǎn)除外)作為待變異節(jié)點(diǎn)；

(3)找到與當(dāng)前待變異節(jié)點(diǎn)直接相連的節(jié)點(diǎn)集合(該集合中不包括起點(diǎn)、終點(diǎn)以及待變異個(gè)體中的節(jié)點(diǎn))；

(4)從節(jié)點(diǎn)集合中隨機(jī)選取一個(gè)節(jié)點(diǎn)作為變異后節(jié)點(diǎn)；

(5)檢查待變異節(jié)點(diǎn)之前和之后的節(jié)點(diǎn)是否與變異后節(jié)點(diǎn)直接相連。若直接相連，則用變異后節(jié)點(diǎn)替代待變異節(jié)點(diǎn)完成變異過程；否則，放棄此次操作，回到第4步，直至將節(jié)點(diǎn)集合中的所有節(jié)點(diǎn)全部選遍。

操作的實(shí)現(xiàn)過程如下：

(1)選擇待變異的個(gè)體為0.0，23.1，50.9，70.3，62.8，109.5，120.4，如圖3所示；

(2)隨機(jī)選擇節(jié)點(diǎn)50.9為變異節(jié)點(diǎn)；

(3)與節(jié)點(diǎn)50.9直接相連的節(jié)點(diǎn)集合為{3.5，31.9，25.6}；

(4)隨機(jī)選擇節(jié)點(diǎn)3.5作為變異后節(jié)點(diǎn)；

(5)經(jīng)過檢查發(fā)現(xiàn)節(jié)點(diǎn)23.1與節(jié)點(diǎn)3.5并不直接相連，所以取消此次變異操作，接著選取節(jié)點(diǎn)31.9作為變異后的節(jié)點(diǎn)，檢查后發(fā)現(xiàn)節(jié)點(diǎn)23.1和節(jié)點(diǎn)31.9、節(jié)點(diǎn)31.9和節(jié)點(diǎn)70.3直接相連，所以此次變異操作是可以的，變異后的新個(gè)體為：0.0，23.1，31.9，70.3，62.8，109.5，120.4。

圖3 變異操作

3.6 終止條件

初始種群規(guī)模相對(duì)較大或者網(wǎng)絡(luò)拓?fù)湟?guī)模相對(duì)較小時(shí)，算法收斂速度則相對(duì)較快?；谶@一原因，算法終止條件選定為“迭代達(dá)到最大世代數(shù)”或者“種群中半數(shù)以上位置被生成的最優(yōu)個(gè)體占據(jù)”。

3.7 算法完整流程

第六步：檢查代數(shù)是否已經(jīng)達(dá)到設(shè)定的值，如果滿足則停止遺傳算法，否則重復(fù)第二步。

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

實(shí)驗(yàn)的網(wǎng)絡(luò)路由模型采用滿足多約束的最小費(fèi)用模型，網(wǎng)絡(luò)規(guī)模為500節(jié)點(diǎn)24 k鏈路，費(fèi)用和時(shí)延皆在[1,10]中隨機(jī)選取。帶寬以1 M為單位，鏈路的帶寬分別在10 G、20 G、30 G、40 G中隨機(jī)選取，隨機(jī)網(wǎng)絡(luò)生成后，隨機(jī)選取源點(diǎn)和宿點(diǎn)并用最短路算法求解最小時(shí)延路的時(shí)延D1和最小費(fèi)用路的時(shí)延D2，取d=(D2-D1)/4。時(shí)延約束取不大于D2+d；請(qǐng)求的業(yè)務(wù)的帶寬要求在1 G、800 M、500 M、50 M中隨機(jī)選取，跳數(shù)約束為不大于80跳。

圖4的實(shí)驗(yàn)結(jié)果是在初始種群規(guī)模為50，交叉變異概率分別為0.5，0.3的情況下生成的，由此說明文中算法對(duì)這種大規(guī)模的約束網(wǎng)絡(luò)模型具有比較快的收斂速度。

圖4 遺傳代數(shù)與最優(yōu)個(gè)體適應(yīng)度值的變化

Dijkstra算法在求解最短路徑的過程中,無論起始節(jié)點(diǎn)距離終點(diǎn)多遠(yuǎn)都需要遍歷整網(wǎng)的拓?fù)洌诠?jié)點(diǎn)數(shù)為n的網(wǎng)絡(luò)中，Dijkstra算法的復(fù)雜度為O(n)。對(duì)于節(jié)點(diǎn)數(shù)和邊數(shù)比較大的大規(guī)模圖，當(dāng)n比較大時(shí),該算法所需計(jì)算機(jī)的時(shí)間資源與空間資源將急劇增加；對(duì)GA算法,路徑長(zhǎng)度主要影響算法的收斂時(shí)間，GA算法的搜索空間大小為路徑的長(zhǎng)度，所以根據(jù)算法的特點(diǎn)決定文中的遺傳算法更適合大規(guī)模網(wǎng)絡(luò)路徑的計(jì)算。圖5是KSP算法和改進(jìn)遺傳算法同時(shí)計(jì)算10條無約束路徑的耗時(shí)，實(shí)驗(yàn)結(jié)果也驗(yàn)證了這個(gè)結(jié)論。

圖5 KSP算法與文中算法的耗時(shí)比較

5 結(jié)束語

文中提出的基于多目標(biāo)多約束的改進(jìn)遺傳算法可以在保證一定性能的前提下，在大規(guī)模網(wǎng)絡(luò)中計(jì)算出符合所有約束的最優(yōu)路徑。并且，該算法主要具有以下特點(diǎn):改進(jìn)了初始路徑的生成方式，顯著提高了算法的搜索效率，可以解決嚴(yán)格下一跳和松散下一跳的約束;實(shí)數(shù)編碼,簡(jiǎn)化了編碼和解碼的操作,省略了復(fù)雜的解碼過程;啟發(fā)式交叉策略,加快了算法收斂的速度；該算法較傳統(tǒng)的K最短路徑算法更適合大規(guī)模網(wǎng)絡(luò)路徑的計(jì)算。