周少武，陳 微，唐東成，張紅強(qiáng)，王 汐，周 游

(1.湖南科技大學(xué)信息與電氣工程學(xué)院，湖南 湘潭 411201;2.湖南大學(xué)電氣與信息工程學(xué)院，長沙 410082)

1 概述

在工程實(shí)踐中，許多問題都涉及優(yōu)化，如成本最低問題、距離最短問題、電力系統(tǒng)中無功補(bǔ)償配置問題等。而啟發(fā)式搜索算法就是解決優(yōu)化問題的一類方法，它不同于經(jīng)典的數(shù)學(xué)算法。這些啟發(fā)式搜索算法是受大自然現(xiàn)象和運(yùn)動(dòng)規(guī)律啟發(fā)得到的，如螢火蟲算法［1］、人工魚群算法［2］、粒子群算法［3］等。這些算法已被事實(shí)證明，它們能解決復(fù)雜的非線性的優(yōu)化計(jì)算問題，因此，在各個(gè)領(lǐng)域得到廣泛的應(yīng)用。值得指出的是，對于所有函數(shù)集合，并不存在萬能的最佳優(yōu)化算法［4］，某種算法可能解決某些函數(shù)極值的求解，因此，啟發(fā)式算法的研究是一個(gè)開放性的問題。

引力搜索算法(Gravitational Search Algorithm，GSA)［5］是由伊朗的克曼大學(xué)教授Esmat Rashedi 等人于2009 年提出的。GSA 算法思想來源于牛頓萬有引力定律，它通過群體中各粒子之間的萬有引力相互作用產(chǎn)生的群體智能指導(dǎo)優(yōu)化搜索［6］。它從可行域中隨機(jī)地產(chǎn)生一組初始解，且把它們看成是帶有一定質(zhì)量的粒子，這個(gè)質(zhì)量決定了粒子對種群中其他粒子吸引的強(qiáng)弱——質(zhì)量越大，吸引能力就越強(qiáng);反之，質(zhì)量越小，吸引力越小，之后求出合力、加速度，再對粒子進(jìn)行速度、位置更新。

引力搜索算法是一個(gè)新興的算法，在文獻(xiàn)［7］中證明GSA 的收斂性明顯優(yōu)于粒子群算法［8］和遺傳算法等其他智能算法，同時(shí)引力搜索概念簡單、容易實(shí)現(xiàn)，而且需要調(diào)整的參數(shù)少。自從GSA 提出以來，從不同的方面對其進(jìn)行了改進(jìn)，如文獻(xiàn)［9］將宇宙中的黑洞操作引入到GSA，在解決單峰函數(shù)問題時(shí)效果很好，文獻(xiàn)［10］將GSA 推廣至離散時(shí)間系統(tǒng)，提出了一種快速離散的GSA 算法。本文受到文獻(xiàn)［11］對類電磁機(jī)制改進(jìn)的啟發(fā)，通過引入親和度概念來改進(jìn)GSA。

2 基本引力搜索算法

假設(shè)在搜索空間中，每一個(gè)粒子的位置用如下向量表示:

其中，N 表示種群數(shù)量;xdi 表示第i 個(gè)粒子在第d 維的位置。

根據(jù)如式(1)和式(2)計(jì)算出粒子的慣性質(zhì)量并得出質(zhì)量的歸一化:

對于最小值問題，best(t)和worst(t)的定義為:

對于最大值問題，best(t)和worst(t)的定義為:

其中，fiti(t)是粒子i 在t 時(shí)刻的適應(yīng)度值。

接著根據(jù)式(7)可以計(jì)算各個(gè)粒子在每一維空間上的引力，在第d 維上第i 個(gè)粒子與第j 個(gè)粒子之間的萬有引力為:

G(t)是引力系數(shù)，它隨時(shí)間而遞減:

其中，G0和α 為時(shí)間常數(shù);T 為最大迭代次數(shù)。

在引力搜索算法中，為了增加算法隨機(jī)特性，認(rèn)為第d 維作用在第i 個(gè)粒子上總的作用力來自其他所有粒子作用力的總和，其大小定義如下:

其中，randj是范圍在［0，1］之間的隨機(jī)數(shù)。

根據(jù)牛頓第二定理，第i 個(gè)粒子在第d 維上t 時(shí)刻的加速度定義如下:

其中，Mi(t)是第i 個(gè)粒子在t 時(shí)刻的慣性質(zhì)量。

最后根據(jù)式(11)和式(12)更新粒子的速度和位置:

其中，randi為［0，1］的隨機(jī)數(shù)。

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

3.1 算法分析

引力搜索算法的關(guān)鍵在于粒子質(zhì)量的計(jì)算，粒子質(zhì)量是由適應(yīng)度來衡量的，適應(yīng)度越好，粒子質(zhì)量越大，對作用粒子的吸引力越大，使作用粒子偏向粒子質(zhì)量大的運(yùn)動(dòng)。對于群體，作用粒子將受到群體粒子質(zhì)量的影響，從而產(chǎn)生一個(gè)合力，影響作用粒子的最優(yōu)方向。

根據(jù)以上過程可知引力與粒子的質(zhì)量(或函數(shù)的適應(yīng)度)息息相關(guān)。因此，通過改變粒子的引力合力計(jì)算公式來對引力搜索算法進(jìn)行改進(jìn)。

3.2 改進(jìn)的合力公式

根據(jù)上文對算法的分析，在式(9)中添加了一個(gè)系數(shù)λ 來修正算法中的合力公式。系數(shù)λ 的計(jì)算公式為:

其中，λ 為式(9)需要添加的系數(shù);k1，k2為可調(diào)整參數(shù)，可以根據(jù)不同函數(shù)設(shè)置;C 為參數(shù)，與k2有關(guān)，即y(x)為一分段函數(shù)，它由x 得來，通過式(14)可以使y(x)在［0，π×2-1］內(nèi)變化，x 的計(jì)算由式(13)得到，其中，M(i)和M(j)分別為粒子i 和粒子j 的質(zhì)量;x 的作用是對函數(shù)值進(jìn)行親和度檢測。x 值越小即2 個(gè)粒子的質(zhì)量值的差越小，表示其親和度越大，且兩者之間的引力越大;反之，兩者之間的引力就越小。此關(guān)系通過式(15)體現(xiàn)出來，因此，將上式代入式(9)得到改進(jìn)的合力計(jì)算公式為:

從式(16)可以看出，通過添加λ 改變合力表達(dá)式，可以加快粒子向最優(yōu)方向運(yùn)動(dòng)。

由于粒子的質(zhì)量是由目標(biāo)函數(shù)適應(yīng)度值確定的，其目標(biāo)函數(shù)適應(yīng)度值的大小越接近，粒子質(zhì)量的大小也越接近，進(jìn)而使得的值越小，代入式(15)得到一個(gè)系數(shù)λ 的值，且由式(15)可以看出，x 越小，λ 的值越大，其親和度越大，進(jìn)而使得兩粒子間的引力也越大。故由上述分析可得，粒子間目標(biāo)函數(shù)適應(yīng)度值越接近，粒子間的引力也越大，從而在理論說明可以加快種群的收斂速度。

3.3 改進(jìn)的算法流程

改進(jìn)的搜索算法流程如下:

(1)搜索空間的識(shí)別，確定問題的搜索空間。

(2)隨機(jī)初始化粒子的位置，最大迭代次數(shù)T，初始化種群N。

(3)對每個(gè)粒子根據(jù)目標(biāo)函數(shù)計(jì)算粒子的適應(yīng)度值。

(4)根據(jù)式(8)計(jì)算更新引力函數(shù)G(t)，根據(jù)式(1)和式(2)計(jì)算更新每個(gè)粒子的質(zhì)量M(t)。

(5)根據(jù)式(7)計(jì)算每個(gè)粒子間的引力。

(6)根據(jù)式(13)計(jì)算各粒子質(zhì)量差。

(7)根據(jù)式(14)映射到區(qū)間［0，π/2］。

(8)根據(jù)式(15)計(jì)算得到系數(shù)，并代入式(16)得到粒子受到的合力。

(9)根據(jù)式(10)和式(11)分別計(jì)算粒子的加速度和速度。

(10)根據(jù)式(12)更新每個(gè)粒子的速度。

(11)重復(fù)步驟(3)～步驟(8)直至滿足算法條件，結(jié)束。

4 仿真實(shí)驗(yàn)

本文仿真實(shí)驗(yàn)在Windows 8 系統(tǒng)和Matlab 2012a 下，進(jìn)行并采用了5 個(gè)經(jīng)典測試函數(shù)去驗(yàn)證算法的有效性，在此算法中先初始化:G0=100，α=20，T=1 000，種群數(shù)N=50，維數(shù)30。計(jì)算所得的結(jié)果是求取其30 次平均值，所選擇的測試函數(shù)如表1 所示，均為最小化問題，最小值都為0。

表1 測試函數(shù)

在表1 中，f1為Sphere 單峰二次函數(shù)，主要用來測試算法尋優(yōu)精度;f2為Rosenbrock 函數(shù)，是一個(gè)非凸、病態(tài)函數(shù);f3為Rsatrigin 函數(shù)，多峰，在S={xi∈(-5.12，+5.12)，i=1，2，…，n}范圍內(nèi)大約存在10n個(gè)局部極小點(diǎn)，一般算法較難得到全局最優(yōu)解;f4為Ackley 函數(shù)，是一個(gè)具有深度局部最小點(diǎn)的多峰函數(shù);f5為Griewank 函數(shù)，多峰，存在大量局部極小點(diǎn)。f3～f5主要用來檢驗(yàn)算法全局搜索的性能和避免早熟。

測試結(jié)果如表2 和表3 所示。其中，表2 是式(14)和式(15)中的可調(diào)參數(shù)，是在實(shí)驗(yàn)所得結(jié)果和收斂性最好的情況下整定得到的。表3 分別為基本GSA、改進(jìn)GSA(PGSA)、文獻(xiàn)［12］的MGSA 和文獻(xiàn)［13］的GSAGJ 所得到結(jié)果的平均值。

表2 可調(diào)參數(shù)值

表3 結(jié)果平均值

圖1～圖5 為函數(shù)f1～f5的仿真實(shí)驗(yàn)曲線。

圖1 f1函數(shù)的進(jìn)化曲線

圖2 f2函數(shù)的進(jìn)化曲線

圖3 f3函數(shù)的進(jìn)化曲線

圖4 f4函數(shù)的進(jìn)化曲線

圖5 f5函數(shù)的進(jìn)化曲線

實(shí)驗(yàn)結(jié)果分析如下:

(1)由表3 和圖1 可知，對于復(fù)雜的單模態(tài)函數(shù)Sphere，PGSA 算法的收斂速度比MGSA 稍快、比GSA 快、比GSAGJ 快得明顯。另外，PGSA 收斂精度高，MGSA 次之，同時(shí)可以看到，GSAGJ 在求單模態(tài)函數(shù)Sphere 時(shí)不是很好。

(2)對于Rosenbrock 函數(shù)，由圖2 可以看出，PGSA 算法進(jìn)化到100 代左右就開始收斂，MGSA 和GSA 均到200 代左右收斂，GSAGJ 到300 代以后才開始收斂，搜索精度相當(dāng)。

(3)Griewank、Ackley、Rsatrigin 等3 個(gè)多模態(tài)函數(shù)均是復(fù)雜的非線性全局優(yōu)化問題，主要用來測試算法的全局搜索性能［14］，從圖3～圖5 和表3 可以看出，3 種改進(jìn)GSA 算法的優(yōu)化效果均比GSA 好。對于3 個(gè)函數(shù)，PGSA 算法的收斂速度均高于GSA、MGSA 和GSAGJ 算法。對于Griewank 函數(shù)，MGSA算法比其他3 種算法搜索的結(jié)果都要好，但PGSA 收斂速度最快，在100 代左右就收斂到了最優(yōu)值。GSAGJ 算法在收斂精度和收斂速度方面都很不理想，只比GSA 稍好。對于Ackley 函數(shù)，PGSA 也能幾乎線性收斂，且收斂速度最快，GSAGJ 算法次之，都比GSA 要好。在收斂精度方面，3 種改進(jìn)算法均優(yōu)于GSA，其中PGSA 算法最好，GSAGJ 算法稍差，PGSA 算法僅比GSA 好。對于Rsatrigin 函數(shù)，在3種改進(jìn)的GSA 算法中，PGSA 無論在收斂速度還是在收斂精度方面都有絕對的優(yōu)勢，并且達(dá)到了理論最優(yōu)值，GSAGJ 次之，MGSA 比GSA 要好。

通過以上算法改進(jìn)的理論敘述與仿真實(shí)驗(yàn)的結(jié)果可知，粒子在搜索解的過程中是不斷尋優(yōu)的，每一個(gè)粒子受到來自各個(gè)不同質(zhì)量吸引力的作用，從而產(chǎn)生一個(gè)合力，并在這個(gè)合力的作用下運(yùn)動(dòng)，通過引進(jìn)粒子質(zhì)量差，發(fā)現(xiàn)質(zhì)量大的粒子與質(zhì)量小的粒子，由于其質(zhì)量差較大，親和度小，因此它們間的引力小，這樣就會(huì)減小質(zhì)量小(即劣解)的粒子對質(zhì)量大的粒子的作用力，從而減小質(zhì)量大的粒子所受的合力對最優(yōu)解的偏差，進(jìn)而使粒子能更好地朝著所期望即最優(yōu)的方向運(yùn)動(dòng)，這樣不僅加快了收斂速度，而且能提高搜索精度?？傊琍GSA 在函數(shù)優(yōu)化時(shí)有它的有效性和優(yōu)勢。

5 結(jié)束語

本文提出了一種基于親和度的改進(jìn)引力搜索算法。通過引入質(zhì)量差來檢測粒子間的親和度，如式(13)所示，然后通過式(14)～式(15)構(gòu)造了一個(gè)系數(shù)添加到合力計(jì)算表達(dá)式中，通過親和度的大小來反映粒子間適應(yīng)度的關(guān)系，從而反映出粒子間的引力大小，質(zhì)量差越小，親和度越大，粒子間引力越大，產(chǎn)生的速度快;反之，質(zhì)量差越大，親和度越小，粒子間引力越小，產(chǎn)生的速度越小。仿真實(shí)驗(yàn)表明，改進(jìn)的GSA 算法提高了算法的收斂速度和搜索精度。然而，針對更為復(fù)雜的函數(shù)，本文算法在尋優(yōu)速度和精度方面還有待提高。

［1］Krishnanand K N，Ghose D.Detection of Multiple Source Locations Using a Glowworm Metaphor with Applications to Collective Robotics［C］//Proc.of Swarm Intelligence Symposium.［S.l.］:IEEE Press，2005:84-91.

［2］李曉磊，邵之江，錢積新.一種基于動(dòng)物自治體的尋優(yōu)模式:魚群算法［J］.系統(tǒng)工程理論與實(shí)踐，2002，22(11):32-38.

［3］Kennedy J.Particle Swarm Optimization［C］//Proc.of IEEE International Conference on Neural Networks.Perth，Australia:IEEE Press，2010:760-766.

［4］江銘炎，袁東風(fēng).人工魚群算法及其應(yīng)用［M］.北京:科學(xué)出版社，2012.

［5］Rashedi E，Nezamabadi-Pour H，Saryazdi S.GSA:A Gravitational Search Algorithm［J］.Information Sciences，2009，179(13):2232-2248.

［6］楊 晶，黎 放，狄 鵬.免疫萬有引力搜索算法的研究與仿真［J］.兵工學(xué)報(bào)，2012，33(12):1533-1538.

［7］Li Chaoshun，Zhou Jianzhou.Parameters Identification of Hydraulic Turbine Governing System Using Improved Gravitational Search Algorithm［J］.Energy Conversion and Management，2011，52(1):374-381.

［8］李 沛，段海濱.基于改進(jìn)萬有引力搜索算法的無人機(jī)航路規(guī)劃［J］.中國科學(xué):技術(shù)科學(xué)，2012，42(10):1130-1136.

［9］Doraghinejad M，Nezamabadi-pour H，Hashempour S A，et al.A Hybrid Algorithm Based on Gravitational Search Algorithm for Unimodal Optimization［C］//Proc.of the 2nd International Conference on Computer and Knowledge Engineering.Mashhad，Iran:IEEE Press，2012:129-132.

［10］Shamsudin H C，Irawan A，Ibrahim Z，et al.A Fast Discrete Gravitational Search Algorithm［C］//Proc.of the 4th International Conference on Computational Intelligence，Modelling and Simulation.Kuantan，Malaysia:IEEE Press，2012:24-28.

［11］姜建國，王雙記，劉永青，等.一種實(shí)用的類電磁機(jī)制算法［J］.西安電子科技大學(xué)學(xué)報(bào):自然科學(xué)版，2013，40(2):59-64.

［12］李春龍，戴 娟，潘 豐.引力搜索算法中粒子記憶性改進(jìn)的研究［J］.計(jì)算機(jī)應(yīng)用，2012，32(10):2732-2735.

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

［14］胡超杰，章 兢.一種采用選擇的免疫差分進(jìn)化算法［J］.計(jì)算機(jī)應(yīng)用研究，2013，30(6):1640-1651.