錢偉懿, 張麗佳

(渤海大學(xué) 數(shù)理學(xué)院, 遼寧 錦州 121013)

?

運(yùn)籌學(xué)與控制論

慣性質(zhì)量衰減的引力搜索算法

錢偉懿, 張麗佳

(渤海大學(xué) 數(shù)理學(xué)院, 遼寧 錦州 121013)

針對引力搜索算法易陷入局部最優(yōu)的缺點(diǎn),提出一種慣性質(zhì)量衰減的引力搜索算法。 該算法認(rèn)為粒子的慣性質(zhì)量有一定衰減,把粒子慣性質(zhì)量的衰減率看成一個(gè)模糊變量,用其隸屬度函數(shù)定義慣性質(zhì)量的衰減率,把衰減率與粒子慣性質(zhì)量乘積作為粒子的慣性質(zhì)量,從而提高算法的開發(fā)能力。另外,為了提高算法的探索能力,給出一個(gè)新的變異算子。最后,把所提出算法應(yīng)用到經(jīng)典測試函數(shù)中,并與引力搜索算法及其他改進(jìn)的引力搜索算法比較,數(shù)值結(jié)果表明所給出的算法能夠提高求解精度和收斂速度。

引力搜索算法; 隸屬度函數(shù); 變異算子; 全局優(yōu)化

在過去幾十年中,研究人員從自然現(xiàn)象中得到啟發(fā),提出了許多啟發(fā)式優(yōu)化算法。例如,遺傳算法[1]、蟻群優(yōu)化算法[2]、粒子群優(yōu)化算法[3-4]、模擬退火法[5]、人工蜂群算法[6]等。這些算法都是針對某些特定問題,目前尚沒有哪一種算法能夠成功地解決所有的優(yōu)化問題。因此,探索新的算法十分必要。

引力搜索算法(Gravitational search algorithm, GSA)是一種新的啟發(fā)式優(yōu)化算法,在2009年,首先被Esmat等人提出[7-8],其原理源于對萬有引力進(jìn)行模擬產(chǎn)生的群體智能優(yōu)化算法。目前引力搜索算法得到了廣泛應(yīng)用,如流水線調(diào)度[9]、模糊聚類[10-11]、濾波器的建模[12], 引起許多學(xué)者的關(guān)注。

Sun等人基于引力搜索算法和遺傳算法提出了一種混合GSA算法[13]。曹茂俊等人[14]在引力搜索算法中融合量子計(jì)算提出了一種改進(jìn)的引力搜索算法。Tsai等人提出了一種引力粒子群算法[15],該算法通過粒子群優(yōu)化算法的速度更新公式和GSA加速度更新公式的結(jié)合提出一種新速度更新公式。張明等人把小生境技術(shù)引入到引力搜索算法中給出一種基于小生境技術(shù)的改進(jìn)引力搜索算法[16]。徐遙等人對粒子的慣性質(zhì)量附加一個(gè)權(quán)值,提出了基于權(quán)值的引力搜索算法[17]。隋永霞等人提出基于高斯變異的引力搜索算法[18]。王奇琪等人引入斥力,提出了基于斥力的引力搜索算法[19]。這些算法未對慣性質(zhì)量進(jìn)行研究,但隨著時(shí)間推移粒子的慣性質(zhì)量有一定衰減,故本文給出慣性質(zhì)量衰減系數(shù),該系數(shù)看成模糊變量,用其隸屬度函數(shù)表示,質(zhì)量衰減系數(shù)乘以慣性質(zhì)量代替原慣性質(zhì)量。為提高群體多樣性,引入一個(gè)新的變異算子,在每次迭代中,以概率p實(shí)行新變異算子的位置更新,以概率(1-p)實(shí)施引力搜索算法位置更新,從而有效平衡了算法的探索能力和開發(fā)能力, 數(shù)值結(jié)果驗(yàn)證了算法的有效性。

1 引力搜索算法

GSA是基于牛頓的萬有引力定律和運(yùn)動定律為基本原理的啟發(fā)式算法。在GSA中把可行域中的解看成一個(gè)粒子,粒子的慣性質(zhì)量由粒子的適應(yīng)值決定,適應(yīng)值越好的粒子其質(zhì)量越大,相反,適應(yīng)值越差的粒子其質(zhì)量越小。根據(jù)粒子的質(zhì)量和粒子間的距離定義萬有引力,粒子在萬有引力作用下在可行域內(nèi)朝著慣性質(zhì)量大的粒子運(yùn)動,即朝著較好的適應(yīng)值運(yùn)動,從而得到全局最優(yōu)解。

在一個(gè)D維的搜索空間中,假設(shè)有N個(gè)粒子,定義第i個(gè)粒子的位置為

設(shè)第i個(gè)粒子在t時(shí)刻的質(zhì)量為Mi(t),其表達(dá)式如下:

(1)

(2)

其中fiti(t)表示粒子i在t時(shí)刻的適應(yīng)值,對于求最小值問題,best(t)和worst(t)定義如下:

(3)

(4)

根據(jù)萬有引力定律,在時(shí)刻t,粒子j對粒子i在d維上的作用力定義如下:

(5)

其中:Rij(t)為粒子i和粒子j之間的歐氏距離;ε是指非常小的常數(shù);G(t)是t時(shí)刻的引力常數(shù),定義如下:

(6)

其中:G0為一個(gè)初始值;α為一個(gè)常數(shù);t為當(dāng)前迭代數(shù);tmax為最大迭代次數(shù).

作用在第i個(gè)粒子在d維上的作用力定義如下:

(7)

其中randj是[0,1]之間的隨機(jī)數(shù),kbest從N到1隨著時(shí)間t線性地減小,使得算法到最后在搜索空間中只有最好的解的那個(gè)粒子去作用于其他的粒子。

(8)

粒子i在第d維上的速度和位置更新如下:

(9)

(10)

其中randi是[0,1]之間的隨機(jī)變量。

2 質(zhì)量衰減的GSA

隨著時(shí)間的推移,粒子的質(zhì)量要有一定的衰減,本文把粒子質(zhì)量衰減率看成一個(gè)模糊變量,模糊變量取決于他的隸屬度函數(shù),本文基于高斯函數(shù)、鐘型函數(shù)、Sigmoid函數(shù)定義質(zhì)量的衰減率,第i粒子在t時(shí)刻質(zhì)量衰減率φi(t)定義如下:

若質(zhì)量衰減率隸屬度函數(shù)基于高斯函數(shù)建立的,則

(11)

若質(zhì)量衰減率隸屬度函數(shù)基于鐘型函數(shù)建立的,則

(12)

若質(zhì)量衰減率隸屬度函數(shù)基于Sigmoid函數(shù)建立的,則

(13)

其中Pt表示t時(shí)刻最好位置,β為一參數(shù),定義如下:

β=best(t)/log(1+t)

顯然t越大,β越小,從而質(zhì)量衰減率越小,質(zhì)量衰減越快。粒子i在t時(shí)刻衰減后的質(zhì)量為

(14)

表1 測試函數(shù)

對于極小問題,粒子j的適應(yīng)值越差(目標(biāo)函數(shù)值大),其質(zhì)量衰減率越小,從而衰減后質(zhì)量越小,對其他粒子引力越小,相反,粒子j的適應(yīng)值越好(目標(biāo)函數(shù)值小),其質(zhì)量衰減率越大,從而衰減后質(zhì)量大,對其他粒子引力越大。該策略在算法后期可能導(dǎo)致陷入局部最優(yōu),為此給出一種新的變異算子

(15)

1) 設(shè)置算法中的參數(shù),隨機(jī)初始化粒子的位置及速度,計(jì)算粒子的適應(yīng)值,確定最好粒子;

2) 按式(1),式(2),式(3)和式(4)計(jì)算每個(gè)粒子的慣性質(zhì)量;按式(6)計(jì)算引力常數(shù);

3) 按式(11)或式(12)或式(13)計(jì)算慣性質(zhì)量衰減率,按式(14)計(jì)算衰減后質(zhì)量;

4) 按式(5)和式(7)計(jì)算每個(gè)粒子的引力;

5) 按式(8)計(jì)算加速度;

6) 按式(9)更新粒子的速度;

7) 在[0,1]中隨機(jī)選取一個(gè)隨機(jī)數(shù)r,若r

8) 計(jì)算每個(gè)粒子適應(yīng)值,更新最好粒子;

9) 若算法滿足終止條件,則輸出最好適應(yīng)值,否則轉(zhuǎn)步2.

3 數(shù)值實(shí)驗(yàn)

為檢驗(yàn)本文算法性能,選用文獻(xiàn)[20]中10個(gè)基準(zhǔn)測試函數(shù)進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)在MATLAB7.0,Windows 7操作系統(tǒng),2.00GB RAM 內(nèi)存和2.10 GHz CPU環(huán)境下運(yùn)行所有程序,且每個(gè)實(shí)驗(yàn)獨(dú)立運(yùn)行30次。表2給出了實(shí)驗(yàn)所用到的基準(zhǔn)測試函數(shù),其中:D表示函數(shù)的維數(shù);Ω是搜索區(qū)間;fopt表示最優(yōu)值。

表2 衰減率為高斯函數(shù)、鐘型函數(shù)、Sigmoid函數(shù)的GSA的比較結(jié)果

表2顯示的是基于不同衰減率本文算法的數(shù)值結(jié)果,其中:G-GSA,B-GSA和S-GSA分別表示質(zhì)量衰減率為高斯函數(shù)、鐘型函數(shù)、Sigmoid函數(shù)定義的質(zhì)量衰減的GSA;best、worst、mean和std分別表示30次實(shí)驗(yàn)中最好適應(yīng)值、最差適應(yīng)值、平均適應(yīng)值和標(biāo)準(zhǔn)差。

表3 B-GSA與GSA,GSAGJ和QGSA比較結(jié)果

從表2可以看出,對于最好適應(yīng)來說,在函數(shù)F7和F9上G-GSA優(yōu)于其他2種算法,在函數(shù)F3,F4,F5,F6和F10上B-GSA優(yōu)于其他2種算法,在F1,F2和F8上S-GSA優(yōu)于其他2種算法;對于最差適應(yīng)值來說,在函數(shù)F9上G-GSA優(yōu)于其他2種算法,在函數(shù)F3,F4,F5,F6,F7和F10上B-GSA優(yōu)于其他2種算法,在F1,F2和F8上S-GSA優(yōu)于其他2種算法;對于平均適應(yīng)值來說,在函數(shù)F6和F9上G-GSA優(yōu)于其他2種算法,在函數(shù)F3,F4,F5,F7和F10上B-GSA優(yōu)于其他2種算法,在F1,F2和F8上S-GSA優(yōu)于其他2種算法.綜合考慮可以看出,B-GSA優(yōu)于其他2種算法。

用B-GSA與GSA,GSAGJ[17]和QGSA[18]3種算法進(jìn)行比較.比較結(jié)果見表3。從表3可以看出,B-GSA與GSA相比,對于最好適應(yīng)值的指標(biāo),在函數(shù)F3,F4,F6,F7和F9上B-GSA優(yōu)于GSA,在函數(shù)F1,F2和F8上B-GSA略好于GSA,但在F5和F10上GSA優(yōu)于B-GSA;對于最差適應(yīng)值指標(biāo),在函數(shù)F1,F3,F4,F5,F6,F7,F9和F10上B-GSA優(yōu)于GSA,在函數(shù)F2和F8上B-GSA略好于GSA;對于平均適應(yīng)值指標(biāo),在函數(shù)F1,F3,F4,F5,F6,F7,F9和F10上B-GSA優(yōu)于GSA,在函數(shù)F2和F8上B-GSA略好于GSA。B-GSA與GSAGJ相比,對于最好適應(yīng)值的指標(biāo),在函數(shù)F3,F4,F6,F7和F9上B-GSA優(yōu)于GSAGJ,在函數(shù)F2和F8上B-GSA略好于GSA,但在F5和F10上GSAGJ優(yōu)于B-GSA,在函數(shù)F1上GSAGJ略優(yōu)于B-GSA;對于最差適應(yīng)值指標(biāo),在函數(shù)F1,F3,F4,F5,F6,F7,F9和F10上B-GSA優(yōu)于GSAGJ,在函數(shù)F2上B-GSA略好于GSAGJ;對于平均適應(yīng)值指標(biāo),在函數(shù)F3,F4,F5,F6,F7,F9和F10上B-GSA優(yōu)于GSAGJ,在函數(shù)F1,F2和F8上B-GSA略好于GSAGJ.B-GSA與QGSA相比,對于最好適應(yīng)值來說,在函數(shù)F1,F3,F4,F5,F6,F9和F10上,B-GSA優(yōu)于QGSA,在函數(shù)F8上,B-GSA略優(yōu)于QGSA,但在函數(shù)F2和F7上,QGSA優(yōu)于B-GSA,對于適應(yīng)值最差來說,在函數(shù)F1,F3,F4,F5,F9和F10上,B-GSA優(yōu)于QGSA,在函數(shù)F2和F8上,B-GSA略優(yōu)于QGSA,但在函數(shù)F7上,QGSA優(yōu)于B-GSA,在函數(shù)F6上,QGSA略優(yōu)于B-GSA;對于平均適應(yīng)值來說,在函數(shù)F1,F3,F4,F5,F9和F10上,B-GSA優(yōu)于QGSA,在函數(shù)F8上,B-GSA略優(yōu)于QGSA,但在函數(shù)F6和F7上,QGSA優(yōu)于B-GSA,在函數(shù)F2上,QGSA略優(yōu)于B-GSA。對于標(biāo)準(zhǔn)差來說,除了函數(shù)F5和F10外,B-GSA都有較好穩(wěn)定性.綜上所述,B-GSA提高了算法的尋優(yōu)能力和求解精度。

為比較各算法性能,圖1～圖6分別表示4種算法在函數(shù)F1,F3,F5,F7,F9,F10上的適應(yīng)值收斂曲線。

圖1 函數(shù)F1的尋優(yōu)曲線

圖2 函數(shù)F3的尋優(yōu)曲線

圖3 函數(shù)F5的尋優(yōu)曲線

圖4 函數(shù)F7的尋優(yōu)曲線

從圖1～圖6中可以看出,B-GSA在函數(shù)F3,F9,F10的收斂速度上明顯優(yōu)于其他3種算法,在函數(shù)F1和F5上,B-GSA的收斂速度相差不多,在函數(shù)F7上,QGSA明顯優(yōu)于其他3種算法,總之,B-GSA能夠提高了算法的收斂速度。

圖5 函數(shù)F9的尋優(yōu)曲線

圖6 函數(shù)F10的尋優(yōu)曲線

4 小 結(jié)

在引力搜索算法(GSA)中,引力搜索算法易陷入局部最優(yōu),為提高算法的探索與開發(fā)能力,用隸屬度函數(shù)定義粒子質(zhì)量的衰減率并給出一個(gè)新的變異算子,從而提出了慣性質(zhì)量衰減的引力搜索算法。數(shù)值實(shí)驗(yàn)結(jié)果顯示所提出的算法在求解精度與收斂速度明顯優(yōu)于標(biāo)準(zhǔn)引力搜索算法、基于權(quán)值的引力搜索算法及基于高斯變異的引力搜索算法。在未來的工作中,進(jìn)一步研究更好的衰減率。

[ 1 ]TANG K, MAN K, KWONG S, et al. Genetic algorithms and their applications[J]. IEEE Signal Process Mag, 1996,13(6):22-37.

[ 2 ]DORIGO M, MANIEZZO V, COLORNI A. The ant system: optimization by acolony of cooperating agents[J]. IEEE Trans Syst Man Cybern B, 1996,26(1):29-41.

[ 3 ]BERGH F, ENGELBRECHT A. A study of particle swarm optimization particle trajectories[J]. Inf Sci, 2006,176(8):937-971.

[ 4 ]KENNEDY J, EBERHART R. Particle swarm optimization[C]∥Proceedings of IEEE International Conference on Neural Networks, Perth WA: IEEE Press, 1995:1942-1948.

[ 5 ]KIRKPATRICK S, GELATTO C, VECCHI M P. Optimization by simulated annealing[J]. Science, 1953,220:671-680.

[ 6 ]KARABOGA D, BASTURK B. On the performance of artificial bee colony(ABC) algorithm[J]. Appl Soft Comput, 2008,8(1):687-697.

[ 7 ]RASHEDI E, NEZAMABADI-POUR H, SARYAZDI S. GSA: a gravitational search algorithm[J]. Inf Sci, 2009,179(13):2232-2248.

[ 8 ]RASHEDI E, NEZAMABADI-POUR H, SARYAZDI S. BGSA: binary gravitational search algorithm[J]. Nat Comput, 2010,9(3):727-745.

[ 9 ]谷文祥,李向濤,朱磊,等. 求解流水線調(diào)度問題的萬有引力搜索算法[J]. 智能系統(tǒng)學(xué)報(bào), 2010,5(5):411-418.

[10]RASHEDI E, NEZAMABADI-POUR H, SARYAZDI S. Filter modeling using gravitational search algorithm[J]. Eng Appl Artif Intell, 2011,24(1):117-122.

[11]YIN M,HU Y, YANG F, et al. A novel hybrid K-harmonic means and gravitational search algorithm approach for clustering[J]. Expert Syst Appli, 2011,38(8):9319-9324.

[12]劉伯穎,張素琪,張麗麗. 一種引力搜索和K-means的混合聚類算法[J]. 河北工業(yè)大學(xué)學(xué)報(bào), 2013,42(3):23-27.

[13]SUN G, ZHANG A. A hybrid genetic algorithm and gravitational search algorithm for image segmentation using Multilevel Thresholding[J]. Pat Recognit Image Anal, 2013,7887:707-714.

[14]曹茂俊,李盼池,尚福華. 量子行為引力搜索算法[J]. 控制與決策, 2016,31(9):1678-1684.

[15]TSAI H C, TYA N Y Y, WU Y W, et al. Gravitational Particle Swarm[J]. Appl Math Comput, 2013,219(17):9106-9117.

[16]張明,田娜,紀(jì)志成,等. 基于小生境技術(shù)的改進(jìn)引力搜索算法[J]. 南京航空航天大學(xué)學(xué)報(bào), 2016,48(5):753-760.

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

[18]隋永霞,孫合明. 基于高斯變異的引力搜索算法[J]. 江南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015,14(5):596-600.

[19]王奇琪,孫根云,王振杰等. 基于斥力的引力搜索算法[J]. 計(jì)算機(jī)科學(xué), 2015,42(9):240-245.

[20]YAO X, LIU Y, LIN G. Evolutionary programming made faster[J]. IEEE Trans Evol Comput, 1999,3(2):81-102.

Gravitational search algorithm with inertial mass attenuation

QIAN Weiyi, ZHANG Lijia

(College of Mathematics and Physics, Bohai University, Jinzhou 121000, China)

In order to overcome the shortcomings that gravitational search algorithm (GSA) traps into local optima easily, a gravitational search algorithm with inertial mass attenuation is proposed. In this algorithm, the particle’s inertial mass is considered to have certain attenuation, the attenuation rate of particle's inertial mass is regarded as a fuzzy variable, the attenuation rate is defined based on membership functions, the particle’s inertial mass is redefined by the product of attenuation rate and particle’s inertial mass. Such exploitation ability of the proposed algorithm is improved. In addition, a new mutation operator is proposed to improve the exploration ability. Finally, the proposed algorithm is tested on several benchmark test functions and compared with GSA and the other improved GSA. The numerical results indicate that the proposed algorithm can improve the convergence speed and precision.

gravitational search algorithm; membership function; mutation operator; global optimization

1673-5862(2017)02-0138-07

2017-02-06。

國家自然科學(xué)基金資助項(xiàng)目(11371071); 遼寧省教育廳科學(xué)研究一般項(xiàng)目(L2013426)。

錢偉懿(1963-),男,遼寧錦州人,渤海大學(xué)教授,博士。

TP18

A

10.3969/ j.issn.1673-5862.2017.02.003