嵌入遺傳算子的混合萬有引力搜索算法

魏煥新+++胡招娣

摘 要：一種以遺傳算子為基礎的混合引力搜索算法被提出用于無約束優化問題的求解，可以避免容易局部最優、收斂速度慢等基本引力搜索算法的弊端。首先，種群多樣性通過混沌序列進行維持；其次，對粒子進行引導靠近全局最優區域，通過當前最優粒子與通過概率選擇的粒子算出交叉得到的。最后，通過多樣性變異操作對當前全局最優粒子操作，避免了局部最優的發生。該方法優秀的尋優性通過8個標準函數運算該算法得到證明。

關鍵詞：混沌；算術交叉；萬有引力搜索算法；多樣性變異

引言

無約束優化問題可以為工程應用求解數值。通常以下公式對無約束優化問題進行描述。

全局優化方法算法，如蟻群優化、差分進化、粒子群優化、遺傳算法是以種群迭代為基礎的智能優化算法，其特點是，原理簡單、成功率高、獨立于求解問題的梯度信息、大概率收斂到問題等。所以，被大量用在無約束優化問題解析中。2009年，Rashedi教授，在科曼大學提出了萬有引力搜索算法。該方法極富啟發性，通過模擬萬有引力定律，利用粒子之間的相互吸引力引發的群體智能，作為指導來進行搜索優化。GSA特點是，少闡述、易操作，其尋優精度和收斂速度都比PSO和GA等智能算法更為優化。

GSA也存在和其它全局優化算法一樣的缺點，比如，收斂速度在后期降低，容易局部化經常出現在基于種群迭代搜索的優化算法。很多學者致力對GSA進行優化。Khatibinia和Khosravi共同提出混合GSA算法，通過對其和正交交叉算子進行改進。混凝土重力壩體型應用該算法被優化；Soleimanpour把量子理論融合到GSA中，提出可以優化函數的量子GSA；基于混沌優化的GSA由Gao等提出，其搜索算子是混沌；GSA在權重的基礎上被徐遙和王士同改進，將慣性質量作為權重。

本文講述通過將遺傳算子嵌入GSA，來改善目前GSA算法不能開發和勘探同時的問題，解決無約束優化問題。群體多樣性是通過混沌序列生成的初始群種進行維持。收斂速度通過變異、交叉操作實現加速的同時可以避免局部最優的出現。該算法通過8個標準測試函數進行驗證，結果證明各異的無約束優化問題可以被該算法有效處理。

1 萬有引力搜索算法

施力與受力粒子、慣性質量、位置是所有GSA中粒子的特質。粒子在粒子間引力的作用下向大質量例子所處方向移動。適應度相當于粒子的慣性質量，問題的解相當于例子位置。

粒子i在t時刻第d維空間中速度：vid（t）

GAS算法步驟如下：

Step1. 參數設定：在搜索空間，設t=0，隨機選取N個粒子的速度、位置進行初始化。

Step2. 所有粒子進行適應度計算；

Step3. 所有粒子進行慣性質量更新計算，運用公式（3）和（4）

Step4.引力系數G（t）使用式（9）更新；

Step5.所有粒子的合力用式（10）計算；

Step6.所有粒子的加速度通過式（11）計算

Step7.所有粒子的速度、位置通過式（12）和（13）計算

Step8. 經過判斷，如果結束條件被滿足，結束計算，得到最佳答案，如果條件沒被滿足，重復步驟2。

2 混合萬有引力搜索算法（HGSA）

2.1 種群初始化

根據Huapt等的研究，初始群種具有很好的多樣性，對以種群迭代搜索為基礎的智能優化算法非常有利于得出全局最佳解。對于基礎GSA，搜索算法的起點由粒子的初始位置決定的。所以，粒子在一個好的初始群里中位置是呈現一個全面對搜索空間覆蓋的趨勢。但是，隨機產生初始群體一般發生在迭代前的基本GSA，算法的搜索效率被降低的原因是粒子在不是均勻分布在解空間。

混沌的特點是隨機性，能根據規律在特定范圍進行狀態的不斷復制，屬于是非線性現象。為了實現搜索空間內個體的均勻分布，可以通過初始化混沌序列來實現。在本文中，種群通過混沌序列進行初始化，混沌序列由維Logistic映射產生，是一個一維映射。可用以下公式表達：

2.2 算術交叉算子

GSA局部搜索能力差，全局搜索能力強。本文通過對算術交叉算子，（將當前最優粒子和隨機從群體中選擇的粒子進行交叉運算）以實現對GSA收斂速度的提升，以及增強其局部搜索能力的目的。表達式為算數交叉：

GSA局部搜索能力差，全局搜索能力強。本文通過對算術交叉算子，（將當前最優粒子和隨機從群體中選擇的粒子進行交叉運算）以實現對GSA收斂速度的提升，以及增強其局部搜索能力的目的。表達式為算數交叉：

子代粒子x'1和x'2在經過算術交叉操作后，位置一定是位于給定的父代粒子x1和x2之間。所以，為了得到更接近最優解的子代粒子，進行算數交叉操作計算應選取當前最優粒子和群體中隨機粒子。算法的收斂速度被提高，局部搜索能力得到加強，由于群通過以上操作被快速的引導去靠近最優粒子，而一般交叉操作的盲目和隨機的特性不會出現。

2.3 多樣性變異算子

以種群搜索為基礎的群智能優化算法在進入GSA進化后期，會出局部最優的現象。群體多樣性降低導致算法收斂速度被降低甚至被終止。根本原因是全部2.4 HGSA算法步驟

HGSA算法可以總結為：

Step1.設t=0，算法參數：G0（引力系數），pm（變異概率），（參數），pc（交叉概率），最大迭代次數（），N（種群規模）；

Step2.N個粒子的位置xit、速度vit通過混沌序列進在搜索空間行初始化

Step3.所有粒子適應度被計算；

Step4.粒子的慣性質量通過式（3） 和 （4） 計算更新；

Step5.引力系數G（t） 通過式 （9） 計算更新；

Step6. 全部粒子的合力之和通過式（10）進行計算；全部粒子的加速度通過式（11） 進行更新；

Step7.全部粒子的速度通過式（12） 計算更新；同時其位置通過式 （13） 進行計算更新；

Step8. 并找出當前最優粒子的位置；最優粒子的位置通過計算全部粒子的適應度得出；

Step9.下一代群里中保留當前全局最優解，新的子代粒子是通過當前最優粒子與隨機選取群體中粒子進行算數交叉操作得到的。即評估當前群體，確保最優保存。

Step10. 新粒子通過變異操作多樣性當前全局最優粒子位置得到；

Step11. 判斷算法是否滿足終止條件，若滿足，則算法結束，輸出全局最優解；否則，令t=t+1，返回Step3。進行條件判斷。如果滿足，結束算法并得到全局最優解；如果不滿足，重復Step3，并設t=t+1

3 結束語

通過對物理學中的有引力作用的模擬而開發的群智能隨機搜索方法，即萬有引力搜索算法。本文通過將遺傳算子嵌入萬有引力搜索算法而對其進行改進。根據運行8個標準測試函數數據，改進算法針對不同函數（單峰、多封）和基本萬有引力搜索算法相比有明顯優勢，表現為高穩定性和高尋優精度。算法性能是否受參數的影響和如何在約束優化問題中對其應用是下一步的研究方向。

參考文獻

[1]許波，彭志平，余建平.一種基于云模型的改進型量子遺傳算法[J].計算機應用研究，2011，28（10）：3684-3686.

[2]徐遙，王士同.引力搜索算法的改進[J].計算機工程與應用，2011，4

7（35）：188-192.

[3]Huapt R， Huapt S. Practical genetic algorithm[M]. USA： John Wiley & Sons， 2004.

[4]梁昔明，龍文，龍祖強，等.自適應梯度指導交叉的進化算法[J].小型微型計算機系統，2011，39（7）：1331-1335.