基于動態分組的多策略引力搜索算法

張強 王梅

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

關鍵詞：引力搜索算法;云模型;佳點集;混沌;連續空間優化

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

0引言

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

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

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

（1）隨機產生初始個體位置，計算個體適應值，依據個體適應值計算慣性質量Mi（t），計算公式為

2動態分組多策略引力搜索算法原理

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

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

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

2.3自適應分組內最優個體的進化方式

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

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

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

步驟（4）：利用正態云模型算法根據步驟（1）到步驟（3）確定的c（Ex，En，He）生成h個云滴（子個體），若發現比分組內最優個體更好的子個體則代替.

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

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

2.4.1優勢子群內個體更新方式

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

2.5算法流程步驟1：設定種群規模、分組個數m、最大迭代數T、分組內迭代數和最小收斂精度，

采用第2.1節的方法初始尋優個體.

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

步驟3：如果未滿足結束條件，且分組內的迭代次數達到指定次數和分組個數m不為2，則執行步驟2.

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

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

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

3實驗仿真

實驗仿真環境為：Windows 7操作系統;Intel酷睿i5處理器;主頻2.5 Hz，4 G內存;開發工具為Matlab.針對8個函數極值求解問題如表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）進行尋優性能對比.本文的多種策略主要涉及動態分組、優勢種群的差分變異和拓展子群的Tent混沌映射;文獻將差分變異和GSA改進的進化方式進行混合尋優，在一定程度上可與本文無動態分組策略的算法相對比;而文獻主要采用高斯變異策略改進，可以與本文的Tent混沌映射相對比.從眾多的變異改進算法結果可知，單一的不同變異策略對改進算法的性能差距各有優劣.故本文算法與文獻的算法和文獻的算法進行對比，可以認為這3種主要策略的協作使得本文算法的尋優效果具有一定的優越性，故它們之間的對比可以等價于這些策略具體功用的實驗證明.

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

3.2高維函數上的優化性能測試

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

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

4結論

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