基于動態(tài)分組的多策略引力搜索算法

張強 王梅

摘要：給出了一種基于動態(tài)分組的多策略引力搜索算法.算法迭代初期利用自適應(yīng)分組策略對種群進行分組尋優(yōu)，每個分組內(nèi)只更新最差個體，采用云模型理論來改進最優(yōu)個體的進化行為;迭代后期將種群分為優(yōu)勢子群和拓展子群，采用差分變異算子更新優(yōu)勢子群提高尋優(yōu)精度和速度，利用Tent混沌理論進化拓展子群完成個體變異.典型復(fù)雜函數(shù)測試表明，該算法具有很好的收斂精度和計算速度.

關(guān)鍵詞：引力搜索算法;云模型;佳點集;混沌;連續(xù)空間優(yōu)化

中圖分類號：TP 301.6 文獻標志碼：A DOI：10.3969/j.issn.1000-5641.2019.01.08

0引言

Rashedi教授于2009年提出的引力搜索算法（Gravitational Search Algorithm，GSA）目前己應(yīng)用到系統(tǒng)辨識、參數(shù)優(yōu)化、模式分類、動態(tài)優(yōu)化、智能決策等領(lǐng)域.文獻的研究表明，與粒子群優(yōu)化算法、遺傳算法等其他仿生算法相比，GSA具有很強的全局搜索能力與較快的收斂速度，但也容易發(fā)生算法早熟、算法運行效率偏低.GSA在迭代初期尋優(yōu)速度較慢，并對個體的初始位置具有一定的依賴性.分析其原因是因為每次迭代都要計算尋優(yōu)個體間的引力和（慣性質(zhì)量、空間距離、引力常數(shù)等）來確定個體的尋優(yōu)軌跡，導(dǎo)致尋優(yōu)初期個體更新計算量較大;而在尋優(yōu)后期若個體視野內(nèi)沒有更優(yōu)個體時，則個體更新操作相當于在周圍進行隨機運動，進而降低了尋優(yōu)效率和收斂速度.目前已在如何保持種群多樣性、與其他智能算法進行融合、個體更新方式和變異等方面提出了一些改進方法.文獻提出了分子群的方式改進GSA的性能;文獻采用粒子群算法的思想使得個體具有記憶功能，且在速度更新公式中引入了個體最優(yōu)位置和全局最優(yōu)位置，但仍需計算原有的引力和，并增加了一些計算量;文獻將差分變異策略引入到個體位置更新，所不同的是文獻通過閾值統(tǒng)計學(xué)習(xí)的方式，在進化過程中根據(jù)兩種策略在先前學(xué)習(xí)代數(shù)的成功率，自適應(yīng)地選擇較優(yōu)策略生成下一代群體，保證了種群在解空間中的探索與開發(fā)能力之間的平衡，但是算法引入的學(xué)習(xí)代數(shù)與閾值的選取對算法的性能具有一定的影響;而文獻是取兩種策略所獲最優(yōu)位置，但不管何種策略都表明用差分變異策略可以改進GSA的尋優(yōu)效果;文獻以預(yù)定的概率來選擇變異的個體，并通過高斯分布來確定個體的新位置，通過動態(tài)的改變變異概率來加快算法收斂速度;文獻利用反向?qū)W習(xí)策略進行種群初始化，并提出精英策略和邊界變異策略來提高個體的探索能力和開發(fā)能力.基于上述文獻的算法改進思路，本文基于分子群、個體更新方式和變異等方面提出了一種基于動態(tài)分組的多策略引力搜索算法fMulti-Strategy Gravitational Search Algorithm Based On DynamicGrouping，MS-GSA）：首先采用佳點集算法初始個體位置，利用動態(tài)分組策略對所有個體進行分組進化尋優(yōu)，每個分組內(nèi)只更新最優(yōu)個體和最差個體;在算法尋優(yōu)后期將所有個體分成優(yōu)勢子群和拓展子群，利用差分變異算子進化優(yōu)勢子群提高尋優(yōu)精度和速度，利用Tent混沌算子進化拓展子群完成個體變異避免陷入局部最優(yōu)解.

1基本引力搜索算法（GSA）

GSA將所有優(yōu)化個體當作有質(zhì)量的物體能夠做無阻力運動.每個個體會受到解空間中其他個體的萬有引力的影響，并產(chǎn)生加速度向質(zhì)量更大的個體運動.個體間通過萬有引力的相互作用來實現(xiàn)優(yōu)化信息的共享.下面以最小值為例對GSA進行描述.

（1）隨機產(chǎn)生初始個體位置，計算個體適應(yīng)值，依據(jù)個體適應(yīng)值計算慣性質(zhì)量Mi（t），計算公式為

2動態(tài)分組多策略引力搜索算法原理

2.1基于佳點集理論的種群初始化

尋優(yōu)個體的初始位置在一定程度上影響著尋優(yōu)性能.個體多樣性越多則找到最優(yōu)解的幾率也越大，若有某些個體就在最優(yōu)解周圍，則有利于加速算法收斂和提高尋優(yōu)性能.故本文算法的個體采用佳點集算法進行初始化.佳點集理論已證明近似計算函數(shù)在s維歐氏空間單位立方體上的積分時，用n個佳點構(gòu)成的加權(quán)和比采用任何其他n個點所得到的誤差都要小.具體定義如下.

（6）考慮到會存在總的進化周期較短，造成后期進化策略還未運行的可能性，所以需設(shè)置一個迭代比例因子λ，用于控制超過預(yù)設(shè)迭代次數(shù)后劃分為兩個子群，進而完成后期的進化策略.

2.3自適應(yīng)分組內(nèi)最優(yōu)個體的進化方式

GSA的個體更新計算量決定著算法的尋優(yōu)速度，可以借鑒混洗蛙跳算法的個體更新方式.在分組內(nèi)只更新最差個體，仍采用GSA的更新方式.而最優(yōu)個體由于所受合力相對較小，實際上等價于隨機移動位置.根據(jù)GSA進化原理可知，每個個體都要計算慣性質(zhì)量、與其他個體的距離和引力，進而指導(dǎo)個體更新軌跡.如果將這個計算復(fù)雜度用另一種計算方式替代，產(chǎn)生最優(yōu)解周圍的若干個體，則既可以保持個體的多樣性，也可以增加獲取更優(yōu)解的概率.社會學(xué)研究表明在較優(yōu)個體周圍往往更容易找到更優(yōu)個體，可以理解為局部最優(yōu)解周圍往往更易發(fā)現(xiàn)更優(yōu)解.云模型在知識表達時具有不確定中帶有確定性、穩(wěn)定之中又有變化的特點，體現(xiàn)了自然界物種進化的基本原理.以局部最優(yōu)個體為中心按云模型理論生成h個子個體.生成步驟如下.

步驟（1）：針對每個分組內(nèi)的最優(yōu)個體，以其作為期望Ex代表子個體的搜索中心.

步驟（2）：計算每個分組的適應(yīng)度方差作為熵En來改變搜索范圍.

步驟（4）：利用正態(tài)云模型算法根據(jù)步驟（1）到步驟（3）確定的c（Ex，En，He）生成h個云滴（子個體），若發(fā)現(xiàn)比分組內(nèi)最優(yōu)個體更好的子個體則代替.

2.4進化后期雙子群進化原理

智能進化算法在尋優(yōu)后期既要增加收斂速度和求解精度，又要盡量避免陷入局部最優(yōu)解，GSA也不例外.算法在尋優(yōu)后期要么已在全局最優(yōu)解附近，要么陷入局部最優(yōu)解.故本文算法利用優(yōu)勢子群來加速尋優(yōu)效率，利用拓展子群來避免陷入局部最優(yōu)，兩個子群在各自經(jīng)過指定次數(shù)的迭代后再重新分成兩個子群.

2.4.1優(yōu)勢子群內(nèi)個體更新方式

差分進化算法是一種簡單且高效的智能優(yōu)化算法，算法中的變異操作在很大程度上影響著尋優(yōu)性能.采用差分進化算法的變異操作來更新優(yōu)勢子群內(nèi)的個體，公式為

2.5算法流程步驟1：設(shè)定種群規(guī)模、分組個數(shù)m、最大迭代數(shù)T、分組內(nèi)迭代數(shù)和最小收斂精度，

采用第2.1節(jié)的方法初始尋優(yōu)個體.

步驟2：根據(jù)第2.2節(jié)對種群里的個體進行分組，根據(jù)第2.3節(jié)對個體進行更新.

步驟3：如果未滿足結(jié)束條件，且分組內(nèi)的迭代次數(shù)達到指定次數(shù)和分組個數(shù)m不為2，則執(zhí)行步驟2.

步驟4：若m等于2，采用第2.4節(jié)的方法進化后期的雙子群個體尋優(yōu)行為.

步驟5：若滿足收斂精度或達到最大迭代數(shù)則退出，否則執(zhí)行步驟4.

從分析MS-GSA的算法原理可知，在不考慮種群初始化的時間復(fù)雜度情況下，MS-GSA在自適應(yīng)分組策略、雙子群分組及進化方式上增加了計算量.但由于經(jīng)典GSA在實現(xiàn)過程中已完成適應(yīng)度的排序和個體間距離的計算，所以進化初期的動態(tài)分組和后期的雙子群分組的復(fù)雜度并沒有增加.故MS-GSA實際的計算開銷主要增加在第2.3節(jié)和公式（7）、公式（9）.針對第2.3節(jié)的復(fù)雜度，其本質(zhì)是利用云模型進行啟發(fā)式計算，在云滴個數(shù)確定的情況下相當于增加若干個個體，這些計算量相對于GSA的最優(yōu)個體計算與其他個體間的距離、引力合力和加速度及最后的位置更新的計算量要小很多，實際上是減少了GSA最優(yōu)個體的計算量，同時每個分組里只更新最差個體.所以總體上自適應(yīng)分組策略的計算量要遠遠少于經(jīng)典GSA.而公式（7）只針對優(yōu)勢子群的個體之間利用子群內(nèi)個體的位置進行更新，公式（9）的變異操作也只是極小部分個體，相對于其GSA原有的個體更新方式計算量要少.故依據(jù)算法復(fù)雜性漸進性理論可知本文的MS-GSA沒有增加GSA的復(fù)雜度，而且還減少了原有算法的計算量.

3實驗仿真

實驗仿真環(huán)境為：Windows 7操作系統(tǒng);Intel酷睿i5處理器;主頻2.5 Hz，4 G內(nèi)存;開發(fā)工具為Matlab.針對8個函數(shù)極值求解問題如表1所示，將本文所提算法fMS-GSA）與文獻的引力搜索算法（GSA）、文獻的差分進化算法（Differential Evolution Algorithm，DE）、文獻的DE-GSA（Hybrid Differential Evolution and Gravitation Search Algo—rithm）和文獻的QGSA（Gravitational Search Algorithm Based on Gaussian Mutation）進行尋優(yōu)性能對比.本文的多種策略主要涉及動態(tài)分組、優(yōu)勢種群的差分變異和拓展子群的Tent混沌映射;文獻將差分變異和GSA改進的進化方式進行混合尋優(yōu)，在一定程度上可與本文無動態(tài)分組策略的算法相對比;而文獻主要采用高斯變異策略改進，可以與本文的Tent混沌映射相對比.從眾多的變異改進算法結(jié)果可知，單一的不同變異策略對改進算法的性能差距各有優(yōu)劣.故本文算法與文獻的算法和文獻的算法進行對比，可以認為這3種主要策略的協(xié)作使得本文算法的尋優(yōu)效果具有一定的優(yōu)越性，故它們之間的對比可以等價于這些策略具體功用的實驗證明.

從本節(jié)的仿真結(jié)果可知，本文的動態(tài)分組多策略引力搜索算法具有很好的尋優(yōu)精度和速度.這是由于GSA的進化原理計算相對復(fù)雜，其中每個個體要計算與其他個體間的距離和引力和，故其運行時間較多.本文的MS-GSA減少了原有算法的計算量，同時利用小生鏡的方式進行尋優(yōu)可以保持群體中個體的多樣性，并且本文的分組策略主要基于適應(yīng)值的排序結(jié)果，故不增加算法的額外計算量，同時在迭代過程中利用分組內(nèi)個體的方差來判定離散程度，進而在進化過程中不斷減少分組個數(shù)，這樣既有利于前期進行全局尋優(yōu)，又可以在后期進行局部精細挖掘和增加收斂速度，并且在分組內(nèi)只更新最優(yōu)個體和最差個體進而減少了算法的計算量，加快了收斂速度;同時MS-GSA采用佳點集理論初始化個體增加了個體靠近最優(yōu)解的幾率，在進化過程中云模型的穩(wěn)定傾向性和隨機性既利于使個體向周圍更優(yōu)個體自適應(yīng)定位，又利于保護個體的多樣性，所以采用云模型更新最優(yōu)個體加強了最優(yōu)個體進化的確定性并保持了隨機多樣性，進而提高了算法的尋優(yōu)速率和性能，有效地改善了GSA在求解一些高維復(fù)雜函數(shù)時求解精度不高、收斂速率慢的缺點.

3.2高維函數(shù)上的優(yōu)化性能測試

對于函數(shù)f1，f2，f3，f4進行維度為N=100，N=200來對比MS-GSA與DE、GSA的性能.各類算法的運行參數(shù)設(shè)置見第3.1節(jié)，收斂精度為10E-6，函數(shù)在每個算法中獨立運行20次，對比結(jié)果如表10所示.

從高維函數(shù)測試的優(yōu)化效果可知，隨著維度的增加，GSA的運行時間增加幅度較大，主要是由于維數(shù)的增加需要計算的個體質(zhì)量、個體間的距離、個體間的引力合力和加速度也大大增加，造成求解速度和精度下降，而MS—GSA利用小生鏡技術(shù)和差分變異算子的優(yōu)勢大大改進了經(jīng)典GSA的不足，同時加速了尋優(yōu)速度和精度，尤其是在高維函數(shù)尋優(yōu)性能的穩(wěn)定性上得到了很大的改進.由于實驗設(shè)定迭代次數(shù)為1000，造成DE和GSA的表現(xiàn)性能不是很好，通過進一步增加迭代次數(shù)發(fā)現(xiàn)，這兩種算法的尋優(yōu)結(jié)果也會得到改善，這也說明本文所提算法在較短的迭代周期內(nèi)能獲得較好的尋優(yōu)速度和精度.

4結(jié)論

本文給出了基于動態(tài)分組的多策略引力搜索算法（MS—GSA）.該算法基于動態(tài)分組技術(shù)將云模型算法、差分變異算法和混沌算法引入到個體更新過程中，有效地改進了GSA迭代初期較大的計算量，加速了迭代初期尋優(yōu)速度，加強了算法后期的逃逸能力，使其快速定位到最優(yōu)解區(qū)域.研究結(jié)果表明將各種算法的優(yōu)勢有機地融合在一起，有利于拓寬算法的研究范圍和應(yīng)用領(lǐng)域，也為智能進化算法的研究進行了新的探索和嘗試.由于本文算法在求解高維優(yōu)化問題的較好性能，可嘗試將其用于去解決工業(yè)控制、機器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)等領(lǐng)域的一些高維優(yōu)化問題.