路 輝,王詩(shī)琪,申澤鵬

(北京航空航天大學(xué) 電子信息工程學(xué)院，北京 100191)

自動(dòng)測(cè)試系統(tǒng)因具有高速度、高精度、多功能、多參數(shù)和寬測(cè)量范圍的優(yōu)點(diǎn)在航空航天、汽車、移動(dòng)通信等領(lǐng)域發(fā)揮著越來(lái)越重要的作用[1]。測(cè)試任務(wù)調(diào)度問(wèn)題(test task scheduling problem，TTSP)是自動(dòng)測(cè)試系統(tǒng)的關(guān)鍵技術(shù)之一，主要解決如何合理安排測(cè)試任務(wù)順序和測(cè)試資源分配，以達(dá)到測(cè)試系統(tǒng)效率最大化、測(cè)試平均負(fù)荷最小等目標(biāo)[2-3]的問(wèn)題。TTSP問(wèn)題是典型的多目標(biāo)組合優(yōu)化問(wèn)題，真實(shí)前沿點(diǎn)較少且比較分散，存在多個(gè)決策空間的解集對(duì)應(yīng)同一個(gè)目標(biāo)空間的帕累托前沿(Pareto front，PF)，具有多模問(wèn)題的特性[4]。本文通過(guò)對(duì)TTSP多目標(biāo)多模特性的分析，研究相應(yīng)的求解方法，為測(cè)試任務(wù)調(diào)度問(wèn)題的研究提供補(bǔ)充。

2016年，Liang等將有多個(gè)決策空間中的解對(duì)應(yīng)于目標(biāo)空間同一個(gè)帕累托前沿的多目標(biāo)問(wèn)題稱為多目標(biāo)多模優(yōu)化問(wèn)題[5]。在現(xiàn)實(shí)生活中，路徑規(guī)劃問(wèn)題、背包問(wèn)題和調(diào)度問(wèn)題等都可以抽象為多目標(biāo)多模優(yōu)化問(wèn)題[6-8]。對(duì)于不同領(lǐng)域的實(shí)際問(wèn)題，首先需要從問(wèn)題特性的角度出發(fā)，從理論層面分析問(wèn)題是否具有多模特性，設(shè)計(jì)與問(wèn)題耦合程度最高的算法進(jìn)而解決問(wèn)題。目前在多模特性的理論分析方面，尚沒(méi)有一套有效證明問(wèn)題多模特性的方法。本文從時(shí)間序列相似性分析的角度出發(fā)，通過(guò)動(dòng)態(tài)時(shí)間彎曲算法(dynamic time warping，DTW)，計(jì)算不同決策空間中的解(Pareto-optimal set，PS)對(duì)應(yīng)目標(biāo)空間中PF之間的相似性，相似性越高，問(wèn)題的多模特性就越強(qiáng)。

在明確問(wèn)題多模特性之后，需要根據(jù)問(wèn)題特性，提出相應(yīng)的多目標(biāo)多模優(yōu)化方法。多目標(biāo)問(wèn)題的特點(diǎn)在于解在目標(biāo)空間和決策空間中的分布是不同的。目標(biāo)空間中距離相近的解在決策空間中可能并不相近。在現(xiàn)存大多數(shù)多目標(biāo)優(yōu)化算法中，只考慮了目標(biāo)空間解的分布，在目標(biāo)空間進(jìn)行擁擠距離排序時(shí)，會(huì)淘汰距離相近的、被支配的解，即使這些解在決策空間中可能并不相近。這就讓決策空間解多樣性的保持非常困難[5]。若要使算法可以解決多目標(biāo)多模優(yōu)化問(wèn)題，找到多個(gè)對(duì)應(yīng)于目標(biāo)空間的同一個(gè)帕累托前沿的決策空間中的解[9],保證解在決策空間的多樣性，就需要添加一定的策略。

現(xiàn)有算法大多數(shù)采取以下3種策略：(1)引入小生境策略以保證決策空間與目標(biāo)空間解的多樣性。如Yue等在MOPSO基礎(chǔ)上引入環(huán)形拓?fù)洳呗裕孕纬煞€(wěn)定的小生境[10]。Liang等將小生境策略引入NSGA-Ⅱ算法中以保證決策空間中解的多樣性，提出DN-NSGAⅡ算法[5]。Liang等利用自組織地圖網(wǎng)絡(luò)聚類相似的解，在決策空間產(chǎn)生小生境[11]。李國(guó)森等引入?yún)⒖键c(diǎn)策略，利用佳點(diǎn)集原理[12]產(chǎn)生均勻分布的參考點(diǎn)，每個(gè)參考點(diǎn)與其附近的粒子構(gòu)成小生境[13]。Liu等利用收斂性和多樣性雙檔案集，在多樣性檔案集中采取聚類策略以保證算法多樣性[14]。(2)加入指標(biāo)控制決策空間中解的分布。不再將目標(biāo)空間中解的擁擠度作為淘汰解的唯一評(píng)價(jià)。如Deb等提出的Omni-optimizer算法將目標(biāo)空間用于擁擠距離排序的指標(biāo)CD(crowding distance)引入決策空間中[15]，用以保持決策空間的多樣性。Liang等將先對(duì)決策空間中的解進(jìn)行非支配排序，然后進(jìn)行擁擠距離排序[5]。Yue等在決策空間擁擠度距離排序的基礎(chǔ)上提出特殊擁擠度距離這一概念(special crowding distance，SCD)，綜合考慮決策空間和目標(biāo)空間解的擁擠度排序[10]。(3)加入變異操作，防止粒子早熟，增加算法多樣性。如文獻(xiàn)[13]所提出的RPMOPSO算法，當(dāng)過(guò)多粒子集中于某一個(gè)參考點(diǎn)附近時(shí)，加入變異策略讓粒子飛出所在區(qū)域。Dong等在粒子群算法中加入全局自適應(yīng)突變選擇算子(AMS)，以提高粒子的搜索能力[16]。這些算法在目標(biāo)空間表現(xiàn)相似，因?yàn)樵谶M(jìn)行非支配排序時(shí)都考慮了目標(biāo)空間中解的分布，但在決策空間表現(xiàn)各有差別，且這些算法沒(méi)有進(jìn)行實(shí)際大規(guī)模問(wèn)題的測(cè)試。

綜上，目前研究在理論層面缺少對(duì)于問(wèn)題是否具有多模特性的證明，從而無(wú)法針對(duì)問(wèn)題的特性選擇合適的優(yōu)化算法。在算法層面，目前存在的多目標(biāo)多模優(yōu)化算法有幾個(gè)缺點(diǎn)：一是對(duì)于小生境策略，一般需要很多復(fù)雜的參數(shù)(如小生境半徑)，而算法結(jié)果對(duì)于這些參數(shù)的設(shè)置非常敏感，在對(duì)問(wèn)題無(wú)先驗(yàn)知識(shí)的情況下對(duì)參數(shù)進(jìn)行合適的設(shè)置比較困難；二是很多算法無(wú)法做到同時(shí)考慮決策空間的擁擠距離和目標(biāo)空間的擁擠距離，因此無(wú)法同時(shí)保持在決策空間以及目標(biāo)空間的多樣性，并且針對(duì)維度更大、PS更多的大規(guī)模的問(wèn)題表現(xiàn)不佳；三是現(xiàn)存的算法缺少對(duì)于維度大、離散程度大、真實(shí)前沿少的實(shí)際問(wèn)題的測(cè)試。

本文主要包含以下兩方面工作。第一，提出分析問(wèn)題多模特性的方法，突破實(shí)際問(wèn)題多模特性的分析和證明，形成多模特性的證明方法。其主要思路是直接利用多目標(biāo)多模的概念，即證明決策空間中不同的PS對(duì)應(yīng)的PF之間的相似性，由于動(dòng)態(tài)時(shí)間彎曲可以不受兩個(gè)被比較序列點(diǎn)數(shù)必須一致的限制，能有效處理兩個(gè)序列某一維度上發(fā)生平移、伸縮后相似性比較的問(wèn)題，因此將其引入多模特性分析領(lǐng)域，用于比較不同PF之間的相似性，從而證明問(wèn)題的多模特性。第二，提出基于區(qū)域遷移的多目標(biāo)粒子群優(yōu)化算法(RMMOPSO)，引入多種群策略、區(qū)域遷移策略、精英池策略和淘汰策略。多個(gè)子種群在決策空間中并行搜索，將迭代過(guò)程分為搜索階段和轉(zhuǎn)移階段。在搜索階段時(shí)子種群中粒子向本種群全局最優(yōu)點(diǎn)收斂；在轉(zhuǎn)移階段，按順序交換各子種群全局最優(yōu)點(diǎn)，使子種群搜索區(qū)域發(fā)生轉(zhuǎn)移，從而每個(gè)子種群都可以搜索到完整決策空間。算法兼具多樣性與收斂性，并且可以得到多個(gè)對(duì)應(yīng)于同一個(gè)PF的不同PS。算法的優(yōu)勢(shì)在于不需要復(fù)雜的參數(shù)設(shè)置，不需要問(wèn)題的先驗(yàn)知識(shí)，并且可以兼顧決策空間和目標(biāo)空間的多樣性，對(duì)于大規(guī)模問(wèn)題和實(shí)際問(wèn)題也具有較好的效果。

1 測(cè)試任務(wù)調(diào)度問(wèn)題

1.1 測(cè)試任務(wù)調(diào)度問(wèn)題的描述

對(duì)于測(cè)試任務(wù)調(diào)度問(wèn)題來(lái)說(shuō)，測(cè)試過(guò)程可能有多個(gè)測(cè)試任務(wù)，這些測(cè)試任務(wù)可能有先后要求，一個(gè)測(cè)試任務(wù)可能存在多種測(cè)試方案，每一種測(cè)試方案所占用的測(cè)試資源也不同。TTSP所要解決的，是合理安排n個(gè)測(cè)試任務(wù)到m個(gè)測(cè)試資源上，確定測(cè)試任務(wù)的測(cè)試順序和每個(gè)測(cè)試任務(wù)的測(cè)試方案，以達(dá)到一定的設(shè)計(jì)目標(biāo)[17]。這些目標(biāo)可能是測(cè)試時(shí)間最短、資源利用率最大、負(fù)載耗能最少等，一般選擇的兩個(gè)目標(biāo)是f1(測(cè)試時(shí)間最小)以及f2(各步平均負(fù)荷最小)[1]。

1.2 編碼方法

編碼是將問(wèn)題轉(zhuǎn)化為數(shù)學(xué)模型，并進(jìn)行求解的基礎(chǔ)。染色體編碼是將所研究的問(wèn)題的解用染色體的形式來(lái)表達(dá)，利用染色體可以進(jìn)行變異交叉等操作。本文采用文獻(xiàn)[18]所提出的IES(integrated encoding scheme)編碼方式，將測(cè)試任務(wù)排序和測(cè)試方案的選擇體現(xiàn)在同一條染色體上，提高編碼效率，降低復(fù)雜性。

基本思想是利用決策變量不同維度之間的大小關(guān)系表示測(cè)試任務(wù)順序，用決策變量的值來(lái)表示所采用的測(cè)試方案。一個(gè)n×mTTSP實(shí)例的決策空間有n維，每一維都是[0,1]之間的一個(gè)數(shù)。n維決策空間中的一個(gè)解表示為：(x1,x2,…,xn),xl∈[0,1]，將x1,x2,…,xn從小到大進(jìn)行排序，xl的排序序號(hào)就是其所對(duì)應(yīng)的測(cè)試任務(wù)號(hào)。接下來(lái)，根據(jù)決策變量xl的值和其所對(duì)應(yīng)的測(cè)試任務(wù)ti，依據(jù)式(1)計(jì)算出ti所采用的測(cè)試方案：

(1)

其中ki是測(cè)試任務(wù)ti所對(duì)應(yīng)的測(cè)試方案總數(shù)。表1給出了一個(gè)4×4 TTSP實(shí)例的編碼過(guò)程。

表1 4×4 TTSP實(shí)例編碼

1.3 TTSP的多模特性

在之前的研究工作中，課題組成員提出利用空間適應(yīng)度地形對(duì)不同規(guī)模TTSP實(shí)例的多模特性進(jìn)行分析的方法，對(duì)于較小規(guī)模TTSP實(shí)例(如4×5、6×8)，采取遍歷的方法，對(duì)于遍歷得到的數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析，并給出空間適應(yīng)度地形，來(lái)分析問(wèn)題的多模特性[4]。表2給出了4×5與6×8 TTSP實(shí)例解空間的統(tǒng)計(jì)結(jié)果,其中:NsoluD表示決策空間中解的數(shù)量;NsoluO表示目標(biāo)空間中解的數(shù)量;RD/O=NsoluD/NsoluO，表示平均每個(gè)目標(biāo)空間中的解會(huì)對(duì)應(yīng)多少個(gè)決策空間中的解;NpareO表示目標(biāo)空間中帕累托前沿中解的數(shù)量;NpareD表示每個(gè)帕累托前沿在決策空間對(duì)應(yīng)解的數(shù)量。4×5與6×8 TTSP實(shí)例所對(duì)應(yīng)的RD/O值均大于1，即平均每個(gè)目標(biāo)空間中的解會(huì)對(duì)應(yīng)多個(gè)決策空間中的解。且NpareD比NpareO大很多，也說(shuō)明目標(biāo)空間中帕累托前沿對(duì)應(yīng)著多個(gè)決策空間中的解。

表2 小規(guī)模TTSP實(shí)例解空間統(tǒng)計(jì)結(jié)果

圖1給出了4×5與6×8 TTSP實(shí)例的空間適應(yīng)度地形，可以看出兩者的空間適應(yīng)度地形存在很多平坦區(qū)域，即有很多不同的任務(wù)排序和方案選擇對(duì)應(yīng)于同一個(gè)適應(yīng)度值，這也反映出TTSP問(wèn)題的多模特性。

圖1 小規(guī)模TTSP實(shí)例空間適應(yīng)度地形

對(duì)于大規(guī)模TTSP問(wèn)題，因其解空間巨大，無(wú)法進(jìn)行遍歷，因此采用隨機(jī)區(qū)域采樣的方法獲得采樣點(diǎn)，對(duì)采樣點(diǎn)進(jìn)行空間適應(yīng)度地形分析，結(jié)果如圖2所示(以20×8規(guī)模為例)。

圖2 20×8 TTSP實(shí)例隨即區(qū)域采樣空間適應(yīng)度地形

從圖2可以看出，對(duì)于大規(guī)模TTSP問(wèn)題，不同區(qū)域內(nèi)適應(yīng)度地形可能是不一樣的，但同樣表現(xiàn)出不同任務(wù)排序和方案選擇對(duì)應(yīng)于同一個(gè)適應(yīng)度值的情況，因此大規(guī)模TTSP問(wèn)題也具有很強(qiáng)的多模特性。

2 TTSP多目標(biāo)多模特性分析

從空間適應(yīng)度地形可以對(duì)TTSP問(wèn)題是否具有多模特性進(jìn)行分析，但如何有效證明問(wèn)題特性是需要解決的問(wèn)題。只有明確問(wèn)題的多模特性，才能更好根據(jù)問(wèn)題特性選擇合適的算法或參數(shù)，達(dá)到效率高、魯棒性好的目標(biāo)，做到問(wèn)題與算法的高度耦合[4]。本文針對(duì)這一問(wèn)題，提出利用動(dòng)態(tài)時(shí)間彎曲來(lái)計(jì)算不同PS對(duì)應(yīng)的PF之間的相似性，用于證明問(wèn)題的多模特性。

2.1 多目標(biāo)多模特性描述

不失一般性，將多目標(biāo)問(wèn)題描述如下：

(2)

多目標(biāo)多模優(yōu)化問(wèn)題可能存在兩個(gè)或更多PS對(duì)應(yīng)于同一個(gè)PF，如圖3所示(以目標(biāo)空間和決策空間為二維為例)。

圖3 多目標(biāo)問(wèn)題多模特性示意圖

可見(jiàn)，多目標(biāo)優(yōu)化問(wèn)題多模特性證明的要點(diǎn)，就是證明決策空間存在多個(gè)不同的PS，對(duì)應(yīng)于目標(biāo)空間同一個(gè)PF。本文提出利用動(dòng)態(tài)時(shí)間彎曲算法來(lái)證明問(wèn)題的多模特性。

2.2 基于動(dòng)態(tài)時(shí)間彎曲算法的多模特性分析方法

2.2.1 動(dòng)態(tài)時(shí)間彎曲 動(dòng)態(tài)時(shí)間彎曲[19]是在時(shí)間序列數(shù)據(jù)挖掘領(lǐng)域，利用距離比較時(shí)間序列相似性的算法[20]。相對(duì)于傳統(tǒng)計(jì)算兩個(gè)時(shí)間序列歐氏距離的方法，DTW可以有效處理時(shí)間序列沿時(shí)間軸伸縮、平移等變形的問(wèn)題，找到兩個(gè)時(shí)間序列之間最相近的點(diǎn)進(jìn)行匹配，能更好反映兩個(gè)時(shí)間序列之間的相似性，并且不需要兩個(gè)時(shí)間序列的長(zhǎng)度完全相等，具有較高的魯棒性[21]。

如圖4所示，單純的歐式距離是將兩個(gè)時(shí)間序列點(diǎn)與點(diǎn)之間的歐式距離進(jìn)行累加，根據(jù)得到的距離和的大小來(lái)判斷兩個(gè)時(shí)間序列的相似性。顯然這樣的方法在時(shí)間序列沿時(shí)間軸發(fā)生平移或伸縮時(shí)是不準(zhǔn)確的。

圖4 歐式距離求時(shí)間序列相似性

DTW利用動(dòng)態(tài)規(guī)劃的思想，構(gòu)造兩個(gè)序列之間的距離陣，在距離矩陣中找到一個(gè)最佳匹配路徑進(jìn)行匹配，這個(gè)最佳匹配路徑通過(guò)的距離矩陣中的元素累加和一定是最少的[22]。

假設(shè)時(shí)間序列P={p1,p2,…,pm}和Q={q1,q2,…,qn}，構(gòu)造一個(gè)m×n的矩陣D(如圖5a所示)。矩陣D中元素d(pi,qj)代表pi和qj間的距離

圖5 時(shí)間序列DTW匹配路徑與匹配結(jié)果

(3)

N為決策空間維度。

彎曲路徑W需要滿足:(1) 邊界約束。彎曲路徑W必須起始于(1,1)，終止于(m,n)，即P的第一個(gè)點(diǎn)必須和Q的第一個(gè)點(diǎn)匹配，P的最后一個(gè)點(diǎn)必須和Q的最后一個(gè)點(diǎn)匹配。(2) 單調(diào)性約束。彎曲路徑元素wk(i,j)和其相鄰元素wk+1(i′,j′)必須滿足i

(4)

K為彎曲路徑中元素個(gè)數(shù)。DTW的求解采用了動(dòng)態(tài)規(guī)劃的回溯思想：

DTW(i,j)=d(pi,qj)+

(5)

DTW得到兩個(gè)序列間的匹配結(jié)果如圖5b所示。

兩個(gè)時(shí)間序列的DTW值越小，說(shuō)明兩個(gè)時(shí)間序列越相似。DTW因?yàn)槠鋭?dòng)態(tài)匹配特性，可以將兩個(gè)具有不同長(zhǎng)度的時(shí)間序列進(jìn)行匹配，較好排除伸縮平移等操作的影響。

對(duì)于多目標(biāo)多模特性證明問(wèn)題，要比較不同PS對(duì)應(yīng)的PF之間的相似性，PF的點(diǎn)數(shù)不同，但形狀可能是相似的，因此將DTW用于比較PF的相似性從而證明多目標(biāo)問(wèn)題的多模特性。大多數(shù)多目標(biāo)問(wèn)題的目標(biāo)空間都是二維的，將其視為時(shí)間序列的時(shí)間軸與幅度軸，就可計(jì)算兩個(gè)PF之間的DTW值。

2.2.2 多目標(biāo)多模特性分析方法 利用DTW來(lái)證明問(wèn)題的多模特性的主要思路是：將求解問(wèn)題在決策空間進(jìn)行分組，求出每一組的PF后，利用DTW計(jì)算出不同組PF與標(biāo)準(zhǔn)PF的DTW距離(適用于標(biāo)準(zhǔn)PF已知的標(biāo)準(zhǔn)測(cè)試函數(shù)問(wèn)題)或組與組PF之間的DTW距離(適用于標(biāo)準(zhǔn)PF未知的實(shí)際問(wèn)題)，通過(guò)比較PF的相似性來(lái)證明算法的多模特性。DTW值越小，問(wèn)題的多模特性越強(qiáng)。圖6給出了多目標(biāo)多模分析的流程圖。

圖6 多目標(biāo)多模特性證明流程

2.3 多目標(biāo)多模特性分析

求解每一組的PF時(shí)可采取任意多目標(biāo)優(yōu)化算法，本文采取MO_Ring_PSO_SCD來(lái)進(jìn)行求解，并將分組數(shù)設(shè)為4組，算法進(jìn)行30次取平均值，下面給出對(duì)于標(biāo)準(zhǔn)測(cè)試函數(shù)以及TTSP問(wèn)題多模特性的證明結(jié)果。

2.3.1 標(biāo)準(zhǔn)測(cè)試函數(shù) 表3展示了在將決策空間分為4組的前提下，標(biāo)準(zhǔn)測(cè)試函數(shù)多模特性證明結(jié)果。從每一組PF與標(biāo)準(zhǔn)PF的DTW值和平均DTW值來(lái)看，標(biāo)準(zhǔn)測(cè)試函數(shù)都有比較強(qiáng)的多模特性。

表3 標(biāo)準(zhǔn)測(cè)試函數(shù)多模特性分析結(jié)果

圖7和圖8展示了MMF1的標(biāo)準(zhǔn)PF與標(biāo)準(zhǔn)PS，以及4組PF與PS，不同顏色代表不同組別。在決策空間中，4組PS沒(méi)有交疊，但在目標(biāo)空間中，4組PF均分布在(1,0)—(0,1)的一條弧線上，與標(biāo)準(zhǔn)PF具有很強(qiáng)的相似性。其他測(cè)試函數(shù)與MMF1同理。

圖7 MMF1多模特性證明結(jié)果圖(PF)

圖8 MMF1多模特性證明結(jié)果圖(PS)

DTW值越小，說(shuō)明不同PS對(duì)應(yīng)的PF的相似性越高，說(shuō)明問(wèn)題的多模特性越強(qiáng)。從表3結(jié)果可以看出，MMF1-MMF7的DTW值較小，多模特性相對(duì)較強(qiáng)，SYM-PRAT simple與SYM-PART rotated的DTW值相對(duì)較大。這可能有兩種原因：該問(wèn)題的多模特性比較弱;求解出的每一組的前沿質(zhì)量不高。多模特性的證明結(jié)果與所選擇的求解每一組前沿的算法有很大的關(guān)系，當(dāng)問(wèn)題規(guī)模比較大時(shí)，如果算法的收斂性或多樣性不足，會(huì)影響每一組前沿的求解質(zhì)量，從而影響到DTW值的計(jì)算和問(wèn)題多模特性的證明。比如對(duì)SYM-PRAT simple與SYM-PART rotated，當(dāng)前沿求解質(zhì)量不好時(shí)，DTW值會(huì)偏大。

2.3.2 TTSP 表4給出了TTSP不同規(guī)模實(shí)例多模特性證明結(jié)果?？梢钥吹綄?duì)于規(guī)模較小的問(wèn)題如4×8和5×8，每一組PS之間的DTW值都為0，即所有組找到的前沿完全一樣，顯然4×8與5×8規(guī)模的TTSP問(wèn)題是具有多模特性的。對(duì)于更大規(guī)模的問(wèn)題如20×8、30×12、40×8,DTW值稍大。但從上面對(duì)于TTSP進(jìn)行空間適應(yīng)度地形分析來(lái)看，高維度的TTSP實(shí)例依然具有很強(qiáng)的多模特性。通過(guò)對(duì)找到的采樣解進(jìn)行分析，發(fā)現(xiàn)DTW值大的原因是：當(dāng)問(wèn)題規(guī)模較大、尋找采樣解的方法收斂性不夠好時(shí)，影響每一組找到前沿的質(zhì)量，影響到分析結(jié)果。

表4 TTSP不同規(guī)模實(shí)例多模特性證明結(jié)果

3 多目標(biāo)多模優(yōu)化算法

3.1 算法框架

本文提出基于區(qū)域遷移策略的多目標(biāo)粒子群優(yōu)化算法(multi-objective particle swarm optimizer based on regional migration strategy，RMMOPSO)，以適用于解決多目標(biāo)多模問(wèn)題，即找到多個(gè)不同的PS對(duì)應(yīng)于同一個(gè)PF。該算法的主要思想是令多個(gè)種群在決策空間并行獨(dú)立搜索，種群之間進(jìn)行信息交互，使得每個(gè)種群都可以找到一個(gè)良好的PF，且在決策空間各PS并不相同。算法針對(duì)TTSP的多目標(biāo)多模特性主要采取以下4個(gè)策略:(1)多種群策略。將決策空間分為N組，每組中有一個(gè)子種群并行獨(dú)立搜索，以通過(guò)子種群數(shù)量來(lái)增加算法在決策空間的多樣性。(2)區(qū)域遷移策略。種群之間利用全局最優(yōu)解進(jìn)行信息交互，引導(dǎo)每個(gè)子種群的搜索區(qū)域不斷發(fā)生轉(zhuǎn)移，使所有子種群可以搜索到完整搜索空間，從而找到多個(gè)不同的PS對(duì)應(yīng)于同一個(gè)前沿，使算法具有多模特性。(3)精英池策略。將每個(gè)階段每個(gè)子種群搜索到的精英解都保存在精英池中。(4)淘汰策略。將精英池中的粒子進(jìn)行非支配排序，淘汰排序靠后的粒子。

圖9給出了RMMOPSO的算法框圖(以4個(gè)子種群為例)。

圖9 RMMOPSO算法框圖

下面將主要介紹本算法兩個(gè)核心策略：多種群策略與區(qū)域遷移策略。

3.2 多種群策略

多種群策略將決策空間分為互不相交的N個(gè)區(qū)域，作為N個(gè)子種群的初始搜索區(qū)域。N個(gè)子種群在各自的搜索區(qū)域內(nèi)并行獨(dú)立搜索，產(chǎn)生種群內(nèi)部的全局最優(yōu)解gbest，進(jìn)行精英解的保存。

子種群的個(gè)數(shù)可以根據(jù)問(wèn)題的維度和每一維度的長(zhǎng)度進(jìn)行調(diào)整。當(dāng)某一維度范圍很廣或有較多維度時(shí)，可以適當(dāng)增加子種群個(gè)數(shù)。算法采用網(wǎng)格狀將決策空間分組。例如，當(dāng)子種群數(shù)為N=2m時(shí)，可以利用決策空間的前m維進(jìn)行分組。當(dāng)分為4組時(shí)，用前兩維進(jìn)行分組，其他維度各組保持一致，如圖10a所示；當(dāng)子種群數(shù)為8時(shí)，用前決策空間前3維進(jìn)行分組，其他維度各組保持一致，如圖10b所示。

圖10 將決策空間分組示意圖

子種群采用基于特殊擁擠距離排序的MOPSO算法進(jìn)行迭代。

策略偽代碼如表5所示。其中:N代表子種群個(gè)數(shù);i表示子種群的序號(hào);range_ui表示子種群i的初始搜索范圍上界;range_li表示子種群i的初始搜索范圍下界;gbesti表示子種群i產(chǎn)生的種群內(nèi)部的全局最優(yōu)解;n_var表示決策空間維度;Global_range_u(1,n_var)表示全局搜索范圍上界;Global_range_l(1,n_var)表示全局搜索范圍下界;skip1與skip2分別表示維度1與維度2上子種群的搜索范圍;archivei表示子種群i的精英池;Iteration表示當(dāng)前迭代次數(shù);MAXIteration表示該子種群總迭代次數(shù)。

表5 多種群策略偽代碼

3.3 區(qū)域遷移策略

為了能使N個(gè)子種群可以在全局范圍內(nèi)都進(jìn)行搜索，并且利用好其他種群的經(jīng)驗(yàn)，使每個(gè)種群都能找到對(duì)應(yīng)于較好前沿的不同PS，引入?yún)^(qū)域遷移策略，順時(shí)針輪流交換子種群的gbesti，使得各個(gè)種群可以在決策空間內(nèi)輪轉(zhuǎn)起來(lái)。將整個(gè)算法分為搜索階段和轉(zhuǎn)移階段。

在搜索階段，子種群i粒子的速度按式(6)來(lái)更新：

vikt=wvik(t-1)+c1(pbestik(t-1))+c2gbesti(t-1)。

(6)

式中：vikt表示子種群i中，第k個(gè)粒子第t次迭代的速度；pbestik(t-1)為子種群i中，第k個(gè)粒子第(t-1)次迭代后個(gè)體歷史最優(yōu)解的坐標(biāo);gbesti(t-1)表示子種群i中第(t-1)次迭代后本種群全局最優(yōu)解坐標(biāo);c1與c2分別為個(gè)體和全局學(xué)習(xí)因子。此時(shí)，粒子在gbesti引導(dǎo)下，會(huì)不斷向本種群全局最優(yōu)解收斂，故本文稱為搜索階段。

在轉(zhuǎn)移階段，N個(gè)子種群的全局最優(yōu)解進(jìn)行交換，交換順序?yàn)閇gbestN→gbest1→gbest2→…→gbestN-2→gbestN-1]，即交換后，子種群1用于更新粒子速度的全局最優(yōu)解為上一搜索階段子種群N迭代得到的gbestN；同理，子種群2用于更新粒子速度的全局最優(yōu)解為上一搜索階段子種群1迭代得到的gbest1，子種群i粒子的速度和位置按式(7)來(lái)更新：

vikt=wvik(t-1)+c1(pbestik(t-1))+c2gbestj。

(7)

式中g(shù)bestj指子種群j上個(gè)搜索階段迭代產(chǎn)生的全局最優(yōu)解。子種群i在gbestj的引導(dǎo)下，會(huì)向gbestj所在區(qū)域不斷收斂，即向子種群j上個(gè)搜索階段所在區(qū)域轉(zhuǎn)移，故本文稱為轉(zhuǎn)移階段。轉(zhuǎn)移階段不僅可以起到讓子種群進(jìn)行轉(zhuǎn)移，盡可能搜索到完整的決策空間，還可以起到交流種群間經(jīng)驗(yàn)的作用。gbestj為子種群j上個(gè)搜索階段所產(chǎn)生的種群經(jīng)驗(yàn)，用此來(lái)引導(dǎo)子種群i轉(zhuǎn)移，可以增加算法收斂性。

表6給出了區(qū)域遷移策略的偽代碼(以子種群個(gè)數(shù)為4為例)。其中N代表子種群個(gè)數(shù)，i表示子種群序號(hào)；Gbest=[gbest4;gbest1;gbest2;gbest3]是子種群gbest的和矩陣，完成子種群間gbest交換的功能；Loop表示(搜索過(guò)程+轉(zhuǎn)移過(guò)程)執(zhí)行次數(shù)，為了讓所有子種群搜索到完整決策空間，Loop與子種群數(shù)相同；Iteralion表示當(dāng)前迭代次數(shù)；MAXIterationsearch表示子種群每次搜索階段的總迭代次數(shù);MAXIterationtrans表示子種群每次轉(zhuǎn)移階段的總迭代次數(shù)。

表6 區(qū)域遷移策略偽代碼

MAXIterationsearch、Loop、MAXIterationtrans之間滿足如下關(guān)系：在有4個(gè)子種群的情況下，一般讓子種群可以完整循環(huán)一圈，即一般令Loop=4,MAXIteration為算法的總迭代次數(shù)，那么有式(8)：

MAXIteration=Loop×(MAXIterationsearch+

MAXIterationtrans)。

(8)

4 仿真與性能分析

本文選擇了11個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)與不同規(guī)模的TTSP實(shí)例來(lái)測(cè)試算法表現(xiàn)，將RMMOPSO與MO_Ring_PSO_SCD算法進(jìn)行對(duì)比，選擇指標(biāo)Hv、PSP及SP來(lái)衡量算法表現(xiàn)，并給出對(duì)于RMMOPSO所具有的多模特性的分析。下面主要介紹實(shí)驗(yàn)的測(cè)試函數(shù)、參數(shù)設(shè)置和說(shuō)明、評(píng)價(jià)指標(biāo)、實(shí)驗(yàn)結(jié)果以及對(duì)實(shí)驗(yàn)結(jié)果的分析。

4.1 測(cè)試函數(shù)

對(duì)于標(biāo)準(zhǔn)測(cè)試函數(shù)，本文選擇了文獻(xiàn)[10]所設(shè)計(jì)的11個(gè)經(jīng)典多目標(biāo)多模測(cè)試函數(shù)：MMF1—MMF8，以及SYM-PART simple、SYM-PART rotated和Omni-test。這些函數(shù)都具有多模特性，但決策空間的維度以及同一個(gè)PF對(duì)應(yīng)的PS的個(gè)數(shù)不同。其中MMF1—MMF8、SYM-PART simple、SYM-PART rotated決策空間為2維；SYM-PART simple、SYM-PART rotated較復(fù)雜，有9個(gè)PS對(duì)應(yīng)于同一個(gè)PF，SYM-PART rotated的PS相對(duì)于SYM-PART simple發(fā)生了旋轉(zhuǎn)，求解更加困難；Omni-test決策空間為3維，有27個(gè)PS對(duì)應(yīng)于同一個(gè)PF，是最復(fù)雜的一個(gè)測(cè)試函數(shù)。

對(duì)于測(cè)試任務(wù)調(diào)度問(wèn)題，本文選擇4×8、5×8、6×8、30×12和40×12實(shí)例作為測(cè)試函數(shù)，據(jù)上文分析可知，它們具有多模特性、真實(shí)前沿少、離散程度大的特征，且決策空間規(guī)模維度不斷增大，適合于檢驗(yàn)算法的收斂性與多樣性。

4.2 評(píng)價(jià)指標(biāo)

為了衡量算法在目標(biāo)空間和決策空間的多樣性和收斂性，采取超體積指標(biāo)(hypervolume, Hv)、SP來(lái)衡量目標(biāo)空間算法性能，采取PSP[10]來(lái)衡量決策空間算法性能。其中PSP包含了解集覆蓋率(cover rate, CR)[23]和決策空間的反向世代距離(inverse generation distance，IGDX)[24]，可以綜合衡量算法在決策空間的收斂性與多樣性。表7給出了這些指標(biāo)的適用范圍和條件。

表7 評(píng)價(jià)指標(biāo)及它們的適用范圍和條件

4.3 參數(shù)設(shè)置

目前多目標(biāo)多模優(yōu)化的主流算法有MO_Ring_PSO_SCD[10]、DN-NSGAⅡ[15]、Omni-optimizer[15]。文獻(xiàn)[10]對(duì)MO_Ring_PSO_SCD算法與Omni-optimizer、DN-NSGAⅡ、NSGAⅡ、MOEAD、SPEA2進(jìn)行了對(duì)比，在目標(biāo)空間內(nèi)，幾個(gè)算法表現(xiàn)相差不大，在決策空間內(nèi)，除了MMF7外，MO_Ring_PSO_SCD在所有算法中表現(xiàn)最好，所以本算法主要與MO_Ring_PSO_SCD算法進(jìn)行比較。比較表7中的11個(gè)測(cè)試函數(shù)和不同規(guī)模TTSP實(shí)例，以分析算法在目標(biāo)空間和決策空間的綜合性能，并著重關(guān)注算法的多模性能，即能否找到多個(gè)PS對(duì)應(yīng)于目標(biāo)空間同一個(gè)PS。

為保證公平性，算法的所有參數(shù)設(shè)置同對(duì)比算法MO_Ring_PSO_SCD完全一致，采用文獻(xiàn)[10]中推薦的參數(shù)：粒子總數(shù)設(shè)置為800，最大迭代次數(shù)為100。式(4)和(5)中的學(xué)習(xí)因子c1和c2都設(shè)置為2.05，慣性權(quán)重w設(shè)置為0.729 8。所有算法運(yùn)行20次，對(duì)指標(biāo)計(jì)算結(jié)果取平均值與方差。

對(duì)于RMMOPSO來(lái)說(shuō)，當(dāng)粒子總數(shù)為800，設(shè)置4個(gè)子種群并行搜索時(shí)，每個(gè)子種群的粒子數(shù)為200。根據(jù)式(8)，設(shè)置Loop=4，當(dāng)MAXIteration=100時(shí)，我們選擇MAXIterationsearch=12，MAXIterationtrans=13，以滿足式(8)。

4.4 結(jié)果分析

本節(jié)主要給出RMMOPSO算法與MO_Ring_PSO_SCD算法在11個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)和不同規(guī)模TTSP問(wèn)題對(duì)比的實(shí)驗(yàn)結(jié)果，并給出結(jié)果分析。

對(duì)于11個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)，選擇指標(biāo)Hv來(lái)衡量算法在目標(biāo)空間的綜合性能，選擇PSP來(lái)衡量算法在決策空間的綜合性能。Hv和PSP的值越大說(shuō)明算法綜合性能越優(yōu)秀。對(duì)于TTSP實(shí)例，因?yàn)闆](méi)有標(biāo)準(zhǔn)前沿，選擇不需要標(biāo)準(zhǔn)前沿的Hv和SP來(lái)衡量算法性能。對(duì)于復(fù)雜的TTSP實(shí)例，目標(biāo)空間解的綜合性能可以反映出決策空間的多樣性和收斂性。Hv越大、SP越小，說(shuō)明算法的綜合性能越好。

為了進(jìn)一步說(shuō)明算法的多樣性，分別給出RMMOPSO每個(gè)子種群找到的前沿的指標(biāo)。

4.4.1 標(biāo)準(zhǔn)測(cè)試函數(shù)實(shí)驗(yàn)結(jié)果 表8和表9給出了11個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的實(shí)驗(yàn)結(jié)果，圖11給出了11個(gè)測(cè)試函數(shù)PSP盒圖。其中，RMMOPSO序號(hào)為1，MO_Ring_PSO_SCD序號(hào)為2。在目標(biāo)空間內(nèi)，RMMOPSO在MMF4和SYM-PART simple表現(xiàn)明顯優(yōu)于MO_Ring_PSO_SCD。對(duì)于其他測(cè)試函數(shù)，二者表現(xiàn)差距不大，這是因?yàn)槎咴谀繕?biāo)空間的排序、淘汰方式差別不大。RMMOPSO在目標(biāo)空間中解的分布略優(yōu)于MO_Ring_PSO_SCD。

圖11 標(biāo)準(zhǔn)測(cè)試函數(shù)PSP盒圖

表8 標(biāo)準(zhǔn)測(cè)試函數(shù)算法對(duì)比結(jié)果(Hv)

表9 標(biāo)準(zhǔn)測(cè)試函數(shù)算法對(duì)比結(jié)果(PSP)

在決策空間中，從PSP平均值來(lái)看，除了Omni-test函數(shù)RMMOPSO表現(xiàn)均優(yōu)于MO_Ring_PSO_SCD。這說(shuō)明RMMOPSO在決策空間中的解分布更均勻、覆蓋率也更高，反映出RMMOPSO在低緯度測(cè)試函數(shù)中在決策空間表現(xiàn)良好，有很好的多樣性。

圖12以標(biāo)準(zhǔn)測(cè)試函數(shù)SYM-PART simple為例給出了RMMOPSO和MO_Ring_PSO_SCD所求得的PS與PF。可以明顯看出，RMMOPSO在目標(biāo)空間和決策空間中解的分布都要更均勻、更能覆蓋標(biāo)準(zhǔn)前沿上的點(diǎn)。

圖12 兩種算法在SYM-PART simple下解得PS與PF對(duì)比

在更高維函數(shù)如Omni-test中，RMMOPSO在決策空間的表現(xiàn)不如MO_Ring_PSO_SCD。圖13給出了兩個(gè)算法對(duì)于Omni-test的求解結(jié)果?？梢钥吹剑谀繕?biāo)空間RMMOPSO求得解更均勻，覆蓋率更好。但是在決策空間，絕大多數(shù)解聚集在幾個(gè)區(qū)域，而其他區(qū)域解比較少。相反，MO_Ring_PSO_SCD在決策空間中的解分布更均勻，PSP指標(biāo)表現(xiàn)更好。這是因?yàn)镺mni-test函數(shù)有27個(gè)PS對(duì)應(yīng)于同一個(gè)PF，且維度更高。如果我們?nèi)匀粚Q策空間分為4組，每組內(nèi)將存在不止一個(gè)PS。而在算法迭代中的轉(zhuǎn)移階段，用于引導(dǎo)子種群i向目標(biāo)區(qū)域發(fā)生轉(zhuǎn)移的是之前在此目標(biāo)區(qū)域搜索的子種群j的全局最優(yōu)點(diǎn)gbestj，所以子種群i在轉(zhuǎn)移時(shí)會(huì)不斷收斂于gbestj；如果gbestj已經(jīng)固定，這會(huì)使粒子群趨于早熟，且子種群i在本目標(biāo)區(qū)域收斂得到的全局最優(yōu)點(diǎn)gbesti還會(huì)引導(dǎo)下一個(gè)子種群向本區(qū)域收斂，因此會(huì)造成大多數(shù)種群集中在少數(shù)幾個(gè)PS上。此時(shí)，應(yīng)當(dāng)根據(jù)問(wèn)題規(guī)模增加子種群數(shù)量，從而達(dá)到更好的效果。后面4.4.3節(jié)將改變子種群個(gè)數(shù)，以標(biāo)準(zhǔn)測(cè)試函數(shù)Omni-test為例給出改變子種群數(shù)后的實(shí)驗(yàn)結(jié)果和分析。

圖13 兩種算法在Omni-test下解得PS與PF對(duì)比

從方差來(lái)看，RMMOPSO方差較大，魯棒性不夠高。這也是區(qū)域遷移策略帶來(lái)的弊端。與上述對(duì)Omni-test函數(shù)實(shí)驗(yàn)結(jié)果分析一致，因?yàn)橐龑?dǎo)子種群搜素區(qū)域發(fā)生轉(zhuǎn)移的是其他子種群的gbest，當(dāng)?shù)谝粋€(gè)在目標(biāo)區(qū)域搜索的粒子群早熟時(shí)，會(huì)造成算法迭代結(jié)束后整個(gè)解的質(zhì)量變差，因此造成算法魯棒性不高，方差較大。

4.4.2 TTSP實(shí)例實(shí)驗(yàn)結(jié)果 下面對(duì)不同規(guī)模TTSP實(shí)例進(jìn)行實(shí)驗(yàn)分析。表10與表11給出了在不同規(guī)模TTSP實(shí)例下，RMMOPSO與MO_Ring_PSO_SCD對(duì)比的結(jié)果。

表10 不同規(guī)模TTSP實(shí)例算法對(duì)比結(jié)果(Hv)

表11 不同規(guī)模TTSP實(shí)例算法對(duì)比SP結(jié)果

在對(duì)RMMOPSO縱向比較來(lái)看，通過(guò)比較不同規(guī)模的TTSP實(shí)例可以發(fā)現(xiàn)，在4×8、5×8、6×8規(guī)模下，問(wèn)題規(guī)模較小，目標(biāo)空間前沿只有2個(gè)點(diǎn)，算法每次找到的點(diǎn)是一樣的，因此方差為0。當(dāng)問(wèn)題規(guī)模逐漸增大時(shí)，指標(biāo)Hv不斷減小，指標(biāo)SP不斷增大，說(shuō)明隨著問(wèn)題的增大，算法收斂性與多樣性降低，此時(shí)需要增加迭代次數(shù)或者增加粒子數(shù)來(lái)增加算法的收斂性。RMMOPSO與MO_Ring_PSO_SCD比較，因?yàn)閱?wèn)題規(guī)模比較大，Hv值也比較大，所以兩者算法性能相差不大。

4.4.3 區(qū)域遷移策略效果分析 本節(jié)主要對(duì)RMMOPSO算法提出的區(qū)域遷移策略的效果進(jìn)行分析。

在區(qū)域轉(zhuǎn)移策略的搜索階段中，每個(gè)區(qū)域向著各自區(qū)域的全局最優(yōu)點(diǎn)收斂，在本次搜索階段結(jié)束，每個(gè)區(qū)域內(nèi)的PF與PS都會(huì)被保存至精英池中，用以指導(dǎo)轉(zhuǎn)移階段子種群的轉(zhuǎn)移，并且在下一個(gè)搜索階段，該區(qū)域新的子種群會(huì)在上一個(gè)在此區(qū)域的子種群的搜索經(jīng)驗(yàn)上繼續(xù)搜索。

區(qū)域轉(zhuǎn)移策略與精英池策略的結(jié)合可以使得每個(gè)子種群在每個(gè)區(qū)域的搜索經(jīng)驗(yàn)都被保存下來(lái)并不斷進(jìn)行利用。因?yàn)橛辛诉@種經(jīng)驗(yàn)的傳遞和指導(dǎo)，在完整算法迭代過(guò)程中，對(duì)于每一個(gè)區(qū)域來(lái)說(shuō)，隨著迭代次數(shù)的增加，該區(qū)域所搜索到的PF與PS是在不斷收斂的，避免了區(qū)域遷移對(duì)于已找到前沿面的破壞。圖14給出了對(duì)于MMF1，在分為4個(gè)子種群的情況下，對(duì)于區(qū)域1，在4次搜索階段中分別獲得的前沿面。

圖14 MMF1測(cè)試函數(shù)區(qū)域1中4次搜索階段獲得的前沿面

可以看出，在4次搜索階段不同子種群對(duì)于區(qū)域1的搜索后，獲得的前沿面互相補(bǔ)充并不斷向里推進(jìn)。迭代完成后，經(jīng)過(guò)去重、淘汰，最終獲得完整的前沿面。由此也可以證明，RMMOPSO可以兼顧決策空間與目標(biāo)空間的多樣性和分布性。

4.4.4 子種群個(gè)數(shù)對(duì)算法的影響 下面以標(biāo)準(zhǔn)測(cè)試函數(shù)Omni-test和30×12 TTSP實(shí)例為例，改變子種群個(gè)數(shù)，將決策空間分為8組進(jìn)行實(shí)驗(yàn)，分析子種群個(gè)數(shù)對(duì)于算法結(jié)果的影響。

決策空間分組方法參照3.2節(jié)。在區(qū)域遷移策略中，Loop、轉(zhuǎn)移階段和搜索階段的迭代次數(shù)依然要滿足式(8)。將總迭代次數(shù)增加一倍，變成200次，令MAXIterationsearch=25，MAXIterationtrans=25，其他參數(shù)保持不變。為了對(duì)比，將決策空間分為4組的情況也增加迭代次數(shù)至200次進(jìn)行實(shí)驗(yàn)。表12和表13分別展示了對(duì)于Omni-test和30×12 TTSP實(shí)例的實(shí)驗(yàn)結(jié)果。 圖15展示了不同子種群數(shù)量找到的PS的對(duì)比。

表12 Omni-test不同子種群數(shù)實(shí)驗(yàn)結(jié)果

表13 30×12 TTSP實(shí)例不同子種群數(shù)實(shí)驗(yàn)結(jié)果

圖15 標(biāo)準(zhǔn)測(cè)試函數(shù)Omni-test下不同子種群數(shù)量找到的PS

從圖15和表12可以看出，對(duì)于Omni-test函數(shù)，當(dāng)增加子種群個(gè)數(shù)時(shí)，找到的PS明顯更多，決策空間指標(biāo)表現(xiàn)也更好。并且通過(guò)8個(gè)子種群200次迭代結(jié)果和4個(gè)子種群200次迭代結(jié)果對(duì)比可以看出，性能的提升并不是因?yàn)榈螖?shù)的增加。但仍然存在決策空間中粒子都集中于部分區(qū)域的現(xiàn)象。

對(duì)于30×12 TTSP實(shí)例，增加子種群個(gè)數(shù)對(duì)算法收斂性改善并不明顯，因?yàn)閱?wèn)題規(guī)模很大，即使增加分組個(gè)數(shù)，也無(wú)法搜索到更大范圍的空間，因此對(duì)效果改善不明顯，但此時(shí)增加迭代次數(shù)可以有效增加算法收斂性。

通過(guò)以上分析，在問(wèn)題規(guī)模較大、維度較高時(shí)，適當(dāng)增加迭代次數(shù)和粒子群個(gè)數(shù)有利于避免所有粒子收斂于少數(shù)幾個(gè)PS上，從而得到更均勻、覆蓋率更高的PS，提升算法性能。

4.4.5 算法多模特性分析 下面以標(biāo)準(zhǔn)測(cè)試函數(shù)SYM-PART simple與20×8 TTSP實(shí)例為例分析算法的多模特性。

圖16展示了RMMOPSO在標(biāo)準(zhǔn)測(cè)試函數(shù)SYM-PART simple下4個(gè)子種群產(chǎn)生的PS與PF。

圖16 RMMOPSO在SYM-PART simple 上各子種群求解結(jié)果

圖17與表15展示了RMMOPSO在20×8 TTSP實(shí)例下4個(gè)子種群分別找到的前沿和這些前沿的Hv和SP指標(biāo)。

表15 20×8 TTSP實(shí)例各子種群Hv、SP指標(biāo)結(jié)果

圖17 RMMOPSO在20×8 TTSP實(shí)例上各子種群求解結(jié)果

表14展示了4個(gè)子種群所得前沿的Hv指標(biāo)。

表14 SYM-PART simple函數(shù)各子種群Hv指標(biāo)結(jié)果

可以看出，對(duì)于標(biāo)準(zhǔn)測(cè)試函數(shù)，無(wú)論從PF的分布還是指標(biāo)來(lái)看，4個(gè)子種群均能得到質(zhì)量好的PF，且與之對(duì)應(yīng)的PS并不相同，說(shuō)明算法可以找到4個(gè)不完全相同的PS對(duì)應(yīng)于目標(biāo)空間同一個(gè)PF，算法具有較好的多樣性。對(duì)于TTSP實(shí)例，可以看到，4個(gè)子種群分別找到的PF在目標(biāo)空間找到的PF不能相互支配，且對(duì)應(yīng)指標(biāo)相似，這說(shuō)明TTSP實(shí)例具有多模特性。子種群的指標(biāo)相較于所有子種群匯總結(jié)果的指標(biāo)略差，因?yàn)樗惴ǖ偨Y(jié)果是所有子種群迭代得到的解中非支配排序靠前的粒子組成的，因此表現(xiàn)更好。

綜上，通過(guò)對(duì)于低維度標(biāo)準(zhǔn)測(cè)試函數(shù)和小規(guī)模TTSP實(shí)例的測(cè)試，RMMOPSO在決策空間和目標(biāo)空間的綜合性能較好，但魯棒性較差；對(duì)于大規(guī)模、高維度問(wèn)題，可以適當(dāng)增加子種群個(gè)數(shù)或者迭代次數(shù)。RMMOPSO還具有可以同時(shí)找到對(duì)應(yīng)于目標(biāo)空間同一個(gè)PF的不同PS的優(yōu)點(diǎn)，具有求解多模問(wèn)題的能力。

5 總結(jié)

本文針對(duì)測(cè)試任務(wù)調(diào)度問(wèn)題的多模特性提出了基于動(dòng)態(tài)時(shí)間彎曲的證明方法，通過(guò)比較決策空間不同區(qū)域?qū)?yīng)的PF的相似性來(lái)判斷問(wèn)題的多模特性，通過(guò)對(duì)11個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)及不同規(guī)模TTSP實(shí)例的測(cè)試，發(fā)現(xiàn)該方法能很好反映問(wèn)題的多模特性；但對(duì)于更復(fù)雜的問(wèn)題，當(dāng)求解算法的收斂性不夠、求得前沿質(zhì)量不高時(shí)，會(huì)影響到DTW計(jì)算結(jié)果。基于多模特性分析結(jié)果，本文提出基于區(qū)域遷移的粒子群多目標(biāo)多模優(yōu)化算法(RMMOPSO)，其中主要采用了多種群策略以及區(qū)域遷移策略。多種群策略可增加決策空間多樣性，區(qū)域遷移策略可以使每個(gè)子種群都能找到對(duì)應(yīng)于同一個(gè)PF的不同PS，以提升算法的多模特性。通過(guò)對(duì)11個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)和不同規(guī)模TTSP問(wèn)題的測(cè)試，發(fā)現(xiàn)RMMOPSO在目標(biāo)空間和決策空間都有較好的收斂性和多樣性，并且能同時(shí)得到多個(gè)對(duì)應(yīng)于目標(biāo)空間同一個(gè)PF的不同PS。但算法容易造成誤差累積，魯棒性較差，且對(duì)于高維、大規(guī)模問(wèn)題，需要適當(dāng)增加子種群個(gè)數(shù)，以得到更好的結(jié)果。

下一步工作將從進(jìn)一步提高算法魯棒性的角度出發(fā)，將RMMOPSO算法與其他算法進(jìn)行融合；從提升多樣性和收斂性的角度，提升搜索區(qū)域的覆蓋性以及解集的均勻性，從而更好地解決多目標(biāo)多模測(cè)試任務(wù)調(diào)度問(wèn)題，并可應(yīng)用于其他領(lǐng)域中的調(diào)度問(wèn)題。