求解多目標路徑優化問題的漣漪擴散算法

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

1.中國民航大學 電子信息與自動化學院，天津 300300

2.中國民航大學 經濟與管理學院，天津 300300

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

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

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

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

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

1 MOPOPs的問題描述

假設一個路網G(V,E)由節點集V和鏈接集E組成。這個路網可以表示為一個NN×NN的鄰接矩陣A，矩陣A(i,j)=1(i=1,2,…,NN;j=1,2,…,NN)表示從節點i到節點j的有向鏈接，當A(i,j)=0時表示不存在鏈接。假設A(i,i)=0，即不允許存在自連接鏈接。待優化的目標函數的個數為NObj，則Ck(i,j)(k=1,2,…,NObj)表示與鏈接A(i,j)相關的、用于計算第k個目標函數值的鏈接成本。

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

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

對于給定的路徑p，根據每個目標函數計算從起始點到終點的總成本為：

其中fk是MOPOP的第k個目標函數。

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

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

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

上述問題的Pareto最優路徑p*具有以下特點：不存在任何p可以使得：

即路徑p*不被任何其他路徑p所Pareto占優。這樣一個p*在目標函數空間里的投影叫做Pareto點。對于上述一對一MOPOP，通常存在一組Pareto最優路徑，該集合在目標函數空間中的投影就稱為Pareto前沿。

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

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

一對多問題的MOPOP的數學描述可看作是NN-1個一對一MOPOP的總和，即對于給定的起始點S，以路網中的另外NN-1個節點中的任一節點作為終點，構造一個一對一MOPOP。因此，在一個一對多的MOPOP中，總共有NN-1個一對一的MOPOP。對每個一對一的MOPOP都要找出相應的完整Pareto前沿。因此，求解一對多的MOPOP需要計算NN-1個完整Pareto前沿。

2 求解MOPOP的RSA

2.1 RSA的基本思想

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

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

2.2 針對MOPOP的RSA設計

2.2.1 一對一MOPOP的RSA設計

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

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

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

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

步驟3如果r=1,2,…,NR，都有SR(r)=0，即不會產生新的漣漪，或者如果對于任意SR(r)=1(1≤r≤NR)，漣漪r的當前路徑成本已經被終點D已有的PNDRs的路徑成本所Pareto占優，則轉到步驟7。否則，轉到步驟4。

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

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

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

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

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

圖2給出了一個RSA求解一對一MOPOP的示例。RSA的漣漪接力賽從S處的漣漪R1開始，在時刻1到2的時段內，R1依次到達節點2、1、3，R1為節點2、1、3上的第一個PNDR，并在節點上觸發新的漣漪（即R2、R3和R4）。然后R1消失，因為它已經到達了S的所有相鄰節點。

在時刻2到3的時段內，R2到達終點D，成為D處的第一個PNDR，所以路徑S-2-D為一條Pareto最優路徑。R3到達節點2，將R3到達節點2時的目標函數值和R1到達節點2時的目標函數值進行對比，由于R3不被R1占優，因此R3成為節點2處的第二個PNDR，并在節點2處觸發新的漣漪R5。雖然R2在時刻2到3的時段內到達節點1，但是R2被R1占優（R1是節點1的第一個PNDR），因此R2不能在節點1觸發新的漣漪。

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

在時刻3到4的時段內，R3先到達D，但由于R3被R2（D處的第一個PNDR）占優，所以R3沒有確定新的Pareto最優路徑；R4跟隨R3到達D，成為D處的第二個PNDR，因此確定路徑S-3-D為另一條Pareto最優路徑；R5跟隨R4到達D，但被R4占優；R4也到達節點2，由于在節點2上R4不被任何之前的PNDR占優（即R1、R3），所以R4成為節點2的第三個PNDR，并在節點2處觸發漣漪R6；R2到達節點3，但被節點3的第一個PNDR（即R1）占優。

在時刻4到5的時段內，R6到達D，因為R6在節點D處不被之前的PNDR占優（即R2和R4），所以路徑S-3-2-D被確定為新的Pareto最優路徑；R6也到達節點1，成為節點1的第二個PNDR，并在節點1觸發R7。

在時刻6，R7到達D點，但由于R7被D處已有的PNDRs占優，所以R7沒有找到任何新的Pareto最優路徑，R7漣漪消失。此時已沒有活躍漣漪，所以漣漪接力賽結束。

這時，根據終點D的所有PNDRs（即R2、R4和R6）所對應的路徑，就可確定出完整的Pareto前沿。

2.2.2 一對多的MOPOP的RSA設計

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

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

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

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

步驟5對于任意節點n，如果至少存在一個1≤r≤NR，使得SR(r)=1，且A(E(r),n)=1，R(r)≥Ch(E(r),n)，即漣漪r是一個到達節點n的漣漪，那么，將節點n上所有的到達漣漪（如果到達漣漪1的數目超過1個）進行比較，并把到達漣漪也與節點n上當前的PNDRs進行比較，找出其中的PNDR。節點n的每個到達漣漪（即漣漪r）將在節點n觸發一個新的PNDR：令NR=NR+1；設E(NR)=n，T(NR)=r，R(NR)=R(r)-Ch(E(r),n)；設SR(NR)=1；ΩPNDR(n)=ΩPNDR(n)+{NR}；漣漪r從起始點S到達節點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)]表示節點n的一個Pareto點，漣漪r從起始點S到節點n的旅行路徑為一個Pareto最優解。這樣，每一個非起點的節點n上的所有PNDRs確定了該節點的完整的Pareto前沿和所有的Pareto最優路徑。

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

3 理論分析

對于求解MOPOP的RSA的最優性和復雜性，有如下理論保證。

引理1假設漣漪到達一個節點，如果這個漣漪不是該節點的PNDR，那么任何從S到D包含這個漣漪的路徑都不是Pareto最優路徑。

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

任何包含p1并連接S和D的路徑可以表示為p4=p1+p3。然后，構建一條新的路徑p5=p2+p3，顯然它也連接S和D。根據目標函數的計算公式（2）以及Ck(i,j)的非負性，可得到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最優路徑。

引理2假設一條路徑p*是連接S和D的Pareto最優路徑，那么當漣漪接力賽結束時，必然在D處存在一個被觸發的漣漪，并且該漣漪的旅行路徑就是這條路徑p*。

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

引理1說明PNDRs在中間節點上排除了從S到D的Pareto最優路徑上所有的無關漣漪，這大大提高了計算效率，且所有在節點D上觸發的漣漪都對應著Pareto最優路徑，這是最優性的必要條件。引理2保證當漣漪接力賽結束時，連接S和D的每條Pareto最優路徑都在D處觸發了相應的漣漪，這是最優性的充分條件。因此，在引理1和引理2的基礎上，可得到關于本文所提出的RSA的最優性的如下定理。

定理1在針對MOPOP的RSA中，當漣漪接力賽結束時，完整的Pareto前沿是由在D點觸發的所有漣漪決定的。

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

定理2在一個具有NN個節點、NL條路徑和給定起始點S的路網中，假定(NN-1)個節點中的每個節點的完整Pareto前沿平均具有NPP個Pareto點，那么對于具有NObj個目標函數的一對多MOPOP，相應的RSA的計算復雜度約為O(NObj×NL×NPP2)。

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

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

表1 平均比較實驗結果Table I Average comparative experimental results

4 算法測試分析

4.1 比較算法

本文第3章給出了針對MOPOP的RSA的最優性的理論證明，在這一章還將給出實驗證明。為此，將新的RSA與文獻[21]的方法、NSGA-II[16]和AOF[4]進行對比。其中AOF方法采用不同的權重組合將NObj個優化目標整合成一個單一目標函數，然后應用Dijkstra算法求解單目標最短路徑，不同權重組合下，Dijkstra算法一般會輸出不同的路徑，AOF基于這些不同的路徑生成Pareto前沿。

4.2 測試方案與性能指標

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

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

4.3 測試結果與分析

從表1、圖4可以看出：

（1）在所有實驗中，本文提出的新的RSA和文獻[21]中的方法具有完全相同的NPPF（找到Pareto點的個數）和RFCPF值（找到完整Pareto前沿的比率，即在路網中某種方法找到的完整Pareto前沿的次數與節點數的比值）。由于文獻[21]中的方法在為MOPOP尋找完整的Pareto前沿時具有理論最優性保障，所以表1和圖4可以作為新的RSA最優性的實驗證明。

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

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

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

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

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

4.4 一個復雜的一對多MOPOP算例

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

本實驗中只比較了NSGA-II和AOF方法，而沒有采用文獻[21]中的方法，因為文獻[21]中的方法在求解這個一對多MOPOP問題時，會因為問題規模太大而耗盡計算機內存，從而導致宕機。

圖5的頂部子圖給出了在路網中選擇不同節點作為終點（節點1始終為起始點）時，不同方法找到的Pareto點的個數。可以看出，當一個完整Pareto前沿具有很多Pareto點時，NSGA-II和AOF方法通常只找到很小比例的真正Pareto點。圖5左下的子圖比較了在節點360為終點時（即最復雜的情況下），AOF方法與RSA所找出的Pareto點的差異，右下的子圖比較了RSA和NSGA-II在相同的條件下找出的Pareto點的差異。實際上，在節點360為終點的情況下，NSGA-II沒有找到任何真正的Pareto點。

在計算效率方面，本文所提出的RSA運行一次找到399個Pareto前沿只需大約500 s。文獻[21]中的方法在運行數天后只會宕機。NSGA-II通常耗費數小時，但最終會產生許多假的Pareto點。AOF方法耗時約400 s，但如圖5所示，它只找到了很小比例的真正的Pareto點。

5 結束語

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

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