質(zhì)量感知的多目標(biāo)云制造服務(wù)組合優(yōu)化算法

劉桂森,賈兆紅,2+

(1.安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,安徽 合肥 230601;2.安徽大學(xué) 計(jì)算智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室,安徽 合肥 230601)

0 引言

云制造3.0系統(tǒng)為制造業(yè)與信息通信技術(shù)的深度融合提供了智能制造系統(tǒng)新模式[1]。云制造融合了網(wǎng)絡(luò)化制造和服務(wù)、云計(jì)算、高性能計(jì)算、物聯(lián)網(wǎng)等技術(shù),實(shí)現(xiàn)硬件設(shè)備、計(jì)算系統(tǒng)、軟件、數(shù)據(jù)、知識(shí)等分類資源的統(tǒng)一制造、集中管理和運(yùn)營(yíng),為制造全生命周期過(guò)程提供可隨時(shí)獲取、按需使用、安全可靠、優(yōu)質(zhì)廉價(jià)的各類制造服務(wù),是一種面向服務(wù)的網(wǎng)絡(luò)化制造模式[2]。

在云制造環(huán)境中,用戶將制造任務(wù)提交到服務(wù)平臺(tái),服務(wù)平臺(tái)通過(guò)分析任務(wù)復(fù)雜度分解任務(wù),并根據(jù)用戶需求從平臺(tái)中選擇符合的服務(wù)進(jìn)行組合,以共同執(zhí)行用戶任務(wù)[3]。然而,云計(jì)算的服務(wù)提供商不斷提供功能相似但質(zhì)量不同的云服務(wù)[4],如何在大量云服務(wù)中選擇組合以滿足用戶的服務(wù)質(zhì)量(Quality of Service,QoS)期望,即QoS感知云服務(wù)組合(Quality of Service—Cloud Service Composition,QoS-CSC)問(wèn)題[5],成為計(jì)算服務(wù)供應(yīng)中的關(guān)鍵問(wèn)題[6]。

例如,隨著現(xiàn)代社會(huì)的發(fā)展,汽車的私人定制逐漸成為一種趨勢(shì)。一款車包括基礎(chǔ)、外部配置、內(nèi)部配置、安全配置、特色配置5部分。基礎(chǔ)部分包括汽車的發(fā)動(dòng)機(jī)、變速箱、底盤三大件,是汽車的主要組成部分;外部配置包括天窗類型、行李架、輪轂等;內(nèi)部配置包括方向盤、液晶儀表等;安全配置包括主動(dòng)安全和被動(dòng)安全;特色配置指車載冰箱、車內(nèi)香氛裝置等。汽車的每個(gè)模塊及部件均有多家供應(yīng)商,每家供應(yīng)商提供的零部件都具有相同功能但功能屬性不同,如成本、時(shí)間、可靠性、可用性、信譽(yù)度等QoS,如何從不同供應(yīng)商中選擇合適的廠家零部件,以完成汽車的私人定制,滿足用戶需求,是云制造服務(wù)組合(Cloud Manufacturing Service Composition,CMSC)的關(guān)鍵。

隨著云環(huán)境中類似的單一服務(wù)越來(lái)越多,CMSC問(wèn)題也成為NP-hard(non-deterministic polynomial—hard)問(wèn)題[7]。由于數(shù)學(xué)模型的非線性特性以及大量的候選服務(wù),采用線性和整數(shù)規(guī)劃等精確方法通常不可行。BAO等[8]用有限狀態(tài)機(jī)來(lái)規(guī)定Web服務(wù)的合法調(diào)用順序,提出一種基于樹修剪的改進(jìn)算法來(lái)創(chuàng)建Web服務(wù)組合樹,生成所有可行的執(zhí)行路徑后,采用簡(jiǎn)單加權(quán)技術(shù)選擇最佳解決方案;CHEN等[9]將帶有約束的多目標(biāo)優(yōu)化問(wèn)題改成兩個(gè)主要目標(biāo),即最小QoS風(fēng)險(xiǎn)(使QoS目標(biāo)與用戶約束之間的差異最小)和最大化QoS性能;JIAN等[10]提出改進(jìn)的鳥群優(yōu)化算法,在基本鳥群優(yōu)化的基礎(chǔ)上引入二階震蕩方程和鳥類的歷史位置記憶來(lái)最小化服務(wù)組合的整體時(shí)間成本;ZHOU等[11]提出一種混合人工蜂群算法,將CMSC問(wèn)題轉(zhuǎn)變?yōu)殡p目標(biāo)問(wèn)題求解;LIANG等[12]將CMSC分為上升和下降的QoS標(biāo)準(zhǔn),采用具有雙重限制的服務(wù)選擇模型進(jìn)行優(yōu)化;YANG等[13]提出一種增強(qiáng)型灰狼優(yōu)化(Enhanced Multi-Objective Grey Wolf Optimizer,EMOGWO)算法,同時(shí)優(yōu)化QoS與能源消耗兩個(gè)目標(biāo)。另外,遺傳算法(Genetic Algorithm,GA)[14]、粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法[15]、MOEAQI(multi-objective evolutionary algorithm framework for service selection with QoS constraints and inter-service correlations)算法等也用于求解服務(wù)組合問(wèn)題,但是這些算法往往通過(guò)加權(quán)組合將多目標(biāo)問(wèn)題簡(jiǎn)化為單目標(biāo)問(wèn)題,很少考慮同時(shí)優(yōu)化4個(gè)或4個(gè)以上目標(biāo)。在多維空間中平衡開發(fā)與探索面臨諸多挑戰(zhàn)[16],如非支配解的指數(shù)增長(zhǎng)所帶來(lái)的收斂壓力損失[17],以及無(wú)效的多樣性維持機(jī)制所導(dǎo)致的反收斂現(xiàn)象[18]。本文針對(duì)同時(shí)優(yōu)化時(shí)間、成本、可靠性、可用性、信譽(yù)度的服務(wù)組合問(wèn)題,提出一種基于自適應(yīng)選擇和反向?qū)W習(xí)策略的進(jìn)化算法(Evolutionary Algorithm based on Adaptive selection and Reverse learning Strategy,ARSEA),首先根據(jù)QoS對(duì)服務(wù)進(jìn)行聚類,剔除效果比較差的服務(wù),其次為目標(biāo)空間中的參考向量分配近鄰和遠(yuǎn)鄰參考向量,然后采用反向?qū)W習(xí)策略增加初始種群的多樣性,在迭代過(guò)程中通過(guò)動(dòng)態(tài)調(diào)整選擇概率自適應(yīng)選擇參與交配的父代個(gè)體,以統(tǒng)一算法的多樣性與收斂性。

1 問(wèn)題描述

1.1 相關(guān)定義

在云制造環(huán)境下,不同于單一的制造任務(wù),加工前為了提高產(chǎn)品質(zhì)量,需將復(fù)雜的制造任務(wù)分解成多個(gè)子任務(wù),根據(jù)每個(gè)子任務(wù)的功能需求生成多個(gè)候選服務(wù)CS,即一組功能相同但非功能屬性不同的服務(wù),構(gòu)成相應(yīng)的云服務(wù)集CSS,再?gòu)南鄳?yīng)的候選云服務(wù)集中獲得每個(gè)子任務(wù)的制造服務(wù)[19]。在此基礎(chǔ)上,基于邏輯序列所選CS組成的組合制造服務(wù)(Composite Manufacturing Service,CMS)可以同時(shí)滿足功能和QoS要求。因此,復(fù)雜制造任務(wù)的執(zhí)行過(guò)程分為4個(gè)步驟:①分析請(qǐng)求和分解任務(wù);②搜索和匹配;③組成服務(wù)和選擇優(yōu)化;④執(zhí)行和反饋任務(wù)。針對(duì)步驟3,給出以下定義。

定義1復(fù)雜制造任務(wù)。ZT={T1,T2,…,Ti},ZT為復(fù)雜制造總?cè)蝿?wù),Ti為所分解的第i個(gè)子任務(wù),i=1,2,…,n。

定義3服務(wù)質(zhì)量。QoS={q1,q2,…,qr},QoS表示CS的非功能屬性,如時(shí)間、成本、效率或可用性,qr為CS的第r個(gè)服務(wù)質(zhì)量屬性值,r=1,2,…,m。

其中,本文擴(kuò)展了服務(wù)質(zhì)量的屬性個(gè)數(shù)。

1.2 服務(wù)質(zhì)量模型

由于QoS由多個(gè)側(cè)重于不同方面的非功能度量組成,很難有所有度量值同時(shí)最佳的解決方案,往往采用一組各度量值相互權(quán)衡的Pareto最優(yōu)解,即改進(jìn)其中一個(gè)度量值可能導(dǎo)致其他度量值惡化。例如,時(shí)間和成本通常是一對(duì)相互矛盾的屬性,縮短時(shí)間可能增加成本。鑒于可測(cè)量性的重要性,本文針對(duì)CMSC的順序、平行、選擇和循環(huán)4種基本復(fù)合結(jié)構(gòu),研究不同結(jié)構(gòu)復(fù)合服務(wù)的聚合QoS公式(如表1),對(duì)這5個(gè)QoS進(jìn)行組合評(píng)估,使整體QoS值達(dá)到最優(yōu)以滿足用戶要求。對(duì)5個(gè)屬性指標(biāo)的描述如下:

表1 不同結(jié)構(gòu)復(fù)合服務(wù)的聚合QoS公式

(1)時(shí)間 從用戶提交制造任務(wù)到該任務(wù)完成并返回結(jié)果的時(shí)間。

(2)成本 當(dāng)所執(zhí)行的云制造服務(wù)完成后,服務(wù)提供商向用戶收取的服務(wù)費(fèi)用。

(3)可靠性 在給定的時(shí)間和條件下,成功執(zhí)行制造任務(wù)的能力。

(4)可用性 在云制造服務(wù)平臺(tái)中,用戶在一定時(shí)間內(nèi)成功調(diào)用制造服務(wù)的能力。

(5)信譽(yù)度 指服務(wù)提供商完成該制造任務(wù)的信譽(yù)履約度。

根據(jù)文獻(xiàn)[15],可以將平行結(jié)構(gòu)、選擇性結(jié)構(gòu)和循環(huán)結(jié)構(gòu)轉(zhuǎn)化為順序結(jié)構(gòu)。另外,由于聚合QoS標(biāo)準(zhǔn)值尺度不同會(huì)嚴(yán)重影響基于分解的多目標(biāo)進(jìn)化算法(Multi-Objective Evolutionary Algorithm,MOEA)標(biāo)度函數(shù),所有聚合的QoS值均在[0,1]內(nèi)歸一化。可靠性、可用性、信譽(yù)度屬于正屬性,時(shí)間和成本屬于負(fù)屬性。對(duì)于QoS的正屬性,較大的值性能更好;對(duì)于負(fù)屬性,較小的值性能更好。正準(zhǔn)則和負(fù)準(zhǔn)則的歸一化方法如下:

(1)

Q(qosr(x)=(Q1(qos1(x)),Q2(qos2(x)),Q3(qos3(x)),
Q4(qos4(x)),Q5(qos5(x)))。

s.t.

x∈Ω。

(2)

其中:Q1～Q5分別表示時(shí)間、成本、可靠性、可用性和信譽(yù)度指標(biāo);Ω表示決策空間。

2 ARSEA算法

2.1 算法框架

本文所提的ARSEA算法流程如下:

算法1ARSEA框架。

輸入:種群規(guī)模N、權(quán)重向量的鄰居向量個(gè)數(shù)H、初始交配選擇的概率Q、間隔代數(shù)L、變異概率P。

輸出:歸檔種群EP。

步驟1過(guò)濾候選服務(wù)。

步驟2在目標(biāo)空間中生成均勻的參考向量,并為每個(gè)參考向量確定其近鄰參考向量和遠(yuǎn)鄰參考向量。

步驟3種群初始化。

步驟4采用反向?qū)W習(xí)策略進(jìn)一步優(yōu)化初始種群。

步驟5迭代:

(1)對(duì)種群中的每個(gè)個(gè)體采用選擇策略,然后交叉、變異得到新個(gè)體Y,更新近鄰解。

(2)將種群中的非支配個(gè)體加入歸檔種群EP,并更新歸檔種群EP。

(3)采用概率更新策略改變交配選擇概率。

首先采用K-means聚類過(guò)濾候選服務(wù);然后在目標(biāo)空間生成一組均勻的參考向量,根據(jù)向量之間的余弦角度找出每個(gè)向量的近鄰向量和遠(yuǎn)鄰向量;其次,將初始化種群中的個(gè)體與參考向量一一對(duì)應(yīng)。步驟4采用反向?qū)W習(xí)策略生成反轉(zhuǎn)的種群,通過(guò)比較反轉(zhuǎn)種群與原初始種群產(chǎn)生最終的初始種群,以提高種群的多樣性。在迭代搜索過(guò)程中,先通過(guò)選擇策略從父代選出優(yōu)秀個(gè)體參與交配,再根據(jù)Pareto方法從新生個(gè)體與其他個(gè)體中選擇較優(yōu)的解放入歸檔種群EP,根據(jù)新解的貢獻(xiàn)度自動(dòng)更新父代選擇概率來(lái)平衡全局開發(fā)與局部探索。

2.2 過(guò)濾候選服務(wù)

隨著智能制造的高速持續(xù)發(fā)展,云制造平臺(tái)中的服務(wù)越來(lái)越多,在CMSC的方案中,可供選擇的候選服務(wù)也越來(lái)越多,需要根據(jù)候選服務(wù)的QoS對(duì)服務(wù)進(jìn)行選擇過(guò)濾以縮短求解時(shí)間,而聚類方法有助于提升服務(wù)選擇的效率。K-means聚類按照類內(nèi)相似度最大化和類間相似度最小化原則對(duì)數(shù)據(jù)樣本進(jìn)行分組,是最常用的無(wú)監(jiān)督聚類方法之一。因此本文基于K-means對(duì)候選云服務(wù)集進(jìn)行聚類,并對(duì)候選服務(wù)進(jìn)行等級(jí)劃分,在得到的每一簇中去除等級(jí)最差的候選服務(wù),如算法2所示。

算法2過(guò)濾候選服務(wù)。

輸入:決策空間信息S1、聚類的簇?cái)?shù)Nc(默認(rèn)與目標(biāo)數(shù)一致)。

輸出:決策空間信息S。

步驟1隨機(jī)選擇Nc個(gè)候選服務(wù)作為簇的中心。

步驟2對(duì)于每一個(gè)簇,計(jì)算簇的質(zhì)心。

步驟3對(duì)于每個(gè)候選服務(wù),計(jì)算其與Nc個(gè)簇質(zhì)心的歐式距離,將其加入距離最小的簇中。

步驟4再次計(jì)算各個(gè)簇的質(zhì)心,如果質(zhì)心位置不變,則執(zhí)行步驟5,否則轉(zhuǎn)步驟3。

步驟5對(duì)每一個(gè)簇中的候選服務(wù),采用式(3)計(jì)算函數(shù)d并進(jìn)行排序,剔除本簇后10%的候選服務(wù)。

2.3 反向?qū)W習(xí)策略

由于CMSC為NP-hard問(wèn)題,在算法初始階段采用如算法3所示的反向?qū)W習(xí)策略改進(jìn)初始種群在解空間的分布,以提高算法的多樣性。首先,在每個(gè)子任務(wù)候選云服務(wù)集中計(jì)算每個(gè)候選服務(wù)與最優(yōu)服務(wù)之間的距離

(3)

算法3反向?qū)W習(xí)。

輸入:初始種群P1、決策空間信息S。

輸出:種群P。

步驟2對(duì)P1中的每個(gè)體,計(jì)算每個(gè)候選服務(wù)在上述排序中的位置,選擇其相反位置的候選服務(wù)組成新的個(gè)體。

步驟3由新的個(gè)體組成新的初始種群P2。

步驟4利用切比雪夫法則比較并保留較優(yōu)的個(gè)體,得到最終的初始種群P。

2.4 選擇策略及概率更新策略

本文采用算法4所示的選擇策略。在選擇父代重組交配時(shí),相近個(gè)體間交配有利于算法的局部開發(fā)能力,較遠(yuǎn)個(gè)體間交配有利于算法的全局探索能力,而且在選擇相近個(gè)體時(shí),從其近鄰范圍內(nèi)的非支配個(gè)體中挑選父代更有利于算法收斂。另外,通過(guò)自適應(yīng)改變交配選擇概率,算法可以自動(dòng)調(diào)整搜索方向。

算法4選擇策略。

輸入:初始交配選擇的概率Q。

輸出:交配父代x1,x2。

步驟1如果產(chǎn)生的隨機(jī)數(shù)大于Q,則隨機(jī)選擇其遠(yuǎn)鄰向量對(duì)應(yīng)的個(gè)體作為x1,x2。

步驟2如果產(chǎn)生的隨機(jī)數(shù)小于等于Q,則先確定其近鄰向量對(duì)應(yīng)的個(gè)體群中非支配解的個(gè)數(shù)n,如果n>2,則隨機(jī)選擇個(gè)體群中的非支配個(gè)體作為x1,x2,否則隨機(jī)選擇個(gè)體群中的個(gè)體作為x1,x2。

在種群進(jìn)化過(guò)程中,算法進(jìn)行全局和局部搜索的需求是可變的,因此本文采用如圖1所示的概率更新流程圖更新交配選擇概率,以平衡算法的開發(fā)和探索能力。早期需要提高算法的全局探索能力,隨著迭代的進(jìn)行需要更好的局部開發(fā)能力,因此為了在開發(fā)和探索之間取得平衡,采用式(4)自適應(yīng)地調(diào)整交配概率,使算法間隔一定代數(shù)后,可以自動(dòng)調(diào)整Q的大小,其中n1和n2分別為前L代種群中由近鄰和遠(yuǎn)鄰交配產(chǎn)生的新個(gè)體數(shù)。

(4)

2.5 算法的時(shí)間復(fù)雜度分析

3 仿真實(shí)驗(yàn)及結(jié)果分析

為了評(píng)估所提ARSEA的性能,選用4種對(duì)比算法,即具有對(duì)抗性搜索的自適應(yīng)雙種群進(jìn)化算法(Adaptive Dual-population evolutionary Paradigm with Adversarial Search,ADPAS)[20]、EMOGWO算法、基于支配和分解的多目標(biāo)進(jìn)化算法(Multi-Objective Evolutionary Algorithm based on Dominance and Decomposition,MOEA/DD)和基于參考向量引導(dǎo)的多目標(biāo)優(yōu)化進(jìn)化算法(Reference Vector guided Evolutionary Algorithm for many-objective optimization,RVEA)[21],其中ADPAS和EMOGWO是兩種解決CMSC最先進(jìn)的算法,MOEA/DD和RVEA是兩種最新提出的經(jīng)典MOEA。另外對(duì)ARSEA的策略進(jìn)行了驗(yàn)證。

3.1 實(shí)驗(yàn)設(shè)計(jì)

采用15個(gè)隨機(jī)生成的測(cè)試算例驗(yàn)證ARSEA在各種條件下的探索和開發(fā)性能,算例的因素和取值范圍如表2所示。每個(gè)實(shí)例由工作流中的子任務(wù)和候選服務(wù)組成,代表不同的CMSC場(chǎng)景。優(yōu)化目錄m的數(shù)量設(shè)置為5,子任務(wù)和候選服務(wù)分別記為T和S,例如T20S60表示有20個(gè)子任務(wù),每個(gè)子任務(wù)有60個(gè)候選服務(wù)、5個(gè)優(yōu)化目標(biāo)。

表2 算例的因素和取值范圍

每個(gè)候選服務(wù)均有時(shí)間、成本、可靠性、可用性、信譽(yù)度QoS標(biāo)準(zhǔn),并隨機(jī)生成一個(gè)綜合QoS數(shù)據(jù)集,其取值范圍如表3所示。所有算法均使用C++編程,在Core i5、3.40 GHz處理器和16 GB RAM的Windows 10 PC上運(yùn)行。

表3 QoS數(shù)據(jù)取值范圍

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

采用田口法為ARSEA選取合適的參數(shù)。ARSEA考慮的主要參數(shù)包括交配選擇概率的更新代數(shù)L、鄰居向量的個(gè)數(shù)H和變異概率P,取值范圍如表4所示。根據(jù)田口法設(shè)計(jì)了9個(gè)參數(shù)組合實(shí)例組,如表5所示。

表4 ARSEA參數(shù)取值范圍

表5 參數(shù)組合

采用反轉(zhuǎn)世代距離IGD評(píng)估具有不同參數(shù)組合的ARSEA性能,用15個(gè)測(cè)試實(shí)例中每個(gè)參數(shù)組合的ARSEA的平均IGD值作為響應(yīng)變量,在MINITAB 19版本上運(yùn)行。實(shí)驗(yàn)結(jié)果如圖2所示,其中x軸表示不同因素對(duì)應(yīng)的水平,y軸表示均值響應(yīng)值,平均值越小表示對(duì)應(yīng)組合參數(shù)的ARSEA效果越好。從圖2可見,最佳參數(shù)值為L(zhǎng)=3,H=15,P=0.1。

ARSEA其他參數(shù)的設(shè)置與4種比較算法相同,即種群規(guī)模N=126,交叉概率設(shè)置為1.0,迭代次數(shù)為500。初次交配選擇的概率P1=0.3,以確保搜索開始時(shí)ARSEA具有更好的勘探能力。對(duì)于每個(gè)實(shí)例,每個(gè)算法重復(fù)運(yùn)行30次,取其平均值作為最終的統(tǒng)計(jì)結(jié)果。

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

采用如下3個(gè)評(píng)價(jià)指標(biāo):

(1)非支配解集規(guī)模NNS表示每種算法獲得的非支配解決方案的數(shù)量,獲得的非支配解決方案越多,為決策者提供的選擇越多,算法的多樣性也就越好。

(2)反轉(zhuǎn)世代距離IGD描述非支配解集與Pareto邊界的接近程度,用于評(píng)估解集的收斂性和多樣性[22],定義為

(5)

式中:υ為某一種比較算法獲得的非支配解集;ρ為所有算法獲得的非支配單個(gè)集合的并集。IGD值越小,算法的收斂性和多樣性越好,越接近真實(shí)的Pareto前沿。

(3)間距度量Spacing反映非支配解集前沿分布的均勻性[23],定義為

(6)

3.4 實(shí)驗(yàn)結(jié)果

ARSEA中采用的策略包括反向?qū)W習(xí)策略、選擇策略和概率更新策略。首先設(shè)計(jì)ARSEA的變體驗(yàn)證所提策略的有效性,其次將ARSEA與其他先進(jìn)算法進(jìn)行比較。在表6～表10中,第1列均為實(shí)例編碼,每個(gè)實(shí)例組的最佳結(jié)果用粗體顯示。

3.4.1 反向?qū)W習(xí)策略的性能

本文設(shè)計(jì)了不含反向?qū)W習(xí)策略的ARSEA變體ARSEA-NRL(ARSEA-non-reverse learning)與ARSEA進(jìn)行比較,結(jié)果如表6所示。

表6 在IGD和NNS下反向?qū)W習(xí)策略的驗(yàn)證實(shí)驗(yàn)結(jié)果

從表6的NNS值可見,ARSEA-NRL在5個(gè)實(shí)例上勝過(guò)ARSEA,ARSEA在其他10個(gè)實(shí)例上可以獲得更多的非支配解,而且ARSEA在大規(guī)模服務(wù)組合問(wèn)題上的優(yōu)勢(shì)更加明顯。另外,從IGD值可見,ARSEA明顯優(yōu)于ARSEA-NRL,說(shuō)明ARSEA的解質(zhì)量更好,更接近問(wèn)題實(shí)際的Pareto前沿,表明所提反向?qū)W習(xí)策略有益于提高算法性能。

3.4.2 選擇策略的性能

設(shè)計(jì)采用隨機(jī)選擇方法的ARSEA變體ARSEA-R(ARSEA-random)進(jìn)行驗(yàn)證,實(shí)驗(yàn)結(jié)果如表7所示。

表7 選擇策略的驗(yàn)證實(shí)驗(yàn)結(jié)果

從表7可見,ARSEA在IGD和NNS上分別有3個(gè)實(shí)例稍遜于ARSEA-R,而在其他10個(gè)實(shí)例上,ARSEA全部?jī)?yōu)于ARSEA-R,表明ARSEA不但能夠找到質(zhì)量更好的解,而且能夠幫助算法提高解的多樣性。

3.4.3 概率更新策略的性能

將ARSEA算法中的選擇概率分別設(shè)置為固定值0.2,0.5,0.8,對(duì)應(yīng)算法分別記為ARSEA-A,ARSEA-B,ARSEA-C,實(shí)驗(yàn)結(jié)果如表8所示。

表8 概率更新策略的驗(yàn)證實(shí)驗(yàn)結(jié)果

由表8可見,ARSEA在10個(gè)實(shí)例上的NNS值較大,其他3個(gè)變體在5個(gè)實(shí)例上具有優(yōu)勢(shì),說(shuō)明ARSEA可以在大部分實(shí)例上找到更多的非支配解。雖然在小規(guī)模服務(wù)組合問(wèn)題中,ARSEA的IGD值較其他算法沒有明顯優(yōu)勢(shì),但是在較大規(guī)模實(shí)例上的結(jié)果都是最好的,表明自適應(yīng)調(diào)整選擇概率可以在算法的開發(fā)和探索之間取得更好的平衡。

3.4.4 算法整體性能比較

4種對(duì)比算法與ARSEA的比較結(jié)果如表9和表10所示。

表9 5種算法的IGD比較結(jié)果

續(xù)表9

表10 5種算法的間距度量Spacing比較結(jié)果

由表9可見,雖然在3個(gè)小規(guī)模的服務(wù)組合實(shí)例中,ARSEA的結(jié)果不如其他算法,但是其他實(shí)例上ARSEA的結(jié)果都是最好的,表明ARSEA在求解CMSC上能夠找到更多且質(zhì)量更好的解。由表10可見,ARSEA在所有測(cè)試實(shí)例上的Spacing值最小,說(shuō)明ARSEA找到的解分布更均勻,多樣性更好。

為了直觀地比較5種算法的性能,圖3～圖5展示了5種算法的IGD、Spacing值和計(jì)算時(shí)間的對(duì)比結(jié)果。ARSEA的計(jì)算時(shí)間最少,其在圖3中的IGD平均值最低,在圖4中的曲線最靠下,表明在收斂性和多樣性上ARSEA較其他4種算法都具有絕對(duì)優(yōu)勢(shì)。

較低的S值表明ARSEA得到的歸檔種群在Pareto前沿上的分布更加均勻,各個(gè)目標(biāo)之間比較平衡,多樣性更好;較低的IGD值表明ARSEA得到的解的收斂性和多樣性較好,說(shuō)明ARSEA在CMSC 5個(gè)目標(biāo)同時(shí)優(yōu)化問(wèn)題上可以得到較好的解決方案。而且,ARSEA求解服務(wù)組合方案的用時(shí)最少,說(shuō)明ARSEA中過(guò)濾候選服務(wù)的方法很適合解決具有大量候選服務(wù)的CMSC問(wèn)題。從實(shí)驗(yàn)結(jié)果整體來(lái)看,ARSEA比其他算法在CMSC問(wèn)題上得到的解更接近問(wèn)題真實(shí)的Pareto前沿,而且解的均勻性更好。算法求解多目標(biāo)CMSC問(wèn)題得到的每個(gè)非支配解,經(jīng)過(guò)解碼后都是一種制造服務(wù)的組合方案,用戶可以根據(jù)需要選擇歸檔種群中的方案執(zhí)行制造服務(wù),使組合服務(wù)的整體QoS達(dá)到最優(yōu)。

從15組實(shí)例的每種子任務(wù)中各選2組,組成6組實(shí)例,繪制出ARSEA在這6組實(shí)例上IGD值的箱線圖,如圖6所示,其中每組圖中x軸分為5組,每組代表的算法分別是ARSEA,ADPAS,EMOGWO,MOEA/DD,RVEA,每組x軸下方是服務(wù)組合的5個(gè)屬性,通過(guò)這些圖可以明顯看出5個(gè)算法之間的差異,ARSEA雖然在部分算例的前兩個(gè)屬性指標(biāo)上稍差,但是另外3個(gè)屬性指標(biāo)值遠(yuǎn)小于其他對(duì)比算法。因此,綜合圖3和圖4可以看出,ARSEA的整體性能較好,其可以獲得更好的解決方案。

在汽車的私人定制過(guò)程中,用戶可以選擇自己的個(gè)性化零部件,每個(gè)零部件都有若干服務(wù)提供商,這些服務(wù)提供商具有相同的功能屬性和不同的非功能屬性(如時(shí)間、成本、可靠性等)。從不同供應(yīng)商中選擇合適的廠家生產(chǎn)零部件來(lái)完成汽車的私人定制,使非功能屬性最優(yōu),是一個(gè)多目標(biāo)CMSC優(yōu)化問(wèn)題,可以采用ARSEA解決該問(wèn)題。ARSEA的求解時(shí)間最少,效率最高,所求得的非支配解集的多樣性和收斂性較好,即汽車私人定制的解決方案數(shù)最多,給用戶的選擇最多,其求得的解決方案在整體QoS上優(yōu)于其他算法。因此,采用ARSEA選擇合適的供應(yīng)商生產(chǎn)零部件,使用戶整體的時(shí)間、成本、可靠性等最優(yōu),用戶滿意度最高。

4 結(jié)束語(yǔ)

本文從多目標(biāo)優(yōu)化的角度研究CMSC問(wèn)題,提出基于自適應(yīng)選擇和反向?qū)W習(xí)策略的進(jìn)化算法ARSEA,采用K-means聚類剔除較差的候選服務(wù),采用反向?qū)W習(xí)策略增加種群的多樣性,將參考向量分為近鄰和遠(yuǎn)鄰參考向量,利用選擇策略和自適應(yīng)調(diào)整的概率更新策略更好地平衡算法的開發(fā)與探索性能,從而為用戶提供更為優(yōu)質(zhì)的服務(wù)組合。隨著全球生態(tài)環(huán)境問(wèn)題越來(lái)越嚴(yán)峻,綠色生態(tài)、可持續(xù)發(fā)展變得愈加重要,未來(lái)的研究將關(guān)注制造服務(wù)提供商的環(huán)境保護(hù)能力,將電價(jià)函數(shù)等加入優(yōu)化目標(biāo),考慮結(jié)合服務(wù)提供商能耗的CMSC優(yōu)化問(wèn)題。