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

魏煥新+++胡招娣

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

關(guān)鍵詞：混沌；算術(shù)交叉；萬有引力搜索算法；多樣性變異

引言

無約束優(yōu)化問題可以為工程應(yīng)用求解數(shù)值。通常以下公式對無約束優(yōu)化問題進行描述。

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

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

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

1 萬有引力搜索算法

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

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

GAS算法步驟如下：

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

Step2. 所有粒子進行適應(yīng)度計算；

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

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

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

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

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

Step8. 經(jīng)過判斷，如果結(jié)束條件被滿足，結(jié)束計算，得到最佳答案，如果條件沒被滿足，重復(fù)步驟2。

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

2.1 種群初始化

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

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

2.2 算術(shù)交叉算子

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

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

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

2.3 多樣性變異算子

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

HGSA算法可以總結(jié)為：

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

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

Step3.所有粒子適應(yīng)度被計算；

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

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

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

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

Step8. 并找出當(dāng)前最優(yōu)粒子的位置；最優(yōu)粒子的位置通過計算全部粒子的適應(yīng)度得出；

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

Step10. 新粒子通過變異操作多樣性當(dāng)前全局最優(yōu)粒子位置得到；

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

3 結(jié)束語

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

參考文獻

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

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

7（35）：188-192.

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

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