魏煥新+++胡招娣

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

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

引言

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

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

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

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

1 萬有引力搜索算法

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

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

GAS算法步驟如下：

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

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

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

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

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

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

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

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

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

2.1 種群初始化

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

混沌的特點(diǎn)是隨機(jī)性，能根據(jù)規(guī)律在特定范圍進(jìn)行狀態(tài)的不斷復(fù)制，屬于是非線性現(xiàn)象。為了實(shí)現(xiàn)搜索空間內(nèi)個(gè)體的均勻分布，可以通過初始化混沌序列來實(shí)現(xiàn)。在本文中，種群通過混沌序列進(jìn)行初始化，混沌序列由維Logistic映射產(chǎn)生，是一個(gè)一維映射?？捎靡韵鹿奖磉_(dá)：

2.2 算術(shù)交叉算子

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

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

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

2.3 多樣性變異算子

以種群搜索為基礎(chǔ)的群智能優(yōu)化算法在進(jìn)入GSA進(jìn)化后期，會(huì)出局部最優(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個(gè)粒子的位置xit、速度vit通過混沌序列進(jìn)在搜索空間行初始化

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

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

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

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

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

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

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

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

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

3 結(jié)束語

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

參考文獻(xiàn)

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

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

7（35）：188-192.

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

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