求解動(dòng)態(tài)優(yōu)化問題的改進(jìn)多種群引力搜索算法

畢曉君，刁鵬飛，王艷嬌，肖婧

?

求解動(dòng)態(tài)優(yōu)化問題的改進(jìn)多種群引力搜索算法

畢曉君1，刁鵬飛1，王艷嬌2，肖婧3

(1. 哈爾濱工程大學(xué)信息與通信工程學(xué)院，黑龍江哈爾濱，150001;2. 東北電力大學(xué)信息工程學(xué)院，吉林吉林，132012;3. 遼寧省交通高等?？茖W(xué)校信息工程系，遼寧沈陽(yáng)，110122)

針對(duì)目前多種群算法解決動(dòng)態(tài)優(yōu)化問題時(shí)存在過多冗余計(jì)算、尋優(yōu)精度低等缺陷，提出多種群串行搜索的引力搜索算法。采用多種群串行搜索的策略，便于當(dāng)前子種群利用其他已收斂種群的進(jìn)化信息。為解決多峰重復(fù)搜索而帶來(lái)的冗余計(jì)算問題，提出具有約束條件的初始化策略，給予初始化的粒子以方向性的指引，避免其初始化在已尋峰區(qū)域；采用距離判決的策略發(fā)現(xiàn)并終止多峰重復(fù)搜索。為全面的監(jiān)測(cè)環(huán)境變化及解決多樣性丟失問題，提出一種監(jiān)測(cè)環(huán)境策略及追蹤策略。研究結(jié)果表明：所提算法，面對(duì)不同的環(huán)境變化程度以及不同的峰值數(shù)量，其求解精度都優(yōu)于其他7種對(duì)比算法的求解精度，證明該算法在求解動(dòng)態(tài)優(yōu)化問題上的優(yōu)越性。

引力搜索算法(GSA)；動(dòng)態(tài)優(yōu)化問題(DOPs)；多種群策略

近年來(lái)，對(duì)智能優(yōu)化算法的研究主要集中在求解不隨時(shí)間變化的靜態(tài)優(yōu)化問題上[1]。然而，實(shí)際工程中的多數(shù)問題都是動(dòng)態(tài)優(yōu)化問題(dynamic optimization problems, DOPs)，如市場(chǎng)波動(dòng)或金融變化等，因此DOPs的研究具有實(shí)際意義。DOPs問題的約束條件、目標(biāo)函數(shù)和解會(huì)隨著時(shí)間或其他參數(shù)發(fā)生變化，對(duì)于DOPs問題來(lái)說(shuō)，求解目標(biāo)已不再是尋得最優(yōu)解，還要求算法可以檢測(cè)到環(huán)境的變化、解決多樣性丟失并盡可能地動(dòng)態(tài)的追蹤最優(yōu)解。典型的智能優(yōu)化算法如粒子群算法[2?3]、差分進(jìn)化算法[4]等作為解決動(dòng)態(tài)優(yōu)化問題的基礎(chǔ)算法，雖表現(xiàn)出良好的搜索能力，但在面臨多種環(huán)境變化的問題，其求解精度仍有待提高。同時(shí)，面對(duì)多樣性缺失、環(huán)境動(dòng)態(tài)變化等問題，采取何種策略與優(yōu)化算法相結(jié)合也是決定算法性能的關(guān)鍵。目前常見的輔助策略主要有：環(huán)境變化后增加多樣性、始終保持多樣性、記憶策略與多種群策略 等[5]。其中，多種群策略是目前被廣泛采用的解決DOPs的策略，該策略的核心思想是通過多個(gè)子種群并行的搜索各個(gè)局部最優(yōu)峰，當(dāng)環(huán)境變化時(shí)，在給出所得最優(yōu)值的同時(shí)，各子種群繼續(xù)追蹤局部峰的變化。但該策略容易出現(xiàn)多個(gè)種群同時(shí)搜索1個(gè)局部峰的情況，增加了計(jì)算開銷，對(duì)此，Blackwell等[6]提出了一種根據(jù)距離判斷重復(fù)搜索的策略，該策略雖能及時(shí)地判斷出多子群重復(fù)搜索，但帶來(lái)了較高的計(jì)算復(fù)雜度，且因多子群重復(fù)搜索而帶來(lái)的計(jì)算開銷仍有望進(jìn)一步減少。引力搜索算法(gravitational search algorithm, GSA)是2009年提出群智能優(yōu)化算法，具有設(shè)置參數(shù)少、全局搜索能力強(qiáng)、計(jì)算簡(jiǎn)單、收斂速度快等優(yōu)點(diǎn)[7]。目前關(guān)于GSA的研究主要集中在靜態(tài)優(yōu)化問題上，國(guó)內(nèi)外針對(duì)DOPs的研究還較少。本文作者通過對(duì)現(xiàn)有的多種群策略進(jìn)行改進(jìn)，并根據(jù)GSA自身特點(diǎn)提出一種基于改進(jìn)多種群的引力搜索算法，采用多種群串行搜索策略，有利于各種群充分共享彼此進(jìn)化過程中得到的信息；采用排斥距離策略以使粒子帶有約束條件的初始化，一定程度上避免粒子初始化在已尋峰所在區(qū)域，提高粒子的進(jìn)化價(jià)值；采用距離判決策略可以及時(shí)發(fā)現(xiàn)當(dāng)前種群是否正在搜索已尋峰，減少計(jì)算開銷；采用一種環(huán)境檢測(cè)策略，及時(shí)全面的檢測(cè)出各個(gè)峰的變化情況；采用一種針對(duì)已尋峰的追蹤策略，提高算法的搜索效率。最后，通過動(dòng)態(tài)標(biāo)準(zhǔn)測(cè)試問題，對(duì)主要參數(shù)進(jìn)行研究分析，并與目前解決DOPs問題效果較好的7種算法相比較，驗(yàn)證本文算法的有效性和先進(jìn)性。

1 引力搜索算法基本原理

在GSA中，種群個(gè)體都是在空間中運(yùn)動(dòng)的個(gè)體，它們?cè)谌f(wàn)有引力的作用下彼此相互吸引運(yùn)動(dòng)，它們的質(zhì)量大小是評(píng)價(jià)其優(yōu)劣的標(biāo)準(zhǔn)，質(zhì)量較大粒子的位置對(duì)應(yīng)較優(yōu)解。在進(jìn)化過程中，GSA算法通過個(gè)體間的萬(wàn)有引力相互作用實(shí)現(xiàn)優(yōu)化信息的共享，引導(dǎo)群體向最優(yōu)解區(qū)域運(yùn)動(dòng)展開搜索。

若空間中含有個(gè)粒子，則第個(gè)粒子的位置為

其中：=1, 2, …,；為搜索空間的維數(shù)；為第個(gè)粒子在第維上的位置信息。在時(shí)刻，2個(gè)粒子間的作用力為

其中：M()和M()分別為粒子和粒子的質(zhì)量；為一個(gè)極小的常量；()為在時(shí)刻的萬(wàn)有引力常數(shù)。具體定義為

其中：0為初始時(shí)刻的引力常數(shù)；為最大迭代次數(shù)，且設(shè)置不同的會(huì)導(dǎo)致引力常數(shù)以不同的趨勢(shì)減小。若R()為粒子與粒子之間的歐氏距離，則在時(shí)刻，粒子在維上受到的其他粒子的合力為

其中：r為變化區(qū)間在[0, 1]之間的隨機(jī)數(shù)；為粒子對(duì)粒子在第維空間上的作用力。依據(jù)牛頓第二定律，定義時(shí)刻粒子在維上的加速度為

在進(jìn)化過程中，粒子的速度和位置的更新方式為

粒子的質(zhì)量與其適應(yīng)度值有關(guān)，質(zhì)量越大的粒子，表明其更接近最優(yōu)粒子，其對(duì)其他粒子的作用力會(huì)較大但是其移動(dòng)速度會(huì)較慢，粒子質(zhì)量的計(jì)算公式為

(7)

其中：f()為粒子的適應(yīng)度；()為質(zhì)量最小粒子的適應(yīng)度；()為質(zhì)量最大粒子的適應(yīng)度。

2 基于改進(jìn)多種群策略的引力搜索算法

通過分析傳統(tǒng)多種群策略在解決動(dòng)態(tài)優(yōu)化問題上存在的不足，對(duì)多種群策略的種群搜索模式進(jìn)行改進(jìn)，并根據(jù)動(dòng)態(tài)優(yōu)化問題的特點(diǎn)，提出一種基于改進(jìn)多種群策略的引力搜索算法。

2.1 改進(jìn)多種群策略

2.1.1 多種群串行搜索

多種群策略是目前被廣泛采用的解決動(dòng)態(tài)優(yōu)化問題的一種策略，其基本思想是多個(gè)子種群共同對(duì)最優(yōu)解展開搜索并分享彼此在進(jìn)化過程中所得到的進(jìn)化信息，當(dāng)發(fā)現(xiàn)環(huán)境變化時(shí)輸出最優(yōu)值，然后利用多個(gè)子種群繼續(xù)的追蹤這些已尋峰，以達(dá)到動(dòng)態(tài)尋優(yōu)的目的。這是一個(gè)多種群并行進(jìn)化搜索的過程，然而多種群同時(shí)展開搜索容易出現(xiàn)多個(gè)子種群同時(shí)搜索同一個(gè)峰的問題，這無(wú)疑會(huì)增加許多計(jì)算開銷，降低算法的尋優(yōu)效率。因此根本上的解決重復(fù)搜索問題是多種群策略能有效解決動(dòng)態(tài)優(yōu)化問題的關(guān)鍵。

對(duì)此，許多學(xué)者都提出了改進(jìn)策略，其中最具代表性的是Blackwell等[6]采用比較各種群最優(yōu)值距離的方法，判斷各個(gè)子種群所尋最優(yōu)值是否相同，判決閾值定義為

其中：為搜索空間；為局部峰值的個(gè)數(shù)；為問題的維數(shù)；excl為判斷重復(fù)搜索的閾值。若當(dāng)前子種群的最優(yōu)粒子與某個(gè)已尋局部峰之間的歐氏距離小于閾值excl時(shí)，判定當(dāng)前種群所優(yōu)化的區(qū)域已被其他種群開采過，則終止最優(yōu)值較差的那個(gè)子群的繼續(xù)搜索。

該策略雖然能判斷出多個(gè)子種群重復(fù)搜索，在一定程度上降低了種群重復(fù)搜索同一個(gè)峰所帶來(lái)的效率低下的影響，但每次迭代搜索都需要計(jì)算各個(gè)子種群所尋最優(yōu)粒子之間的距離，這會(huì)增加較多的計(jì)算復(fù)雜度；另外，當(dāng)較多子種群都同時(shí)搜索同一個(gè)峰時(shí)，重新初始化這些子種群仍會(huì)增加許多的計(jì)算開銷，這會(huì)降低算法優(yōu)化動(dòng)態(tài)問題的整體性能。

因此，為解決現(xiàn)有多種群策略存在重復(fù)搜索的問題，本文在原有多種群策略的基礎(chǔ)上，提出一種改進(jìn)的多種群策略，即將原有多個(gè)種群同時(shí)對(duì)解空間優(yōu)化搜索，改進(jìn)為各個(gè)子種群依次優(yōu)化搜索最優(yōu)解，并在優(yōu)化的過程中，采用文獻(xiàn)[6]所述方式監(jiān)測(cè)子種群是否發(fā)生重復(fù)搜索的情況，這種改進(jìn)的多種群策略相比于現(xiàn)有多種群并行搜索策略的優(yōu)勢(shì)是：1) 重復(fù)搜索最多只會(huì)發(fā)生在2個(gè)子種群之間，一旦判斷出子種群重復(fù)搜索時(shí)，只需要重新初始化1個(gè)子種群，這節(jié)省了較多計(jì)算開銷；2) 只需計(jì)算當(dāng)前種群與其他已尋峰之間的歐式距離，減小了計(jì)算復(fù)雜度。

2.1.2 收斂判決策略

本文提出的改進(jìn)多種群搜索策略，是多個(gè)子種群按順序搜索解空間，當(dāng)1個(gè)子種群收斂時(shí)，再初始化1個(gè)新子群，因此需要為每個(gè)種群設(shè)定收斂的條件。而當(dāng)種群逐漸收斂時(shí)，則種群的多樣性會(huì)逐漸降低，并由此而導(dǎo)致當(dāng)前最優(yōu)粒子與種群中的其他粒子在各個(gè)維度上的差異度也隨之降低，因此，可以通過種群當(dāng)前最優(yōu)粒子與其他粒子在各個(gè)維度上整體的差異度來(lái)判斷種群的收斂情況?；诖怂枷?，本文提出一種判斷收斂的方式，具體為

其中：為問題的維數(shù)；Gbestj()為在時(shí)刻種群所搜尋的最優(yōu)個(gè)體在第維上的位置信息，rj()為在時(shí)刻，除最優(yōu)個(gè)體Gbestj()外，種群中其他個(gè)體在第維上的位置信息的平均值；l為判決閾值。如果l較大，則收斂程度不是很高的種群會(huì)符合收斂條件，這會(huì)導(dǎo)致尋優(yōu)精度的降低；當(dāng)l較小時(shí)，雖然種群會(huì)得到精度較高的解，但隨著收斂程度的不斷提高，尋優(yōu)結(jié)果在精度上提高的幅度會(huì)越來(lái)越不明顯，而且還會(huì)增加子種群完成1次尋優(yōu)的計(jì)算開銷，這會(huì)降低算法整體的優(yōu)化效率，因此l需要平衡對(duì)單個(gè)解的開采精度及計(jì)算開銷之間的關(guān)系。通過實(shí)驗(yàn)比較，當(dāng)l為0.01時(shí)，算法性能最好。

當(dāng)1個(gè)種群符合收斂條件時(shí)，則說(shuō)明當(dāng)前種群最優(yōu)粒子與其他粒子在各個(gè)維度上的差異度較小，此時(shí)種群已收斂，記錄當(dāng)前所尋值，并重新初始化1個(gè)新種群繼續(xù)搜索最優(yōu)解。

2.1.3 帶有約束條件的初始化策略

對(duì)于多種群串行的搜索策略，當(dāng)判定1個(gè)子種群收斂時(shí)，記錄該子群所得峰值并重新初始化1個(gè)新的子群，然而隨機(jī)初始化的粒子有可能生成在已尋峰所在區(qū)域，特別是隨著已尋峰數(shù)量的增多，這種可能性會(huì)逐漸增加。對(duì)于依靠粒子間的相互作用力進(jìn)行優(yōu)化的GSA來(lái)說(shuō)，隨著進(jìn)化的進(jìn)行，這些初始化在已尋峰周圍的粒子，極有可能在力的作用下吸引其他粒子進(jìn)入已尋峰所在區(qū)域，進(jìn)而導(dǎo)致該子群重復(fù)搜索已尋峰，因此，為了防止子群重復(fù)搜索已尋峰，需要給予初始化的粒子一定方向上的指引。通過以上分析，本文提出一種帶有約束條件的種群初始化方式來(lái)指引粒子的生成，約束條件為

其中：X()為粒子在時(shí)刻的位置信息；為第次環(huán)境下已尋峰的位置信息；為粒子與已尋峰之間的歐氏距離；為約束距離，即當(dāng)前初始化粒子與任何一個(gè)已尋峰相互間的距離小于時(shí)，粒子極可能陷入了已尋峰所在的區(qū)域，此時(shí)重新初始化該粒子以得到搜索價(jià)值更高的粒子。通過實(shí)驗(yàn)比較，當(dāng)為70時(shí)算法性能達(dá)到最優(yōu)，若過大，約束距離較大會(huì)使粒子錯(cuò)過一些未尋峰值所在的區(qū)域，則會(huì)增加對(duì)這些未尋峰的搜索難度；若較小，則不能達(dá)到跳出已尋區(qū)域的目的。當(dāng)1個(gè)子種群達(dá)到收斂條件時(shí)，采用帶有約束條件的初始化方式生成新種群，可以提高初始化粒子的進(jìn)化價(jià)值，利于對(duì)其他未尋峰展開搜索，提高了整體的搜索效率。

2.2 環(huán)境監(jiān)測(cè)與追蹤

2.2.1 環(huán)境監(jiān)測(cè)策略

智能優(yōu)化算法對(duì)問題的優(yōu)化過程實(shí)際上是種群逐漸收斂的過程，其多樣性會(huì)逐漸下降。而對(duì)于動(dòng)態(tài)優(yōu)化問題，當(dāng)環(huán)境發(fā)生變化時(shí)，已收斂的種群因其多樣性降低而不再具有開采新解的能力。因此，算法需要具有檢測(cè)環(huán)境變化的能力，以及時(shí)的更新存儲(chǔ)的諸如已尋峰等相關(guān)信息。

為了達(dá)到檢測(cè)環(huán)境的目的，目前采取的環(huán)境檢測(cè)方式主要有哨兵法[8]和最優(yōu)值變化法[9]，這2種方式都是通過比較某個(gè)粒子前后代值的變化情況來(lái)檢測(cè)環(huán)境的，無(wú)法準(zhǔn)確的判斷出哪些局部峰發(fā)生了變化?；谝陨戏治?，為了準(zhǔn)確的判斷出整體環(huán)境的變化情況，本文采取的檢測(cè)策略描述如下：

1) 每隔代，比較各個(gè)已尋峰的變化情況。

2) 當(dāng)有某個(gè)已尋峰發(fā)生變化時(shí)，則此時(shí)環(huán)境發(fā)生變化，輸出已尋峰中的最優(yōu)值。

3) 對(duì)于未變化的峰，則將其視為環(huán)境變化后的已尋峰。

其中：對(duì)于參數(shù)的取值，若設(shè)置過大，則會(huì)延誤環(huán)境變化后被檢測(cè)出來(lái)的時(shí)間，若設(shè)置過小，則會(huì)增加額外的計(jì)算開銷。通過實(shí)驗(yàn)比較，當(dāng)為10時(shí)算法性能可以達(dá)到最優(yōu)。這種檢測(cè)策略，一方面能及時(shí)準(zhǔn)確的判斷出環(huán)境的變化；另一方面，將未變化的峰直接作為下一代已尋峰，減少了待尋峰的個(gè)數(shù)，提高了算法的整體搜索效率。

2.2.2 追蹤策略

對(duì)于DOPs問題，當(dāng)環(huán)境發(fā)生變化時(shí)，雖然各個(gè)局部峰會(huì)出現(xiàn)不同程度的變化，但并不是完全隨機(jī)的重新生成新的峰，其變化在一定的范圍內(nèi)可追蹤。在本文中，將環(huán)境變化前被種群搜尋到，且隨環(huán)境發(fā)生變化的峰稱為待追蹤峰。

當(dāng)環(huán)境變化時(shí)若初始化的粒子在待尋峰周圍生成，則會(huì)加快種群對(duì)該峰的搜索速度，提高算法的搜索效率。因此，為了準(zhǔn)確的追蹤各個(gè)局部峰，本文采用下式方式初始化粒子。

其中：為變化區(qū)間在[0, 1]之間的隨機(jī)數(shù)；X()為隨機(jī)產(chǎn)生的第個(gè)粒子在維上的信息；X為第個(gè)已尋峰在第維上的信息；為控制粒子生成區(qū)間的參數(shù)。

在種群追蹤待追蹤峰的過程中，若能縮小待搜索區(qū)域，則會(huì)提高搜尋待追蹤峰的效率，因此希望參數(shù)越小越好。然而，若搜尋區(qū)域設(shè)置過小，則可能導(dǎo)致待追蹤峰種群的追蹤。通過實(shí)驗(yàn)比較，當(dāng)參數(shù)為3時(shí)，算法會(huì)獲得更好的優(yōu)化效果。

通過在待追蹤峰周圍隨機(jī)生成的方式追蹤峰值的變動(dòng)，大大縮小算法對(duì)最優(yōu)解的搜索區(qū)域，減少了對(duì)最優(yōu)解的搜索時(shí)間，提高了優(yōu)化搜索的效率。當(dāng)完成對(duì)所有待追蹤峰的追蹤后，若仍未檢測(cè)出環(huán)境變化，則采用具有約束條件的種群初始化策略，繼續(xù)對(duì)解空間展開搜索。

2.3 所提算法主要過程

1) 種群初始化，設(shè)置種群規(guī)模為，排斥距離，判斷種群是否收斂的閾值l，以及參數(shù)。

2) 初始化1個(gè)種群并對(duì)解空間展開搜索，當(dāng)種群滿足式(9)時(shí)，則種群收斂，記錄當(dāng)前種群的最優(yōu)值。

3) 按式(10)所示約束條件初始化1個(gè)新種群。

4) 在每個(gè)種群搜索最優(yōu)解的過程中，通過式(8)判斷當(dāng)前種群是否搜尋的是已被尋到的峰。

5) 采用2.2.1所述方式檢測(cè)環(huán)境的變化，當(dāng)檢測(cè)到環(huán)境變化時(shí)，輸出環(huán)境變化前一刻所尋到的全局最優(yōu)值。

6) 當(dāng)環(huán)境變化后，根據(jù)各個(gè)已尋峰的變化情況，對(duì)各個(gè)已尋峰進(jìn)行分類，若峰值未發(fā)生變化，則將其作為環(huán)境變化后的已尋峰處理；若該峰發(fā)生變化，則采用2.2.2所述的追蹤策略，追蹤這些峰。

7) 當(dāng)采用追蹤策略完成對(duì)所有待追蹤峰的優(yōu)化搜索后，種群初始化策略仍采用帶有約束條件的初始化方式。

3 仿真實(shí)驗(yàn)與結(jié)果分析

所有實(shí)驗(yàn)在硬件配置為Intel? Core?2 Duo CPU P7570 2.26 GHz、2 G內(nèi)存、2.27 GHz主頻的計(jì)算機(jī)上進(jìn)行，開發(fā)環(huán)境為Matlab2010.b。

3.1 測(cè)試問題

本文采用目前國(guó)際上較為權(quán)威的移動(dòng)峰問題(moving peaks benchmark，MPB)[10]來(lái)對(duì)算法進(jìn)行測(cè)試，該測(cè)試問題的特點(diǎn)是周期性的改變峰的高度、寬度和移動(dòng)峰的位置以構(gòu)造復(fù)雜的動(dòng)態(tài)環(huán)境，測(cè)試問題的目標(biāo)函數(shù)為

其中：W()和H()分別為第個(gè)局部最優(yōu)峰在時(shí)刻的寬度和高度；X()為第峰在維上的位置信息。MPB的相關(guān)參數(shù)如表1所示。通過比較離線誤差和標(biāo)準(zhǔn)方差來(lái)比較算法性能，離線誤差的公式為

其中：為環(huán)境變化次數(shù)；h為理論最優(yōu)值；f-為第次環(huán)境變化前的算法所尋最優(yōu)值。

表1 MPB問題參數(shù)設(shè)置

3.2 實(shí)驗(yàn)設(shè)置

采用2組實(shí)驗(yàn)研究多種群引力搜索算法在解決動(dòng)態(tài)優(yōu)化問題上的性能。第1組實(shí)驗(yàn)主要分析關(guān)鍵參數(shù)對(duì)于算法整體性能的影響。第2組實(shí)驗(yàn)是比較多種群引力搜索算法與目前解決動(dòng)態(tài)優(yōu)化問題效果較好的7種算法，7種算法分別為：CDDE_Ar[4]，F(xiàn)TMPSO[11]，jDE[12]，CPSOR[13]，Dopt-aiNET[14]，CPSO[8]和PSO-CP[15]。對(duì)于引力搜索算法的相關(guān)參數(shù)設(shè)定參考文獻(xiàn)[6]，種群規(guī)模取10，閾值l取0.01，排斥距離取80，取3，環(huán)境變化次數(shù)取100次。所有仿真實(shí)驗(yàn)都獨(dú)立運(yùn)行20次。

3.3 參數(shù)分析

3.3.1參數(shù)的研究

在GSA中，如式(3)所示，需要為引力常數(shù)設(shè)置合適的變化趨勢(shì)，也即對(duì)參數(shù)的設(shè)置。本組實(shí)驗(yàn)?zāi)康氖茄芯繀?shù)對(duì)算法性能的影響，實(shí)驗(yàn)結(jié)果如表2所示。從表2可以看出：當(dāng)為150時(shí)，離線誤差最小，算法所得到的求解精度最高；當(dāng)參數(shù)大于150時(shí)，算法性能會(huì)逐漸下降。這是因?yàn)楫?dāng)較大時(shí)，則引力常數(shù)()變化較緩，進(jìn)而導(dǎo)致進(jìn)化步長(zhǎng)變化較慢，雖然能使種群更加精細(xì)的對(duì)解空間展開搜索，但是會(huì)增加單個(gè)種群搜索的計(jì)算量，減少種群的搜索次數(shù)，降低算法整體的優(yōu)化性能；當(dāng)較小時(shí)，()變化較快，使得進(jìn)化步長(zhǎng)變化較快，進(jìn)而導(dǎo)致種群收斂到非局部最優(yōu)峰上，降低了算法的搜索能力。

3.3.2 種群規(guī)模的研究

本組實(shí)驗(yàn)?zāi)康氖茄芯坎煌姆N群規(guī)模對(duì)算法優(yōu)化性能的影響，取種群規(guī)模，實(shí)驗(yàn)結(jié)果如表3所示。從表3可以看出：當(dāng)種群規(guī)模設(shè)置為10時(shí)，會(huì)得到較好的實(shí)驗(yàn)結(jié)果。當(dāng)種群規(guī)模較小時(shí)，由于種群多樣性較低，種群搜索最優(yōu)解的難度加大，使得算法的整體優(yōu)化性能下降；而當(dāng)種群規(guī)模設(shè)置較大時(shí)，則會(huì)增加種群?jiǎn)未嗡阉鞯挠?jì)算量，會(huì)減少種群的搜索次數(shù)，降低算法的整體優(yōu)化性能。

表2 參數(shù)T研究結(jié)果

表3 種群規(guī)模的研究結(jié)果

3.4 與其他算法的對(duì)比

3.4.1 不同動(dòng)態(tài)程度DOPs的比較

為了考察在不同的環(huán)境變化強(qiáng)度下，比較所提算法與其他目前解決動(dòng)態(tài)優(yōu)化問題效果較好的7種算法，結(jié)果如表4所示，從表4可以看出：隨著環(huán)境變化強(qiáng)度的增加，各算法的求解精度在一定程度上都會(huì)有所下降，這是因?yàn)榄h(huán)境變化越來(lái)越劇烈，加大了算法跟蹤全局最優(yōu)解的難度。但所提算法在不同的變化強(qiáng)度下，精度和穩(wěn)定性都優(yōu)于其他的7種算法的精度和穩(wěn)定性。這是因?yàn)槎喾N群策略、帶有約束條件的初始化策略及重復(fù)搜索監(jiān)測(cè)策略為優(yōu)化節(jié)約了大量的計(jì)算成本，進(jìn)而增加了初始新子種群的次數(shù)，使最優(yōu)解有更多的機(jī)會(huì)被開采到，當(dāng)環(huán)境監(jiān)測(cè)策略及時(shí)全面的檢測(cè)到環(huán)境的變化后，追蹤策略又保證了對(duì)已尋峰的追蹤。另外，如果環(huán)境變化程度較大，個(gè)別已尋峰脫離種群追蹤，那么多種群串行搜索的策略又能繼續(xù)的追蹤到該峰。

3.4.2 不同峰值DOPs的比較

考察所提算法與其他7種算法，在解決不同峰值數(shù)量的動(dòng)態(tài)問題上的性能對(duì)比，實(shí)驗(yàn)結(jié)果如表5所示，從表5可以看出：隨著局部最優(yōu)峰數(shù)量的逐漸增多，各個(gè)算法性能都有不同程度的降低，這是因?yàn)殡S著峰值數(shù)量的增加，在有限的計(jì)算成本下，算法搜尋到最優(yōu)解的難度加大。本文所提算法相比于其他7種對(duì)比算法在解決不同峰值數(shù)量的動(dòng)態(tài)優(yōu)化問題時(shí)，表現(xiàn)出明顯的優(yōu)勢(shì)。這是因?yàn)楸疚乃惴ㄒ环矫鏈p少了因重復(fù)搜索帶來(lái)的計(jì)算開銷，另一方面，及時(shí)全面的檢測(cè)環(huán)境的變化并采取相應(yīng)的追蹤策略，縮小了隨時(shí)間變化的局部峰的搜索區(qū)域，GSA快速的搜索速度又進(jìn)一步減少了搜尋峰值所需的計(jì)算開銷。

表4 IMGSA與其他7種算法在不同環(huán)境變化強(qiáng)度下實(shí)驗(yàn)對(duì)比

注：括號(hào)內(nèi)的數(shù)據(jù)為標(biāo)準(zhǔn)誤差；括號(hào)外的數(shù)據(jù)為離線誤差。

表5 IMGSA與其他7種算法在不同峰數(shù)下實(shí)驗(yàn)對(duì)比

注：括號(hào)內(nèi)的數(shù)據(jù)為標(biāo)準(zhǔn)誤差；括號(hào)外的數(shù)據(jù)為離線誤差。

通過對(duì)仿真結(jié)果的分析可知：IMGSA算法與其他7種算法相比，在解決不同的環(huán)境變化程度及不同峰值數(shù)量問題時(shí)，均表現(xiàn)出較好的尋優(yōu)性能，表明了本文算法在解決DOPs問題上的優(yōu)越性。

4 結(jié)論

1) 提出了一種基于改進(jìn)多種群策略的引力搜索算法。該算法采用多個(gè)種群串行搜索的方式，共享種群間的進(jìn)化信息；采用帶有約束條件的初始化策略給予初始化粒子方向性的指引；采用監(jiān)測(cè)種群重復(fù)搜索的策略，減少了重復(fù)搜索同一個(gè)峰而帶來(lái)的冗余計(jì)算；采用一種環(huán)境檢測(cè)策略，在及時(shí)檢測(cè)環(huán)境變化的同時(shí)，全面的掌握了各個(gè)峰值變化的具體情況，對(duì)于未變化峰予以保留；采用一種追蹤策略，準(zhǔn)確追蹤各個(gè)已尋峰的變化。

2) 找出了最適合的算法進(jìn)化步長(zhǎng)變化的趨勢(shì)，提高了算法的求解精度。本文提出的IMGSA算法較現(xiàn)有的多種動(dòng)態(tài)優(yōu)化算法在不同峰值、不同環(huán)境變化程度下，其尋優(yōu)精度均優(yōu)于其他多種動(dòng)態(tài)優(yōu)化算法尋優(yōu)精度，在解決動(dòng)態(tài)優(yōu)化的實(shí)際問題中具有廣泛的應(yīng)用價(jià)值。

[1] 施榮華, 朱炫滋, 董健, 等. 基于粒子群?遺傳混合算法的MIMO雷達(dá)布陣優(yōu)化[J]. 中南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2013, 44(11): 4500?4505. SHI Ronghua, ZHU Xuanzi, DONG Jian, et al. A hybrid approach based on PSO and GA for array optimization in MIMO radar[J]. Journal of Central South University (Science and Technology), 2013, 44(11): 4500?4505.

[2] 朱慶保, 徐曉晴, 朱世娟. 一種新的求解動(dòng)態(tài)連續(xù)優(yōu)化的分層粒子群算法[J]. 控制與決策, 2013, 28(10): 1573?1577. ZHU Qingbao, XU Xiaoqing, ZHU Shijuan. A new hierarchical PSO algorithm for solving dynamic and continuous optimization problems[J]. Control and Decision, 2013, 28(10): 1573?1577.

[3] 高平安, 蔡自興, 余伶俐. 一種基于多子群的動(dòng)態(tài)優(yōu)化算法[J]. 中南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2009, 40(3): 731?736. GAO Pingan, CAI Zixin, YU Linli. Multi-swarm based optimization algorithm in dynamic environments[J]. Journal of Central South University (Science and Technology), 2009, 40(3): 732?736.

[4] Halder U, Das S, Maity D. A cluster-based differential evolution algorithm with external archive for optimization in dynamic environments[J]. IEEE Transactions on Cybernetics, 2013, 43(3): 881?897.

[5] Zuo X, Xiao L. A DE and PSO based hybrid algorithm for dynamic optimization problems[J]. Soft Computing, 2014, 18(7): 1405?1424.

[6] Blackwell T, Branke J. Multiswarms, exclusion, and anti- convergence in dynamic environments[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(4): 459?472.

[7] Rashedi E, Nezamabadi-Pour H, Saryazdi S. GSA: A gravitational search algorithm[J]. Information Sciences, 2009, 179(13): 2232?2248.

[8] YANG Shengxiang, LI Changhe. A clustering particle swarm optimizer for locating and tracking multiple optima in dynamic environments[J]. IEEE Transactions on Evolutionary Computation, 2010, 14(6): 959?974.

[9] 劉黎黎, 李國(guó)家, 汪定偉. 動(dòng)態(tài)環(huán)境下帶有非線性效應(yīng)的復(fù)合粒子群優(yōu)化算法[J]. 控制理論與應(yīng)用, 2012, 29(10): 1253?1262. LIU Lili, LI Guojia, WANG Dingwei. Composite particle swarm optimization with nonlinear effect in dynamic environment[J]. Control Theory & Applications, 2012, 29(10): 1253?1262.

[10] Branke J. Memory enhanced evolutionary algorithms for changing optimization problems[C]// Proceedings of the 1999 Congress on Evolutionary Computation-CEC99. Washington, DC, United S tates: IEEE, 1999: 1875?1882.

[11] Yazdani D, Nasiri B, Sepas-Moghaddam A, et al. A novel multi-swarm algorithm for optimization in dynamic environments based on particle swarm optimization[J]. Applied Soft Computing, 2013, 13(4): 2144?2158.

[12] Brest J, Zamuda A, Boskovic B, et al. Dynamic optimization using self-adaptive differential evolution[C]// 2009 IEEE Congress on Evolutionary Computation. Trondheim, Norway: IEEE, 2009: 415?422.

[13] LI Changhe, YANG Shengxiang. A general framework of multipopulation methods with clustering in undetectable dynamic environments[J]. IEEE Transactions on Evolutionary Computation, 2012, 16(4): 556?577.

[14] Brest J, Koro?ec P, ?ilc J, et al. Differential evolution and differential ant-stigmergy on dynamic optimisation problems[J]. International Journal of Systems Science, 2013, 44(4): 663?679.

[15] LIU Lili, YANG Shengxiang, WANG Dingwei. Particle swarm optimization with composite particles in dynamic environments[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2010, 40(6): 1634?1648.

(編輯 羅金花)

Improved multi-population gravitational search algorithm for dynamic optimization problems

BI Xiaojun1, DIAO Pengfei1, WANG Yanjiao2, XIAO Jing3

(1. College of Information and Communication Engineering, Harbin Engineering University, Harbin 150001, China;2. College of Information Engineering, Northeast Dianli University, Jilin 132012, China;3. Department of Information Engineering, Liaoning Provincial College of Communications, Shenyang 110122, China)

To improve the redundant computing and low accuracy of solving dynamic optimization problems (DOPs) for multi-population algorithm, a novel improved multi-population gravitational search algorithm (IMGSA) was proposed. In IMGSA, the multi-population serial strategy was good for the present subpopulation to use evolutionary information of convergence population. A constraint initialization strategy was proposed to reduce the redundant computing which was generated by multiple populations searching repeatedly. Simultaneously, a distance decision strategy was used to stop multiple populations searching. Eventually, a monitoring and tracking strategy was used to monitor the environmental change and track the local peaks. The results show that IMGSA has a better performance in solving DOPs than those of other seven dynamic algorithms in different degree of environmental change or different peak number. It can prove the validity of proposed algorithm.

gravitational search algorithm (GSA); dynamic optimization problems (DOPs); multi-population strategy

10.11817/j.issn.1672-7207.2015.09.023

TP18

A

1672?7207(2015)09?3325?07

2014?09?26；

2014?11?30

國(guó)家自然科學(xué)基金資助項(xiàng)目(61175126)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(HEUCFZ1209)；高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金項(xiàng)目資助課題(20112304110009)；黑龍江省博士后基金資助項(xiàng)目(LBH-Z12073)；遼寧省教育廳科學(xué)研究一般項(xiàng)目(L2012458)；遼寧省博士科研啟動(dòng)基金資助項(xiàng)目(20120511) (Project(61175126) supported the National Natural Science Foundation of China; Project(HEUCFZ1209) supported by the Fundamental Research Funds for the Central Universities; Project(20112304110009) supported by the Special Scientific Research Foundation of the Doctoral Program of Higher Education; Project(LBH-Z12073) supported by Post Doctoral Fund of Heilongjiang Province; Project(L2012458) supported by General Project of Scientific Research of the Education Department of Liaoning Province; Project(20120511) supported by the Doctoral Research of Liaoning Province)

畢曉君，博士，教授，從事信息智能處理技術(shù)、智能優(yōu)化算法、數(shù)字圖像處理研究；E-mail: 398317196@qq.com