一種改進(jìn)文化算法的研究

王雪潔+楊磊

摘要：文化算法是一雙重進(jìn)化算法，它基于知識(shí)經(jīng)驗(yàn)的積累，具有較強(qiáng)的全局搜索能力。首先，本文將免疫優(yōu)勢(shì)克隆算法嵌入文化算法的種群空間，增強(qiáng)種群空間的進(jìn)化速度，從而使提高算法的搜索速度；其次，本文還設(shè)計(jì)了新的隨種群進(jìn)化代數(shù)更新的動(dòng)態(tài)接受函數(shù)，以促進(jìn)算法中信念空間知識(shí)更新，更好地利用先驗(yàn)知識(shí)指導(dǎo)種群進(jìn)化，進(jìn)一步提高算法的搜索能力。

關(guān)鍵詞：種群空間；接受函數(shù)；文化算法；免疫優(yōu)勢(shì)克隆算法

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）15-0204-03

1 概述

自上世紀(jì)八十年代以來，各種優(yōu)化算法的研究為工業(yè)生產(chǎn)等方面的復(fù)雜問題提供了新的解決途徑。文化算法是一種基于種群進(jìn)化模型，其思想來源于存在于人類社會(huì)中的文化，從古至今文化承載著人類發(fā)展的經(jīng)驗(yàn)和知識(shí)一代代傳承。而文化算法正是在種群進(jìn)化的過程中采用一定的顯性機(jī)制獲取群體進(jìn)化中得到的知識(shí)和經(jīng)驗(yàn)，并將這些知識(shí)和經(jīng)驗(yàn)進(jìn)行整合和保存，用于下一代種群的進(jìn)化。國(guó)內(nèi)外已有的科學(xué)研究表明該算法具有很好的全局搜索和局部能力，對(duì)于實(shí)際工業(yè)生產(chǎn)中的各種尋優(yōu)問題很有效，是一個(gè)值得研究的問題。

目前文化算法已在故障診斷方面有了一定的研究和應(yīng)用，隨著現(xiàn)代工業(yè)的不斷發(fā)展，工業(yè)生產(chǎn)中的故障診斷成為了焦點(diǎn)問題。本文根據(jù)文化算法的特性，對(duì)文化算法進(jìn)行改進(jìn)，并對(duì)改進(jìn)后的文化算進(jìn)行函數(shù)尋優(yōu)測(cè)試。

2文化算法

1994年，Reynolds提出了這種具有雙重進(jìn)化過程的文化算法[1]（Cultural Algorithm， CA），該算法包含兩個(gè)空間——種群空間和信念空間，這兩個(gè)空間和接受函數(shù)及影響函數(shù)共同作用構(gòu)成了文化算法的框架結(jié)構(gòu)，如圖1所示。

從圖1中可以看出文化算法的種群空間主要進(jìn)行群體的進(jìn)化并有相應(yīng)的種群評(píng)價(jià)機(jī)制，信念空間從種群空間中獲取樣本庫，經(jīng)過知識(shí)自更新得到進(jìn)化知識(shí)庫，進(jìn)化知識(shí)庫又通過影響函數(shù)去指導(dǎo)種群空間中種群的進(jìn)化選擇。由此可以看出這兩個(gè)空間即可相互獨(dú)立運(yùn)行，同時(shí)又可通過一定的通信方式互相影響。這兩個(gè)空間既有自適應(yīng)性又有相互促進(jìn)性。

所以文化算法中的種群空間為基礎(chǔ)空間，因?yàn)樗惴ㄖ械闹匾闹R(shí)和經(jīng)驗(yàn)積累的樣本都來自于種群空間中種群的進(jìn)化。本文對(duì)文化算法的改進(jìn)是將免疫優(yōu)勢(shì)克隆選擇算法嵌入文化算法的種群空間，從種群的樣本基礎(chǔ)著手達(dá)到優(yōu)化算法的目的。

3文化算法的改進(jìn)

3.1 種群空間的設(shè)計(jì)

文化算法最大的特點(diǎn)之一就是善于繼承和積累知識(shí)和經(jīng)驗(yàn)，而這些知識(shí)和經(jīng)驗(yàn)來源于種群的進(jìn)化過程，所以對(duì)種群空間的改進(jìn)設(shè)計(jì)至關(guān)重要，本節(jié)將一種新型的免疫優(yōu)勢(shì)克隆算法[2]放進(jìn)文化算法的基礎(chǔ)空間，實(shí)現(xiàn)對(duì)種群空間自進(jìn)化過程的改進(jìn)。

免疫優(yōu)勢(shì)克隆算法屬于免疫類算法中的一種，她利用免疫學(xué)中免疫優(yōu)勢(shì)的概念構(gòu)造相應(yīng)的免疫優(yōu)勢(shì)算子。所以將其與一般免疫算法比較，具有以下幾個(gè)優(yōu)勢(shì)：①具有免疫優(yōu)勢(shì)算子，抗體群的抗體信息可以完成有目的的交換；②選擇性采用多克隆或單克隆算子，保證進(jìn)化種群的多樣性；③局部搜索和全局搜索同時(shí)獨(dú)立進(jìn)行，使種群進(jìn)化代數(shù)減少，提升了算法搜索速度。所以本文以免疫優(yōu)勢(shì)克隆算法承擔(dān)文化算法的種群基礎(chǔ)，嵌入種群空間，目標(biāo)是改善文化算法的種群基礎(chǔ)，這樣才能通過相應(yīng)的通訊通道給上層信念空間提供更優(yōu)良樣本庫，得到更好的知識(shí)和經(jīng)驗(yàn)的積累。

而免疫類算法并不善于利用經(jīng)驗(yàn)知識(shí)指導(dǎo)加速種群的進(jìn)化，文化算法中信念空間的存在正好彌補(bǔ)了這方面的缺陷，所以將現(xiàn)將免疫優(yōu)勢(shì)克隆算法嵌入到文化算法的種群空間中，以優(yōu)化文化算法的種群基礎(chǔ)，并利用文化算法善于積累利用知識(shí)經(jīng)驗(yàn)的優(yōu)勢(shì)促進(jìn)新嵌入種群的進(jìn)化，以達(dá)到對(duì)文化算法改進(jìn)的目的，提高算法搜索的快速性和穩(wěn)定性。

免疫優(yōu)勢(shì)克隆算法的步驟為：

①初始種群的選取，根據(jù)需要隨機(jī)性的選取一定數(shù)目的初始抗體群，設(shè)置各項(xiàng)參數(shù)，建立進(jìn)化終止條件；

②計(jì)算抗體親和度，終止條件滿足則算法終止，否則進(jìn)行Step3的操作步驟；

③初始免疫優(yōu)勢(shì)抗體群的選擇，在初始種群中按一定比例選取親和度高的抗體組成初始免疫優(yōu)勢(shì)抗體群；

④新免疫優(yōu)勢(shì)抗體群的獲取，首先選擇出比較抗體，將初始免疫優(yōu)勢(shì)抗體群中任意最優(yōu)抗體和比較抗體相較，將免疫優(yōu)勢(shì)以一定概率推廣到其他抗體中并重新選擇免疫優(yōu)勢(shì)抗體群；

⑤變異和重組，針對(duì)新免疫優(yōu)勢(shì)抗體群進(jìn)行得到新抗體群，計(jì)算中抗體親和度；

⑥克隆選擇，根據(jù)進(jìn)化所需的種群大小選擇親和度高的抗體，組成新抗體群，回到②。

3.2 信念空間的設(shè)計(jì)

信念空間可分為環(huán)境知識(shí)（Situation Knowledge）和標(biāo)準(zhǔn)知識(shí)（Normative Knowledge） [3]。這些知識(shí)從種群空間的進(jìn)化過程中獲得，經(jīng)過信念空間知識(shí)更新函數(shù)更新，得到更新后的知識(shí)庫用于指導(dǎo)種群空間的進(jìn)化

3.2.1 標(biāo)準(zhǔn)知識(shí)

標(biāo)準(zhǔn)知識(shí)是種群進(jìn)化的標(biāo)準(zhǔn)，即為優(yōu)勝區(qū)間，決定出算法搜索的方向以及每一步搜索的距離。更新規(guī)則如下：

3.2.2環(huán)境知識(shí)

環(huán)境知識(shí)取自信念空間的自進(jìn)化過程，是種群進(jìn)化中積累出的經(jīng)驗(yàn)的沉淀，由進(jìn)化過程中歷代種群里的最優(yōu)個(gè)體集聚而成，更新方式為：

3.3 通訊通道的設(shè)計(jì)

3.3.1 影響函數(shù)

影響函數(shù)是連接文化算法中種群空間和信念空間的重要通道之一，上層信念空間的自進(jìn)化自更新為的是選擇出最優(yōu)良的經(jīng)驗(yàn)知識(shí)保存，并傳遞到下層的種群空間，以幫助下層空間的加速進(jìn)化，該種有目的性的指導(dǎo)方式在文化算法中通過影響因子完成的。基于信念空間中保存的知識(shí)，影響函數(shù)設(shè)計(jì)如下：

3.3.2 接受函數(shù)

接受函數(shù)[4]是文化算法中的另一個(gè)重要通道，種群中的優(yōu)秀經(jīng)驗(yàn)來源于種群中的優(yōu)秀個(gè)體，通過接受函數(shù)選擇性的將種群中的優(yōu)秀個(gè)體輸送到信念空間，為信念空間的自我更新提供新的更好的經(jīng)驗(yàn)基礎(chǔ)，實(shí)現(xiàn)文化算法的雙重更新機(jī)制。一般來說，選取當(dāng)前種群空間中種群親和度值的15%左右。但是為了使接受函數(shù)的設(shè)計(jì)更符合種群進(jìn)化的特點(diǎn)，本節(jié)設(shè)計(jì)了一種新型的動(dòng)態(tài)自適應(yīng)接受函數(shù)，該接受函數(shù)隨著種群進(jìn)化的代數(shù)而不斷變化，如下式：

綜上所述，經(jīng)過改進(jìn)后的文化算法的流程如圖2所示。

3.4 改進(jìn)文化算法的函數(shù)尋優(yōu)比較測(cè)試

為了測(cè)試改進(jìn)文化算法的綜合有效性，本節(jié)采用函數(shù)尋優(yōu)的方法[5][6]對(duì)算法進(jìn)行測(cè)試，并從平均最優(yōu)值、收斂代數(shù)及達(dá)優(yōu)率這幾個(gè)方面對(duì)算法進(jìn)行比較評(píng)價(jià)。測(cè)試函數(shù)如下：

將本文改進(jìn)后的文化算法（GCA）、文化算法（CA）和免疫算法（IA）分別對(duì)上述Rastrigin函數(shù)和Shubert函數(shù)進(jìn)行函數(shù)尋優(yōu)，各項(xiàng)參數(shù)值設(shè)置為：種群最大迭代代數(shù)，種群規(guī)模，變異因子，重組因子，動(dòng)態(tài)接受函數(shù)參數(shù)。函數(shù)尋優(yōu)測(cè)試結(jié)果比較如表1所示。

從表1中可以看出改進(jìn)后文化算法各項(xiàng)測(cè)試指標(biāo)都優(yōu)于未改進(jìn)的文化算法，且同免疫算法相比各項(xiàng)測(cè)試指標(biāo)的優(yōu)越性更加明顯。綜上所述，改進(jìn)后的文化算法有效對(duì)的克服了算法早熟，既保證全局最優(yōu)又加快了函數(shù)的收斂速度，從表1中的收斂代數(shù)中可以良好的展現(xiàn)。

4 結(jié)束語

本文對(duì)傳統(tǒng)的文化算法進(jìn)行了改進(jìn)，將一種新型的免疫類算法嵌入文化算法的種群空間，并對(duì)算法進(jìn)行了性能測(cè)試，測(cè)試結(jié)果表明改進(jìn)后的文化算法的性能和效率都得到了有效提高。

而本文經(jīng)過改進(jìn)后的文化算法在性能上還有一定的提升空間，比如說：免疫優(yōu)勢(shì)克隆算法本身的改進(jìn)，文化算法中通信通道（影響函數(shù)和接受函數(shù)）的改進(jìn)設(shè)計(jì)等，這些都有待于在日后的項(xiàng)目研究工作中加以改進(jìn)，以進(jìn)一步優(yōu)化算法性能，并用于實(shí)際問題的研究之中。

參考文獻(xiàn)：

[1] Gao Fang， Cui Gang， Liu Hongwei. Integration of Genetic Algorithm and Cultural Algorithms for Constrained Optimization[J]. I.King et al. （Eds.）： ICONIP 2006， Part III， LNCS 4234. 2006： 817-825.

[2] 黃海燕. 基于文化算法的故障診斷方法及其在工業(yè)過程中的應(yīng)用研究[D].上海： 華東理工大學(xué). 2008.

[3] 盧開澄. 單目標(biāo)多目標(biāo)與整數(shù)規(guī)劃[M]. 北京： 清華大學(xué)出版社，2004：79-85.

[4] 黃海燕，顧幸生，劉漫丹. 求解約束優(yōu)化問題的文化算法研究[J].自動(dòng)化學(xué)報(bào)，2007，33（10）： 1115-1120.

[5] 宋辰，黃海燕.基于免疫文化算法的故障特征選擇方法 [J]. 計(jì)算機(jī)應(yīng)用研究，2012，29（11）： 4162-4164.

[6] 左萬利，韓佳育，劉露，等. 基于人工免疫算法的增量式用戶興趣挖掘[J].計(jì)算機(jī)科學(xué)，2015，42（5）： 34-41.