胡小兵，陳樹念，張盈斐，谷升豪

1.中國民航大學(xué) 電子信息與自動(dòng)化學(xué)院，天津 300300

2.中國民航大學(xué) 經(jīng)濟(jì)與管理學(xué)院，天津 300300

3.中國民航大學(xué) 中歐航空工程師學(xué)院，天津 300300

Pareto前沿是解決多目標(biāo)優(yōu)化問題（Multi-Objective Optimization Problem，MOOPs）的關(guān)鍵概念，它與一組Pareto最優(yōu)解[1-4]相關(guān)?，F(xiàn)有的MOOPs方法大多只能找到部分或近似的Pareto前沿，無法得出完整的Pareto前沿。現(xiàn)有的MOOPs方法主要分為三類：重構(gòu)單目標(biāo)函數(shù)法（Aggregate Objective Function，AOF）、約束目標(biāo)函數(shù)法（Constrained Objective Function，COF）和Pareto標(biāo)準(zhǔn)評級法（Pareto-Compliant Ranking，PCR）。AOF和COF均是通過求解單目標(biāo)優(yōu)化問題（Single-Objective Optimization Problem，SOOP），得到原多目標(biāo)優(yōu)化問題的解[2，5-9]。其中AOF是將所有原始目標(biāo)整合成一個(gè)單一的目標(biāo)函數(shù)，而在COF中，只有一個(gè)目標(biāo)函數(shù)被優(yōu)化，而其他目標(biāo)函數(shù)都被當(dāng)作約束條件[10-12]。PCR是通過基于種群進(jìn)化的各種進(jìn)化算法（如遺傳算法、粒子群算法和蟻群算法）和Pareto非占優(yōu)解，生成一個(gè)候選解集，得到多個(gè)Pareto非占優(yōu)解[13-20]。盡管這些方法被廣泛應(yīng)用于解決各種MOOPs，但通常很難判斷它們是否找到了完整的Pareto前沿[11]并且很難證明所得到的離散MOOPs的近似Pareto前沿是否就是理論上的完整Pareto前沿[4]。

文獻(xiàn)[21]介紹了一種在理論和實(shí)踐上都能保證找到離散MOOPs的完整Pareto前沿的確定性方法，即漣漪擴(kuò)散算法（Ripple-Spreading Algorithm，RSA）。簡單來說，文獻(xiàn)[21]中的RSA有兩個(gè)重要步驟：第一步，找出MOOP的每個(gè)單目標(biāo)函數(shù)的前k個(gè)單目標(biāo)最優(yōu)解，假設(shè)給定的MOOP有NObj個(gè)目標(biāo)函數(shù)，那么就有NObj×k個(gè)單目標(biāo)最優(yōu)解；第二步，比較這NObj×k個(gè)單目標(biāo)最優(yōu)解，找出其中所有的Pareto非占優(yōu)解，這些解將確定完整的Pareto前沿。該方法被成功應(yīng)用于新產(chǎn)品開發(fā)項(xiàng)目管理[22]和災(zāi)害風(fēng)險(xiǎn)科學(xué)[23]中的一些多目標(biāo)優(yōu)化問題（MOOPs）的求解。

對于多目標(biāo)路徑優(yōu)化問題（Multi-Objective Path Optimization Problem，MOPOP），已有研究證明，利用標(biāo)號設(shè)置和標(biāo)號校正等方法均能找到完整的Pareto前沿[24-27]。一般而言，這些方法都是針對單目標(biāo)路徑優(yōu)化問題的Dijkstra算法和A*算法的拓展[25]。如文獻(xiàn)[28-30]所示，RSA作為一種新型的、受自然啟發(fā)的、基于多智體的確定性算法，在解決一些復(fù)雜的路徑優(yōu)化問題時(shí)，相對于傳統(tǒng)的Dijkstra算法和A*算法有一定的優(yōu)勢。例如，當(dāng)考慮具有時(shí)間窗或時(shí)變路徑的路網(wǎng)時(shí)，RSA比Dijkstra算法和A*算法表現(xiàn)出更大的靈活性和更高的計(jì)算效率[29-30]。

文獻(xiàn)[21]中求解MOPOP的方法的基本思想與RSA的漣漪擴(kuò)散優(yōu)化原理無關(guān)，文獻(xiàn)[21]中所使用的RSA本身是一種單目標(biāo)路徑優(yōu)化問題的求解方法。對于具有NObj個(gè)目標(biāo)函數(shù)的MOOP，文獻(xiàn)[21]中的RSA至少需要運(yùn)行NObj次，本文在文獻(xiàn)[28]所述的漣漪擴(kuò)散優(yōu)化原理的基礎(chǔ)上，開發(fā)一種可以直接求解MOPOP的完整Pareto前沿的RSA。在這個(gè)新的RSA中，無需計(jì)算前k個(gè)單目標(biāo)最優(yōu)解，只需運(yùn)行一次就可以得到一對多問題中每個(gè)MOPOP完整的Pareto前沿，并且具有理論最優(yōu)性保障。假設(shè)路網(wǎng)有NN個(gè)節(jié)點(diǎn)，如果將文獻(xiàn)[21]的方法應(yīng)用于一對多問題的MOPOPs，需要將文獻(xiàn)[21]的方法應(yīng)用(NN-1)次，即文獻(xiàn)[21]中的RSA需要運(yùn)行至少(NN-1)×NObj次。而新的RSA只需運(yùn)行一次，就可以解決同樣的一對多問題中的所有MOPOPs。

1 MOPOPs的問題描述

假設(shè)一個(gè)路網(wǎng)G(V,E)由節(jié)點(diǎn)集V和鏈接集E組成。這個(gè)路網(wǎng)可以表示為一個(gè)NN×NN的鄰接矩陣A，矩陣A(i,j)=1(i=1,2,…,NN;j=1,2,…,NN)表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j的有向鏈接，當(dāng)A(i,j)=0時(shí)表示不存在鏈接。假設(shè)A(i,i)=0，即不允許存在自連接鏈接。待優(yōu)化的目標(biāo)函數(shù)的個(gè)數(shù)為NObj，則Ck(i,j)(k=1,2,…,NObj)表示與鏈接A(i,j)相關(guān)的、用于計(jì)算第k個(gè)目標(biāo)函數(shù)值的鏈接成本。

在一對一MOPOP中，一對起始點(diǎn)和終點(diǎn)表示為[S,D]，找出從S到D的所有Pareto最優(yōu)路徑方法如下：假設(shè)候選路徑表示為整數(shù)向量p(i)=j，即節(jié)點(diǎn)j是路徑p上第i個(gè)節(jié)點(diǎn)（i=1,2,…,NP；j=1,2,…,NN，NP表示節(jié)點(diǎn)個(gè)數(shù)，包含起始點(diǎn)和終點(diǎn)），p(1)=S，p(NP)=D。由于本研究中不允許出現(xiàn)循環(huán)路徑，所以一個(gè)節(jié)點(diǎn)在一條路徑中最多只能出現(xiàn)一次，即：

當(dāng)i≠j(i=1,2,…,NP;j=1,2,…,NP)，

對于給定的路徑p，根據(jù)每個(gè)目標(biāo)函數(shù)計(jì)算從起始點(diǎn)到終點(diǎn)的總成本為：

其中fk是MOPOP的第k個(gè)目標(biāo)函數(shù)。

則一對一MOPOP可表述為如下最小化問題：

其中p滿足約束條件式（1），并且：

ΩP是連通[S,D]的所有的可能路徑的集合。

上述問題的Pareto最優(yōu)路徑p*具有以下特點(diǎn)：不存在任何p可以使得：

即路徑p*不被任何其他路徑p所Pareto占優(yōu)。這樣一個(gè)p*在目標(biāo)函數(shù)空間里的投影叫做Pareto點(diǎn)。對于上述一對一MOPOP，通常存在一組Pareto最優(yōu)路徑，該集合在目標(biāo)函數(shù)空間中的投影就稱為Pareto前沿。

目前的大多數(shù)方法只能找到MOPOP部分或近似的Pareto前沿，無法確定完整的Pareto前沿。由圖1可見，在雙目標(biāo)路徑優(yōu)化問題中，完整的Pareto前沿與部分、近似的Pareto前沿往往存在差異，如果給決策者提供一個(gè)部分、近似Pareto前沿，決策者將無從知曉是否還存在其他的Pareto最優(yōu)方案（在圖1中，用AOF/COF方法得到的部分Pareto前沿遺漏了最佳的折中解決方案），甚至無法確定提供解決方案的點(diǎn)確實(shí)為Pareto最優(yōu)（在圖1中，PCR方法得到的近似Pareto前沿實(shí)際上有4個(gè)假的Pareto點(diǎn)）。因此，使用部分或近似的Pareto前沿意味著決策者可能無法得到最想要的解決方案。顯然，如果計(jì)算出完整的Pareto前沿，那么決策者在面對MOPOP時(shí)，就可以得到最全面的信息進(jìn)行決策支持。

圖1 近似Pareto前沿和完整Pareto前沿Fig.1 Examples of partial，approximated and completePareto fronts

一對多問題的MOPOP的數(shù)學(xué)描述可看作是NN-1個(gè)一對一MOPOP的總和，即對于給定的起始點(diǎn)S，以路網(wǎng)中的另外NN-1個(gè)節(jié)點(diǎn)中的任一節(jié)點(diǎn)作為終點(diǎn)，構(gòu)造一個(gè)一對一MOPOP。因此，在一個(gè)一對多的MOPOP中，總共有NN-1個(gè)一對一的MOPOP。對每個(gè)一對一的MOPOP都要找出相應(yīng)的完整Pareto前沿。因此，求解一對多的MOPOP需要計(jì)算NN-1個(gè)完整Pareto前沿。

2 求解MOPOP的RSA

2.1 RSA的基本思想

自然界中的漣漪擴(kuò)散現(xiàn)象反映了一個(gè)優(yōu)化原理：漣漪以相同的速度向四周擴(kuò)散，總是最先到達(dá)最近的節(jié)點(diǎn)。這個(gè)簡單的優(yōu)化原理可以很容易地應(yīng)用于有效求解路徑優(yōu)化問題（Path Optimization Problem，POP）。現(xiàn)有的路徑優(yōu)化方法大多是集中式、自上而下、基于邏輯的搜索算法，而RSA卻是一種離散式、自下而上、基于多智體的仿真模型。一般而言，多智體模型具有以下顯著特點(diǎn)：各個(gè)智體按某種規(guī)則各自獨(dú)立行為，單個(gè)智體的行為一般不需要全局性的信息支持；所有智體各自獨(dú)立的微觀行為合在一起就自下而上地涌現(xiàn)出了模型和算法的某種宏觀特性。在RSA中，各個(gè)漣漪和節(jié)點(diǎn)就是智體；每個(gè)漣漪的擴(kuò)散行為和終止行為，以及每個(gè)節(jié)點(diǎn)的漣漪激活行為，都由特定規(guī)則決定，且各個(gè)智體的行為彼此獨(dú)立（例如，兩個(gè)漣漪可以同時(shí)擴(kuò)散，但是這兩個(gè)漣漪的擴(kuò)散狀態(tài)完全獨(dú)立）；漣漪行為和節(jié)點(diǎn)行為不需要全局性的信息；各自獨(dú)立的漣漪行為和節(jié)點(diǎn)行為最后涌現(xiàn)出RSA的宏觀最優(yōu)性保證（即無需全局信息的智體微觀行為最后卻能產(chǎn)生全局最優(yōu)性的路徑）。

RSA模擬了路網(wǎng)中的一次漣漪接力賽。漣漪從起始點(diǎn)開始擴(kuò)散，當(dāng)擴(kuò)散到某一節(jié)點(diǎn)時(shí)，在一定條件下，該節(jié)點(diǎn)可能會(huì)觸發(fā)新的漣漪；當(dāng)漣漪到達(dá)其起始點(diǎn)的所有相鄰節(jié)點(diǎn)時(shí)，漣漪將消失；所有存在的漣漪不斷擴(kuò)散，在空間上更遠(yuǎn)的節(jié)點(diǎn)處觸發(fā)更多的漣漪；當(dāng)滿足終止條件時(shí)，接力賽結(jié)束。RSA由于是一種基于智體的模型，根據(jù)特定問題設(shè)計(jì)微觀智體行為（即節(jié)點(diǎn)如何產(chǎn)生漣漪）和宏觀終止條件（即漣漪接力賽何時(shí)結(jié)束），就可以有效地解決各種POPs以及任何可轉(zhuǎn)化為POP的問題[28]。

2.2 針對MOPOP的RSA設(shè)計(jì)

2.2.1 一對一MOPOP的RSA設(shè)計(jì)

首先，為了找到第1章中定義的一對一MOPOP的可以保證理論最優(yōu)性的完整Pareto前沿，定義了RSA新的微觀智體行為和宏觀終止條件。在針對MOPOP的RSA中，微觀智體行為定義是：當(dāng)某節(jié)點(diǎn)處剛到達(dá)的漣漪不被該節(jié)點(diǎn)處任何先前的Pareto非占優(yōu)漣漪（Pareto Non-Dominated Ripples，PNDR）所Pareto占優(yōu)時(shí)（公式（5）和公式（6）的條件），且漣漪接力賽沒有結(jié)束，那么該節(jié)點(diǎn)將會(huì)觸發(fā)新的漣漪。

基于一對給定的[S,D]的MOPOP的RSA，即一對一的MOPOP，描述如下：將漣漪r從起始點(diǎn)S到達(dá)節(jié)點(diǎn)n的NObj個(gè)路徑成本與節(jié)點(diǎn)n上的每個(gè)PNDR的NObj個(gè)路徑成本進(jìn)行對比，如果漣漪r相對該節(jié)點(diǎn)上之前的PNDRs是Pareto非占優(yōu)的，那么漣漪r就成為節(jié)點(diǎn)n上的一個(gè)新的PNDR。假設(shè)漣漪r∈ΩPNDR(n)（ΩPNDR(n)是在節(jié)點(diǎn)n上的PNDRs），F(xiàn)i(r,n)表示基于第i(i=1,2,…,NObj)個(gè)目標(biāo)函數(shù)的漣漪T(r)（T(r)表示產(chǎn)生漣漪r的漣漪）從S到達(dá)節(jié)點(diǎn)n的路徑成本。則求解一對一MOPOP的完整Pareto前沿的RSA的步驟如下：

步驟1為同時(shí)保證最優(yōu)性和高效性[28]，假設(shè)第h個(gè)目標(biāo)函數(shù)在所有NObj個(gè)目標(biāo)函數(shù)中具有最大值min(Ch(i,j))/max(Ch(i,j))，則設(shè)置漣漪擴(kuò)散速度為：

步驟2令ΩPNDR(n)=?,1≤n≤NN。在起始點(diǎn)S處產(chǎn)生第一個(gè)漣漪，并將當(dāng)前漣漪數(shù)NR設(shè)置為NR=1。設(shè)E(NR)=S（E(r)表示在節(jié)點(diǎn)E(r)處產(chǎn)生漣漪r），R(NR)=0（R(r)表示漣漪r的半徑），SR(NR)=1（SR(r)=0/1表示漣漪r處于非激活狀態(tài)/激活狀態(tài)），T(NR)=0（第一個(gè)漣漪為自觸發(fā)）。讓ΩPNDR(S)={NR}，并設(shè)置Fi(NR,S)=0，i=1,2,…,NObj。設(shè)置當(dāng)前仿真時(shí)間t=0。

步驟3如果r=1,2,…,NR，都有SR(r)=0，即不會(huì)產(chǎn)生新的漣漪，或者如果對于任意SR(r)=1(1≤r≤NR)，漣漪r的當(dāng)前路徑成本已經(jīng)被終點(diǎn)D已有的PNDRs的路徑成本所Pareto占優(yōu)，則轉(zhuǎn)到步驟7。否則，轉(zhuǎn)到步驟4。

步驟4令t=t+1。對于每一個(gè)漣漪r，即若SR(r)=1(1≤r≤NR)，則漣漪r的半徑增加v，即：

步驟5對于任意節(jié)點(diǎn)n，如果至少存在一個(gè)1≤r≤NR，使 得SR(r)=1，而 且A(E(r),n)=1，R(r)≥Ch(E(r),n)，即漣漪r是一個(gè)到達(dá)節(jié)點(diǎn)n的漣漪。那么，先將所有到達(dá)節(jié)點(diǎn)n的漣漪（如果到達(dá)漣漪的數(shù)目超過1個(gè)）進(jìn)行對比，再將到達(dá)漣漪與節(jié)點(diǎn)n上的當(dāng)前PNDRs進(jìn)行對比，找出其中的PNDR。節(jié)點(diǎn)n的每個(gè)到達(dá)漣漪（即漣漪r）將在節(jié)點(diǎn)n觸發(fā)一個(gè)新的PNDR：令NR=NR+1；設(shè)E(NR)=n，T(NR)=r，R(NR)=R(r)-Ch(E(r),n)。當(dāng)n≠D時(shí)，設(shè)SR(NR)=1；否則設(shè)SR(NR)=0，即在終點(diǎn)上觸發(fā)的新漣漪不會(huì)擴(kuò)散；ΩPNDR(n)=ΩPNDR(n)+{NR}；漣漪r從起始點(diǎn)S到達(dá)節(jié)點(diǎn)n的路徑成本記錄為Fi(NR,n)(i=1,2,…,NObj)。

步驟6對于擴(kuò)散中的漣漪r（即SR(r)=1），對任意滿足A(E(r),n)=1的節(jié)點(diǎn)n，如果都滿足以下條件：

則令SR(r)=0，即漣漪消失。轉(zhuǎn)到步驟3。

步驟7對終點(diǎn)D上的每個(gè)PNDR，即如果r∈ΩPNDR(D),1≤r≤NR。則[F1(r,D),F2(r,D),…,FnObj(r,D)]就是一個(gè)Pareto點(diǎn)，漣漪r從S到D的旅行路徑就是一個(gè)Pareto最優(yōu)解。D上的所有PNDRs就確定了完整的Pareto前沿和所有的Pareto最優(yōu)路徑。

圖2給出了一個(gè)RSA求解一對一MOPOP的示例。RSA的漣漪接力賽從S處的漣漪R1開始，在時(shí)刻1到2的時(shí)段內(nèi)，R1依次到達(dá)節(jié)點(diǎn)2、1、3，R1為節(jié)點(diǎn)2、1、3上的第一個(gè)PNDR，并在節(jié)點(diǎn)上觸發(fā)新的漣漪（即R2、R3和R4）。然后R1消失，因?yàn)樗呀?jīng)到達(dá)了S的所有相鄰節(jié)點(diǎn)。

在時(shí)刻2到3的時(shí)段內(nèi)，R2到達(dá)終點(diǎn)D，成為D處的第一個(gè)PNDR，所以路徑S-2-D為一條Pareto最優(yōu)路徑。R3到達(dá)節(jié)點(diǎn)2，將R3到達(dá)節(jié)點(diǎn)2時(shí)的目標(biāo)函數(shù)值和R1到達(dá)節(jié)點(diǎn)2時(shí)的目標(biāo)函數(shù)值進(jìn)行對比，由于R3不被R1占優(yōu)，因此R3成為節(jié)點(diǎn)2處的第二個(gè)PNDR，并在節(jié)點(diǎn)2處觸發(fā)新的漣漪R5。雖然R2在時(shí)刻2到3的時(shí)段內(nèi)到達(dá)節(jié)點(diǎn)1，但是R2被R1占優(yōu)（R1是節(jié)點(diǎn)1的第一個(gè)PNDR），因此R2不能在節(jié)點(diǎn)1觸發(fā)新的漣漪。

圖2 RSA確定一對一MOPOP的完整Pareto前沿的示例Fig.2 Illustration about how complete Pareto front is identified for one-to-one MOPOP by RSA

在時(shí)刻3到4的時(shí)段內(nèi)，R3先到達(dá)D，但由于R3被R2（D處的第一個(gè)PNDR）占優(yōu)，所以R3沒有確定新的Pareto最優(yōu)路徑；R4跟隨R3到達(dá)D，成為D處的第二個(gè)PNDR，因此確定路徑S-3-D為另一條Pareto最優(yōu)路徑；R5跟隨R4到達(dá)D，但被R4占優(yōu)；R4也到達(dá)節(jié)點(diǎn)2，由于在節(jié)點(diǎn)2上R4不被任何之前的PNDR占優(yōu)（即R1、R3），所以R4成為節(jié)點(diǎn)2的第三個(gè)PNDR，并在節(jié)點(diǎn)2處觸發(fā)漣漪R6；R2到達(dá)節(jié)點(diǎn)3，但被節(jié)點(diǎn)3的第一個(gè)PNDR（即R1）占優(yōu)。

在時(shí)刻4到5的時(shí)段內(nèi)，R6到達(dá)D，因?yàn)镽6在節(jié)點(diǎn)D處不被之前的PNDR占優(yōu)（即R2和R4），所以路徑S-3-2-D被確定為新的Pareto最優(yōu)路徑；R6也到達(dá)節(jié)點(diǎn)1，成為節(jié)點(diǎn)1的第二個(gè)PNDR，并在節(jié)點(diǎn)1觸發(fā)R7。

在時(shí)刻6，R7到達(dá)D點(diǎn)，但由于R7被D處已有的PNDRs占優(yōu)，所以R7沒有找到任何新的Pareto最優(yōu)路徑，R7漣漪消失。此時(shí)已沒有活躍漣漪，所以漣漪接力賽結(jié)束。

這時(shí)，根據(jù)終點(diǎn)D的所有PNDRs（即R2、R4和R6）所對應(yīng)的路徑，就可確定出完整的Pareto前沿。

2.2.2 一對多的MOPOP的RSA設(shè)計(jì)

在針對一對一MOPOP的RSA基礎(chǔ)上，只需修改RSA中的微觀智體行為（即不存在終點(diǎn)，每個(gè)PNDR總是會(huì)在節(jié)點(diǎn)觸發(fā)一個(gè)新的漣漪）就可以將其擴(kuò)展用于求解一對多的MOPOP。在一對多的MOPOP中，對于給定起始點(diǎn)S，需要為路網(wǎng)中其他(NN-1)個(gè)節(jié)點(diǎn)中的每個(gè)節(jié)點(diǎn)均找到完整的Pareto前沿。如圖3所示，本小節(jié)給出了針對一對多MOPOP的RSA的步驟細(xì)節(jié)。

步驟1、步驟2與針對一對一MOPOP的RSA的步驟1、步驟2相同。

步驟3如果r=1,2,…,NR，都有SR(r)=0，即不會(huì)產(chǎn)生新的漣漪，則轉(zhuǎn)到步驟7；否則，轉(zhuǎn)到步驟4。

步驟4與針對一對一MOPOP的RSA的步驟4相同。

步驟5對于任意節(jié)點(diǎn)n，如果至少存在一個(gè)1≤r≤NR，使得SR(r)=1，且A(E(r),n)=1，R(r)≥Ch(E(r),n)，即漣漪r是一個(gè)到達(dá)節(jié)點(diǎn)n的漣漪，那么，將節(jié)點(diǎn)n上所有的到達(dá)漣漪（如果到達(dá)漣漪1的數(shù)目超過1個(gè)）進(jìn)行比較，并把到達(dá)漣漪也與節(jié)點(diǎn)n上當(dāng)前的PNDRs進(jìn)行比較，找出其中的PNDR。節(jié)點(diǎn)n的每個(gè)到達(dá)漣漪（即漣漪r）將在節(jié)點(diǎn)n觸發(fā)一個(gè)新的PNDR：令NR=NR+1；設(shè)E(NR)=n，T(NR)=r，R(NR)=R(r)-Ch(E(r),n)；設(shè)SR(NR)=1；ΩPNDR(n)=ΩPNDR(n)+{NR}；漣漪r從起始點(diǎn)S到達(dá)節(jié)點(diǎn)n的路徑成本記錄為Fi(NR,n)(i=1,2,…,NObj)。

圖3 RSA確定一對多MOPOP的完整Pareto前沿的示例Fig.3 Illustration about how complete Pareto front is identified for one-to-all MOPOP by RSA

步驟6與針對一對一MOPOP的RSA的步驟6相同。

步驟7如果漣漪r∈ΩPNDR(n)，1≤r≤NR，則[F1(r,n),F2(r,n),…,FnObj(r,n)]表示節(jié)點(diǎn)n的一個(gè)Pareto點(diǎn)，漣漪r從起始點(diǎn)S到節(jié)點(diǎn)n的旅行路徑為一個(gè)Pareto最優(yōu)解。這樣，每一個(gè)非起點(diǎn)的節(jié)點(diǎn)n上的所有PNDRs確定了該節(jié)點(diǎn)的完整的Pareto前沿和所有的Pareto最優(yōu)路徑。

通過修改RSA，還可以擴(kuò)展到其他一些更復(fù)雜的MOPOPs。許多傳統(tǒng)的路徑優(yōu)化方法（如Dijkstra算法和A*算法）都是集中式的、全局信息和基于邏輯規(guī)則的算法，對全局信息的需求往往意味著針對具體問題的定制化修改是困難的，而RSA是一個(gè)分散的、基于多智體的仿真模型。每個(gè)節(jié)點(diǎn)只需要通過其到達(dá)漣漪的信息來決定其自身產(chǎn)生和傳播新漣漪的行為。RSA通過簡單地修改節(jié)點(diǎn)的行為，可以很容易地應(yīng)用于各種路徑問題（包括一些傳統(tǒng)方法可能難以解決的問題）。例如，當(dāng)涉及到具有時(shí)間窗口或隨時(shí)間動(dòng)態(tài)變化的路網(wǎng)時(shí)，Dijkstra算法和A*算法甚至在單目標(biāo)優(yōu)化問題上也會(huì)遇到困難，通常需要進(jìn)行繁瑣的修改。而RSA只要簡單地引入節(jié)點(diǎn)的漣漪等待和聯(lián)合觸發(fā)行為，就可以處理與時(shí)間窗口和時(shí)變路網(wǎng)相關(guān)的路徑優(yōu)化問題[29-31]。同理，通過對本文的RSA進(jìn)行簡單修改就可以應(yīng)用求解于時(shí)間窗口和時(shí)變路網(wǎng)相關(guān)的MOPOPs。

3 理論分析

對于求解MOPOP的RSA的最優(yōu)性和復(fù)雜性，有如下理論保證。

引理1假設(shè)漣漪到達(dá)一個(gè)節(jié)點(diǎn)，如果這個(gè)漣漪不是該節(jié)點(diǎn)的PNDR，那么任何從S到D包含這個(gè)漣漪的路徑都不是Pareto最優(yōu)路徑。

證明假設(shè)p1為到達(dá)節(jié)點(diǎn)n的某個(gè)漣漪所經(jīng)過的包含NL1個(gè)節(jié)點(diǎn)的路徑，p2為節(jié)點(diǎn)n處一個(gè)PNDR漣漪所經(jīng)過的包含NL2個(gè)節(jié)點(diǎn)的路徑，可得出p1(1)=p2(1)=S，p1(NL1)=p2(NL2)。根據(jù)Pareto最優(yōu)定義，如果經(jīng)過p1的漣漪不是節(jié)點(diǎn)n的PNDR，則可得出fk(p1)≥fk(p2)(k=1,2,…,NObj)，fh(p1)＞fh(p2)(h∈[1,2,…,NObj])。

任何包含p1并連接S和D的路徑可以表示為p4=p1+p3。然后，構(gòu)建一條新的路徑p5=p2+p3，顯然它也連接S和D。根據(jù)目標(biāo)函數(shù)的計(jì)算公式（2）以及Ck(i,j)的非負(fù)性，可得到fk(p4)=fk(p1+p3)≥fk(p2+p3)=fk(p5)(k=1,2,…,NObj)和fh(p4)=fh(p1+p3)＞fh(p2+p3)=fh(p5)。這意味著p5＞p4。所以，任何包含p1的路徑都不是連接S和D的Pareto最優(yōu)路徑。

引理2假設(shè)一條路徑p*是連接S和D的Pareto最優(yōu)路徑，那么當(dāng)漣漪接力賽結(jié)束時(shí)，必然在D處存在一個(gè)被觸發(fā)的漣漪，并且該漣漪的旅行路徑就是這條路徑p*。

證明假設(shè)引理2為假，即p*中必有一個(gè)節(jié)點(diǎn)p*(i)（1＜i≤NL*，NL*表示p*中的節(jié)點(diǎn)數(shù)），經(jīng)過旅行路徑p*(1),p*(2),…,p*(i-1)到達(dá)節(jié)點(diǎn)p*(i)的漣漪不是該節(jié)點(diǎn)的PNDR。那么，根據(jù)引理1，由于p*包含了路徑[p*(1),p*(2),…,p*(i-1)]，所以不是Pareto最優(yōu)的。因此，引理2必為真。

引理1說明PNDRs在中間節(jié)點(diǎn)上排除了從S到D的Pareto最優(yōu)路徑上所有的無關(guān)漣漪，這大大提高了計(jì)算效率，且所有在節(jié)點(diǎn)D上觸發(fā)的漣漪都對應(yīng)著Pareto最優(yōu)路徑，這是最優(yōu)性的必要條件。引理2保證當(dāng)漣漪接力賽結(jié)束時(shí)，連接S和D的每條Pareto最優(yōu)路徑都在D處觸發(fā)了相應(yīng)的漣漪，這是最優(yōu)性的充分條件。因此，在引理1和引理2的基礎(chǔ)上，可得到關(guān)于本文所提出的RSA的最優(yōu)性的如下定理。

定理1在針對MOPOP的RSA中，當(dāng)漣漪接力賽結(jié)束時(shí)，完整的Pareto前沿是由在D點(diǎn)觸發(fā)的所有漣漪決定的。

這里討論的針對一對多MOPOP的RSA的復(fù)雜性，可看作是針對一對一MOPOP的RSA的復(fù)雜性的上界。

定理2在一個(gè)具有NN個(gè)節(jié)點(diǎn)、NL條路徑和給定起始點(diǎn)S的路網(wǎng)中，假定(NN-1)個(gè)節(jié)點(diǎn)中的每個(gè)節(jié)點(diǎn)的完整Pareto前沿平均具有NPP個(gè)Pareto點(diǎn)，那么對于具有NObj個(gè)目標(biāo)函數(shù)的一對多MOPOP，相應(yīng)的RSA的計(jì)算復(fù)雜度約為O(NObj×NL×NPP2)。

證明根據(jù)定理1，可知在漣漪接力賽中平均每個(gè)節(jié)點(diǎn)（S以外的節(jié)點(diǎn)）都有NPP個(gè)PNDRs并觸發(fā)NPP個(gè)漣漪。RSA主要分為三個(gè)基本的計(jì)算步驟：（1）通過恒定的漣漪擴(kuò)散速度增加漣漪的半徑；（2）判斷漣漪是否到達(dá)相鄰節(jié)點(diǎn)；（3）判斷到達(dá)漣漪是否被節(jié)點(diǎn)上已有的PNDR所占優(yōu)。假設(shè)每個(gè)節(jié)點(diǎn)平均有2×NL/NN鏈接，漣漪經(jīng)過一條路徑平均需要NATU個(gè)時(shí)間單位。那么，在該漣漪消失之前平均需要(2×NATU+NObj+NObj×NPP)×2×NL/NN次計(jì)算。由于起始點(diǎn)S只會(huì)產(chǎn)生一個(gè)漣漪，而其他(NN-1)個(gè)節(jié)點(diǎn)平均會(huì)產(chǎn)生NPP個(gè)漣漪，因此，當(dāng)所有的漣漪都消失時(shí)，即漣漪接力賽結(jié)束），需要進(jìn)行(1+(NN-1)×NPP)×(2×NATU+NObj+NObj×NPP)×2×NL/NN次計(jì)算。通常情況下，NPP＞＞NObj并且NObj×NPP?2×NATU，所以，RSA的計(jì)算復(fù)雜度大約為O(NObj×NL×NPP2)。

文獻(xiàn)[21]中的方法求解一對多MOPOP時(shí)，對每一個(gè)非起點(diǎn)的節(jié)點(diǎn)都要進(jìn)行一次一對一MOPOP求解，總共需要運(yùn)行(NN-1)次。每次求解一對一MOPOP平均需要運(yùn)行大約NObj×k2/2次某種求解前k條單目標(biāo)最短路徑的算法；假定用文獻(xiàn)[29]中的求解前k條單目標(biāo)最短路徑的算法求解，則單次運(yùn)行的復(fù)雜度為O(NATU×NL×k)。通常k具有與NPP相似的數(shù)量級，因?yàn)镹PP條Pareto最優(yōu)路徑是從NObj×k條單目標(biāo)最短路徑中通過比較篩選得出的。所以，文獻(xiàn)[21]的方法求解一對多MOPOP的復(fù)雜度約為O(NN×NObj×NATU×NL×NPP3)。顯然，相較文獻(xiàn)[21]的方法而言，本文所提出的新的RSA的計(jì)算復(fù)雜度大大降低了，尤其是在NN和NPP都很大的大規(guī)模網(wǎng)絡(luò)問題中。

表1 平均比較實(shí)驗(yàn)結(jié)果Table I Average comparative experimental results

4 算法測試分析

4.1 比較算法

本文第3章給出了針對MOPOP的RSA的最優(yōu)性的理論證明，在這一章還將給出實(shí)驗(yàn)證明。為此，將新的RSA與文獻(xiàn)[21]的方法、NSGA-II[16]和AOF[4]進(jìn)行對比。其中AOF方法采用不同的權(quán)重組合將NObj個(gè)優(yōu)化目標(biāo)整合成一個(gè)單一目標(biāo)函數(shù)，然后應(yīng)用Dijkstra算法求解單目標(biāo)最短路徑，不同權(quán)重組合下，Dijkstra算法一般會(huì)輸出不同的路徑，AOF基于這些不同的路徑生成Pareto前沿。

4.2 測試方案與性能指標(biāo)

本實(shí)驗(yàn)中采用了文獻(xiàn)[21]的設(shè)置，在測試中使用節(jié)點(diǎn)總數(shù)NN=[25,36,49]、節(jié)點(diǎn)平均鏈接數(shù)NAL=[4,6]和優(yōu)化目標(biāo)數(shù)NObj=[2,3]來調(diào)整實(shí)驗(yàn)的規(guī)模，對每一組[NN,NAL,NObj]值，隨機(jī)生成100個(gè)路網(wǎng)。實(shí)驗(yàn)結(jié)果如表1和圖4所示。在圖4中，上邊的子圖是實(shí)驗(yàn)中的一個(gè)路網(wǎng)(NN=49,NAL=4,NObj=2)，以及用于示例的兩條Pareto最優(yōu)路徑（對于目標(biāo)函數(shù)f1，紅色單點(diǎn)劃線標(biāo)識的為最佳路徑；而對于目標(biāo)函數(shù)f2，紅色雙點(diǎn)劃線則為最佳路徑）；下邊的子圖給出了四種不同方法計(jì)算出的Pareto前沿。

圖4 當(dāng)NN=49時(shí)，用不同方法求解所得Pareto前沿Fig.4 Example of solutions by different methods(NN=49)

4.3 測試結(jié)果與分析

從表1、圖4可以看出：

（1）在所有實(shí)驗(yàn)中，本文提出的新的RSA和文獻(xiàn)[21]中的方法具有完全相同的NPPF（找到Pareto點(diǎn)的個(gè)數(shù)）和RFCPF值（找到完整Pareto前沿的比率，即在路網(wǎng)中某種方法找到的完整Pareto前沿的次數(shù)與節(jié)點(diǎn)數(shù)的比值）。由于文獻(xiàn)[21]中的方法在為MOPOP尋找完整的Pareto前沿時(shí)具有理論最優(yōu)性保障，所以表1和圖4可以作為新的RSA最優(yōu)性的實(shí)驗(yàn)證明。

（2）在平均計(jì)算時(shí)間（秒）（Computational Time，CT）方面，新的RSA算法與AOF方法有相似的CTs，而AOF方法在大多數(shù)測試中計(jì)算效率是高于NSGA-II和文獻(xiàn)[21]中的方法的。

（3）表1和圖4清晰地表明，NSGA-II或AOF方法往往無法找到完整的Pareto前沿。在RFCPF方面，AOF方法由于不能找到位于Pareto前沿非凸部分的Pareto點(diǎn)，所以表現(xiàn)是最糟糕的。雖然有時(shí)AOF方法找到的Pareto點(diǎn)的個(gè)數(shù)多于NSGA-II，但由于絕大多數(shù)Pareto前沿都是非凸的（即使構(gòu)成前沿的Pareto點(diǎn)很少），所以NSGAII找到完整Pareto前沿的可能性反而高于AOF方法。

（4）如圖4所示，NSGA-II通常很難找到真正的Pareto點(diǎn)，即NSGA-II得到的相當(dāng)一部分解通常不是Pareto最優(yōu)的。由于NSGA-II本質(zhì)上是隨機(jī)搜索算法，對于單目標(biāo)優(yōu)化問題也無法保證理論上的最優(yōu)性，因此在求解多目標(biāo)優(yōu)化問題上效果更加糟糕。

（5）就NPPF和RFCPF而言，問題規(guī)模(NN,NAL,NObj)對新的RSA和文獻(xiàn)[21]中的方法沒有影響，因?yàn)檫@兩種方法都有理論保證找到完整的Pareto前沿。但隨著問題規(guī)模變大，AOF和NSGA-II的求解效果會(huì)變差。

（6）就CT而言，問題規(guī)模對所有4種方法都有顯著影響，都會(huì)引起CT增加。不過新的RSA與AOF方法的CTs隨問題規(guī)模變化較慢，而文獻(xiàn)[21]方法和NSGA-II的CTs隨問題規(guī)模增加很快。

4.4 一個(gè)復(fù)雜的一對多MOPOP算例

4.1 節(jié)中實(shí)驗(yàn)的問題規(guī)模很小，即所有的實(shí)驗(yàn)都只是一對一的雙目標(biāo)路徑優(yōu)化問題，最大的路網(wǎng)只有NN=49個(gè)節(jié)點(diǎn)，最復(fù)雜的Pareto前沿只有30多個(gè)Pareto點(diǎn)。本節(jié)求解了一個(gè)NN=400的三目標(biāo)一對多MOOP，其中節(jié)點(diǎn)1為起始點(diǎn)。在NN=400的一對多MOPOP問題中，總共需求解399個(gè)Pareto前沿。本文提出的新的RSA只需在路網(wǎng)上進(jìn)行一次漣漪接力賽，就可以找到全部399個(gè)完整的Pareto前沿，而無需像NSGA-II、AOF和文獻(xiàn)[27]中的方法，必須運(yùn)行399次，才能解決這個(gè)一對多MOPOP問題。新的RSA的計(jì)算結(jié)果顯示，在這399個(gè)完整Pareto前沿中，最復(fù)雜的一個(gè)Pareto前沿具有2 463個(gè)Pareto點(diǎn)（當(dāng)節(jié)點(diǎn)360是終點(diǎn)時(shí)）。

本實(shí)驗(yàn)中只比較了NSGA-II和AOF方法，而沒有采用文獻(xiàn)[21]中的方法，因?yàn)槲墨I(xiàn)[21]中的方法在求解這個(gè)一對多MOPOP問題時(shí)，會(huì)因?yàn)閱栴}規(guī)模太大而耗盡計(jì)算機(jī)內(nèi)存，從而導(dǎo)致宕機(jī)。

圖5的頂部子圖給出了在路網(wǎng)中選擇不同節(jié)點(diǎn)作為終點(diǎn)（節(jié)點(diǎn)1始終為起始點(diǎn)）時(shí)，不同方法找到的Pareto點(diǎn)的個(gè)數(shù)?？梢钥闯?，當(dāng)一個(gè)完整Pareto前沿具有很多Pareto點(diǎn)時(shí)，NSGA-II和AOF方法通常只找到很小比例的真正Pareto點(diǎn)。圖5左下的子圖比較了在節(jié)點(diǎn)360為終點(diǎn)時(shí)（即最復(fù)雜的情況下），AOF方法與RSA所找出的Pareto點(diǎn)的差異，右下的子圖比較了RSA和NSGA-II在相同的條件下找出的Pareto點(diǎn)的差異。實(shí)際上，在節(jié)點(diǎn)360為終點(diǎn)的情況下，NSGA-II沒有找到任何真正的Pareto點(diǎn)。

在計(jì)算效率方面，本文所提出的RSA運(yùn)行一次找到399個(gè)Pareto前沿只需大約500 s。文獻(xiàn)[21]中的方法在運(yùn)行數(shù)天后只會(huì)宕機(jī)。NSGA-II通常耗費(fèi)數(shù)小時(shí)，但最終會(huì)產(chǎn)生許多假的Pareto點(diǎn)。AOF方法耗時(shí)約400 s，但如圖5所示，它只找到了很小比例的真正的Pareto點(diǎn)。

5 結(jié)束語

現(xiàn)有的RSA只針對SOOP，如文獻(xiàn)[21-23]求解MOOP所使用的RSA只能求解前k個(gè)單目標(biāo)最優(yōu)解。本文首次提出了一種真正針對MOPOP的RSA算法，僅通過一次漣漪接力賽就可以計(jì)算出完整的Pareto前沿。新的RSA是基于多智體的自下向上的仿真模型，通過提出PNDR的概念并由之定義微觀智體的漣漪激發(fā)和擴(kuò)散行為，在漣漪接力賽的宏觀層面上就可以表現(xiàn)出完整的Pareto前沿。新的RSA具有求解出完整Pareto前沿的理論保障，因此可作為研究MOOP的基準(zhǔn)方法來衡量其他離散MOOP方法（如遺傳算法和粒子群算法）性能。未來的工作可以放在分布式并行RSA的設(shè)計(jì)上，并將其應(yīng)用于可轉(zhuǎn)換為MOPOP的各種實(shí)際多目標(biāo)優(yōu)化問題的求解。例如在針對突發(fā)事件的應(yīng)急資源配置的問題中對應(yīng)急路徑的規(guī)劃，以應(yīng)急路徑的時(shí)效性（即行程時(shí)間）和可靠性（即行程時(shí)間可靠度）為雙目標(biāo)建立模型，對最優(yōu)路徑進(jìn)行搜索。在多目標(biāo)無人機(jī)路徑規(guī)劃問題中，以路徑長度和路徑受威脅程度為優(yōu)化目標(biāo)，建立無人機(jī)路徑規(guī)劃的雙目標(biāo)優(yōu)化模型，求解從起始點(diǎn)到目的地路徑的Pareto前沿。然后就本文中的RSA在找到Pareto點(diǎn)的個(gè)數(shù)、找到完整Pareto前沿的比率和平均計(jì)算時(shí)間三個(gè)方面的測試結(jié)果與其他算法的性能進(jìn)行比較，以驗(yàn)證新方法的有效性和高效性。

圖5 當(dāng)NN=400時(shí)的一對多MOPOPFig.5 Example of one-to-all MOPOP(NN=400)