袁 博 馬 力

（西安郵電大學(xué) 西安 710061）

1 引言

由于受到自然界群體現(xiàn)象的啟發(fā)，在過去的幾十年里，研究人員提出了多種群體智能算法，如人工蟻群算法［1］，粒子群算法［2］等，它們一般通過模擬生物種群或者自然物體的客觀規(guī)律來達(dá)到尋找最優(yōu)值的目的。

萬有引力搜索算法［3］（Gravitational Search Algorithm，GSA）在2009年首次由伊朗克曼大學(xué)的教授Esmat Rashedi等提出。萬有引力搜索算法是一種新的啟發(fā)式智能優(yōu)化算法，它是在牛頓萬有引力定律［4］及粒子間的相互作用的基礎(chǔ)上被提出的。

近幾年，有關(guān)萬有引力搜索算法一直是人們研究的重點(diǎn)，文獻(xiàn)［5］用萬有引力搜索算法來解決約束優(yōu)化問題。為防止出現(xiàn)早熟現(xiàn)象，文獻(xiàn)［6］將混沌變異添加到萬有引力搜索算法中。為提高分類問題的精確度，文獻(xiàn)［7］提出了將GSA與SVM相結(jié)合的模型。

但GSA算法也一定的缺點(diǎn)：算法停滯、早熟現(xiàn)象以及局部最優(yōu)問題，因此本文利用萬有引力搜索算法和粒子群算法相結(jié)合，并對粒子運(yùn)動速度方程方程進(jìn)行改進(jìn)，結(jié)合實驗，所改進(jìn)的算法具有較好的性能。

2 萬有引力搜索算法

2.1 萬有引力搜索算法原理

在GSA中，慣性質(zhì)量大的粒子比慣性質(zhì)量小的粒子運(yùn)動得慢，所以物質(zhì)都朝著慣性質(zhì)量大的粒子運(yùn)動。粒子的位置就是問題的解，當(dāng)算法滿足結(jié)束的條件時，擁有最大慣性質(zhì)量的粒子它的位置就代表問題的最優(yōu)解。

在GSA中，設(shè)參與搜索的粒子組成的系統(tǒng)是獨(dú)立的，是遵循萬有引力定律及牛頓運(yùn)動定律的人工制造的世界。萬有引力定律及運(yùn)動定律的定義分別如下：

1）萬有引力定律：任意兩粒子彼此間均是互相吸引的，兩個粒子間引力的大小和它們慣性質(zhì)量的積成正比關(guān)系，和它們間歐氏距離的平方成反比關(guān)系。但在在GSA中，我們用R代替R2，因為大量實驗結(jié)果顯示，使用R比使用R2的效果更好。

2）運(yùn)動定律：任意粒子的速度都等于它此時的速度與其加速度之和。加速度都等于作用在此粒子上的外力除以其慣性質(zhì)量。

2.2 萬有引力搜索算法簡介

設(shè)在一個擁有N個粒子的引力系統(tǒng)中，粒子i的位置是：

其中，xid表示粒子i在第d維空間上的位置。

由牛頓萬有引力定律可知，t時刻在第d維上粒子i受到粒子j的作用力為

其中，Mi、Mj分別表示粒子i和粒子j的引力質(zhì)量，ε是一個很小的常量，Rij(t)是粒子i和粒子j在t時刻時它們之間的歐氏距離：

G（t）是t時刻的引力常數(shù)，其值由宇宙的真實年齡決定，G（t）的值［8］隨著宇宙年齡的增長反而會變小，它們之間的關(guān)系如下式所示：

其中，G0代表在宇宙初期的萬有引力常數(shù)，一般取值為100；α為20；T為最大迭代次數(shù)。

為了讓GSA有隨機(jī)性的特點(diǎn)，通常給第d維空間上作用在粒子i上的萬有引力的合力設(shè)定一個隨機(jī)數(shù)，如下定義：

rand為［0，1］內(nèi)的隨機(jī)數(shù)。

由運(yùn)動定律可知，第d維空間上粒子i，t時刻的加速度為

GSA中設(shè)定引力質(zhì)量與慣性質(zhì)量相等，由適應(yīng)度函數(shù)得出粒子的引力質(zhì)量的定義：

fi(t)為t時刻粒子i的適應(yīng)度函數(shù)值；fworst(t)、fbest(t)分別為t時刻群體最差適應(yīng)度函數(shù)值和群體最好適應(yīng)度函數(shù)值；引力質(zhì)量一般用單位值表示如下：

對于求最大值問題：

對于求最小值問題：

由以上可知粒子的運(yùn)動速度和位置分別是：

其中，rand是［0，1］上均勻分布的隨機(jī)數(shù)，GSA使用隨機(jī)數(shù)來實現(xiàn)其在搜索過程中的隨機(jī)性。

3 改進(jìn)的萬有引力搜索算法

對萬有引力搜索算法中的速度和位置，由式（11）、（12）分析可知，GSA僅有當(dāng)前的位置信息在迭代過程中起作用，由此可知萬有引力搜索算法是一種缺乏記憶的算法。從式（6）、（11）、（12）可以得知，當(dāng)粒子運(yùn)動至最優(yōu)解或接近最優(yōu)解之前，由于引力的大小與距離成反比，所以粒子的速度會不斷的增加，當(dāng)粒子運(yùn)動至或接近最優(yōu)解時，粒子的運(yùn)動速度有可能會非?？欤ù嬖陔S機(jī)性），由運(yùn)動學(xué)的規(guī)律可以知道，上面的情況會致使粒子在最優(yōu)解周圍來回的震蕩，從而降低了算法的搜索精度。因此本文將萬有引力搜索算法和粒子群算法進(jìn)行了結(jié)合并做以改進(jìn)。

粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）是1995年由Kennedy博士和Eberhart教授提出的算法。其它的群體智能算法相類似，PSO也是一種隨機(jī)搜索的全局優(yōu)化算法，當(dāng)對整個群體對解空間中最優(yōu)解的搜索時，僅需要粒子追隨自己及整個群體當(dāng)前的最好位置移動。

粒子群算法中的粒子的運(yùn)動速度和位置方程為如下式（13）和式（14）：其中，rand1、rand2為區(qū)間［0，1］內(nèi)的隨機(jī)數(shù)。c1，c2為正常數(shù)是學(xué)習(xí)因子也稱為加速系數(shù)，c1和c2分別是調(diào)整粒子的個體經(jīng)驗和群體經(jīng)驗并對粒子運(yùn)動軌跡產(chǎn)生影響的重要參數(shù)。若c1=0，則僅有群體經(jīng)驗在粒子的運(yùn)動中起作用，對于復(fù)雜問題算法很容易出現(xiàn)局部收斂的問題。若c2=0，則僅有個體經(jīng)驗影響粒子的運(yùn)動，粒子之間缺乏信息交互的能力。w是慣性權(quán)重，w的作用就是為防止算法早熟收斂而產(chǎn)生擾動。pi為粒子i曾經(jīng)歷過的最好位置即個體極值，代表個體經(jīng)驗；gbest為所有粒子曾經(jīng)歷過的最好位置即全局極值，代表群體經(jīng)驗。

借助粒子群優(yōu)化算法的優(yōu)點(diǎn)，為引力搜索算法中的粒子增加記憶性和信息共享能力。則將萬有引力搜索算法與粒子群優(yōu)化算法相結(jié)合后的粒子運(yùn)動速度的式（15）：

其中，rand1、rand2和rand3均為區(qū)間［0，1］內(nèi)的隨機(jī)數(shù)；w1和w2均為慣性權(quán)重，可以通過調(diào)節(jié)w1和w2的值來調(diào)整粒子在運(yùn)動的過程中受引力、信息共享的影響程度，顯然，當(dāng)w1和w2為零時改進(jìn)后的算法退化為引力搜索算法。PSOGSA的流程圖如圖1。

圖1 PSOGSA的流程圖

PSOGSA能緩解GSA出現(xiàn)的算法停滯的缺點(diǎn)。PSOGSA利用目前所獲得的最優(yōu)解引導(dǎo)慣性質(zhì)量大的粒子朝全局最優(yōu)方向移動，而不是所有粒子都朝最優(yōu)解聚集。顯然，PSOGSA也可以加快群體的整體運(yùn)動，促使PSOGSA算法的尋優(yōu)能力增強(qiáng)。

圖2用y=x2函數(shù)顯示了GSA在兩次迭代過程中粒子的運(yùn)動情況。M2是一個較優(yōu)解周圍的粒子向M2聚攏。如圖3所示，PSOGSA利用目前所獲得的最優(yōu)解引導(dǎo)慣性質(zhì)量大的粒子朝全局最優(yōu)方向gbest移動［9］。（M1代表現(xiàn)在搜索所處位置）

圖2 GSA在兩次迭代過程中粒子的運(yùn)動情況

圖3 PSOGSA的兩次迭代過程中粒子的運(yùn)動情況

文獻(xiàn)［10］通過實驗證明，PSOGSA在解決優(yōu)化問題上要優(yōu)于PSO和GSA。然而原始PSOGSA主要解決的是連續(xù)優(yōu)化問題，但是實際中有很多優(yōu)化問題都是離散的比如Web服務(wù)選擇問題和路由選擇問題。為了解決工程實際中眾多的組合優(yōu)化問題，本文借鑒Mirjalili和Lewis提出的二進(jìn)制PSO算法的理論對原始PSOGSA做以改進(jìn)。為了讓搜索可以在離散的搜索空間內(nèi)進(jìn)行，需要修改位置更新式（14）。又由文獻(xiàn)［3］和［11］可知，改變搜索代理的位置是需要一個傳遞函數(shù)的，這個傳遞函數(shù)映射速度的值對位置狀態(tài)改變的概率。文獻(xiàn)［12］中例舉了許多標(biāo)準(zhǔn)傳遞函數(shù)。根據(jù)Mirjalili和Lewis提出的理論可知傳遞函數(shù)應(yīng)該要保證當(dāng)速度的絕對值大時，改變位置狀態(tài)的概率也就大。反之概率小。此外，傳遞函數(shù)是在［0，1］范圍內(nèi)隨著速度的增加而增加的。參考文獻(xiàn)［3］本文將傳遞函數(shù)定義如下：

圖4是對式（16）的說明。

圖4 S（v）與v關(guān)系

得到S（vid（t））的結(jié)果后，搜索代理就會按照下面的規(guī)則更新位置：

由文獻(xiàn)［13］可知，將gbest加入到速度矢量中會減弱算法的尋優(yōu)能力，為了解決這個問題，本文對c1和c2做如下變化：

由于PSO算法和GSA算法都存在收斂速度慢，容易出現(xiàn)停滯的現(xiàn)象，也就是說，粒子聚集且運(yùn)動速度幾乎為零，粒子難以逃離局部極值區(qū)，從而導(dǎo)致算法早熟。為了避免萬有引力搜索算法與粒子群優(yōu)化算法相結(jié)合后的算法出現(xiàn)以上問題，可以通過在進(jìn)化過程中動態(tài)調(diào)整搜索空間的邊界來進(jìn)行對粒子飛行位置的追蹤，當(dāng)發(fā)現(xiàn)粒子聚集時，通過對邊界進(jìn)行一定的操作和在新的搜索空間內(nèi)激活停滯粒子，使粒子跳出局部區(qū)域，去尋找最優(yōu)解［14］。

通過如下公式對搜索空間的左邊界進(jìn)行擴(kuò)展：

上面的式子中，Bdl表示d維下搜索間的左邊界，Bdr表示d維下搜索空間的右邊界；Cb代表收縮率，-cb=1-cb；Ob代表擴(kuò)展率。

rand1～rand6是服從［0，1］上均勻分布的隨機(jī)數(shù)。從式（19）～（21）可以看出，通過以全局的極值點(diǎn)為核心在一定范圍內(nèi)進(jìn)行隨機(jī)收縮或擴(kuò)展從而對搜索空間的邊界進(jìn)行調(diào)整。若在第d維時當(dāng)前的邊界被重置，則表明在第d維粒子是聚集在一起的，那么，為了增加粒子的多樣性在這時算法會隨機(jī)的挑選少量的粒子進(jìn)行激活，讓其跳出局部極值的區(qū)域。

3.1 算法的主要步驟

在每次迭代結(jié)束后，算法都會執(zhí)行下面的3個步驟。

1）標(biāo)記當(dāng)前搜索空間的左右邊界。在第d維中，查看是否有粒子跳出當(dāng)前邊界［Bdl，Bdr］，若有粒子跳出，則在第d維將邊界標(biāo)識置為true，反之置為false。

2）在此步中，我們將分別處理搜索空間在每一維中的左右邊界。如果全局極值點(diǎn)和邊界的距離大于閾值ε，且在該維上邊界的標(biāo)識為false，那么使用式（19）對邊界進(jìn)行收縮，否則使用式（20）對邊界進(jìn)行擴(kuò)展；如果全局極值點(diǎn)和邊界的距離小于或等于閾值ε，則表示出現(xiàn)了粒子聚集的現(xiàn)象，那么使用式（21）重置邊界。

3）在此步中為了增加粒子的多樣性，我們將激活處于停滯狀態(tài)下的粒子，清除粒子的個體經(jīng)驗。如果在第d維中當(dāng)前的邊界被重置，那么在此時的邊界內(nèi)給速度加上一個服從正態(tài)分布的隨機(jī)數(shù)，以便激活粒子。當(dāng)算法得到最優(yōu)解或達(dá)到最大迭代次數(shù)時算法終止。

3.2 服務(wù)場景設(shè)計與數(shù)據(jù)組織

采用在Web服務(wù)組合領(lǐng)域經(jīng)常使用的旅游場景，作為驗證本文改進(jìn)的萬有引力搜索算法在解決基于多目標(biāo)優(yōu)化的Web服務(wù)組合問題中的可行性和有效性。在應(yīng)用場景中，服務(wù)請求者只需再提供一些非功能需求如出發(fā)日期和酒店等級等信息，作為服務(wù)提供者選擇最佳方案的依據(jù)。服務(wù)提供者就會給服務(wù)請求者返回一個最優(yōu)的組合服務(wù)。該組合服務(wù)按照服務(wù)的功能需求需要4個服務(wù)類如圖5所示：訂票、訂酒店、租車和找導(dǎo)游服務(wù)。為每個服務(wù)類選取5個候選服務(wù)則共有20個原子服務(wù)，從服務(wù)日志中讀取這20個原子服務(wù)的歷史QoS信息，經(jīng)過量綱統(tǒng)一和極性一致性處理，然后基于灰色系統(tǒng)理論對其QoS屬性值進(jìn)行預(yù)測，得到各服務(wù)類中候選服務(wù)的QoS屬性預(yù)測值如表1～4所示。

圖5 旅游場景

表1 訂票服務(wù)的QoS屬性預(yù)測值

表2 訂酒店服務(wù)的QoS屬性預(yù)測值

表3 租車服務(wù)的QoS屬性預(yù)測值

表4 找導(dǎo)游服務(wù)的QoS屬性預(yù)測值

根據(jù)上述表中給出的預(yù)測值，使用窮舉法得到的最優(yōu)服務(wù)組合方案的序列是（1，4，5，3），最優(yōu)值為0.495。得到的最優(yōu)結(jié)果是用于判斷后文中用改進(jìn)萬有引力搜索算法得到的結(jié)果是否優(yōu)的依據(jù)。

3.3 Web服務(wù)選擇過程

依據(jù)3.2節(jié)構(gòu)造的基于多目標(biāo)優(yōu)化問題的Web服務(wù)選擇模型，應(yīng)用非功能屬性參數(shù)也就是QoS屬性來評估服務(wù)請求中每個服務(wù)的適應(yīng)度函數(shù)值。慣性質(zhì)量按照下面的式（7）更新。fi(t)為t時刻粒子i的適應(yīng)度函數(shù)值，它是由非功能屬性參數(shù)和t時刻每個服務(wù)的適應(yīng)值來計算的［15］。

在特殊時刻，

其中，G（t）是t時刻的引力常數(shù)，es是一個很小的常數(shù)，Rij(t)是t時刻服務(wù)i和服務(wù)j之間的歐氏距離。

4 實驗與分析

為了證明改進(jìn)的萬有引力搜索算法在解決基于多目標(biāo)優(yōu)化的Web服務(wù)組合問題中的可行性和有效性。使用3.2節(jié)中建立的旅游場景和測試數(shù)據(jù)對改進(jìn)的萬有引力搜索算法進(jìn)行實驗，同時和標(biāo)準(zhǔn)萬有引力算法進(jìn)行對比。實驗環(huán)境為Windows 7系統(tǒng)，2.27GHz CPU，4G內(nèi)存，工具為Matlab 7.0，使用語言Matlab。初始參數(shù)的設(shè)置：種群規(guī)模P=80，交叉概率Pc=0.5，變異概率Pm=0.03，最大進(jìn)化代數(shù)T=1000。

表5～7分別代表PSO、GSA和DBPSOGSA算法獨(dú)立運(yùn)行十次的結(jié)果。

表5 PSO獨(dú)立運(yùn)行10次的結(jié)果

表6 GSA獨(dú)立運(yùn)行10次的結(jié)果

由表5、表6、表7可知在求解同一規(guī)模的問題時，GSA、PSO和本文所提出的DBPSOGSA算法都可以得到最優(yōu)解，但迭代的次數(shù)和耗時是有差異的，圖7是這三種算法在求解同規(guī)模問題時運(yùn)行次數(shù)和迭代次數(shù)對比圖。

圖6 PSO、GSA和DBPSOGSA求解同規(guī)模問題時運(yùn)行次數(shù)和迭代次數(shù)對比圖

圖7 PSO、GSA和DBPSOGSA求解同規(guī)模問題時運(yùn)行次數(shù)和運(yùn)行時間對比圖

由實驗結(jié)果可以看出：PSO算法平均迭代130次左右才可找到最優(yōu)解，平均耗時251ms，GSA算法平均需要迭代110次可以找到最優(yōu)解，平均耗時約為130ms，而改進(jìn)的DBPSOGSA算法平均迭代53次就可以找到最優(yōu)解，平均耗時約為85ms，該算法在迭代次數(shù)和平均耗時上都比PSO和GSA算法有所提升，擁有較好的性能。

引用旅游場景的實驗證明改進(jìn)的萬有引力搜索算法在解決基于多目標(biāo)優(yōu)化的Web服務(wù)組合問題上也具有一定的可行性。

5 結(jié)語

本文先是對原始萬有引力搜索算法的基本原理和優(yōu)化過程做以介紹；再通過引入粒子群算法改進(jìn)GSA中粒子的記憶性，使粒子在優(yōu)化過程中不但受空間中其他粒子的影響，而且受自身記憶的影響，通過對邊界進(jìn)行一定的操作和在新的搜索空間內(nèi)激活停滯粒子，使粒子跳出局部區(qū)域，去尋找最優(yōu)解。最后進(jìn)行了算法和服務(wù)性能的對比，證明了所提出的改進(jìn)的萬有引力有較好的性能。

接下來的工作就是進(jìn)一步驗證所提出算法的全局收斂性，以及如何改進(jìn)萬有引力搜索算法使其具有更廣泛的適用性。