一種基于混沌領域搜索的自適應遺傳算法
2009-01-01 00:00:00魏明蔡延光
計算機應用研究 2009年2期
（廣東工業大學 自動化學院， 廣州 510090）
摘 要：提出一種基于混沌領域搜索的自適應混沌遺傳算法，該方法在遺傳進化的過程根據種群相對多樣性對每代個體引入混沌領域方法搜索有效基因，并有效地結合遺傳算法善于全局優化和混沌局部搜索能力強等特點。計算結果表明，該算法可以顯著提高計算效率，具有較大的實用價值。
關鍵詞：遺傳算法；混沌優化；旅行商問題
中圖分類號：TP301.6； U116.2 文獻標志碼：A
文章編號：10013695(2009)02046402
Chaos neighborhoodbased selfadaptive genetic algorithm
WEI Ming，CAI Yanguang
(Faculty of Automation， Guangdong University of Technology， Guangzhou 510090， China)
Abstract:This paper proposed a chaos neighborhoodbased selfadaptive genetic algorithm(CNSAGA) to combine the chaos optimization with standard genetic algorithm effectively together. Differing from other conventional chaos genetic hybrid algorithms， the algorithm proposed a chaos neighborhood operator was introduced in the evolution process to find best gene according to the measure of species diversity. The research shows that CNSAGA can achieve satisfactory optimization results.
Key words:genetic algorithm(GA)；chaotic optimization；TSP
遺傳算法[1，2]（GA）是由美國Michigan大學的Holland于1975年提出的，是一種模擬自然界中的生命進化和群體遺傳過程，以一定概率進行自然選擇、交叉、變異等，從而在給定問題空間進行搜索解空間，以獲得問題的最優解的全局優化算法，具有簡單通用、魯棒性強、適于并行處理、易于與其他方法相結合等特點。目前遺傳算法廣泛應用于許多工程領域，如函數優化、模式識別、圖像處理等，并取得了大量研究成果。其在顯示巨大優越性的同時也暴露出早熟問題，種群進化過程關鍵基因缺乏或丟失，以及遺傳操作算子或控制參數設計不當導致缺乏產生最優個體的強大能力。針對標準遺傳算法的缺陷，出現了各種各樣的改進方法[3~10]，尤其是利用混沌理論改進遺傳算法的性能值得關注。
混沌[11~13]是自然界廣泛存在的一種非線性現象，具有隨機性、遍歷性和對初始條件的極度敏感性等特點，在一定范圍內能夠按其自身的規律不重復地遍歷所有狀態。在搜索空間小時混沌優化方法效果顯著，但搜索空間大時幾乎無能為力[13]。因此，本文提出了一種新型的基于混沌領域搜索的自適應混沌遺傳算法（chaos neighborhood based selfadaptive genetic algorithm，CNSAGA），并用于求解標準14點TSP。計算結果表明，該算法不僅能增強全局最優解的搜索性能，而且還能加快遺傳算法的收斂速度，經過較少的進化代數即能找到最優解。
1 CNSAGA的算法設計
種群多樣性急劇減少導致遺傳算法的交叉算子和選擇算子不能產生更有生命力的新個體，僅依靠變異操作恢復丟失的有效基因可能性很小，從而遺傳算法適合于找到最優解所在的領域，但如何尋找全局最優卻非其所長。為此，本文首次提出了搜索空間自適應調整的混沌領域搜索算法，通過判斷種群早熟機制決定每代種群個體是否進行混沌鄰域搜索，搜索其有效基因，從而快速引導種群跳出局部最優，有效利用遺傳算法的全局搜索和混沌領域局部搜索能力，使兩種算法的優勢得到互補。
1.1 混沌鄰域搜索法
本文采用Logistic映射產生混沌序列：
tk+1=μ#8226;tk#8226;(1.0-tk)（1）
其中：0≤tk≤1，當μ=4時，系統完全處于混沌狀態，其混沌空間為[0 ，1]。
混沌變量映射到染色體基因座空間：
S(k)=[N.tk]（2）
其中：[x]表示對x取整；N為染色體長度。
設染色體個體XT =x1T x2T…xN-1T xN T為當前進行混沌搜索有效基因的個體，對應的適應度值為fT=f(XT)。混沌鄰域搜索的基本步驟如下：
a）初始化，對式（1）賦予一個不同的初值，可以得到一個軌跡不同的混沌變量tk（k=1，2，…，s）。其中s為混沌迭代的最大次數。
b）按式（2）把tk和tk+1混沌變量映射到染色體基因座空間S(k)和S(k+1)，對應染色體基因片段Xs(k)T Xs(k)+1T …Xs(k+1)-1T Xs(k+1)T構建一個領域搜索空間。
c）利用混沌遍歷性，搜索基因片段有效基因，生成新的個體X* =x1T x2T …xs(k)* xs(k)+1* …xs(k+1)-1* xs(k+1)*…xN-1T xNT ，并計算相應的適應值f(X*)。如果f(X*)>fT，則XT =X*，fT =f(X*)，k=k+1，如果達到給定的迭代次數，則結束，否則轉b）。
1.2 CNSAGA的算法實現
本文將遺傳算法與混沌領域搜索有效結合起來，形成一種新型的自適應混沌遺傳算法，該算法的基本步驟如下：
a）取t=0，設種群規模N和合適的正常數α。隨機構造初始種群X(0)=( X1(0)，X2(0)，…XN(0))∈SN。
b）通過變異、交叉和選擇XT(t)={Tmi(Tci(Tsi(X(t))))，i=1，…，N}。其中：Tmi、Tci、Tsi分別為變異、交叉、選擇算子。
c）計算種群的多樣度λ(XT(t))和λ(X(t))及種群的總體適應度Fs(XT(t))和Fs(X(t))。其中：多樣度λ(X(t))字義為向量Y=∑Xi(t)取值不為0和N的分量個數； f：S→R+是定義在S上的適應度函數；Fs(X)=max f(Xi))為最大總體種群適應度。
d）計算相對種群多樣性Ct=min{1，[λ(XT(t))/λ(X(t))]a/t#8226;[Fs(XT(t))/Fs(X(t))]t}，它用于決定是否對XT(t)調用混沌鄰域搜索算法。生成[0，1]中均勻分布隨機數ρ，若ρ≤Ct ，X(t+1)=X*(t)。其中X*(t) 是對最優個體XT(t)運用混沌鄰域搜索獲得的最優解。
e）若結束條件不滿足，則令t=t+1，轉b）。
2 仿真實驗
為了驗證算法的有效性，用SACGA求解了http://www.crpc.rice.edu/softlib/tsplib中公布14點標準TSP問題(表1)，并與標準遺傳算法（standard genetic algorithm，SGA）和文獻[12]的混沌遺傳算法（chaos genetic algorithm，CGA）作了比較。實驗運行50次，SACGA、SGA和CGA平均只需75、220和300代，均能夠找到目前已知最好的解30.878 5，其巡回路線為11091181371265431421。
從圖中可以看出， SACGA比SGA和CGA在收斂性能上有所提高，這說明SACGA通過計算種群多樣性判斷早熟程度，控制種群每代個體進行搜索空間自適應調整的混沌領域搜索的概率是可行的。一方面避免混沌變量過早嵌入GA搜索有效基因，此時GA能夠依靠自身操作維持種群多樣性，引入混沌搜索效果并不明顯，卻增加了計算復雜性；另一方面利用混沌遍歷性，生成覆蓋整個搜索區域許多領域搜索空間，避免搜索范圍較大時，存在搜索盲區，提高了搜索效率。
表1 14點TSP
node1234567891011121314
X16.4716.4720.0922.3925.2322.0020.4717.2016.3014.0516.5321.5219.4120.09
Y96.1094.4492.5493.3797.2496.0597.0296.2997.3898.1297.3895.5997.1394.55
3 結束語
本文結合遺傳算法全局搜索能力強及混沌善于小范圍的優點，提出了一種新的基于混沌鄰域搜索的自適應混沌遺傳算法。該算法根據種群相對多樣性概率分布空間分別對每代種群個體引入混沌領域搜索，有效地結合遺傳算法全局優化及混沌局部搜索能力特點，既提高了收斂速度，又解決了算法早熟問題。實驗仿真表明，該算法求解14點標準TSP可以顯著提高計算效率，具有較大的實用價值。
參考文獻：
［1］
陳國良. 遺傳算法及其應用[M]. 北京:人民郵電出版社，1996.
[2]PONS J C，YERRI D G，SURYA B Y.The development and evolution of an improved genetic algorithm based on migration and artificial selection[J].IEEE Trans on SMC，1994，24(1):7386.
[3]陳奉蘇.混沌學及其應用[M].北京:中國電力出版社，1998.
[4]陳炳瑞，楊成祥，馮夏庭，等.適應混沌遺傳混合算法及其參數敏感性分析[J].東北大學學報， 2006，27(6):690693.
[5]FENG X T，YANG C X.Coupling recognition of the structure and parameters of nonlinear constitutive material models using hybrid evolutionary algorithms[J].International Journal for Numerical Method in Engineering，2004，59:12271250.
[6]康波. 一種混沌遺傳算法及其在測試生成中的應用[J].系統工程與電子技術，2006，28(11):17431746.
[7]姚俊峰，梅熾，彭小奇.混沌遺傳算法(CGA)的應用研究及其優化效率評價[J].自動化學報，2002，28(6):935942.
[8]陸子強，郭國雄，蔣金山.基于鄰域搜索的混合遺傳算法及其在對稱TSP中的應用[J].計算機工程與應用，2005，17(6):7982.
[9] 陳曉方，桂衛華，吳敏，等.一種基于混沌遷移的偽并行遺傳算法及其應用[J].控制理論與應用，2004，21(6):9971002.
[10]袁曉輝，袁艷斌，王乘，等.一種新型的自適應混沌遺傳算法[J].電子學報，2006，34(4):709712.
[11]LI B，JIANG W S.Chaos optimization method and its application[J].Control Theory and Applications，1997，14(4):613615.
[12]楊波，宋耀良.一種新的混沌遺傳算法及其在多播路由選擇中的應用[J].南京理工大學學報， 2004，28(1):3032.
[13] ZHANG T，WANG H W，WANG Z C.Mutative scale chaos optimization algorithm and its application[J].Control and Decision，1999，14(3):285287.
