周少武，陳 微，唐東成，張紅強，王 汐，周 游

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

1 概述

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

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

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

2 基本引力搜索算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 改進的引力搜索算法

3.1 算法分析

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

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

3.2 改進的合力公式

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

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

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

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

3.3 改進的算法流程

改進的搜索算法流程如下:

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

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

(3)對每個粒子根據(jù)目標函數(shù)計算粒子的適應度值。

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

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

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

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

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

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

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

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

4 仿真實驗

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

表1 測試函數(shù)

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

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

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

表3 結(jié)果平均值

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

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

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

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

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

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

實驗結(jié)果分析如下:

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

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

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

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

5 結(jié)束語

本文提出了一種基于親和度的改進引力搜索算法。通過引入質(zhì)量差來檢測粒子間的親和度，如式(13)所示，然后通過式(14)～式(15)構造了一個系數(shù)添加到合力計算表達式中，通過親和度的大小來反映粒子間適應度的關系，從而反映出粒子間的引力大小，質(zhì)量差越小，親和度越大，粒子間引力越大，產(chǎn)生的速度快;反之，質(zhì)量差越大，親和度越小，粒子間引力越小，產(chǎn)生的速度越小。仿真實驗表明，改進的GSA 算法提高了算法的收斂速度和搜索精度。然而，針對更為復雜的函數(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］李曉磊，邵之江，錢積新.一種基于動物自治體的尋優(yōu)模式:魚群算法［J］.系統(tǒng)工程理論與實踐，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］江銘炎，袁東風.人工魚群算法及其應用［M］.北京:科學出版社，2012.

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

［6］楊 晶，黎 放，狄 鵬.免疫萬有引力搜索算法的研究與仿真［J］.兵工學報，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］李 沛，段海濱.基于改進萬有引力搜索算法的無人機航路規(guī)劃［J］.中國科學:技術科學，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］姜建國，王雙記，劉永青，等.一種實用的類電磁機制算法［J］.西安電子科技大學學報:自然科學版，2013，40(2):59-64.

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

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

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