1、略一種基于混沌搜索的文化算法及其應(yīng)用摘要:針對(duì)文化算法求解函數(shù)優(yōu)化問(wèn)題存在過(guò)早收斂、不穩(wěn)定等缺陷,基于文化算法框架、嵌入混沌搜索優(yōu)化,提出了一種混沌文化算法。該算法模型由基于混沌的群體空間和存儲(chǔ)知識(shí)的信念空間組成,利用標(biāo)準(zhǔn)知識(shí)和形勢(shì)知識(shí)分別引導(dǎo)混沌搜索和混沌擾動(dòng),有效克制了文化算法過(guò)早收斂、混沌搜索優(yōu)化對(duì)初值敏感、搜索效率低等缺陷。實(shí)例說(shuō)明,該方法具有較強(qiáng)的全局搜索才能,在搜索效率、精度和穩(wěn)定性上有顯著表現(xiàn),并能有效處理高維函數(shù)優(yōu)化問(wèn)題。關(guān)鍵詞:進(jìn)化計(jì)算;文化算法;混沌文化算法;混沌搜索;知識(shí)引導(dǎo)ulturalalgrithbasednhatisearhanditsappliatinhejia

2、n-jia,xufu-yuan,hesheng-xu,huanghe(shlfbusiness,universityfshanghaifrsienetehnlgy,shanghai200093,hina)abstrat:frpreaturenvergeneandinstabilityfulturalalgrithinslvingfuntinptiizatinprble,basednulturalalgrithandhassearhptiizatin,thispaperprpsedahasulturalalgrith(a).thealgrithdelnsistedfahas-basedppula

3、tinspaeandastredknledgebeliefspae,usingnrativeknledgeandsituatinalknledgefrhassearhandhasperturbatinrespetively,andeffetivelyavidedpreaturenvergenefulturalalgrithandveraehassearhptiizatinssensitivitytinitialvaluesandpreffiieny.testresultsshthatthisalgrithisstrnginglbalsearh,andhasgdperfraneinsearhin

4、geffiieny,preisinandstability,espeiallyinslvinghigh-diensinalptiizatinprble.keyrds:evlutinaryputatin;ulturalalgrith;hasulturalalgrith(a);hassearh;knledgeguide0引言從20世紀(jì)50年代仿生學(xué)的創(chuàng)立起,人們開(kāi)場(chǎng)模擬生物進(jìn)化的機(jī)理,提出了許多諸如遺傳規(guī)劃、免疫算法等解決優(yōu)化問(wèn)題的進(jìn)化計(jì)算方法。這些算法研究主要集中在生物自然選擇這一層面上。許多情況說(shuō)明,文化能使種群以一定的速度進(jìn)化和適應(yīng)環(huán)境,而這個(gè)速度是超越單純依靠基因遺傳生物進(jìn)化速度的1。在人

5、類(lèi)社會(huì)中,文化被看做存儲(chǔ)信息的載體,這些信息在社會(huì)群體之間和群體內(nèi)部廣泛地傳遞,并能被社會(huì)所有成員繼承,從而有效地指導(dǎo)成員的行為來(lái)解決問(wèn)題。受此啟示,reynlds1于1994年提出了文化算法這種全新的進(jìn)化算法。文化算法從微觀和宏觀兩個(gè)層次模擬進(jìn)化,不同層次間互相促進(jìn)且互相影響。該算法提供了一種顯性的機(jī)制來(lái)獲娶保存和整合問(wèn)題求解的知識(shí),從而進(jìn)步搜索效率。目前,文化算法已成為算法研究的熱點(diǎn),并已成功應(yīng)用到多個(gè)領(lǐng)域,在一些問(wèn)題上獲得了比傳統(tǒng)進(jìn)化算法更好的結(jié)果24。在函數(shù)優(yōu)化方面,文化算法求解效率高,但存在過(guò)早收斂、不穩(wěn)定等缺乏;混沌搜索優(yōu)化全局搜索才能強(qiáng),但對(duì)初值敏感、搜索效率低。因此,本文將混沌

6、搜索優(yōu)化引入到文化算法模型中,提出了用于解決優(yōu)化問(wèn)題的混沌文化算法(hasulturalalgrith,a)。該算法利用混沌搜索優(yōu)化的遍歷性、隨機(jī)性特性,增加算法全局搜索才能,防止算法過(guò)早收斂,同時(shí)利用文化算法的知識(shí)引導(dǎo)作用,進(jìn)步了算法的搜索效率和精度。1文化算法的原理文化算法框架是由群體空間(ppulatinspae)和信念空間(beliefspae)兩部分組成,兩者分別從微觀和宏觀兩個(gè)層面模擬進(jìn)化過(guò)程,如圖1所示。前者是問(wèn)題的解空間,后者用于知識(shí)經(jīng)歷的形成、存儲(chǔ)和傳播,兩者互相獨(dú)立又互相聯(lián)絡(luò),它們之間通過(guò)特定的協(xié)議進(jìn)展信息交流。首先,aept()函數(shù)將群體空間進(jìn)化過(guò)程中優(yōu)秀的個(gè)體經(jīng)歷傳遞到

7、信念空間;接著update()函數(shù)根據(jù)信念空間現(xiàn)有的經(jīng)歷和新經(jīng)歷更新群體經(jīng)歷或知識(shí);然后influene()函數(shù)利用群體經(jīng)歷或知識(shí)指導(dǎo)群體空間的進(jìn)化。另外,bjetive()函數(shù)是目的函數(shù),用來(lái)評(píng)價(jià)群體空間中個(gè)體的適應(yīng)值;generate()函數(shù)根據(jù)群體經(jīng)歷形成下一代個(gè)體;selet()函數(shù)根據(jù)規(guī)那么從新生成個(gè)體中選擇一部分個(gè)體作為下代個(gè)體的父輩。文化算法的根本偽代碼5如下:begint=0;initializeppulatinpp(t);initializebeliefspaeblf(t);repeatevaluateppulatinpp(t);update(blf(t),aept(pp(t

8、);variatin(pp(t),influene(blf(t);t=t+1;selet(pp(t)frpp(t-1);untilterinatinnditinahievedend2混沌文化算法的設(shè)計(jì)本文將混沌搜索優(yōu)化6嵌入到文化算法模型中,利用由hung等人7,8提出的區(qū)間形式(intervalsheata)來(lái)表達(dá)信念空間中的知識(shí),形成混沌文化算法。這樣做既利用了混沌搜索的全局搜索才能,又利用了迭代過(guò)程中形成的經(jīng)歷知識(shí),引導(dǎo)算法進(jìn)展有效的搜索,進(jìn)步了搜索效率。另外,算法采用混沌搜索優(yōu)化的并行構(gòu)造,能有效降低算法對(duì)初值的敏感性。不失一般性,非線性函數(shù)最優(yōu)化問(wèn)題可以表示為2.1混沌搜索優(yōu)化其中:

9、當(dāng)u=4時(shí),lgisti映射為混沌狀態(tài),區(qū)間(0,1)是映射的混沌不變集9?；煦缢阉鲀?yōu)化的根本思想就是用類(lèi)似載波的方法將混沌狀態(tài)引入到優(yōu)化變量中,并把混沌運(yùn)動(dòng)的遍歷范圍放大到優(yōu)化變量的取值范圍,然后利用混沌變量進(jìn)展搜索6。其根本步驟如下:lgisti映射(u=4)經(jīng)過(guò)一定次數(shù)的迭代后,在(0,1)上分布了大量的軌道點(diǎn)(混沌序列)。其概率密度函數(shù)(z)9為(z)=1z(1-z)(4)該式為切比雪夫分布,如圖2所示。從圖2可知,lgisti映射混沌序列的分布特點(diǎn)是中間比擬均勻、兩頭特別多、在端點(diǎn)到達(dá)無(wú)窮多9。利用lgisti映射這一分布特點(diǎn),結(jié)合文化算法優(yōu)勝區(qū)間(下文介紹),便能使群體空間中個(gè)體的

10、各個(gè)決策變量主要分布在對(duì)應(yīng)優(yōu)勝區(qū)間兩端附近,減少盲目搜索,加快搜索效率。2.2信念空間的構(gòu)造信念空間的構(gòu)造定義在文化算法框架中非常重要,其主要作用是提供一個(gè)明確的機(jī)制來(lái)獲娶存儲(chǔ)和傳遞知識(shí)經(jīng)歷。本文采用文化算法最根本的兩種知識(shí):形勢(shì)知識(shí)(situatinalknledge)和標(biāo)準(zhǔn)知識(shí)(nrativeknledge),即b=s,nn。在本文中,e直接取群體空間的規(guī)模ppsize。初始化時(shí),最優(yōu)個(gè)體集合取初始群體空間的所有個(gè)體。nn存儲(chǔ)了n組決策變量的變化區(qū)間,又稱優(yōu)勝區(qū)間,這些區(qū)間給出了最優(yōu)解最可能出現(xiàn)的范圍。由這個(gè)范圍來(lái)引導(dǎo)混沌迭代,將能更快找到最優(yōu)解。其數(shù)據(jù)構(gòu)造10如圖4所示,描繪為2.3信念空間的更新信念空間的形勢(shì)知識(shí)每代更新兩次,一次在混沌搜索之后,一次在混沌擾動(dòng)之后;標(biāo)準(zhǔn)知識(shí)每代更新一次。本文對(duì)于形勢(shì)知識(shí)更新的方法借鑒了錦標(biāo)賽法。詳細(xì)方法是:a)每次迭代后將種群空間中的所有個(gè)體集合和形勢(shì)知識(shí)所代表的最優(yōu)個(gè)體集合組成一個(gè)新的集合(本文算法新集合規(guī)模為2ppsize)。b)在新集合中隨機(jī)選擇出個(gè)競(jìng)爭(zhēng)者(一般=ppsiz