一種基于軌道均勻分布的混沌遺傳優(yōu)化算法

(西北工業(yè)大學 自動化學院， 西安710072)

摘 要：

提出一種軌道均勻分布的混沌遺傳優(yōu)化算法。根據(jù)logistic映射概率密度分布，得到軌道均勻分布的反三角函數(shù)logistic映射。結合遺傳算法，構造混合混沌算法。該算法在混沌優(yōu)化區(qū)間等概率搜索子空間，克服了logistic映射優(yōu)化算法對優(yōu)化區(qū)間邊緣進行大概率搜索的缺點，從而有效地提高搜索速度。仿真算例表明了該方法的可行性和反三角函數(shù)logistic映射的應用前景。

關鍵詞：混沌優(yōu)化； 邏輯映射； 遺傳算法； 均勻分布

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

文章編號：1001-3695(2009)04-1292-02

Chaos genetic optimization algorithm based on track uniform distribution

WANG De-cheng， LIN Hui

(College of Automatic， Northwestern Polytechnical University， Xi’an 710072， China)

Abstract:

This paper presented one new track uniform distribution chaos genetic optimization algorithm. According to logistic map distribution probability density， presented one anti-trigonometric function logistic map that had uniform distribution. Combined with genetic algorithm， constructed a hybrid chaos optimization algorithm. It could search whole optimization interval by equal probability. It overcomed disadvantage that logistic map chaos optimization search optimization interval edge by greater probability. So it could improve searching speed. Simulation examples show the feasibility of the algorithm， as well as the practicability of anti-trigonometric function logistic map.

Key words：chaos optimization； logistic map； genetic algorithm； uniform distribution

混沌是非線性系統(tǒng)獨特的一種運動形式，行為復雜且類似隨機，但存在固有的內(nèi)在規(guī)律性。規(guī)律性決定混沌序列可以由確定的函數(shù)關系式產(chǎn)生；軌道遍歷性，即混沌序列能夠不重復地歷經(jīng)一定范圍內(nèi)的所有狀態(tài)，是混沌應用于函數(shù)優(yōu)化問題的根本出發(fā)點?；煦鐑?yōu)化方法無須優(yōu)化問題具有連續(xù)性和可導性，在一定范圍內(nèi)遍歷求解，有利于找到全局最優(yōu)解，可以克服傳統(tǒng)優(yōu)化方法的缺點。目前混沌優(yōu)化算法的基本思路是將logistic映射產(chǎn)生的混沌序列映射到優(yōu)化變量區(qū)間上，按混沌變化的規(guī)律依次考查經(jīng)過的各點，接受較好的點作為最優(yōu)解，同時按照一定規(guī)則改變優(yōu)化變量的搜索區(qū)間[1~7]。Logistic映射產(chǎn)生的混沌序列分布不均勻，進行優(yōu)化時，搜索大多在變量空間的兩端進行。當全局最優(yōu)點不在設計變量空間兩端時，不利于找到全局最優(yōu)點。鑒于tent映射遍歷的均勻性，文獻[8]提出基于tent映射的混沌優(yōu)化算法。由于計算機字長有限，tent序列不能逼近[0，1]區(qū)間的任意值。文獻[9]提出的基于冪函數(shù)載波的混沌優(yōu)化方法，平滑logistic映射軌道概率密度函數(shù)，使軌道分布呈波浪狀。當全局最優(yōu)點對應的混沌變量在波谷時，不利于找到全局最優(yōu)點。

本文從logistic映射的概率密度函數(shù)出發(fā)，建立一種軌道均勻分布的反三角函數(shù)logistic映射。該映射結構簡單，且迭代過程有利于計算機產(chǎn)生。結合遺傳算法，建立了一種混沌遺傳優(yōu)化算法。通過仿真算例驗證了該方法的可行性和有效性。

1 反三角函數(shù)logistic映射

Logistic映射如下：

xn+1=μxn(1-xn)(1)

根據(jù)皮隆—弗洛本紐斯方程可得其軌道概率密度函數(shù)為

f(x)=1/πx(1-x) x∈[0，1](2)

引入x=φ(y)，假設y=φ-1(x)是單調(diào)函數(shù)，則序列{yn}的概率密度函數(shù)為

f(y)=1/πφ(y)[1-φ(y)][φ(y)](3)

若序列{yn}均勻分布，即f(y)=α(α為常數(shù))，式(3)等價于

1/πφ(y)[1-φ(y)][φ(y)]=α(4)

求解式(4)的微分方程，可得

φ(y)=cos(-απy/2+C)*cos(-απy/2+C)(5)

式(5)中選取合適的常數(shù)C，可得

y=2/απ arcsin(x)(6)

x的定義域為[0，1]，式(6)的定義域為[0，1]。在定義域上，式(6)所確定的函數(shù)是單調(diào)，與前面的假設吻合。取α=π/2，μ=4，則由式(7)所確定的反三角函數(shù)logistic映射軌道均勻分布。

xn+1=4xn(1-xn)yn+1=arcsin[4xn(1-xn)](7)

選取初值0.1，迭代50 000次，得到的logistic映射分布圖見圖1，曲線顯示落在[0，0.1]和[0.9，1]的概率較大。圖2是利用反三角logistic映射得到的分布圖，在區(qū)間[0，π/2]上分布比較均勻。

2 基于軌道均勻分布的混沌遺傳算法

2.1 遺傳算法與混沌優(yōu)化算法的結合

遺傳算法是一類借鑒生物界自然選擇和遺傳的隨機搜索算法，由美國Michigan大學的Holland教授于1975年首先提出的。標準遺傳算法的主要操作過程：a)初始化參數(shù)，包括編碼方式、適應度函數(shù)、種群規(guī)模、交叉概率、變異概率等；b)隨機產(chǎn)生初始種群；c)對種群的個體進行選擇、交叉、變異遺傳操作，產(chǎn)生新的種群；d)重復c)的操作，直到滿足終止條件。遺傳操作使用由目標函數(shù)變換來的適應度函數(shù)值，確定進一步的搜索方向和搜索范圍，克服了傳統(tǒng)優(yōu)化算法借助于目標函數(shù)的導數(shù)確定搜索方向的缺點。



雖然遺傳算法的馬爾可夫鏈分析表明算法具有遍歷性，保證從任何初態(tài)均能夠向最優(yōu)值進化，即遺傳算法本身能保證種群的不斷優(yōu)化。初始種群的產(chǎn)生是隨機的，產(chǎn)生的初始種群中有些個體遠離最優(yōu)解，進化過程非常緩慢；種群中個體之間比較近，群體的多樣性不夠豐富，容易早熟收斂?；煦缧蛄芯哂斜闅v性，利用混沌序列產(chǎn)生初始種群，減少可能出現(xiàn)的數(shù)據(jù)冗余，有助于加快遺傳算法的收斂速度。

種群的個體經(jīng)過交叉、變異操作后，不能保證個體性能比原來更好，因此遺傳算法雖然具有全局優(yōu)化搜索的優(yōu)點，但是局部搜索能力差，使得在接近最優(yōu)解時進化過程變得緩慢。將混沌序列嵌入到遺傳操作中，對部分最差個體附加混沌擾動進行搜索，引導種群進化，解決了遺傳算法在接近全局最優(yōu)解時速度明顯減慢的問題。

2.2 混沌遺傳優(yōu)化算法

設一類優(yōu)化問題為

max f(xi); i=1，2，…，ns t . ai≤xi≤bi(8)

混沌遺傳優(yōu)化算法的基本過程如下：

a)算法初始化，設置選擇算子、交叉算子、變異算子，種群規(guī)模，變量取值范圍，迭代終止條件。

b)給定n個初值：x(0)1，0，x(0)2，0，…，x(0)n，0利用式(7)確定的反三角函數(shù)logistic映射生成混沌變量 x(0)i，j(i=1，2，…，n;j=1，2，…，M)，并按式(9)將混沌變量映射到優(yōu)化變量可行域上，得到初始種群y(0)i，j。

y(0)i，j=ai+x(0)i，j×2/π×(bi-ai)(9)

c)采用精英保留原則，對當前種群中部分適應度較差的90%個體進行選擇、交叉和變異遺傳操作。

d)計算新的適應度，求出個體最大適應度f(X)max和平均適應度f(X)，若式(10)成立，則認為尋優(yōu)過程結束，輸出最優(yōu)值；否則轉(zhuǎn)e)。

f(X)max-f(X)＜α(10)

e)對當前種群中部分適應度較差的90%個體對應的優(yōu)化變量按照式(11)施加混沌擾動，在局部搜索最優(yōu)值。其中:δ*為當前最優(yōu)解映射到[0，π/2]的混沌變量;δk為迭代K次的混沌變量;δk為施加的混沌擾動。隨著進化代數(shù)的增加，α逐漸變小，保證迭代逐漸向最優(yōu)解靠近

δk=(1-α)δ*+αδk(11)

f)計算新的適應度，求出個體最大適應度和平均適應度，若式(10)成立，則認為尋優(yōu)過程結束，輸出最優(yōu)值。

g)若達到最大遺傳代數(shù)，則終止運算輸出結果；否則轉(zhuǎn)向c)。

3 算例仿真

為了驗證本文算法的有效性，用它求解兩個常用測試算法性能的典型函數(shù)的極值。兩個目標函數(shù)表達式如下：

F1=100(x21-x2)2+(1-x1)2-2.048≤xi≤2.048(12)

F2=[1+(x1+x2+1)2(19-14x1+3x21-14x2+6x1x2+3x22)][30+(2x1-3x2)2(18-32x1+12x21+48x2-36x1x2+37x22)]-2≤xi≤2(13)

F1和F2兩個函數(shù)具有理論最小值F1(1，1)=0，F(xiàn)2(0，-1)=3。

本文采用混沌優(yōu)化算法的參數(shù)設置如下：編碼方式為實數(shù)編碼，選擇算子為輪盤賭算子，交叉算子為算數(shù)算子，變異算子為非一致性變異算子，種群規(guī)模為200，最大遺傳代數(shù)為500，交叉概率為0.9，變異概率為0.01。利用基于反三角logistic映射和基于logistic映射的混沌遺傳優(yōu)化算法對F1和F2兩個函數(shù)進行50次尋優(yōu)，尋優(yōu)結果如表1所示。



對比表1，雖然兩種不同的映射得到的最優(yōu)值相似，但是基于反三角logistic映射的混沌遺傳優(yōu)化算法平均遺傳代數(shù)更小，尋優(yōu)效率更高。說明基于反三角函數(shù)logistic映射的混沌遺傳優(yōu)化算法比基于logistic映射的混沌遺傳優(yōu)化算法具有更快的收斂速度。這是因為反三角logistic映射進行混沌尋優(yōu)時，對優(yōu)化區(qū)間進行等概率搜索，區(qū)別于logistic映射對優(yōu)化區(qū)間邊緣進行大概率搜索。

4 結束語

反三角函數(shù)logistic映射在[0，π/2]均勻分布，對優(yōu)化變量區(qū)間內(nèi)的變量進行等概率搜索，比基于logistic映射尋優(yōu)方法更加有效搜索變量區(qū)間。本文將反三角函數(shù)logistic映射和遺傳算法相結合，形成了有效的混沌遺傳算法，實現(xiàn)了快速尋優(yōu)，其效率高于基于logistic映射的混沌尋優(yōu)。

參考文獻：

[1]李兵，蔣慰孫.混沌優(yōu)化方法及其應用[J].控制理論與應用，1997，14(4):613-615.

[2]張彤，王宏偉，王子才.變尺度混沌優(yōu)化方法及其應用[J].控制與決策，1999，14(3):285-288.

[3]張志新，張明廉.基于并行混沌和單純形法的混合全局優(yōu)化算法[J].系統(tǒng)仿真學報，2004，16(1):35-37.

[4]張國勝，方宗德，李愛民.基于混沌技術的連續(xù)禁忌搜索算法研究[J].計算機應用研究，2008，25(2):411-413.

[5]YANG Di-xiong， LI Gang， CHENG Geng-dong. On the efficiency of chaos optimization algorithms for global optimization[J]. Chaos， Solitons Fractals， 2007， 34(4):1366-1375.

[6]TAVAZOEI M S， HAERI M. Comparison of different one-dimensional maps as chaotic search pattern in chaos optimization algorithms[J]. Applied Mathematics and Computation，2007，187(2):1076-1085.

[7]姚俊峰，梅熾，彭小奇，等.混沌遺傳算法及其應用[J].系統(tǒng)工程，2001，19(1):70-74.

[8]江善和，王其申，江巨浪.一種新型skew tent映射的混沌混合優(yōu)化算法[J].控制理論與應用，2007，24(2):269-273.

[9]唐巍.基于冪函數(shù)載波的混沌優(yōu)化方法及其應用[J].控制與決策，2005，20(9):1043-1046.