面向交通出行服務的多目標優化選擇方法

楊萬春 張晨曦

(山東交通學院理學院 山東 濟南 250357) 2(同濟大學軟件學院 上海 201804)

0 引 言

隨著交通行業信息化的發展和出行方式的多元化,現有研究在交通服務選擇[1]和交通流預測[2]等方面開展了大量工作,其中在功能相似的海量服務資源中挑選交通出行服務成為智能交通系統的關鍵。為此,如何將功能單一的服務按需定制、重新組裝來滿足用戶需求成為當下的研究重點。如出行者要去參加國際會議,并在參加國際會議的空閑之余游覽旅游景點,需要用到信息搜索、規劃線路、選擇交通方式、預訂酒店與景點、支付費用、地圖顯示等服務。服務質量(Quality of Service,QoS)包含多個指標,用戶在選擇出行服務的時候,會考慮速度、花費、滿意度等非功能屬性。現有的交通服務選擇研究大多將各個目標聚合為一個單目標函數,然后采用數學規劃方法或者啟發進化算法對單目標問題進行求解。文獻[3]采用蟻群算法進行交通出行服務的選擇。文獻[4]將煙花爆炸算法和變異算子相結合以應用于服務選擇模型。文獻[5]提出一種混合混沌機制與Levy變異的改進煙花算法,但上述方法無法滿足用戶多目標的需求。由于各個指標維度之間可能存在矛盾,某個指標的改善會引起其他指標的惡化,例如可用性高的服務,其價格花費就會相應提高,這就需要在不同維度指標之間進行平衡,從而能夠滿足用戶多方位的出行需求。多目標優化問題不存在使得所有目標都達到最優解,其是由Pareto最優解或非劣最優解構成的解集。

現階段已有相關研究將啟發式進化算法應用于服務的多目標選擇問題中,從而達到Pareto前沿。文獻[6]針對有數據依賴的組合服務構建了依賴圖,基于依賴圖設計了基于集束搜索(beam search)和非支配排序遺傳算法(NSGA-II)的改進啟發式進化算法。文獻[7]采用分布估計算法進行局部搜索以提高NSGA-II的性能。文獻[8]采用多目標遺傳算法來確定一個Pareto最優多維邊界,并能夠權衡相互沖突的目標。文獻[9]針對服務選擇問題,給出了改進的多目標粒子群算法,在算法中加入了近似距離方法和外部存檔機制。文獻[10]先對候選服務進行排序優化篩選,在此基礎上給出了基于多目標粒子群優化的云服務選擇排序系統。文獻[11]提出了ε支配的多目標遺傳算法來解決服務組合優化問題。它支持用戶在當前服務失敗時做出靈活的決策或選擇替代方案。文獻[12]給出了混合多目標進化算法,其將NSGA-II和差分進化算法相結合,其中的差分進化算法采用了自適應變異算子和交叉算子。文獻[13]給出了基于多目標進化算法與決策支持的組合優化方法。該方法首先應用決策支持方法來計算用戶偏好的權重,然后將計算出來的權重應用于擁擠距離的求解中。以上多目標服務選擇方法采用不同的算法解決了多目標服務選擇問題,但它們都沒有考慮服務的事務屬性問題。

針對網絡環境的不穩定、信息傳輸的不可靠等因素,采用事務處理技術來保證組合服務的可靠性和一致性。文獻[14]給出了服務的事務屬性定義和規則。文獻[15]針對事務性服務的組合問題,給出了改進的遺傳算法。文獻[16]給出了SLA感知的事務型組合服務容錯方法。

綜上所述,針對交通出行服務選擇,現有的研究都是基于服務的QoS屬性構建了多目標選擇模型,沒有考慮服務的事務屬性。基于服務選擇模型的多目標優化算法在解集的收斂性、均勻性、廣泛性方面還存在性能不足。本文從QoS和事務兩個維度建立了服務優化選擇模型,在該模型基礎上,設計了煙花爆炸算法與啟發式的差分進化算法相結合的混合優化方法,對組合服務進行優化選擇,利用外部存檔中的解作為Pareto最優解集。該多目標優化算法將煙花爆炸算法的局部搜索能力以及差分進化算法的種群多樣性結合起來,重新定義了爆炸半徑、交叉與變異算子,具有較好的搜索性能。

1 服務優化選擇模型

服務選擇問題是首先根據用戶的需求構建抽象服務流程,然后在候選服務中選擇具體服務,將選擇出的具體服務和抽象服務進行綁定。這些候選服務具有不同的屬性參數值,因此可形成海量的服務組合方案。

1.1 QoS屬性

交通信息服務的QoS屬性包括花費(cost)、及時性(time)、可用性(availability)、可靠性(reliability)、滿意度(satisfaction)等。由于每種QoS屬性的單位或取值范圍不一樣,因此需要在統一的標準下計算QoS屬性。QoS屬性可以分為積極屬性和消極屬性兩類。積極屬性考慮QoS的最大化,如可用性、可靠性、滿意度等,其歸一化公式為式(1)。消極屬性考慮QoS的最小化,如花費、及時性等,其歸一化公式為式(2)。

(1)

(2)

式中:q表示QoS屬性;q′表示歸一化后的結果;qmin表示QoS屬性中的最小值;qmax表示QoS屬性中的最大值。若qmax=qmin,則q′=1。

1.2 組合函數

雖然服務的組合類型不同,但都可將其分解為順序類型的組合函數。順序類型的組合服務由n個組件順序構成,其花費和及時性具有累加特點,而可用性、可靠性和滿意度則具有累乘特點,如表1所示。

表1 組合函數

1.3 事務屬性

由于網絡的動態性和不穩定性,組合服務在運行過程中可能存在服務失效或異常情況,這會降低組合服務的可靠性。事務性組合服務就是利用事務處理的方法來保證組合服務的可靠性和一致性。在文獻[14]中,服務的事務屬性包含如下幾類:可補償的事務屬性(c)、可重試的事務屬性(r)、樞紐事務屬性(p),及它們的組合cr(可補償+可重試)。組合服務的事務屬性由其組成部分的事務屬性來決定[14]。若該組合服務的事務屬性是{p,c,r,cr}之一,則這個組合服務滿足事務屬性的要求。為了保證組合服務的事務屬性,設置了事務優先級,cr的優先級為L3,c和r的優先級都為L2,p的優先級為L1,其中L3>L2>L1,并約定c和r不可比較。

1.4 多目標服務優化選擇模型

本文將及時性、可用性和滿意度作為三個目標準則,希望組合服務CS的響應時間短,可用性與滿意度高。設置五個QoS約束條件和一個事務約束條件,A0表示組合服務的最低可用性,T0表示組合服務的最大反應時間,C0表示組合服務的最高花費,R0表示組合服務的最低可靠性,S0表示組合服務的最低信譽度,TP(CS)表示組合服務的事務屬性。對于QoS屬性來說,有些是越大越好,有些是越小越好,因此我們統一求Maximum,即在及時性的計算公式前面加負號。帶約束條件的多目標優化模型如下:

Maximum(-T(CS),A(CS),S(CS))

s.t.

(1)A(CS)≥A0

(2)T(CS)≤T0

(3)C(CS)≤C0

(4)R(CS)≥R0

(5)S(CS)≥S0

(6)TP(CS)∈{p,c,r,cr}

2 多目標服務優化選擇方法

本文提出的改進多目標算法采用的是混合優化選擇方法,將煙花爆炸算法[17]與差分進化算法[18]相結合,利用外部存檔中的解作為Pareto最優解集。

2.1 編碼策略

采用一個整數數組進行編碼,數組的長度為個體所包含的服務數,數組中每個元素的值為對應抽象服務綁定的具體服務實例的標識。圖1中是6個服務構成的組合服務,其中S[1]3表示第1個抽象服務選擇了其第3個候選服務實例,依此類推。

S[1]3S[2]6S[3]8S[4]10S[5]20S[6]2

2.2 煙花爆炸算法

煙花彈在空中爆炸會釋放出許多火星,且火星分布在以煙花彈為中心的一定區域范圍內。對于煙花xi,其產生的火星數目si計算公式為:

(3)

式中:fmin表示種群中最小的適應度值;α和m是常數,m用來控制火星個數。煙花xi爆炸產生的半徑Ai的計算公式如下:

(4)

式中:fmax是種群中適應度的最大值;A是常數,用來調整爆炸半徑的大小。針對組合服務問題,我們通過變異率來替換半徑大小,即好的煙花爆炸后產生的半徑小,其對應組合服務的變異率就小,差的煙花爆炸后產生的半徑大,其對應組合服務的變異率就大。假設候選個體集合大小為K,煙花種群的大小為N,要在候選個體集合中選擇N-1個個體進入到下一代,對于候選者xi,其被選擇的概率計算公式如下:

(5)

式中:R(xi)為xi到候選個體集合中的其他個體的距離之和。

(6)

式中:d(xi,xj)表示個體xi和xj的距離。在種群集合中,若個體的密度高,則選中該個體的概率就小。

2.3 啟發式的差分進化算法

差分進化算法(DE)由變異、交叉和選擇操作構成。對于第t代種群中的每一個目標個體向量Xi(t),其相應的變異操作如下:

Vi(t+1)=Xbest(t)+F×(Xr1(t)-Xr2(t))

(7)

式中:r1、r2為隨機選擇的整數,且與個體i不相同,表示父代種群中兩個不同的個體;Xbest(t)是基向量;F為常數,稱為縮放因子,用來控制差分向量的縮放程度。結合組合服務的特點,我們設置變異操作公式中的F=1。假設有兩個個體Xr1(t)=(S[1]3,S[2]5,S[3]6,S[4]3),Xr2(t)=(S[1]6,S[2]5,S[3]9,S[4]2),將Xr1(t)與Xr2(t)比較,只有第2個服務相同,所以Xr1(t)-Xr2(t)=(1,0,1,1)。在Xbest(t)+(Xr1(t)-Xr2(t))的計算過程中,對Xbest(t)的第1、3、4個服務進行變異,從而產生變異個體向量Vi(t+1)。

為了增強種群的多樣性,差分進化算法將目標向量個體Xi(t)與其相應的變異個體Vi(t+1)進行啟發式的交叉操作,得到試驗個體,即目標個體的候選個體Ui(t+1)。

(8)

式中:xij(t)表示父代種群中目標個體向量Xi(t)中的第j維分量;vij(t+1)為變異個體Vi(t+1)中的第j維分量;tp(xij(t))表示Xi(t)的第j維分量的事務屬性。

差分進化算法利用優勝劣汰的方法來引導算法向全局最優解逼近。在選擇操作中,算法首先對試驗個體Ui(t+1)和目標個體Xi(t)的適應度值進行計算,然后將二者進行比較,并按照式(9)來選擇適應度值較優的個體進入下一代。

(9)

經過以上的變異、啟發式的交叉和選擇操作,種群將進化到下一代,該過程反復循環,直到算法達到預定的最大迭代次數時算法結束。

2.4 適應度計算

本文采用了一種可行解優先的法則來處理約束條件,具體內容如下:(1) 如果i是可行解,j是不可行解,則i優于j;(2) 如果i和j都是可行解,則目標函數適應值大的個體較好;(3) 如果i和j都是不可行解,則違反約束力最少的個體較好。可行解的適應度值由支配度(Domination Value)與密度(Density)兩個方面共同決定[19]。若i和j的支配度不同,則支配度值大的適應度值大;若i和j的支配度相同,則考慮解的密度。可行解i的適應度函數計算公式如下:

Fitness(i)=Domination-Value(i)×Density(i)

(10)

個體i的支配度由其支配其他個體的個數來決定。個體i擁擠距離的計算方法是:首先針對一個目標,計算圍繞個體i的最近兩個體的目標函數值差的絕對值,然后用該絕對值除以該目標的最大值與最小值的差,得到個體i的一個目標距離值,其次計算出個體i所有目標的目標距離值,最后將i的所有目標距離值進行平均即得密度,計算公式如下:

(11)

針對不可行解,我們設置了不可行度閾值α,計算公式如式(12)所示。該閾值能夠在種群中保留一部分目標值較好的不可行解,從而達到由不可行解向可行解演變的目的,防止算法的未成熟收斂。

(12)

式中:T表示迭代次數;v(i)表示個體i違反約束的程度;n為群體規模。如果i的約束違反度小于給定的閾值,則i的適應度值按照式(10)計算,否則按照式(13)計算。

Fitness(i)=-∑vk/Domination-Value(i)

(13)

式中:vk表示個體i違反第k個約束的程度。

2.5 外部存檔

算法采用外部存檔來存儲進化優良個體加入外部存檔[20]。算法開始時外部存檔為空,隨著迭代次數的增加,那些不被父代個體所支配的試驗個體將與外部存檔中的個體依次比較,若試驗個體被外部存檔中的個體所支配,則拒絕該試驗個體加入到外部存檔中;若試驗個體支配外部存檔中的某些個體,則被支配的個體將從外部存檔中剔除;若試驗個體與外部存檔中的個體之間互不占優,則試驗個體是一個Pareto解從而加入到外部存檔中。當外部存檔的容量達到最大時,我們采用文獻[20]中基于緊鄰個體間距離值和最小的剔除方法來進行處理。該方法首先將新的非支配解加入到外部存檔中,然后求取所有個體與其緊鄰個體之間的距離值,其次求取任一個體左右緊鄰的兩個距離值和,最后剔除距離值和最小的個體。

2.6 改進的多目標優化算法

改進的多目標優化算法通過煙花爆炸與變異算子實現了局部搜索,同時利用差分進化算法使種群具備較好的分布性和擴展性,進而向Pareto前沿面搜索。

步驟1在解空間內隨機生成滿足事務屬性要求的n個體來構成種群P,創建空的外部存檔NP。

步驟2計算P中每個個體的適應度值,從種群P中選出非支配個體來更新NP,t=1。

步驟3若終止條件不滿足,則執行步驟4到步驟7,否則轉至步驟8。

步驟4利用式(3)和式(4)生成新的種群P1,利用式(10)和式(13)計算新產生個體的適應度值,用新個體更新外部存檔NP。

步驟5在種群P1中選擇n個個體構成種群P2,個體的選擇概率與其適應度值成正比。

步驟6對種群P2中的每個個體利用式(7)、式(8)和式(9)所示的變異及交叉操作生成子代個體,計算新產生個體的適應度值,用新個體更新外部存檔NP。

步驟7利用式(5)和式(6)中基于距離的選擇方法選擇n個個體構成新的種群,迭代次數t=t+1,返回步驟3。

步驟8輸出非支配解集NP,并終止算法。

3 實驗與結果分析

以下通過仿真實驗分析算法的可行性和有效性。實驗環境為Windows 10,內存為8 GB,開發語言為Python。在交通出行應用場景中提取8個抽象服務構成全體抽象服務集合,并假定流程為順序結構,考慮了五種QoS屬性:花費、及時性、可用性、可靠性和滿意度。文獻[21]給出了仿真QoS數據在取值范圍內的生成規則,文獻[22]中給出的QWS2.0數據集收集了網絡上實際存在的Web服務集,這些屬性提供者都是通過標準的測量工具測得的真實數據。百度地圖中針對服務給出了真實的評分和滿意度數據。本文參考文獻[21-22]與百度地圖中的服務數據,得到相應的實驗指標數據。服務的事務屬性從{p,c,r,cr}中隨機選擇。本文從問題規模、約束強度、迭代次數三個方面進行比較,采用Hypervolume[23]評價指標來分析各算法的優劣。Hypervolume指標能夠對解集的收斂性、均勻性、廣泛性進行評估,從而給出解集的綜合評估結果。圖2中虛線所圍的部分即是集合w={w1,w2,w3,w4}的Hypervolume指標值HV(w),而個體w5則被集合{w1,w2,w3,w4}所支配。

圖2 Hypervolume指標

Hypervolume指標值越大表明集合的質量越高。為了比較不同的多目標優化算法的性能,我們融合多個優化算法的Hypervolume指標值,得到最大的集合wmax,然后利用式(14)計算集合w的HV ratio的值:

HVratio=HV(w)/HV(wmax)

(14)

θ用來表示全局約束的強度。對于積極屬性與消極屬性,分別用式(15)與式(16)計算θ。

(15)

(16)

3.1 問題規模方面的性能比較

設定約束強度為0.2,候選服務數量從40增加到120。如表2所示,隨著問題規模的增長,混合算法始終保持了較高的HV ratio值,優于其他算法。當候選服務數量為120時,混合算法的HV ratio為91.4%,NSGA-II-DE的值為89.3%,MOPSO的值為87.5%,NSGA-II的值為87.1%,GDE的值為78.4%。實驗結果表明,本文算法在不同的問題規模情況下均能夠得到較好的解,由此可以驗證本文算法在解決大規模服務選擇問題上具有可行性和有效性。

表2 候選服務數量方面的性能比較

3.2 約束強度方面的性能比較

設置候選服務數量為100,約束強度從0.2增長到0.6。隨著約束強度的增大,滿足約束的個體數量降低。表3所示混合算法的HV ratio值始終保持在90%以上。當約束強度為0.6時,混合算法的HV ratio值為91%,NSGA-II-DE的值為88.1%,MOPSO的值為86.2%,NSGA-II的值為85.1%,GDE的值為66.3%。由此可見,混合算法能夠有效地解決強約束情況下的多目標服務選擇問題。

表3 約束強度方面的性能比較

3.3 迭代次數方面的性能比較

設置候選服務數量為100,約束強度為0.2,迭代次數從0到400。隨著迭代次數的增大,算法的HV ratio值都逐漸增大。在圖3中,當迭代400次時,混合算法的HV ratio值達到93.1%,NSGA-II-DE的值為91.5%,MOPSO的值為90.6%,NSGA-II的值為87.3%,GDE的值為80.2%。經過比較,混合算法能夠收斂到較高值,這說明混合算法求得的Pareto最優解能夠很好地逼近理論Pareto最優解。相對于其他算法,混合算法在解集的分布和范圍上具有明顯優勢,從而驗證了其在多目標優化選擇問題上的有效性,能夠滿足用戶對算法求解精度的要求。

圖3 迭代次數方面的性能比較

4 結 語

本文分析了交通出行服務的QoS和事務維度屬性,建立了多目標服務優化選擇模型。基于該模型,給出基于煙花爆炸與啟發式差分進化的混合優化算法。實驗結果表明,混合優化算法有較好的搜索性能,保證種群在進化過程中保持良好的分布性和擴展性,收斂性好,能夠有效地解決多目標服務優化選擇問題。下一步將研究面向交通領域的數據密集型服務的多目標選擇問題,并進一步改進算法的性能。