曾志峰

(湖南人文科技學(xué)院通信與控制工程系,湖南婁底 417001)

基于細(xì)胞自動機(jī)演化算法求解無約束函數(shù)優(yōu)化問題

曾志峰

(湖南人文科技學(xué)院通信與控制工程系,湖南婁底 417001)

在最優(yōu)化領(lǐng)域目前廣泛應(yīng)用的智能優(yōu)化算法有遺傳算法、模擬退火算法、神經(jīng)網(wǎng)絡(luò)算法等。但這些算法的實(shí)現(xiàn)模式都還是基于串行模式。利用細(xì)胞自動機(jī)來解決優(yōu)化問題,也就意味著能夠建立極度并行的解決最優(yōu)化問題的程序。提出了一種基于細(xì)胞自動機(jī)的演化算法,以求解無約束函數(shù)優(yōu)化問題,并用實(shí)驗(yàn)分析了此算法的性能。

細(xì)胞自動機(jī);函數(shù)優(yōu)化;演化算法

細(xì)胞自動機(jī)是當(dāng)前計(jì)算機(jī)科學(xué)的一個(gè)研究熱點(diǎn)。細(xì)胞自動機(jī)本質(zhì)上是一個(gè)時(shí)間離散化、空間離散化的動力學(xué)系統(tǒng)。它所具有的極度并行性、基本單元的簡單性、細(xì)胞相互作用的局部性等特點(diǎn)引起眾多學(xué)科的學(xué)者們越來越多的關(guān)注。

在最優(yōu)化領(lǐng)域,不斷出現(xiàn)一些超大規(guī)模的非線性問題,由于這些問題的復(fù)雜性、強(qiáng)約束性、非線性、不確定性,使得這類問題難于解答,而且當(dāng)前這類問題一般使用的很多算法的架構(gòu)依然是建立在 Von Neumann結(jié)構(gòu)的計(jì)算機(jī)系統(tǒng)上,不太適合細(xì)胞架構(gòu)的機(jī)器。假如我們利用細(xì)胞自動機(jī)來解決優(yōu)化問題,也就意味著能夠建立極度并行的解決最優(yōu)化問題的程序。另外,在函數(shù)優(yōu)化方面,生活中許多問題用傳統(tǒng)的數(shù)學(xué)計(jì)算方法來求精確解是不可能的,實(shí)際應(yīng)用中只要求求出其“優(yōu)化解”即可。演化計(jì)算求解無約束函數(shù)優(yōu)化問題,實(shí)際上是對函數(shù)參數(shù) (自變量)不斷優(yōu)化的過程。

1 無約束最優(yōu)化問題

無約束最優(yōu)化問題的一般模型為:

其中 Rn為 n維歐式空間,f(x):Rn→R為連續(xù)可微函數(shù)[1]。

求解無約束最優(yōu)化問題的算法主要是迭代算法,常采用如下形式:

其中αk是通過某種線性搜索而獲得的步長,dk為某一下降方向,對αk和 dk的不同選擇就構(gòu)成了不同的迭代算法。廣泛采用的最優(yōu)化計(jì)算方法有 N ew ton型方法、最速下降方法、共軛梯度方法、信賴域方法以及內(nèi)點(diǎn)算法等等。N ew ton型方法和信賴域方法對中小型最優(yōu)化問題具有較好的收斂特征,但它在每步迭代時(shí)需要的存貯量和計(jì)算工作量較大,不適于求解大型最優(yōu)化問題;最速下降算法在每步迭代時(shí)需要的存貯量和計(jì)算工作量較小,可用于求解大型最優(yōu)化問題,但該算法的收斂速度慢且容易在最優(yōu)點(diǎn)附近產(chǎn)生拉鋸現(xiàn)象。

De Jong F2函數(shù)[2]是一個(gè)典型的無約束最優(yōu)化問題,由于該問題在早期下降速度最快的地方后期下降速度很慢,所以一般的算法并不容易找到最優(yōu)解,標(biāo)準(zhǔn)的精英演化算法對這個(gè)問題常常很慢收斂到最優(yōu)解。其函數(shù)表達(dá)式為:

其圖形如圖 1所示。該函數(shù)的最小值為 0,位于 (1,1)。

圖1 De Jong F2函數(shù)的圖象

2 基于細(xì)胞自動機(jī)演化算法

2.1 算法有關(guān)定義

一個(gè)演化細(xì)胞自動機(jī) (Evolutionary Cellular Automata)ECA=[3]

(1)U為狀態(tài)空間集合,UEi為第 i個(gè)細(xì)胞所取的狀態(tài),其中,U={x1,x2,…,xn}∈X,即 U在向量空間 X中取值

(2)E為細(xì)胞集合,Ei為編號為 i的細(xì)胞

(3)N為鄰居集合,Ni={Ej|Ej與 Ei的空間距離小于等于常數(shù) r}

(4)T為離散時(shí)間

(5)F為轉(zhuǎn)換函數(shù)集合 (也稱為轉(zhuǎn)換規(guī)則表),第 i細(xì)胞的轉(zhuǎn)換函數(shù) Fi滿足 Fi:Uni×T→U,其中,Fi為演化算子中的交叉和變異算子若要將細(xì)胞自動機(jī)用于優(yōu)化,顯然需要對它改造。

構(gòu)造 ECA滿足如下條件:

(1)令 E0是所有細(xì)胞元的鄰居

其中 r為常數(shù),g為最小化函數(shù),UEi為細(xì)胞 i的當(dāng)前狀態(tài),U′由 UNi狀態(tài)使用某一種規(guī)則 (算子)產(chǎn)生。如果算子選用得當(dāng),則該細(xì)胞自動機(jī)可用于優(yōu)化函數(shù) g,使 g以概率1收斂于全局極小值。

對于該算法,最主要的問題是 U’的生成,即 U’的生成規(guī)則,稱之為細(xì)胞元的協(xié)同演化規(guī)則?？梢赃x用的算子包括經(jīng)典算法中的算子如最速下降,也可以選用模擬退火算子,也可以選用遺傳算法中的雜交算子和變異算子,當(dāng)然,也可以選用它們的組合。

若選用模擬退火算子或變異算子,則規(guī)則 3中的第三點(diǎn)可以略去。

2.2 算法描述

對于細(xì)胞元的協(xié)同演化規(guī)則,可以使用雜交算子和變異算子及它們的組合。如在一維細(xì)胞自動機(jī)中,對于函數(shù)優(yōu)化問題,可以有:

(1)U′=t＊UE(I)+(1-t)＊UE(I+1) t為隨機(jī)數(shù)

t為隨機(jī)數(shù)

當(dāng)然,還可以列出其他各種各樣的協(xié)同演化規(guī)則。

在組合優(yōu)化中,同樣可以有很多種協(xié)同演化規(guī)則。如類似于 SGA的交叉算子,2-交叉法、k-交叉法、貪婪變異等。

實(shí)際上,在應(yīng)用的過程中,算法沒有必要一定收斂到全局最優(yōu),只需要求得滿意解就可以了。在很多情況下,收斂到全局最優(yōu)的代價(jià)是等同于枚舉的。所以,使用下面的算法就可以達(dá)到較好的優(yōu)化效果了。

也可以在其中加入隨機(jī)變異算子,此時(shí),算法為:

3 實(shí)驗(yàn)分析

簡單遺傳算法[4](SGA,simple GA)中采用的線性適應(yīng)度以及恒定交叉、變異概率,容易造成算法早熟或停滯,且運(yùn)行效率低。為此,國內(nèi)、外諸多學(xué)者對簡單遺傳算法進(jìn)行改進(jìn),如 Goldberg引入的線性拉伸方法 (LGA,linear GA)以及 Paul等提出的模擬退火思想,改進(jìn)了 SGA中的線性適應(yīng)度;針對恒定交叉、變異概率引起的不足,Srinvivas等提出自適應(yīng)交叉、變異概率,馬鈞水等采用大變異操作代替 SGA中恒定概率的變異操作[5]。

本文也用 SGA算法求解該函數(shù),算法采用輪盤賭選擇策略,均勻雜交,隨機(jī)變異,發(fā)現(xiàn)該算法有很多缺點(diǎn):

1)評價(jià)函數(shù)的選取需要相當(dāng)多的經(jīng)驗(yàn),若選取不當(dāng),有收斂到局部極大值的可能性大大增加。

2)精度相對于本算法比較差,一般為 10-5-10-6(本算法為 10-9-10-10)。

3)理論上是總可以收斂到全局最優(yōu)解的,實(shí)際上常常不可能,因?yàn)樗惴ǔ３Ｐ枰谟邢薏絻?nèi)終止。

在實(shí)驗(yàn)中,利用 SGA計(jì)算了 10次,種群大小 100,交叉概率選為 0.9,變異概率為 0.1,終止條件為計(jì)算 1000代,計(jì)算結(jié)果的精度為 10-5。

實(shí)驗(yàn)的結(jié)果如表1:

表1 SGA與本算法的比較

從以上實(shí)驗(yàn)數(shù)據(jù)中,可以看到本算法具有較好的性能。

4 結(jié)論

最優(yōu)化問題在實(shí)際工程中常見,各種最優(yōu)化方法應(yīng)運(yùn)而生,人們也提出了各種各樣的函數(shù)來檢測最優(yōu)化算法的性能。本文提到的算法具有較好的性能,但是,遺憾的是,所有的算法,無論你采用什么算子,如果你提升對某一類問題的性能,那么該算法針對另外的某一類問題性能必然下降。

[1]SARKAR P.A brief history of cellular automata[J].ACM Computing Surveys,2000,32(1):45-49.

[2]BERLECAMP E R,CONWAY J H,GUY R K.W inning ways[J].Houston:Academic Press,1985,2(1):22-29.

[3]BURKSA W.Essayson cellular automata[J].Paris:Universityof Illinois Press,1972:56-98.

[4]WOLFRAM S.Cellular automaton on supercomputing,high-speed computing[J].Scientific Applications and Algorithm Design,1988:33-93.

[5]WOLFRAM S.Statistical mechanics of cellular automata[J].Reviews ofModem Physics,1983:68-69.

(責(zé)任編校:光明)

Opt im ization Problems about Answering Unconstra ined Function Based on Cellular Automata Evolution

ZENG Zhi-feng

(Depar tment of Communication and Control Engineering,Hunan Institute of Humanities,Science and Technology,Loudi,417001,China)

In the field of optimization,intelligentoptimization algorithms arewidely used,including genetic algorithm,simulated annealing and neutral network and so on.But implementation patterns of these algorithms are based on serial mode.When the cellular automation is applied to solve the problem of opt imization,itmeans thatwe can establish a program which can solve those problemswith super concurrency.An evolutionary algorithm based on the cellular automaton is raised to ans wer the optimization problem of unconstrained function.We also use the experiment to analyze the function of this algorithm.

cellular automata;function optimization;evolutionary algorithm

O242.1

A

1673-0712(2010)02-0027-03

2010-02-20.

曾志峰 (1976- ),男,湖南雙峰人,湖南人文科技學(xué)院通信與控制工程系講師,研究方向:數(shù)據(jù)挖掘,計(jì)算機(jī)網(wǎng)絡(luò)。