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

（1.空軍工程大學(xué)信息與導(dǎo)航學(xué)院，西安 710077；2.93182部隊(duì)，沈陽(yáng) 110015；3.空軍工程大學(xué)裝備管理與無(wú)人機(jī)工程學(xué)院，西安 710051）

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

0 引言

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

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

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

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

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

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

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

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

1.1 相關(guān)定義

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

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

定義3服務(wù)質(zhì)量是一個(gè)4 元組Q=(t，c，ava，rel)，t是服務(wù)響應(yīng)時(shí)間，c是服務(wù)調(diào)用一次的成本，ava是服務(wù)可用性，rel是服務(wù)可靠性。

定義4W=[ω1，ω2，ω3，ω4]是Q中各屬性對(duì)應(yīng)的權(quán)重，并滿足。

定義5服務(wù)質(zhì)量評(píng)價(jià)函數(shù)F=WT*Q。

1.2 QoS計(jì)算方法

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

圖2 服務(wù)組合結(jié)構(gòu)Fig.2 Service composition structures

表1 不同結(jié)構(gòu)下復(fù)合服務(wù)QoS計(jì)算公式Tab.1 Calculation formulas of composite service QoS under different structures

表1 中，tj、cj、aj、rj分別表示第j個(gè)服務(wù)的響應(yīng)時(shí)間、服務(wù)費(fèi)用、可用性和可靠性；n為服務(wù)的個(gè)數(shù)，k為循環(huán)結(jié)構(gòu)中具體服務(wù)的執(zhí)行次數(shù)。

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

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

2.1 標(biāo)準(zhǔn)KH算法

KH算法其運(yùn)動(dòng)方式可以歸納為誘導(dǎo)運(yùn)動(dòng)、覓食運(yùn)動(dòng)和隨機(jī)擴(kuò)散。定義磷蝦個(gè)體的速度更新公式如下：

其中：Xi為第i只磷蝦的位置；Ni、Fi、Di分別代表誘導(dǎo)運(yùn)動(dòng)、覓食運(yùn)動(dòng)和隨機(jī)擴(kuò)散。Ni的構(gòu)造公式如下：

其中：Nmax表示最大誘導(dǎo)速度；αi代表誘導(dǎo)方向；ωn代表誘導(dǎo)權(quán)重；為上一次運(yùn)動(dòng)的誘導(dǎo)活動(dòng)方向。誘導(dǎo)方向定義如下：

覓食運(yùn)動(dòng)主要由食物位置和先前關(guān)于食物位置的經(jīng)驗(yàn)共同決定。覓食運(yùn)動(dòng)公式構(gòu)造如下：

其中：Vfood是覓食速度；Bi是覓食方向；覓食慣性權(quán)重是上一次運(yùn)動(dòng)的覓食活動(dòng)方向。覓食方向由食物對(duì)磷蝦個(gè)體的吸引力和最佳磷蝦個(gè)體對(duì)磷蝦的吸引力共同組成，具體計(jì)算公式如下：

擴(kuò)散運(yùn)動(dòng)可以理解為一種磷蝦群體隨機(jī)性勘探外界的行為，當(dāng)群體逐漸聚集，整體趨于最優(yōu)時(shí)，這種運(yùn)動(dòng)會(huì)越來(lái)越弱，具體構(gòu)造公式如下：

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

在磷蝦個(gè)體速度更新公式的基礎(chǔ)上，定義位置更新公式如下：

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

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

其中：Xi，m表示第i只磷蝦交叉前的位置；Xr，m表示與第r只磷蝦進(jìn)行了交叉后的磷蝦位置，r是1 到N的隨機(jī)數(shù)；Ri，m為第i只磷蝦的一個(gè)隨機(jī)數(shù)，用來(lái)判定是否需要交叉；Cr為第r只磷蝦對(duì)應(yīng)的交叉概率。

2.2 算法改進(jìn)策略

2.2.1 自適應(yīng)交叉算子

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

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

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

2.2.2 隨機(jī)擾動(dòng)算子

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

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

在此分析的基礎(chǔ)上，本文提出一種隨機(jī)擾動(dòng)算子，定義隨機(jī)擾動(dòng)更新公式如下：

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

2.3 算法流程

PRKH算法步驟如下：

步驟1 種群初始化和參數(shù)設(shè)置；

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

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

步驟4 按式（3）～（7）計(jì)算誘導(dǎo)運(yùn)動(dòng)、覓食運(yùn)動(dòng)和擴(kuò)散運(yùn)動(dòng)帶來(lái)的位置偏移量；

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

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

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

3 仿真分析

3.1 實(shí)驗(yàn)數(shù)據(jù)和實(shí)驗(yàn)環(huán)境

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

本實(shí)驗(yàn)以指揮信息系統(tǒng)服務(wù)組合為例，由于當(dāng)前還沒(méi)有標(biāo)準(zhǔn)數(shù)據(jù)集供實(shí)驗(yàn)調(diào)用，各候選服務(wù)集中的具體服務(wù)的QoS參數(shù)均在規(guī)定的范圍內(nèi)隨機(jī)生成。設(shè)定抽象服務(wù)數(shù)量為20個(gè)，每個(gè)抽象服務(wù)對(duì)應(yīng)的候選服務(wù)集中候選服務(wù)數(shù)為100 個(gè)。為保證實(shí)驗(yàn)公平有效，所有算法均采用此隨機(jī)數(shù)據(jù)集進(jìn)行測(cè)試。為降低偶然性，每組實(shí)驗(yàn)重復(fù)100次并取平均值。

3.2 實(shí)驗(yàn)參數(shù)

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

表2 各算法參數(shù)設(shè)置Tab.2 Parameter setting of each algorithm

3.3 仿真結(jié)果分析

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

3.3.1 PRKH算法與KH、RKH、PKH算法對(duì)比

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

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

為了防止實(shí)驗(yàn)的偶然性，將100 輪迭代尋找到的最優(yōu)解適應(yīng)度值進(jìn)行平均，同時(shí)將100 輪迭代中的最優(yōu)解作為算法最終尋找到的最優(yōu)解，實(shí)驗(yàn)結(jié)果如圖5 所示。可以看出，PRKH 算法100 輪迭代中尋找到的最優(yōu)解適應(yīng)度值的平均值和最佳值相較RKH、PKH、KH 算法均更好，驗(yàn)證了自適應(yīng)交叉算子和隨機(jī)擾動(dòng)算子在提升最優(yōu)解質(zhì)量上的有效性。同時(shí)可以看出，自適應(yīng)交叉算子對(duì)KH 算法性能的提升相比隨機(jī)擾動(dòng)算子更大。

圖5 PRKH、RKH、PKH和KH算法最佳適應(yīng)度值對(duì)比Fig.5 Best fitness comparison of PRKH，RKH，PKH and KH

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

圖6 PRKH、RKH、PKH和KH算法最佳適應(yīng)度數(shù)據(jù)箱線圖Fig.6 Best fitness data box plot of PRKH，RKH，PKH and KH algorithms

表3 PRKH、RKH、PKH和KH算法最佳適應(yīng)度值標(biāo)準(zhǔn)差Tab.3 Standard deviations of best fitness values of PRKH，RKH，PKH and KH

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

圖7 PRKH、RKH、PKH和KH算法時(shí)間開(kāi)銷箱線圖Fig.7 Time cost box plot of PRKH，RKH，PKH and KH algorithms

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

3.3.2 改進(jìn)KH算法與PSO、ABC、FPA對(duì)比

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

圖8 PRKH、PSO、ABC和FPA最佳適應(yīng)度對(duì)比Fig.8 Best fitness comparison of PRKH，PSO，ABC and FPA

2）最優(yōu)解穩(wěn)定性。圖9 和表4 可以看出PRKH 算法尋優(yōu)結(jié)果數(shù)據(jù)離散程度略大于PSO、ABC、FPA，標(biāo)準(zhǔn)差數(shù)據(jù)顯示四者仍在同一量級(jí)。經(jīng)分析，可能是因?yàn)镻RKH 算法中磷蝦個(gè)體同時(shí)受到誘導(dǎo)運(yùn)動(dòng)、覓食運(yùn)動(dòng)和擴(kuò)散運(yùn)動(dòng)三種因素影響，復(fù)雜性更高，帶來(lái)了相較其他智能優(yōu)化算法更高的不穩(wěn)定性。

圖9 PRKH、PSO、ABC和FPA最佳適應(yīng)度數(shù)據(jù)箱線圖Fig.9 Best fitness data box plot of PRKH，PSO，ABC and FPA

表4 PRKH、PSO、ABC和FPA最佳適應(yīng)度值標(biāo)準(zhǔn)差Tab.4 Standard deviation of best fitness values of PRKH，PSO，ABC and FPA

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

圖10 PRKH、PSO、ABC和FPA的時(shí)間開(kāi)銷對(duì)比Fig.10 Time cost comparison of PRKH，PSO，ABC and FPA

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

4 結(jié)語(yǔ)

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