曾志峰

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

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

曾志峰

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

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

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

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

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

1 無(wú)約束最優(yōu)化問(wèn)題

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

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

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

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

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

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

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

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

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

一個(gè)演化細(xì)胞自動(dòng)機(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為編號(hào)為 i的細(xì)胞

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

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

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

構(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ì)胞自動(dòng)機(jī)可用于優(yōu)化函數(shù) g,使 g以概率1收斂于全局極小值。

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

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

2.2 算法描述

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

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

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

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

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

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

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

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

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

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

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

2)精度相對(duì)于本算法比較差,一般為 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)化問(wèn)題在實(shí)際工程中常見(jiàn),各種最優(yōu)化方法應(yīng)運(yùn)而生,人們也提出了各種各樣的函數(shù)來(lái)檢測(cè)最優(yōu)化算法的性能。本文提到的算法具有較好的性能,但是,遺憾的是,所有的算法,無(wú)論你采用什么算子,如果你提升對(duì)某一類(lèi)問(wèn)題的性能,那么該算法針對(duì)另外的某一類(lèi)問(wèn)題性能必然下降。

[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ò)。