基于精英遷移的主從式雙種群動態遺傳算法

申鼎才

(湖北工程學院 計算機與信息科學學院，湖北 孝感 432000)

基于精英遷移的主從式雙種群動態遺傳算法

申鼎才

(湖北工程學院 計算機與信息科學學院，湖北 孝感 432000)

針對0-1編碼的動態優化問題，提出了一種基于精英遷移的主從式雙種群動態遺傳算法。主種群采用記憶機制，把從種群獲得的最優個體替換主種群中較差的個體，同時參與到與記憶個體的演化操作。通過一組動態優化函數進行實驗，仿真結果表明，本文提出的算法在各變化周期和變化強度下均能很好的跟蹤環境的動態變化。

精英遷移；遺傳算法；動態優化

在現實生活中，很多優化問題是動態的，即目標函數、約束條件和環境參數會隨著時間的變化而改變。與靜態優化問題相比，由于動態優化問題增加了問題求解的不確定性，因而在一定程度上增加了動態優化問題的求解難度。

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

1 相關研究工作

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

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

2 算法實現

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

表1 算法基本實現步驟

3 數值實驗

3.1測試函數

本節實驗中，將通過一組在動態優化中廣泛采用的測試函數來驗證本文算法的有效性。接下來將首先介紹本文采用的一組靜態測試函數，然后介紹如何針對這類采用0-1編碼方式的靜態測試函數生成動態測試函數。

3.1.1 OneMax函數

OneMax函數沒有局部最優解，該函數的目標為最大化編碼串中1的個數，一個編碼長度為l的OneMax函數可以描述如下：

(1)

3.1.2 RoyalRoad函數

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

(2)

圖1 RoyalRoad函數

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

3.1.3 欺騙函數

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

表2 四階欺騙函數

3.2動態函數的生成

(3)

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

(4)

其中，k=?t/τ」為環境變化周期索引，符號?」為下取整運算。

XOR生成動態環境時，動態環境的變化強度可以通過τ和ρ來表征，τ越小，則環境變化頻率越大，對算法及時跟蹤環境變化的能力要求越高，反之，則算法有更多的時間來對變化的環境作出響應；ρ值越小，則環境變化強度越趨于緩和，反之環境變化則越劇烈。

3.3實驗結果及性能評估

3.3.1 參數設置

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

3.3.2 結果與分析

由于實驗是要驗證不同變化周期和變化強度下算法對最優解的跟蹤能力，因此本文采用每個算法的最大演化代數為30個環境變化周期，即對不同環境變化周期，算法最大運行代數是不同的。各算法在每一種變化強度下對應每一種變化周期各自獨立運行30次，每次運行采用不同的隨機種子。

表3-5給出不同算法在置信水平為0.05，自由度為58，各算法在不同變化周期和變化強度下的t檢驗結果，表中數據表示各測試函數在各種環境變化強度和變化周期下，MSDPGA算法和其他三種算法在獲取累計平均最優值性能方面的比較，其中，符號+、-、～分別表示MSDPGA性能優于、劣于和不劣于其他算法。

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

表3 OneMax函數t檢驗結果

表4 RoyalRoad函數t檢驗結果

表5 四階欺騙函數t檢驗結果

從表4統計結果可以看出，對于RoyalRoad函數，在變化強度較小(ρ= 0.1)時，SORIGA性能最優，求得的最優解要優于其他算法，SGA性能最差。由于RoyalRoad函數本身的特點，此時MSDPGA采用的記憶機制對尋優沒有明顯的幫助。相反，隨機遷入的新個體反而有助于算法找到最優解。隨著變化強度的增大，MSDPGA采用的記憶機制效果逐漸顯現出來，尋得的最優值要略優于SORIGA和RIGA。

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

綜上知，本文提出的算法在沒有增加過多的時間復雜度的情況下，通過在主、從種群中引入不同的演化策略，結合主種群采用記憶機制，使得算法在各變化周期和變化強度下均取得了較好的效果。同時，對于相同的測試函數，算法在變化周期較短時性能要劣于變化周期較長的情形，這是因為變化周期較短，要求算法對環境變化及時做出響應，從而增加了算法的難度；隨著周期增加，算法有更長的時間適應環境變化，因此求得的解優于周期較短的情形。在同一變化周期，隨著變化強度增大，MSDPGA的優勢越來越明顯，采用記憶機制對算法跟蹤最優解的變化具有明顯的作用。

4 結語

本文提出了一種基于精英遷移的主從式雙種群動態遺傳算法。實驗結果表明，該算法在各種環境變化周期和變化強度下，具有較強的魯棒性，能較快適應環境的變化，在多數情況下優于其他三種算法的性能。

[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] 王洪峰，汪定偉.一種動態環境下帶有記憶的三島粒子群算法[J].系統工程學報,2008,23(3): 252-256.

[6] 武燕，王宇平，劉小雄.求解動態優化問題的多群體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] 周明，孫樹棟.遺傳算法原理及應用 [M].長沙：國防工業出版社,1999：90-104.

(責任編輯：張凱兵)

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- )，男，江西南康人，湖北工程學院計算機與信息科學學院講師，博士。