申鼎才

(湖北工程學(xué)院 計(jì)算機(jī)與信息科學(xué)學(xué)院，湖北 孝感 432000)

基于精英遷移的主從式雙種群動(dòng)態(tài)遺傳算法

申鼎才

(湖北工程學(xué)院 計(jì)算機(jī)與信息科學(xué)學(xué)院，湖北 孝感 432000)

針對(duì)0-1編碼的動(dòng)態(tài)優(yōu)化問題，提出了一種基于精英遷移的主從式雙種群動(dòng)態(tài)遺傳算法。主種群采用記憶機(jī)制，把從種群獲得的最優(yōu)個(gè)體替換主種群中較差的個(gè)體，同時(shí)參與到與記憶個(gè)體的演化操作。通過一組動(dòng)態(tài)優(yōu)化函數(shù)進(jìn)行實(shí)驗(yàn)，仿真結(jié)果表明，本文提出的算法在各變化周期和變化強(qiáng)度下均能很好的跟蹤環(huán)境的動(dòng)態(tài)變化。

精英遷移；遺傳算法；動(dòng)態(tài)優(yōu)化

在現(xiàn)實(shí)生活中，很多優(yōu)化問題是動(dòng)態(tài)的，即目標(biāo)函數(shù)、約束條件和環(huán)境參數(shù)會(huì)隨著時(shí)間的變化而改變。與靜態(tài)優(yōu)化問題相比，由于動(dòng)態(tài)優(yōu)化問題增加了問題求解的不確定性，因而在一定程度上增加了動(dòng)態(tài)優(yōu)化問題的求解難度。

近年來，動(dòng)態(tài)環(huán)境下優(yōu)化問題越來越得到研究人員的關(guān)注，研究出了很多GA的變體算法應(yīng)用于動(dòng)態(tài)環(huán)境下的優(yōu)化，取得了很好應(yīng)用效果。如在GA中引入超變異策略[1]、隨機(jī)移民策略[2]、自組織隨機(jī)移民策略[3]等等。在上述策略中，維持或增加種群多樣性是引入相關(guān)策略的一個(gè)重要目標(biāo)。為了增加種群多樣性，同時(shí)減少多個(gè)種群交換信息從而導(dǎo)致算法復(fù)雜度的增加，本文提出一種多種群的簡化模式，采用主從式雙種群策略，根據(jù)不同種群在演化過程中功能的不同，分別采用不同的操作策略，使算法能保持較好的種群多樣性，從而提高跟蹤動(dòng)態(tài)環(huán)境的能力。

1 相關(guān)研究工作

在動(dòng)態(tài)環(huán)境下，增加種群多樣性是一種常見的進(jìn)化策略。Grefenstette[2]采用隨機(jī)移民策略，即在算法執(zhí)行過程中，通過在每一代引入新的個(gè)體替換當(dāng)前種群個(gè)體，以此來增加群體的多樣性。 Tinós[3]采用在每一代結(jié)束時(shí)用隨機(jī)生成的個(gè)體替換當(dāng)前種群中個(gè)體。由于鏈?zhǔn)椒磻?yīng)的存在，文獻(xiàn)[3]采用一種改進(jìn)的替換策略，即在選擇操作中，如果當(dāng)前個(gè)體被替換過，則選擇操作發(fā)生在所有被替換過的個(gè)體中，否則，選擇操作發(fā)生在所有未被替換過的個(gè)體中，以此來達(dá)到保護(hù)隨機(jī)引入的新個(gè)體。在通常的替換策略中，根據(jù)替換個(gè)體的不同，又有隨機(jī)替換和替換適應(yīng)值最小的個(gè)體等替換策略。Branke[4]提出的SOS中，在種群規(guī)模增大或者由于子種群位置的移動(dòng)而導(dǎo)致父種群某些個(gè)體無效時(shí)，采用隨機(jī)生成的個(gè)體填充。文獻(xiàn)[5]采用一種通過搜索子種群找到最優(yōu)解，并把自己搜索到的最優(yōu)解傳遞到記憶子種群。文獻(xiàn)[6]采用對(duì)3個(gè)子種群按適應(yīng)值排序，根據(jù)排序結(jié)果按比例分成3部分，即3個(gè)子種群，然后結(jié)合精英保留策略來產(chǎn)生新一代群體。文獻(xiàn)[7]采用混合遷移策略，該策略結(jié)合了精英保留策略、對(duì)偶策略和隨機(jī)遷入策略，當(dāng)前種群最差個(gè)體被遷入的個(gè)體所替換。

遺傳算法具有天然的并行性。為提高遺傳算法效率而引入的并行遺傳策略，能有效提高算法搜索速度，同時(shí)對(duì)維持種群多樣性也有一定的幫助，在一定程度上能減少或避免早熟現(xiàn)象。為使種群在進(jìn)化過程中維持一定的多樣性，多種群演化[8]也是一種常用的進(jìn)化策略，即各個(gè)種群可采用相同或不同的初始值和控制參數(shù)以及不同的選擇策略，以控制選擇壓力，使得算法在各個(gè)潛在區(qū)域搜索的同時(shí)，還能使已經(jīng)獲得的優(yōu)解在種群中擴(kuò)散，使算法收斂到滿意的全局最優(yōu)解，最終達(dá)到種群多樣性和選擇壓力的有效平衡。

2 算法實(shí)現(xiàn)

本文借助并行遺傳算法的多種群思想，將整個(gè)種群分成兩部分，每個(gè)部分的子種群各自獨(dú)立地按一定模式分別進(jìn)行演化，根據(jù)各子種群功能的不同，其中一個(gè)作為主種群，實(shí)施開發(fā)和記憶功能，另一個(gè)作為從種群，實(shí)施探索功能，并定期向主種群輸送搜索到的最優(yōu)解。對(duì)記憶種群，或者稱為主種群中，采用適應(yīng)值共享策略，而后在選擇過程中采用輪盤賭選擇策略，并結(jié)合精英保留策略。本文闡述的精英個(gè)體來源包括兩個(gè)方面：主種群本身進(jìn)化過程中每一代的精英個(gè)體和搜索種群中每一代的最優(yōu)個(gè)體。在從種群中，為使算法能夠維持在一個(gè)較高水平的多樣性，同時(shí)保持一定的探索能力，選擇策略選用錦標(biāo)賽選擇策略，同時(shí)在從種群中采用隨機(jī)移民策略，以維持種群中個(gè)體的多樣性，即每一次迭代用一定數(shù)量的隨機(jī)生成的新個(gè)體替換當(dāng)前種群中適應(yīng)值較小的個(gè)體。主種群中搜索到的最優(yōu)解保存在一個(gè)隊(duì)列中，如果達(dá)到記憶隊(duì)列長度上限 ，則刪除最早進(jìn)入隊(duì)列的最優(yōu)解。同時(shí)，以當(dāng)前代獲得的最優(yōu)解和記憶隊(duì)列中的最優(yōu)解為父體，經(jīng)交叉變異后生成的后代替換掉主種群中適應(yīng)值較差的個(gè)體，然后對(duì)主種群執(zhí)行常規(guī)的遺傳操作生成新的子種群，并把后代種群中發(fā)現(xiàn)的更優(yōu)個(gè)體更新到記憶隊(duì)列中，算法的基本實(shí)現(xiàn)步驟如表1所示。

表1 算法基本實(shí)現(xiàn)步驟

3 數(shù)值實(shí)驗(yàn)

3.1測(cè)試函數(shù)

本節(jié)實(shí)驗(yàn)中，將通過一組在動(dòng)態(tài)優(yōu)化中廣泛采用的測(cè)試函數(shù)來驗(yàn)證本文算法的有效性。接下來將首先介紹本文采用的一組靜態(tài)測(cè)試函數(shù)，然后介紹如何針對(duì)這類采用0-1編碼方式的靜態(tài)測(cè)試函數(shù)生成動(dòng)態(tài)測(cè)試函數(shù)。

3.1.1 OneMax函數(shù)

OneMax函數(shù)沒有局部最優(yōu)解，該函數(shù)的目標(biāo)為最大化編碼串中1的個(gè)數(shù)，一個(gè)編碼長度為l的OneMax函數(shù)可以描述如下：

(1)

3.1.2 RoyalRoad函數(shù)

由 Mitchell、Forrest 和 Holland提出的 Royal Road 函數(shù)被很多算法采用，本文采用長度為64位、包含8個(gè)連續(xù)8位積木塊(building block)的位串，該函數(shù)的適應(yīng)值采用如下方式計(jì)算：

(2)

圖1 RoyalRoad函數(shù)

其中，ci=8，δi={1，如果x∈S；0，否則}，S={s1,s2,s3,s4,s5,s6,s7,s8}。si可描述為圖1。

3.1.3 欺騙函數(shù)

欺騙函數(shù)是一族不能由低階模式直接重組成高階模式的函數(shù)，單純的三階或四階欺騙函數(shù)由于受種群規(guī)模的影響而不足于說明搜索策略的優(yōu)劣，這里采用10個(gè)4階完全Deceptive函數(shù)DF2組合而成，DF2定義如表2，經(jīng)過組合后的函數(shù)由40個(gè)二進(jìn)位串組成，位串全為"1"是唯一全局最優(yōu)解，最大值為300。

表2 四階欺騙函數(shù)

3.2動(dòng)態(tài)函數(shù)的生成

(3)

其中，?為異或操作(即有：1?1，1?0=1，0?0=0)。然后對(duì)第t代群體中的每一個(gè)個(gè)體采用式(3)進(jìn)行操作:

(4)

其中，k=?t/τ」為環(huán)境變化周期索引，符號(hào)?」為下取整運(yùn)算。

XOR生成動(dòng)態(tài)環(huán)境時(shí)，動(dòng)態(tài)環(huán)境的變化強(qiáng)度可以通過τ和ρ來表征，τ越小，則環(huán)境變化頻率越大，對(duì)算法及時(shí)跟蹤環(huán)境變化的能力要求越高，反之，則算法有更多的時(shí)間來對(duì)變化的環(huán)境作出響應(yīng)；ρ值越小，則環(huán)境變化強(qiáng)度越趨于緩和，反之環(huán)境變化則越劇烈。

3.3實(shí)驗(yàn)結(jié)果及性能評(píng)估

3.3.1 參數(shù)設(shè)置

在動(dòng)態(tài)環(huán)境下，分別采用本文的基于精英遷移的主從式雙種群動(dòng)態(tài)遺傳算法(MSDPGA)、隨機(jī)移民遺傳算法(RIGA)[2]、自組織隨機(jī)移民遺傳算法(SORIGA)[3]和簡單遺傳算法(SGA)，對(duì)動(dòng)態(tài)OneMax問題、RoyalRoad函數(shù)、欺騙函數(shù)進(jìn)行仿真實(shí)驗(yàn)，并對(duì)四種算法的性能進(jìn)行對(duì)比分析。各實(shí)驗(yàn)參數(shù)設(shè)置如下：種群大小N設(shè)置為100，交叉率ρc=0.6，變異率pm=0.001。 變化強(qiáng)度分別為0.1，0.5，0.9，即在每個(gè)環(huán)境變化周期中，種群中個(gè)體染色體二進(jìn)制位串中分別有10%，50%，90%的位發(fā)生變化，分別對(duì)應(yīng)變化強(qiáng)度弱、中、強(qiáng)。環(huán)境變化周期為每隔25，50，100代發(fā)生一次變化。MSDPGA中，精英保留數(shù)為1，MSDPGA 中主種群適應(yīng)值共享半徑的取值由于本文所采用的二進(jìn)制編碼串長不一致，因此在分析算法求得的累計(jì)平均最優(yōu)解和多樣性時(shí)，采用按串長的20%為共享半徑。SORIGA和RIGA以及MSDPGA從種群中替換率rr均為3。

3.3.2 結(jié)果與分析

由于實(shí)驗(yàn)是要驗(yàn)證不同變化周期和變化強(qiáng)度下算法對(duì)最優(yōu)解的跟蹤能力，因此本文采用每個(gè)算法的最大演化代數(shù)為30個(gè)環(huán)境變化周期，即對(duì)不同環(huán)境變化周期，算法最大運(yùn)行代數(shù)是不同的。各算法在每一種變化強(qiáng)度下對(duì)應(yīng)每一種變化周期各自獨(dú)立運(yùn)行30次，每次運(yùn)行采用不同的隨機(jī)種子。

表3-5給出不同算法在置信水平為0.05，自由度為58，各算法在不同變化周期和變化強(qiáng)度下的t檢驗(yàn)結(jié)果，表中數(shù)據(jù)表示各測(cè)試函數(shù)在各種環(huán)境變化強(qiáng)度和變化周期下，MSDPGA算法和其他三種算法在獲取累計(jì)平均最優(yōu)值性能方面的比較，其中，符號(hào)+、-、～分別表示MSDPGA性能優(yōu)于、劣于和不劣于其他算法。

從表3-5統(tǒng)計(jì)結(jié)果可以看出，MSDPGA在各變化周期和變化強(qiáng)度下對(duì)本文采用的測(cè)試函數(shù)是有效的。從表3可以看出，對(duì)于OneMax函數(shù)，各算法均能追蹤到環(huán)境的變化，其中SGA性能最差。同一變化周期下，各變化強(qiáng)度下MSDPGA均要顯著優(yōu)于其他算法，且在同一變化周期內(nèi)，當(dāng)變化強(qiáng)度(ρ= 0.9)最大時(shí)，MSDPGA的優(yōu)勢(shì)越明顯，表明此時(shí)算法中采用的記憶策略起了較大的作用。同時(shí)，對(duì)于相同變化強(qiáng)度環(huán)境下，變化周期越長，算法求得的最優(yōu)解越好，此時(shí)算法有更長的時(shí)間來跟蹤環(huán)境的變化。

表3 OneMax函數(shù)t檢驗(yàn)結(jié)果

表4 RoyalRoad函數(shù)t檢驗(yàn)結(jié)果

表5 四階欺騙函數(shù)t檢驗(yàn)結(jié)果

從表4統(tǒng)計(jì)結(jié)果可以看出，對(duì)于RoyalRoad函數(shù)，在變化強(qiáng)度較小(ρ= 0.1)時(shí)，SORIGA性能最優(yōu)，求得的最優(yōu)解要優(yōu)于其他算法，SGA性能最差。由于RoyalRoad函數(shù)本身的特點(diǎn)，此時(shí)MSDPGA采用的記憶機(jī)制對(duì)尋優(yōu)沒有明顯的幫助。相反，隨機(jī)遷入的新個(gè)體反而有助于算法找到最優(yōu)解。隨著變化強(qiáng)度的增大，MSDPGA采用的記憶機(jī)制效果逐漸顯現(xiàn)出來，尋得的最優(yōu)值要略優(yōu)于SORIGA和RIGA。

對(duì)于四階欺騙函數(shù)，從表5可以看出，除SGA性能較差之外，其他三種算法均能較好地跟蹤環(huán)境的變化。進(jìn)一步分析可以得出，在變化周期較短時(shí)，MSDPGA、SORIGA和RIGA三種算法找到的最優(yōu)解相差不大。隨著變化周期變長，各算法性能均有所提高，MSDPGA優(yōu)勢(shì)更為明顯，表明在較長的變化周期，算法所采用的記憶機(jī)制對(duì)算法尋得最優(yōu)解起了較大的作用。

綜上知，本文提出的算法在沒有增加過多的時(shí)間復(fù)雜度的情況下，通過在主、從種群中引入不同的演化策略，結(jié)合主種群采用記憶機(jī)制，使得算法在各變化周期和變化強(qiáng)度下均取得了較好的效果。同時(shí)，對(duì)于相同的測(cè)試函數(shù)，算法在變化周期較短時(shí)性能要劣于變化周期較長的情形，這是因?yàn)樽兓芷谳^短，要求算法對(duì)環(huán)境變化及時(shí)做出響應(yīng)，從而增加了算法的難度；隨著周期增加，算法有更長的時(shí)間適應(yīng)環(huán)境變化，因此求得的解優(yōu)于周期較短的情形。在同一變化周期，隨著變化強(qiáng)度增大，MSDPGA的優(yōu)勢(shì)越來越明顯，采用記憶機(jī)制對(duì)算法跟蹤最優(yōu)解的變化具有明顯的作用。

4 結(jié)語

本文提出了一種基于精英遷移的主從式雙種群動(dòng)態(tài)遺傳算法。實(shí)驗(yàn)結(jié)果表明，該算法在各種環(huán)境變化周期和變化強(qiáng)度下，具有較強(qiáng)的魯棒性，能較快適應(yīng)環(huán)境的變化，在多數(shù)情況下優(yōu)于其他三種算法的性能。

[1] Cobb H G.An investigation into the use of hypermutation as an adaptive operator in genetic algorithms having continuous, time-dependent nonstationary environments[R].Washington,USA, 1990: 1-8.

[2] Grefenstette J . Genetic algorithms for changing environments[C]//Proceedings of Grefenstette 92 Genetic Algorithms,1992:137-144.

[3] Tinós Renato，Yang Shengxiang. A self-organizing random immigrants genetic algorithm for dynamic optimization problems[J].Genetic Programming and Evolvable Machines,2007,8(3):255-286.

[4] Branke Jurgen.Evolutionary optimization in dynamic environments[M].Dordrecht: Kluwer Academic Publishers,2001：58-65.

[5] 王洪峰，汪定偉.一種動(dòng)態(tài)環(huán)境下帶有記憶的三島粒子群算法[J].系統(tǒng)工程學(xué)報(bào),2008,23(3): 252-256.

[6] 武燕，王宇平，劉小雄.求解動(dòng)態(tài)優(yōu)化問題的多群體UMDA[J].控制與決策,2008,23(12):1401-1406.

[7] Yang Shengxiang，Renato Tin.A hybrid immigrants scheme for genetic algorithms in dynamic environments[J].International Journal of Automation and Computing,2007,4(7):243-254.

[8] 周明，孫樹棟.遺傳算法原理及應(yīng)用 [M].長沙：國防工業(yè)出版社,1999：90-104.

(責(zé)任編輯：張凱兵)

Master-SlaveDual-PopulationDynamicGeneticAlgorithmBasedonEliteMigration

Shen Dingcai

(SchoolofComputerandInformationScience,HubeiEngineeringUniversity,Xiaogan,Hubei432000,China)

A Master-slave dual-population dynamic genetic algorithm based on the elite migration is proposed for the dynamic optimization problems of 0-1 encoding. Memory strategy is adopted in the master population, in which the worst individual in the master population is replaced by the best individual found by the slave-population and the elite participates into the evolution of the memory individual. Simulation results on a set of dynamic benchmark functions verifies that the proposed algorithm is capable of tracking the dynamic environment in various change cycle and intensity.

elite migration; genetic algorithm; dynamic optimization

TP18

A

2095-4824(2013)06-0043-05

2013-09-18

申鼎才(1975- )，男，江西南康人，湖北工程學(xué)院計(jì)算機(jī)與信息科學(xué)學(xué)院講師，博士。