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

曾志峰

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

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

曾志峰

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

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

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

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

在最優(yōu)化領(lǐng)域,不斷出現(xiàn)一些超大規(guī)模的非線性問題,由于這些問題的復(fù)雜性、強約束性、非線性、不確定性,使得這類問題難于解答,而且當(dāng)前這類問題一般使用的很多算法的架構(gòu)依然是建立在 Von Neumann結(jié)構(gòu)的計算機系統(tǒng)上,不太適合細胞架構(gòu)的機器。假如我們利用細胞自動機來解決優(yōu)化問題,也就意味著能夠建立極度并行的解決最優(yōu)化問題的程序。另外,在函數(shù)優(yōu)化方面,生活中許多問題用傳統(tǒng)的數(shù)學(xué)計算方法來求精確解是不可能的,實際應(yīng)用中只要求求出其“優(yōu)化解”即可。演化計算求解無約束函數(shù)優(yōu)化問題,實際上是對函數(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)化計算方法有 N ew ton型方法、最速下降方法、共軛梯度方法、信賴域方法以及內(nèi)點算法等等。N ew ton型方法和信賴域方法對中小型最優(yōu)化問題具有較好的收斂特征,但它在每步迭代時需要的存貯量和計算工作量較大,不適于求解大型最優(yōu)化問題;最速下降算法在每步迭代時需要的存貯量和計算工作量較小,可用于求解大型最優(yōu)化問題,但該算法的收斂速度慢且容易在最優(yōu)點附近產(chǎn)生拉鋸現(xiàn)象。

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

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

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

2 基于細胞自動機演化算法

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

一個演化細胞自動機 (Evolutionary Cellular Automata)ECA=[3]

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

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

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

(4)T為離散時間

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

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

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

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

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

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

2.2 算法描述

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

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

t為隨機數(shù)

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

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

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

也可以在其中加入隨機變異算子,此時,算法為:

3 實驗分析

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

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

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

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

3)理論上是總可以收斂到全局最優(yōu)解的,實際上常常不可能,因為算法常常需要在有限步內(nèi)終止。

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

實驗的結(jié)果如表1:

表1 SGA與本算法的比較

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

4 結(jié)論

最優(yōu)化問題在實際工程中常見,各種最優(yōu)化方法應(yīng)運而生,人們也提出了各種各樣的函數(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ù)挖掘,計算機網(wǎng)絡(luò)。