基于建筑塊遷移策略的并行遺傳算法

摘要:通過分析模式定理及建筑塊理論，提出一種基于建筑塊遷移策略并行遺傳算法。算法根據(jù)種群的收斂情況，從其他種群中獲取非重疊的建筑塊，采用模擬退火思想防止優(yōu)良模式的濃度過快地增大引起早熟。理論分析和對多峰函數(shù)的仿真結果均表明，該算法減少了無效遷移次數(shù)，降低了通信開銷，而且發(fā)生成熟前收斂的概率明顯下降，保證了遺傳算法的全局收斂性。

關鍵詞:并行遺傳算法; 模式定理; 建筑塊; 模擬退火機制; 遷移策略

中圖分類號:TP301.6文獻標志碼:A

文章編號:1001－3695(2008)02－0405－03

GA作為一種基于生物界自然選擇和遺傳原理的高效搜索技術，已成功地應用于工程設計#65380;工商管理#65380;科學實驗等領域的復雜優(yōu)化問題的求解。隨著問題規(guī)模和復雜程度的不斷提高，SGA的搜索過程將會成倍延長。因此，很多專家一直致力于提高GA的搜索速度。其中一個重要的研究方向是GA的并行化執(zhí)行，即并行GA(PGA)[1]。

多群體PGA[2]是一種很自然的并行計算模式，其主要影響是子群體的數(shù)量#65380;規(guī)模和個體遷移策略。粗粒度PGA可視為多群體PGA的實現(xiàn)，它將群體劃分為多個子群體(又稱區(qū)域)，每個區(qū)域獨自運行一個GA。子群體進化過程中以某種方式交換個體，稱為個體遷移，并由一組參數(shù)控制將一個子群體中的遺傳信息復制出一個副本，再傳輸給另一個子群體。關于多群體PGA的遷移策略，一般需要考慮群體的拓撲結構#65380;遷移方式和數(shù)量#65380;遷移頻率或進化代的間隔#65380;接受的子群體的替代方式。近些年，許多學者在這方面作了大量研究并取得了可喜的進展。然而，如何突破通信瓶頸#65380;充分發(fā)揮硬件資源#65380;提高算法性能以及如何使并行遺傳算法具有更好的可擴展性等問題依然困擾著并行遺傳算法的進一步發(fā)展[3]。

本文在分析了多群體并行遺傳算法的主要因素及前人工作的基礎上，提出了以建筑模塊為理論依據(jù)的遷移策略，以及與Boltzmann生存機制相結合的并行遺傳算法。該算法降低了通信代價，提高了多群體PGA 的搜索效率。

1相關理論

1.1建筑模塊理論[4]

定義1模式是指字符串中具有類似特征的子集。

定義2m(H，t)表示在第t次迭代中，群體A中有n個個體。其中m個個體屬于模式H。遺傳算法在經(jīng)過復制#65380;交叉#65380;變異后，模式H在下一代群體中所擁有的個體數(shù)目為

m(H，t+1)=m(H，t)[f(H)/f]×[1-Pcδ(H)/(L-1)-O(H)Pm]。

建筑模塊理論說明只有字長O(H)短#65380;階次δ(H)低#65380;模式平均適應度f(H)高于群體平均適應度f的優(yōu)良模式才能存活。正是利用這些優(yōu)良模式的堆疊才能逐步得到最優(yōu)值。

1.2模擬退火算法[5]

模擬退火算法起源于統(tǒng)計物理學中對固體退火過程的模擬。它采用Boltzmann接收準則接收新解， 用一個稱為冷卻系數(shù)的參數(shù)控制算法進程，使算法在多項式時間中給出一個近似最優(yōu)解。溫度T控制著求解過程向極值的優(yōu)化方向進行，同時它又以概率exp(-Δf/Tk)來接收劣質解，因此算法可以跳出局部極值點。只要初始溫度足夠高，退火過程足夠慢，算法就能收斂到全局最優(yōu)解。

2基于建筑塊遷移策略的并行遺傳算法

基于建筑塊遷移策略的并行遺傳算法(BBPGA)運用種群收斂的異步遷移機制提取建筑塊，并結合Boltzmann生存機制，保持有用的多樣性，防止早熟的發(fā)生。它在確保算法有效性的前提下降低了通信代價，提高了算法的整體性能。

2.1建筑塊算子

為保證搜索的全局性搜索過程，至少包含一個能完全覆蓋整個樣本空間的位置等價非重疊建筑塊集[6]。

3模式收斂性分析

3.1馬爾柯夫鏈模型

引理1有限齊次馬爾柯夫鏈從任意非常返狀態(tài)出發(fā)以概率1必定要到達常返狀態(tài)[7]。

定理1基于建筑塊遷移策略的PGA運行過程是一個時間齊次的有限馬爾柯夫鏈。

6結束語

本文分析了模式理論及由模式理論推導的建筑塊理論，給出了建筑塊算子定義。通過建筑塊提取傳播和Metropolis接受準則，將建筑塊遷移策略引入到多群體并行遺傳算法中。算法減少了無效遷移次數(shù)，降低了通信開銷，提高了算法搜索效率，而且發(fā)生成熟前收斂的概率明顯下降，保證了遺傳算法的全局收斂性。

參考文獻:

[1]GOLDBERG D E. Genetic algorithms in search， optimization and machine learning[M]. New York:Addison－Wesley， 1989.

[2]李敏強，寇紀淞，林丹，等.遺傳算法的基本理論與應用[M].北京:科學出版社，2002:253－261.

[3]CANTU－PAZ E. A survey of parallel genetic algorithms[J]. Calculateurs Paralleles， 1998，10(2):141－171.

[4]王耀南.計算智能信息處理技術及其應用[M].長沙:湖南大學出版社，1999:192－196.

[5]吳浩揚，常炳國，朱長純，等.基于模擬退火機制的多種群并行遺傳算法[J].軟件學報，2000，11(3):416－420.

[6]莫鴻強，羅飛，毛宗源.遺傳算法的全局快速尋優(yōu)[J].控制理論與應用，2002，19(5):809－811.

[7]王宏剛，曾建潮，徐玉斌.優(yōu)良模式自學習遺傳算法[J].自動化學報，1999，25(3):375－379.

[8]管宇，徐寶文.基于模式遷移策略的并行遺傳算法[J].計算機學報，2003，26(3):294－301.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”