基于改進磷蝦群算法的服務組合優(yōu)化

廖水聰，孫 鵬，劉星辰，鐘 贇

（1.空軍工程大學信息與導航學院，西安 710077；2.93182部隊，沈陽 110015；3.空軍工程大學裝備管理與無人機工程學院，西安 710051）

（?通信作者電子郵箱lsc520802kgd@163.com）

0 引言

隨著面向服務的架構（Service Oriented Architecture，SOA）技術的逐步應用，大量資源被虛擬化為服務。然而隨著用戶需求的日益復雜，單個服務難以滿足用戶實際需求，將性能單一的單個服務通過服務組合［1］的方式統(tǒng)一起來，構建復合服務以滿足用戶復雜需求，已成為當前研究的主流。隨著服務數量的不斷增加，實際中存在大量功能相同但非功能屬性不同的服務，導致同一服務組合邏輯下存在大量滿足要求的復合服務。為了評價復合服務的優(yōu)劣，學者們引入了服務質量（Quality of Service，QoS）指標來衡量服務的非功能屬性［2］，期望在滿足用戶功能需求的基礎上，找到總體QoS 最佳的服務。這類問題稱為服務組合優(yōu)化問題。

隨著抽象服務和候選服務數量的增多，可能的組合方案數呈爆炸性增長，服務組合優(yōu)化問題已成為非確定性多項式（Non-deterministic Polynomial，NP）難問題，此時如果通過遍歷的方式尋找最佳復合服務，時間代價將變得難以接受。智能優(yōu)化算法因其可以在較短時間內找到全局最優(yōu)或者近似全局最優(yōu)解的特性，常被用于求解服務組合優(yōu)化問題。學者們使用遺傳算法［3-4］、蟻群算法［5-6］、粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法［7］、煙花算法［8］、人工蜂群（Artificial Bee Colony，ABC）算法［9-10］等各類智能優(yōu)化算法來求解服務組合優(yōu)化問題。然而此類算法由于自身尋優(yōu)機理的原因，一方面存在易早熟，陷入局部最優(yōu)解的問題；另一方面時間開銷上仍有待優(yōu)化。

Gandomi 等［11］在南極磷蝦群生存運動行為的基礎上，于2012 年提出了一種磷蝦群（Krill Herd，KH）算法。KH 算法認為磷蝦個體的運動位置受誘導活動、覓食活動和擴散活動影響，基于三種運動設計了全局搜索和局部搜索兩種策略，兩種策略并行工作，顯著提升了算法尋優(yōu)的效率。同時，該算法借鑒了遺傳的思想，在磷蝦運動位置更新后進行交叉操作，提高了算法跳出了局部最優(yōu)解的能力。Gandomi 將KH 算法和其他智能優(yōu)化算法進行對比，驗證了KH 算法較好的尋優(yōu)性能。目前KH 算法主要用于函數優(yōu)化領域［12-15］，較少用于組合優(yōu)化領域，僅有部分學者用于數據聚類［16］等方面，取得了一定的效果，但暫無人用于求解服務組合優(yōu)化問題?？紤]到KH 算法較好的尋優(yōu)性能，本文將KH算法引入到服務組合優(yōu)化領域。

盡管KH 算法能在迭代初期很快地找到優(yōu)秀的可行解，但隨著迭代次數的增加，誘導和覓食運動對磷蝦個體吸引力趨同，算法局部搜索能力下降，也存在容易陷入局部最優(yōu)解的問題。針對上述問題，學者們對KH 算法做了不同程度的改進：文獻［12］中提出一種基于動態(tài)壓力控制算子的KH 算法，用多個優(yōu)秀個體代替?zhèn)鹘y(tǒng)最優(yōu)個體來計算誘導運動，從而加速新磷蝦個體的產生，提高了磷蝦個體的局部探索能力；文獻［13］中利用模擬退火算法和貪婪策略對KH 算法進行改進，模擬退火增加了種群的多樣性，貪婪策略小概率接受模擬退火中適應度低的解，避免算法早熟收斂，增強了算法跳出局部最優(yōu)解的能力；文獻［14］中從改進擴散活動的角度出發(fā)，用和聲搜索代替物理擴散過程，在大多數情況下取得了優(yōu)于基本KH算法和其他優(yōu)化算法的性能；文獻［15］中提出了一種基于對立學習的自由搜索KH 算法，每個磷蝦個體可以根據自己的感知和活動范圍進行搜索，這種自由搜索策略使磷蝦個體能有效跳出局部最優(yōu)，提高了磷蝦種群的多樣性和探索能力。這些針對磷蝦算法的不同改進均旨在提高算法搜索能力，以期找到質量更高的最優(yōu)解，同時盡可能降低算法所需的時間開銷，取得了一定的效果。

本文提出一種加入自適應交叉算子和隨機擾動算子的KH（KH with adaptive crossover and random perturbation operator，PRKH）算法，在增加種群多樣性的同時，一定程度上提高了算法的搜索能力。實驗結果表明，本文提出的PRKH 算法在尋找最優(yōu)復合服務方面優(yōu)于基本KH 算法、PSO算法、ABC 算法和花朵授粉算法（Flower Pollination Algorithm，FPA）。

1 服務組合優(yōu)化問題描述

服務組合優(yōu)化的基本模型可以分為三層：任務層、抽象服務層和候選服務集。如圖1 所示，服務組合優(yōu)化過程可以描述為從任務層中選擇任務T2，然后確定該任務對應的服務工作流程，即抽象服務層中的S1至Sn。最后對每一個抽象服務，從候選服務集中選擇對應的具體服務si，j，在滿足用戶QoS 約束的基礎上尋找QoS最優(yōu)的復合服務。

圖1 服務組合優(yōu)化示意圖Fig.1 Schematic diagram of service composition optimization

1.1 相關定義

定義1任務集合為S=[S1，S2，…，Sn]，n為抽象服務的數量。

定義2候選服務集中的具體服務定義為si，j，其中i≤n，j≤m，m是候選服務集中具體服務的數量。

定義3服務質量是一個4 元組Q=(t，c，ava，rel)，t是服務響應時間，c是服務調用一次的成本，ava是服務可用性，rel是服務可靠性。

定義4W=[ω1，ω2，ω3，ω4]是Q中各屬性對應的權重，并滿足。

定義5服務質量評價函數F=WT*Q。

1.2 QoS計算方法

通常認為QoS 由一些非功能屬性組成，主要包括服務響應時間、服務執(zhí)行費用、服務可靠性、服務可用性等屬性［2］。復合服務QoS 可以由單個服務QoS 來表示，根據組合結構的不同，在順序、并行、選擇、循環(huán)結構下均有對應的計算公式。組合結構和計算公式如圖2和表1所示。

圖2 服務組合結構Fig.2 Service composition structures

表1 不同結構下復合服務QoS計算公式Tab.1 Calculation formulas of composite service QoS under different structures

表1 中，tj、cj、aj、rj分別表示第j個服務的響應時間、服務費用、可用性和可靠性；n為服務的個數，k為循環(huán)結構中具體服務的執(zhí)行次數。

對于成本型屬性，優(yōu)化目標是越小越好；對于效益型屬性，優(yōu)化目標是越大越好。在計算復合服務QoS之前，有必要對QoS 值進行歸一化處理，使得歸一化后的服務的各個QoS屬性值變換到［0，1］域，且實際意義上各QoS屬性值均為越低越好，便于后期算法處理。歸一化公式如下，其中：f為QoS屬性值，maxf為磷蝦群中最大適應度值，minf表示磷蝦群中最小適應度值。

2 基于改進磷蝦群算法的服務組合優(yōu)化

2.1 標準KH算法

KH算法其運動方式可以歸納為誘導運動、覓食運動和隨機擴散。定義磷蝦個體的速度更新公式如下：

其中：Xi為第i只磷蝦的位置；Ni、Fi、Di分別代表誘導運動、覓食運動和隨機擴散。Ni的構造公式如下：

其中：Nmax表示最大誘導速度；αi代表誘導方向；ωn代表誘導權重；為上一次運動的誘導活動方向。誘導方向定義如下：

覓食運動主要由食物位置和先前關于食物位置的經驗共同決定。覓食運動公式構造如下：

其中：Vfood是覓食速度；Bi是覓食方向；覓食慣性權重是上一次運動的覓食活動方向。覓食方向由食物對磷蝦個體的吸引力和最佳磷蝦個體對磷蝦的吸引力共同組成，具體計算公式如下：

擴散運動可以理解為一種磷蝦群體隨機性勘探外界的行為，當群體逐漸聚集，整體趨于最優(yōu)時，這種運動會越來越弱，具體構造公式如下：

其中：δ為隨機單位方向矢量，范圍是［-1，1］。

在磷蝦個體速度更新公式的基礎上，定義位置更新公式如下：

其中：Δt是位置更新步長，Ct是取值范圍在［0，2］的步長限制因子，NV是變量的總數，UBj和LBj分別是第j個變量的上限和下限。

為提升算法的性能，Gandomi 在文獻［11］中使用交叉算子對算法進行改進，取得了較好的效果。交叉算子公式如下：

其中：Xi，m表示第i只磷蝦交叉前的位置；Xr，m表示與第r只磷蝦進行了交叉后的磷蝦位置，r是1 到N的隨機數；Ri，m為第i只磷蝦的一個隨機數，用來判定是否需要交叉；Cr為第r只磷蝦對應的交叉概率。

2.2 算法改進策略

2.2.1 自適應交叉算子

Gandomi 在文獻［11］中已通過實驗證明加入交叉算子能有效提高磷蝦算法的性能。然而，不同大小的交叉概率會明顯影響算法收斂情況和尋找最優(yōu)解的能力：較大的交叉概率會幫助算法產生更高比例的新磷蝦位置，在前期快速接近全局最優(yōu)解，提高算法收斂速度，但較大的交叉概率在后期可能會導致磷蝦種群難以穩(wěn)定，算法難以收斂。因此確定一個合適的交叉概率對提升算法性能非常關鍵。

本文借鑒自適應的思想，采用文獻［17］提出的自適應交叉算子，使交叉概率能隨適應度自動改變，隨迭代次數呈現出一種前高后低的態(tài)勢。適應度值低于種群平均值的個體，保持較大的交叉概率，從而更快地產生新的磷蝦位置，加速尋找全局最優(yōu)解。個體適應度值高于種群平均值的個體，交叉概率降低但仍保留一定的交叉概率，使優(yōu)良個體仍處在一種會變化的狀態(tài)，避免算法陷入局部最優(yōu)。自適應交叉算子公式如下：

其中：fmax為最優(yōu)磷蝦的適應度值，favg是磷蝦群的平均適應度值，f ′為待交叉磷蝦的適應度值中較大值；pc1是最大交叉概率，pc2是最小交叉概率，pc1=0.9，pc2=0.6；pc為待交叉概率，對應式（10）中的Cr。

2.2.2 隨機擾動算子

迭代后期磷蝦群在食物中心附近聚集，此時誘導運動和覓食運動對磷蝦位置更新的吸引力趨同，容易陷入局部最優(yōu)解。為了使算法快速收斂和提高算法跳出局部最優(yōu)解的能力，考慮在每輪迭代的最后加入隨機擾動。

如果采用傳統(tǒng)的擾動思想，應該在磷蝦位置更新時，加入一個隨機偏移量以提高算法跳出局部最優(yōu)解的能力，但如果這個隨機偏移量過大，導致產生的新的磷蝦位置跳出邊界范圍，將對尋找最優(yōu)解沒有幫助。因此一方面需要進行邊界檢查，另一方面需要對這個隨機偏移量的范圍進行限制。本文考慮在每輪迭代中誘導運動、覓食運動和隨機擴散運動產生的實際偏移量的基礎上，通過乘以一個在(0.75，1.25)內波動的隨機擾動系數將隨機偏移量限制在(-0.25，0.25)倍實際偏移量的范圍內。同時，這個隨機偏移量應該在迭代前期相對較大，以提高算法在前期的全局搜索能力，在迭代后期相對較小直至歸零，在給算法提供一定局部搜索能力的基礎上，加快算法收斂。因此本文考慮將隨機擾動系數設置為一個隨迭代次數逐漸降低，并最終收斂于1的一個動態(tài)系數。

在此分析的基礎上，本文提出一種隨機擾動算子，定義隨機擾動更新公式如下：

其中：pr是隨機擾動系數。通過式（12）和式（13），給KH 算法的位置更新過程添加了一個擾動系數隨迭代次數降低，系數在(0.75，1.25)內波動最終收斂于1的隨機擾動。

2.3 算法流程

PRKH算法步驟如下：

步驟1 種群初始化和參數設置；

步驟2 隨機生成所有磷蝦的位置集合X、計算適應度值并記錄最佳磷蝦的位置和適應度值f；

步驟3 進入迭代，計算虛擬食物中心的位置Xfood和敏感鄰域半徑ds，j，并不斷更新食物中心位置；

步驟4 按式（3）～（7）計算誘導運動、覓食運動和擴散運動帶來的位置偏移量；

步驟5 按式（11）計算自適應交叉概率pc，按式（12）和（13）執(zhí)行隨機擾動算子，更新磷蝦位置和適應度值；

步驟6 如果滿足終止條件（迭代次數），輸出最佳磷蝦適應度值和所在位置，否則返回步驟3。

圖3 PRKH算法流程Fig.3 PRKH algorithm flowchart

3 仿真分析

3.1 實驗數據和實驗環(huán)境

為驗證本文提出的PRKH 算法解決基于QoS 的服務組合優(yōu)化問題的有效性，本文從最優(yōu)解質量、最優(yōu)解穩(wěn)定性、時間開銷三個維度對KH 算法、加入隨機擾動的KH（KH with Random disturbance，RKH）算法、加入自適應交叉算子的KH（KH with adaptive crossover operator，PKH）算法和PRKH 算法進行比較，同時也將PRKH 算法和粒子群優(yōu)化（PSO）算法、人工蜂群（ABC）算法、花朵授粉算法（FPA）進行比較以驗證優(yōu)于其他基本算法的性能。實驗環(huán)境為：Windows 7（64位）操作系統(tǒng)，CUP 為Inter Xeon E5 2620-v3 2.40 GHz，內存為32 GB，Matlab 2020a。

本實驗以指揮信息系統(tǒng)服務組合為例，由于當前還沒有標準數據集供實驗調用，各候選服務集中的具體服務的QoS參數均在規(guī)定的范圍內隨機生成。設定抽象服務數量為20個，每個抽象服務對應的候選服務集中候選服務數為100 個。為保證實驗公平有效，所有算法均采用此隨機數據集進行測試。為降低偶然性，每組實驗重復100次并取平均值。

3.2 實驗參數

考慮到作戰(zhàn)時對可靠性和可用性要求較高，給予這兩個指標相對較高的權重，設定屬性權重W=［0.15，0.15，0.35，0.35］，其他各算法參數設置如表2所示。

表2 各算法參數設置Tab.2 Parameter setting of each algorithm

3.3 仿真結果分析

實驗使用定義5 中的服務質量評價函數作為算法中的適應度值計算公式。QoS 數據按式（1）歸一化處理后，適應度值越小代表最優(yōu)解的質量越高。

3.3.1 PRKH算法與KH、RKH、PKH算法對比

1）最優(yōu)解質量。如圖4所示，從100輪結果中隨機選取了第6 輪迭代的結果?？梢钥闯?，在本次迭代中，本文提出的PRKH 算法尋得了比其他三種算法質量更高的最優(yōu)解，同時PRKH 算法以更快的速度接近了全局最優(yōu)解。在算法后期，其他算法已經陷入局部最優(yōu)解時，PRKH 算法仍有一定的跳出局部最優(yōu)解的能力，能不斷提高局部最優(yōu)解的質量。

圖4 第6輪迭代結果Fig.4 Results of the sixth iteration

為了防止實驗的偶然性，將100 輪迭代尋找到的最優(yōu)解適應度值進行平均，同時將100 輪迭代中的最優(yōu)解作為算法最終尋找到的最優(yōu)解，實驗結果如圖5 所示?？梢钥闯觯琍RKH 算法100 輪迭代中尋找到的最優(yōu)解適應度值的平均值和最佳值相較RKH、PKH、KH 算法均更好，驗證了自適應交叉算子和隨機擾動算子在提升最優(yōu)解質量上的有效性。同時可以看出，自適應交叉算子對KH 算法性能的提升相比隨機擾動算子更大。

圖5 PRKH、RKH、PKH和KH算法最佳適應度值對比Fig.5 Best fitness comparison of PRKH，RKH，PKH and KH

2）最優(yōu)解穩(wěn)定性。如圖6所示，將100輪迭代的最佳適應度值數據以箱線圖的形式表示，可以看出PRKH算法和RKH、PKH、KH算法尋優(yōu)結果數據離散程度差異不大。具體標準差數據如表3 所示，可以看出PRKH 算法尋子在提升KH 算法最優(yōu)解穩(wěn)定性上有一定效果，但效果不大。觀察箱線圖中數據平均值也可看出PRKH 算法尋找到的最優(yōu)解質量更高，驗證上述結論。

圖6 PRKH、RKH、PKH和KH算法最佳適應度數據箱線圖Fig.6 Best fitness data box plot of PRKH，RKH，PKH and KH algorithms

表3 PRKH、RKH、PKH和KH算法最佳適應度值標準差Tab.3 Standard deviations of best fitness values of PRKH，RKH，PKH and KH

3）時間開銷。取100 輪迭代的平均時間開銷進行對比，如圖7 所示，PRKH 算法的時間開銷略大于其他3 種算法，每輪迭代時間數據離散程度相差不大。PRKH 算法中的自適應交叉算子比原有交叉算子更復雜，添加的隨機擾動算子也增加了算法的復雜性，因此一定程度上提升了PRKH 算法的時間開銷。但兩種改進算子并未改變算法復雜度，圖中也可看出4 種算法的時間開銷仍保持在同一個量級內，因此在對時間要求不高的實際問題中，PRKH算法仍有較大價值。

圖7 PRKH、RKH、PKH和KH算法時間開銷箱線圖Fig.7 Time cost box plot of PRKH，RKH，PKH and KH algorithms

綜上，自適應交叉算子和隨機擾動算子有效地提高了KH算法尋找到的最優(yōu)解的質量，標準差方面PRKH 算法也較RKH、PKH、KH 算法有了一定的提升。盡管在時間開銷方面PRKH 算法略大于其他三種算法，但當用戶追求高QoS 而對時間容忍度較高時，PRKH算法仍是較優(yōu)的選擇。

3.3.2 改進KH算法與PSO、ABC、FPA對比

1）最優(yōu)解質量。如圖8 所示，PRKH 算法100 輪迭代中尋找到的最優(yōu)解適應度值的平均值和最佳值相較PSO、ABC、FPA 均更好。其中PRKH 算法尋優(yōu)性能明顯高于PSO 和ABC算法，略高于FPA。

圖8 PRKH、PSO、ABC和FPA最佳適應度對比Fig.8 Best fitness comparison of PRKH，PSO，ABC and FPA

2）最優(yōu)解穩(wěn)定性。圖9 和表4 可以看出PRKH 算法尋優(yōu)結果數據離散程度略大于PSO、ABC、FPA，標準差數據顯示四者仍在同一量級。經分析，可能是因為PRKH 算法中磷蝦個體同時受到誘導運動、覓食運動和擴散運動三種因素影響，復雜性更高，帶來了相較其他智能優(yōu)化算法更高的不穩(wěn)定性。

圖9 PRKH、PSO、ABC和FPA最佳適應度數據箱線圖Fig.9 Best fitness data box plot of PRKH，PSO，ABC and FPA

表4 PRKH、PSO、ABC和FPA最佳適應度值標準差Tab.4 Standard deviation of best fitness values of PRKH，PSO，ABC and FPA

3）時間開銷。由圖10 可以看出，PRKH 算法的時間開銷明顯小于PSO 算法和FPA，略低于ABC 算法。迭代時間數據的離散程度也小于PSO和FPA，具有穩(wěn)定性。

圖10 PRKH、PSO、ABC和FPA的時間開銷對比Fig.10 Time cost comparison of PRKH，PSO，ABC and FPA

綜上，與PSO、ABC 和FPA 相比，PRKH 算法尋找到最優(yōu)解的質量較PSO 和ABC 算法有明顯提升，且時間開銷上量級相當；PRKH 算法較FPA 性能上略有提升，但時間開銷比FPA小得多。盡管PRKH 算法在標準差上略遜于其他三種算法，但從滿足用戶對QoS 高質量需求角度，PRKH 仍是綜合最優(yōu)的選擇。

4 結語

本文研究了磷蝦群（KH）算法在服務組合優(yōu)化問題中的應用，通過在標準KH 算法的基礎上加入自適應交叉算子和隨機擾動算子，提出了一種PRKH 算法。實驗結果表明該算法相較其他智能優(yōu)化算法，能迅速找到更優(yōu)的復合服務。下一步我們將考慮服務組合優(yōu)化問題中服務間的約束關系和動態(tài)環(huán)境下服務性能變化的問題，同時分析制約KH 算法性能的原因，以期進一步提高算法性能。