徐耀群，王長舉

(哈爾濱商業(yè)大學(xué)計算機與信息工程學(xué)院，哈爾濱150028)

本文在分析了粒子群優(yōu)化算法，萬有引力及Rashedi E，Nezamabadi－pour H，Saryazdi S提出的引力搜索算法[5]的基礎(chǔ)上，提出了一種萬有引力優(yōu)化算法，并與粒子群優(yōu)化算法進行比較，之后又進行了收斂分析.

1 引力優(yōu)化算法

引力優(yōu)化算法(Universal gravitation optimization，UGO)是一種根據(jù)牛頓萬有引力而提出的一種優(yōu)化算法.在提出和完善引力優(yōu)化算法的時候，借鑒了引力搜索算法和引力搜索算法的改進[6].前者是對每個質(zhì)點都進行了計算，在速度更新的時候也用了隨機因子和質(zhì)點加速度倆個因子，質(zhì)點的慣性質(zhì)量是由適應(yīng)值大小來計算的;后者在前者的基礎(chǔ)上引入了加權(quán)值，通過改變質(zhì)點的慣性質(zhì)量對引力搜索算法進行的改進.在引力優(yōu)化算法中，每個質(zhì)點在各自的活動過程中搜索問題的解空間，并記錄下已找到的最優(yōu)值[7].在整個群體之中，各個質(zhì)點之間存在著引力關(guān)系，找到最優(yōu)點的質(zhì)點會產(chǎn)生引力吸引其他質(zhì)點向著該質(zhì)點所在位置的方向飛行，找到次優(yōu)點的質(zhì)點會產(chǎn)生引力吸引其他質(zhì)點向著該質(zhì)點所在位置的方向飛行，找到第三優(yōu)點的質(zhì)點會產(chǎn)生引力吸引其他質(zhì)點向著該質(zhì)點所在位置的方向飛行，以此類推，在這種引力的作用下，質(zhì)點會改變原有的飛行路線，在新的飛行中又將找到新的最優(yōu)點，產(chǎn)生新的引力吸引其他質(zhì)點，在這種迭代中，質(zhì)點們將找到全局最優(yōu)點.(在具體的應(yīng)用中只取找到最優(yōu)點的質(zhì)點和找到次優(yōu)點的質(zhì)點，它們將對其他質(zhì)點產(chǎn)生有效的引力.)質(zhì)點之間按公式，(萬有引力公式)產(chǎn)生引力，也就是，質(zhì)點之間的萬有引力等于引力常量G乘以兩質(zhì)點質(zhì)量的乘積除以它們距離的平方.其中G代表引力常量，其值約為6.67×10－11，單位 N·m2/kg2.質(zhì)點xi將按照公式(1)和(2)進行速度和位置的更新:

公式中的f1和f2分別是最優(yōu)質(zhì)點和次優(yōu)質(zhì)點對當(dāng)前質(zhì)點產(chǎn)生的引力，C1和C2為學(xué)習(xí)因子或加速常量(Learning Factor，Acceleration Constant).此外，為使質(zhì)點速度不至于過大，還設(shè)置了速度上限Vmax，即公式(1)中的 V ＞Vmax時，V=Vmax;V ＜ －Vmax時，V=－Vmax.公式(1)中的第1部分為質(zhì)點先前的速度;第2部分為最優(yōu)質(zhì)點對當(dāng)前質(zhì)點速度的影響;第3部分為次優(yōu)質(zhì)點對當(dāng)前質(zhì)點速度的影響.

引力優(yōu)化算法的基本步驟如下:

步驟1:初始化，設(shè)定學(xué)習(xí)因子C1、C2，最大進化代數(shù)Tmax，當(dāng)前的進化代數(shù)t=1:定義質(zhì)點空間Rn中隨機產(chǎn)生 m 個質(zhì)點 x1，x2，…，xm，形成種群矩陣X(t);隨機產(chǎn)生各個質(zhì)點位移變化v1，v2，…，vm形成位移變化矩陣V(t).

步驟2:評價種群，計算每個質(zhì)點的適應(yīng)值F(Xi).

步驟3:比較質(zhì)點的當(dāng)前適應(yīng)值F(Xi)和自身歷史最優(yōu)值 pbest，如果 F(Xi)優(yōu)于 pbest，則置pbest為當(dāng)前值F(Xi)，并置pbest的位置pbest為n維空間中的當(dāng)前位置.

很多學(xué)生在參與中長跑活動后會出現(xiàn)一些副作用，包括胸悶、氣短、臉色發(fā)白等，這些副作用讓學(xué)生對中長跑活動存有一定的抵觸心理。所以教師要云用合適的方法引導(dǎo)學(xué)生去“善后”，幫助學(xué)生去可致不良反應(yīng)，這樣能夠讓學(xué)生環(huán)節(jié)對中長跑活動的為難心理。如教師可以帶領(lǐng)學(xué)生做一些保健按摩、放松操，適當(dāng)?shù)淖鲆恍┖唵蔚妮p松的小游戲等，讓學(xué)生對中長跑活動不再抵觸。

步驟4:比較質(zhì)點當(dāng)前適應(yīng)值F(Xi)與種群最優(yōu)值gbest，如果 F(Xi)優(yōu)于 gbest，則置 gbest為當(dāng)前值F(Xi)，并置gbest的位置gbest為n維空間中的當(dāng)前位置.

步驟5:按公式(1)和公式(2)更新質(zhì)點的速度，并產(chǎn)生新種群X(t+1).

步驟6:檢查評價函數(shù)值是否達到事先給定精度，若已達到或進化代數(shù)次數(shù)達到Tmax，則結(jié)束循環(huán);否則令t+1，轉(zhuǎn)步驟2.

2 引力優(yōu)化算法收斂性分析

考慮全局收斂性

假設(shè) 1:f(D(z，ξ))≤f(Z)，并且如果 ξ∈S，則

假設(shè)2:對于S的任意Borel子集A，若其測度v(A) ＞0，則有

其中:μk(A)是由測度μk所得到的A的概率.

定理1:引力優(yōu)化算法滿足假設(shè)1.

證明:定義函數(shù)D為

其中:符號g(xi，k)表示引力優(yōu)化的更新方程，具體為

其中:xi，k表示第k代時的質(zhì)點位置，按照這里定義的函數(shù)D，引力優(yōu)化滿足假設(shè)1.

定理2:任意取ε＞0，存在N≥1，使得對于任意的 n≥N，如果選擇 ω、φ1、φ2，使得 max(||α||，||β||) ＜1，則有 gn(xi，k) － gn+1(xi，k)‖ ＜ ε.證明:由于

且 X(t+1) －X(t)=V(t+1)，因此，當(dāng) max(||α||，||β||) ＜1 時，下式成立

兩邊取極限，從而有

3 仿真研究

3.1 實驗設(shè)計

為了分析引力優(yōu)化算法的性能，本文涉及了4個測試函數(shù)，如表1.通過對4個測試函數(shù)尋找最小值，可以分析本文提出的算法的優(yōu)化能力.在本文的實驗部分，為了減少大量的計算，而提出了此實驗?zāi)Ｐ?只考慮引力最大點和引力第二大點對該質(zhì)點產(chǎn)生有效的引力作用.通過對這三個模型的計算分析可以觀察出，引力優(yōu)化算法的尋優(yōu)的最優(yōu)值，速度，穩(wěn)定性方面的尋優(yōu)能力.

表1 四個標準測試函數(shù)

進行測試是求函數(shù)的最小值，種群大小為40，空間維數(shù)是10，每次測試獨立運行10次.其中UGO中的引力系數(shù)Q、迭代次數(shù)Tmax、速度上限、速度下限，如表3，C1=2.05，C2=2.05，ω =0.729 8.PSO 中的學(xué)習(xí)因子 C1=2.05，C2=2.05，慣性權(quán)重為ω=0.729 8，迭代次數(shù)Tmax=1200.然后求其平均值、最大值、最小值、方差.得到各個函數(shù)分別用粒子群算法和引力優(yōu)化進行優(yōu)化的過程比較，得到的結(jié)果如表2，引力優(yōu)化算法的參數(shù)值如表3，在引力優(yōu)化算法中，隨著迭代次數(shù)的增加函數(shù)適應(yīng)值的變化如圖1～4.在粒子群優(yōu)化中，隨著迭代次數(shù)的增加函數(shù)適應(yīng)值的變化如圖5～8.

表2 UGO與PSO性能比較

表3 函數(shù)的參數(shù)

圖8 函數(shù)F4粒子群的適應(yīng)值隨迭代次數(shù)的變化

3.2 實驗結(jié)果分析

從試驗的結(jié)果看出來，UGO算法總體上看跟PSO算法的優(yōu)化能力相近，在函數(shù)F1、F4中UGO稍好于 PSO，而在函數(shù) F2、F3中 UGO表現(xiàn)的比PSO稍差一點.在求函數(shù)最小值的時候，UGO在一些函數(shù)中能夠找到更小的最小值，找到最小值的速度也是挺快的，穩(wěn)定性和求最優(yōu)的能力上，還需要在以后的研究工作中繼續(xù)探索和加以改進.

4 結(jié)語

本文借鑒了粒子群方法，針對粒子群早熟收斂和搜索能力差的問題，提出了引力優(yōu)化該算法有著與粒子群相同的簡單收斂快的優(yōu)點，并對算法的收斂性進行分析.在與粒子群比較的過程中發(fā)現(xiàn)，該算法速度較快，對像F1、F3、F4這樣的函數(shù)有著較好的尋優(yōu)能力，但對像F2這樣的函數(shù)經(jīng)過多次運行其能找到最優(yōu)的能力要比粒子群要好，但存在這不穩(wěn)定性.在進一步的工作中將要調(diào)整算法，使其尋優(yōu)能力更加穩(wěn)定，提高其全局和局部搜索能力.

[1] EBERHART R C，KENNEDY J.Particles swarm optimization[C]//IEEE Int Conf on Neural Network，Perth，1995:1942－1948.

[2] EBERHART R C，KENNEDY J.A new optimizer using particle swarm theory[C]//The 6th Int Symposium on Micro Machine and Human Science，Nagoya，1995:39 －43.

[3] 高 浩，冷文浩，須文波.一種全局收斂的PSO算法及其收斂分析[J].控制與決策，2009，24(2):196－201.

[4] KALYAN V，LISA O，GANAPATHI K.Probabilistically driven particle swarms for optimization of multi valued discrete problems:Design an analysis[C]//Proc of IEEE Swarm Intelligence Symposium(SIS).Honolulu，2007:141－149.

[5] RASHEDI E，NEZAMABADIPOUR H，SARYAZDI S.GSA:a gravitational search algorithm[J].Information Sciences，2009，179(13):2232－2248.

[6] 徐 遙，王士同.引力搜索算法的改進[J].計算機工程與應(yīng)用，2011，47(35):188－192.

[7] 許 楠，徐耀群.反三角函數(shù)混沌神經(jīng)網(wǎng)絡(luò)的模擬退火策略[J].哈爾濱商業(yè)大學(xué)學(xué)報:自然科學(xué)版，2011，27(6):814－818.