袁 戀,陳 明,劉衍民*

（1.貴州民族大學(xué)數(shù)據(jù)科學(xué)與信息工程學(xué)院貴州貴陽(yáng)550025；2.遵義師范學(xué)院數(shù)學(xué)學(xué)院貴州遵義563006）

1 引言

近年來(lái)，國(guó)內(nèi)外的學(xué)者為了解決非線性、全局尋優(yōu)、組合優(yōu)化等復(fù)雜的優(yōu)化問(wèn)題，提出了不少性能良好的群體智能優(yōu)化算法，例如：粒子群算法、遺傳算法、蟻群算法、神經(jīng)網(wǎng)絡(luò)算法、模擬退火法等。由于這些算法在圖像處理、模式識(shí)別、電子通信、自動(dòng)化控制等眾多領(lǐng)域中得到了成功的應(yīng)用，因此吸引了眾多國(guó)內(nèi)外學(xué)者的關(guān)注，掀起了群體智能優(yōu)化算法的研究熱潮。

在現(xiàn)有的進(jìn)化算法中大多都難以平衡全局搜索能力與局部搜索能力的問(wèn)題，如：在粒子群算法（PSO）中[1]，由于其收斂速度快，容易陷入局部最優(yōu)解，無(wú)法對(duì)解空間的未知領(lǐng)域進(jìn)行開(kāi)發(fā)，導(dǎo)致其收斂精度低和不易收斂。在蟻群算法（ACO）[2]中，由于其初始信息匱乏，一般需要較長(zhǎng)的搜索時(shí)間，導(dǎo)致其容易陷入局部最優(yōu)，而且CAO在搜索過(guò)程中容易出現(xiàn)停滯現(xiàn)象，即在搜索進(jìn)行到一定程度后，所有個(gè)體發(fā)現(xiàn)的解完全一致，不能對(duì)解空間進(jìn)一步的進(jìn)行探索，不利于收斂。遺傳算法（GA）[3]具有良好的全局搜索能力，可以快速的搜索出解空間中的全體解，防止其陷入局部最優(yōu)解的快速下降陷阱，但是GA的局部搜索能力較差，搜索時(shí)間長(zhǎng)，導(dǎo)致在進(jìn)化后期的搜索效率較低。模擬退火算法(SA）[4]雖然具有擺脫局部最優(yōu)的能力，但是SA缺乏對(duì)整個(gè)搜索空間結(jié)構(gòu)的了解，在搜索過(guò)程中難以進(jìn)入到有希望的搜索區(qū)域，不利于尋求最優(yōu)解。

為了克服傳統(tǒng)進(jìn)化算法難以平衡全局搜索能力與局部搜索能力的問(wèn)題，本文提出了一種基于生命進(jìn)化行為的新型生物社會(huì)網(wǎng)絡(luò)優(yōu)化算法（BNSO）。該算法使用群體搜索技術(shù)，通過(guò)個(gè)體與環(huán)境、個(gè)體與細(xì)胞、個(gè)體與個(gè)體、個(gè)體與群體的交互機(jī)制，使種群中的個(gè)體相互“協(xié)作”和“競(jìng)爭(zhēng)”，從而產(chǎn)生新的種群，并逐步使種群進(jìn)化到包含或接近最優(yōu)解的狀態(tài)。

2 相關(guān)工作

粒子群算法源自于對(duì)鳥(niǎo)群捕食行為的研究，在1995年Kennedy和Eberhart提出了粒子群算法。該算法將空間中的每一個(gè)鳥(niǎo)都看作是一個(gè)輕微粒子，代表問(wèn)題的一個(gè)潛在解，每個(gè)粒子初始時(shí)都被賦予了飛行的方向和速度。然后結(jié)合自己的運(yùn)動(dòng)經(jīng)驗(yàn)并與其它粒子進(jìn)行共享位置和速度信息來(lái)調(diào)整自身的飛行方向，直到收斂到全局最優(yōu)解，一些學(xué)者也提出了改進(jìn)算法[5]-[8]。

蟻群算法是對(duì)自然界中蟻群尋求最優(yōu)路徑的研究：螞蟻在尋找路徑的過(guò)程當(dāng)中在途徑的路徑上釋放信息素進(jìn)行信息傳遞，而螞蟻在運(yùn)動(dòng)的過(guò)程中能夠感知這種物質(zhì)，并以此來(lái)引導(dǎo)自己的運(yùn)動(dòng)方向?；谶@樣的群體行為，M.Dorigo和A.Colorni等人通過(guò)仿真提出的一種基于種群的啟發(fā)式隨機(jī)搜索算法。在搜索過(guò)程中的螞蟻會(huì)釋放信息素，在碰到還沒(méi)走過(guò)的路口就隨機(jī)挑選一條路走，同時(shí)，釋放與路徑長(zhǎng)度有關(guān)的信息素，信息素濃度與路徑長(zhǎng)度成反比。隨著時(shí)間的推移，當(dāng)一條路徑上經(jīng)過(guò)的螞蟻越來(lái)越多時(shí)，就會(huì)留下越來(lái)越多的信息素。后來(lái)的螞蟻再次碰到該路口時(shí)，就選擇信息素濃度較高的路徑，最優(yōu)路徑上的信息素濃度越來(lái)越大，最終蟻群可通過(guò)路徑上的信息素濃度找到最優(yōu)尋食路徑，一些學(xué)者提出了一些改進(jìn)的ACO算法[9]-[12]。

遺傳算法是由J.H.Holland首次提出，該算法是一類(lèi)以達(dá)爾文進(jìn)化論和孟德?tīng)栠z傳學(xué)說(shuō)為理論基礎(chǔ)的仿生型算法。GA使用群體搜索技術(shù)，將種群代表一組問(wèn)題的解，通過(guò)對(duì)當(dāng)前種群執(zhí)行選擇、交叉、變異等遺傳操作來(lái)產(chǎn)生一個(gè)適合生存的種群，以此來(lái)求解出優(yōu)化問(wèn)題的全局最優(yōu)解。

免疫算法[13]是結(jié)合基因進(jìn)化機(jī)理，模仿生物免疫機(jī)制，從而人工構(gòu)造出的一種智能優(yōu)化算法。該算法將生物免疫系統(tǒng)中的抗原視為一個(gè)待優(yōu)化問(wèn)題，將抗體視為優(yōu)化問(wèn)題的可行解，根據(jù)待優(yōu)化問(wèn)題的特點(diǎn)設(shè)計(jì)合適的抗體編碼規(guī)則。并在此規(guī)則下利用問(wèn)題的先驗(yàn)知識(shí)產(chǎn)生初始抗體種群，對(duì)種群中的抗體質(zhì)量進(jìn)行評(píng)價(jià)，對(duì)優(yōu)秀的抗體進(jìn)行免疫選擇、克隆、變異、克隆抑制等免疫操作，形成基于生物免疫系統(tǒng)克隆選擇原理的進(jìn)化規(guī)則和方法，實(shí)現(xiàn)對(duì)各種問(wèn)題的尋優(yōu)搜索。

以上所提到的進(jìn)化算法，對(duì)解決大多的優(yōu)化問(wèn)題都具有較好的性能，但都存在難以平衡全局搜索能力與局部搜索能力的問(wèn)題。

3 生物社會(huì)網(wǎng)絡(luò)算法

3.1 提出生物社會(huì)網(wǎng)絡(luò)算法

美國(guó)著名的生物學(xué)家Thomas H.Morgan提出“生命=DNA+環(huán)境+環(huán)境與遺傳的交互作用”的思想，生命的進(jìn)化是個(gè)體與個(gè)體、個(gè)體與細(xì)胞、個(gè)體與環(huán)境、個(gè)體與種群的交互作用。

種群中的每個(gè)個(gè)體通過(guò)個(gè)體與細(xì)胞的交互作用實(shí)現(xiàn)遺傳物質(zhì)的變異為種群的進(jìn)化提供原料；通過(guò)個(gè)體與環(huán)境的交互作用使個(gè)體適應(yīng)不斷變化的環(huán)境；通過(guò)個(gè)體與個(gè)體的交互進(jìn)行個(gè)體間信息的交流；通過(guò)個(gè)體與群體的交互來(lái)獲取有利于進(jìn)化的遺傳信息，選取個(gè)體適應(yīng)度強(qiáng)的遺傳信息遺傳給下一代，從而實(shí)現(xiàn)種群的進(jìn)化。

圖1 生物社會(huì)網(wǎng)絡(luò)的規(guī)則

根據(jù)ThomasH提出的生命進(jìn)化思想（如圖1所示），我們對(duì)個(gè)體生命進(jìn)化行為進(jìn)行建模與仿真，將個(gè)體進(jìn)化行為置于“細(xì)胞→個(gè)體→環(huán)境→細(xì)胞”構(gòu)成的生物網(wǎng)絡(luò)與社會(huì)網(wǎng)絡(luò)的結(jié)點(diǎn)中，研究個(gè)體進(jìn)化過(guò)程，進(jìn)而提取一種基于生命進(jìn)化行為的新型生物社會(huì)網(wǎng)絡(luò)優(yōu)化算法。

3.2 生物社會(huì)網(wǎng)絡(luò)算法的建立

美國(guó)著名遺傳生物學(xué)家Thomas H.Morgan指出目前已知地球上現(xiàn)存的生命主要是以DNA作為遺傳物質(zhì)，除遺傳外，決定生物特征的因素還有環(huán)境，以及環(huán)境與遺傳的交互作用。借鑒生命進(jìn)化的過(guò)程，對(duì)生命進(jìn)化過(guò)程進(jìn)行建模。首先將“細(xì)胞→個(gè)體→環(huán)境→細(xì)胞”看作生物網(wǎng)絡(luò)與社會(huì)網(wǎng)絡(luò)的混合體，這里稱作“生物社會(huì)網(wǎng)絡(luò)”，將個(gè)體看作生物社會(huì)網(wǎng)絡(luò)中的一個(gè)結(jié)點(diǎn)，細(xì)胞自身形成細(xì)胞周期網(wǎng)絡(luò)，環(huán)境看作個(gè)體所處的社會(huì)群體，它會(huì)對(duì)個(gè)體產(chǎn)生宏觀（自身適應(yīng)能力的改變）和微觀（基因突變、基因重組等）的影響。

基于生命進(jìn)化行為基礎(chǔ)上，我們利用BA無(wú)標(biāo)度網(wǎng)絡(luò)來(lái)作為生物社會(huì)網(wǎng)絡(luò)的基礎(chǔ)，將個(gè)體看作生物社會(huì)網(wǎng)絡(luò)中的一個(gè)結(jié)點(diǎn)，細(xì)胞自身形成細(xì)胞周期網(wǎng)絡(luò)，環(huán)境看作個(gè)體所處的社會(huì)群體，它會(huì)對(duì)個(gè)體產(chǎn)生宏觀（自身適應(yīng)能力的改變）和微觀（基因突變、基因重組等）的影響。采用BA無(wú)邊度網(wǎng)絡(luò)對(duì)種群個(gè)體影響過(guò)程如下：

(2)優(yōu)先連接：一個(gè)新的節(jié)點(diǎn)與一個(gè)已經(jīng)存在的節(jié)點(diǎn) 相連的概率與節(jié)點(diǎn) 的度之間的關(guān)系為=/(+++…+)，其中為網(wǎng)絡(luò)中的節(jié)點(diǎn)的總個(gè)數(shù)。

(3)節(jié)點(diǎn)決策：給出每一個(gè)節(jié)點(diǎn)的概率分布，作用是通過(guò)產(chǎn)生0(1之間的隨機(jī)數(shù)來(lái)做出決策。

(4)通過(guò)節(jié)點(diǎn)決策概率，選擇新增進(jìn)入的個(gè)體。選擇過(guò)程根據(jù)環(huán)境的變化優(yōu)先選擇。

圖2給出基于不同種群規(guī)模的度分布圖。可以看出，當(dāng)節(jié)點(diǎn)初始規(guī)模為種群規(guī)模的60%時(shí)效果最佳，因此，在本文提出的算法中，采用種群規(guī)模的60%作為初始增長(zhǎng)節(jié)點(diǎn)。

3.3 生物社會(huì)網(wǎng)絡(luò)算法過(guò)程

圖2 種群BA網(wǎng)絡(luò)度分布圖

生命進(jìn)化行為建模具體包括：生物社會(huì)網(wǎng)絡(luò)中細(xì)胞、個(gè)體和環(huán)境之間的復(fù)雜相互作用，它類(lèi)似于生命體中個(gè)體與細(xì)胞的交互，完成基因的突變、染色體的變異、基因的重組。個(gè)體所在細(xì)胞周期網(wǎng)絡(luò)的突變對(duì)個(gè)體成長(zhǎng)的影響類(lèi)似于種群中的個(gè)體通過(guò)結(jié)合個(gè)體與個(gè)體間的交流信息和個(gè)體與群體的交流信息的過(guò)程。具體如下：

假設(shè)由N個(gè)個(gè)體組成一個(gè)種群，每個(gè)個(gè)體攜帶了D個(gè)基因。將D維決策空間中的第i個(gè)個(gè)體表示為：

第i個(gè)個(gè)體根據(jù)公式（2）實(shí)現(xiàn)個(gè)體與環(huán)境的交互，使進(jìn)化的個(gè)體能夠適應(yīng)不斷變化的外部環(huán)境。

第i個(gè)個(gè)體根據(jù)公式(3)(4)(5)實(shí)現(xiàn)個(gè)體與細(xì)胞的交互，完成基因的突變、染色體的變異、基因的重組，給個(gè)體的進(jìn)化提供原料。

種群中的個(gè)體根據(jù)公式（6）進(jìn)行個(gè)體間的信息交流。

這里C1是［0，1］范圍內(nèi)的均勻隨機(jī)數(shù)；是到第n次迭代為止，第i個(gè)個(gè)體的最優(yōu)個(gè)體;代表個(gè)體通過(guò)與個(gè)體間交流所獲得的遺傳信息.

種群中的個(gè)體根據(jù)公式（7）獲取有利于種群進(jìn)化的遺傳信息.

這里C2是［0，1］范圍內(nèi)的均勻隨機(jī)數(shù);是到第n次迭代為止，種群中的最優(yōu)個(gè)體;是個(gè)體通過(guò)與群體間交流所獲得的有利于種群進(jìn)化的遺傳信息.

種群中的個(gè)體通過(guò)結(jié)合個(gè)體與個(gè)體間的交流信息和個(gè)體與群體的交流信息，根據(jù)公式（8）實(shí)現(xiàn)進(jìn)化。

這里r1r2是［0，1］范圍內(nèi)的均勻隨機(jī)數(shù)。

3.4 生物社會(huì)網(wǎng)絡(luò)算法流程

生物社會(huì)網(wǎng)絡(luò)算法使用群體搜索技術(shù)，通過(guò)個(gè)體與環(huán)境、個(gè)體與細(xì)胞、個(gè)體與個(gè)體、個(gè)體與群體的交互機(jī)制，使種群中的個(gè)體相互“協(xié)作”和“競(jìng)爭(zhēng)”，從而產(chǎn)生新的種群，并逐步使種群進(jìn)化到包含或接近最優(yōu)解的狀態(tài)。

生物社會(huì)網(wǎng)絡(luò)算法（BNSO）的流程如圖3所示。具體的步驟如下：

步驟1：初始化。包括種群規(guī)模N，隨機(jī)生成初始化種群P。

步驟2：計(jì)算每個(gè)個(gè)體的適應(yīng)值.

步驟3：執(zhí)行個(gè)體與環(huán)境的交互機(jī)制.對(duì)種群中的個(gè)體以一定的概率進(jìn)行擾動(dòng)操作，產(chǎn)生新的個(gè)體，運(yùn)行無(wú)標(biāo)度BA網(wǎng)絡(luò)。

步驟4：執(zhí)行個(gè)體與細(xì)胞的交互機(jī)制。對(duì)種群中的個(gè)體執(zhí)行突變、變異、重組一系列的操作產(chǎn)生新的個(gè)體。

步驟5：執(zhí)行個(gè)體與個(gè)體的交互機(jī)制，獲取個(gè)體間交流的遺傳信息 。

步驟6：執(zhí)行個(gè)體與群體的交互機(jī)制，獲取種群中有利于進(jìn)化的遺傳信息 。

步驟7：進(jìn)化。通過(guò)結(jié)合個(gè)體與個(gè)體間的交流信息和個(gè)體與群體的交流信息實(shí)現(xiàn)進(jìn)化。

步驟8：判斷是否滿足終止條件：若是，結(jié)束算法并輸出結(jié)果；否則，返回步驟2.

圖3 BNSO流程圖

4 實(shí)驗(yàn)仿真及其分析

為了測(cè)試BNSO算法，我們采用了11個(gè)Benchmark函數(shù)[14]來(lái)測(cè)試提出算法的性能。并且將BNSO算法分別與GPSO,LPSO,GA和AOC算法相比，來(lái)檢測(cè)我們提出算法的有效性。另外，為進(jìn)一步測(cè)試算法的性能，將檢測(cè)函數(shù)進(jìn)行旋轉(zhuǎn)，以進(jìn)一步測(cè)試BNSO算法的優(yōu)化能力，旋轉(zhuǎn)方法參見(jiàn)文獻(xiàn)[15]，表1和表2分別給出旋轉(zhuǎn)檢測(cè)函數(shù)和非旋轉(zhuǎn)檢測(cè)函數(shù)的函數(shù)屬性。各種算法參數(shù)設(shè)置如下：PSO種群規(guī)模為30個(gè)粒子，檢測(cè)函數(shù)獨(dú)立運(yùn)行30次取平均值，每個(gè)檢測(cè)函數(shù)的維數(shù)為30，其它參數(shù)的選取與算法提出時(shí)一致。另外，對(duì)非旋轉(zhuǎn)和旋轉(zhuǎn)的檢測(cè)函數(shù)每次運(yùn)行3×104函數(shù)評(píng)價(jià)(Fitness Evaluations)。

圖4 非旋轉(zhuǎn)檢測(cè)函數(shù)收斂圖

圖5 旋轉(zhuǎn)檢測(cè)函數(shù)收斂圖

表1 非旋轉(zhuǎn)的Benchmark函數(shù)

表2 旋轉(zhuǎn)的Benchmark函數(shù)

圖4和圖5分別給出不同算法在旋轉(zhuǎn)檢測(cè)函數(shù)和非旋轉(zhuǎn)檢測(cè)函數(shù)的收斂特征曲線圖。表3和表4分別給出非旋轉(zhuǎn)函數(shù)和旋轉(zhuǎn)檢測(cè)函數(shù)在3×104函數(shù)評(píng)價(jià)后的均值和置信區(qū)間，為檢驗(yàn)BNSO優(yōu)化能力與PSO，ACO,GA算法在優(yōu)化能力上是否具有統(tǒng)計(jì)學(xué)差異，用Wilcoxon秩和檢驗(yàn)來(lái)測(cè)試BNSO與其它算法的優(yōu)化結(jié)果進(jìn)行檢測(cè)，統(tǒng)計(jì)結(jié)果在表3和表4的底部。

另外，為測(cè)試不同算法的計(jì)算復(fù)雜度，采用用Matlab 2013軟件中的(tic,toc)命令來(lái)測(cè)試算法運(yùn)行時(shí)間，表 5和表 6分別給出非旋轉(zhuǎn)檢測(cè)函數(shù)在 3(104FES函數(shù)評(píng)價(jià)后的運(yùn)行時(shí)間。

從圖4和圖5非檢測(cè)函數(shù)和檢測(cè)收斂圖中可以看出BNSO算法在收斂特性中優(yōu)于其它三種智能算法。表3和表4的運(yùn)行結(jié)果統(tǒng)計(jì)圖也顯示出同樣的結(jié)果。但是，在對(duì)于單峰檢測(cè)函數(shù)Sphere來(lái)說(shuō)，雖然BNSO優(yōu)于GA、LPSO、GPSO和GA算法，但是在 Wilcoxon秩和檢驗(yàn)檢測(cè)中并沒(méi)有在統(tǒng)計(jì)學(xué)意義下優(yōu)于其它算法，這也說(shuō)明智能算法在優(yōu)化單峰問(wèn)題時(shí)都具有較好的效果。但是BNSO算法在多峰檢測(cè)函數(shù)和旋轉(zhuǎn)的多峰檢測(cè)函數(shù)上表現(xiàn)出了極優(yōu)的運(yùn)行效果，這也說(shuō)明本文提出的借鑒“生命=DNA+環(huán)境+環(huán)境與遺傳的交互作用”的思想，提出的生物社會(huì)網(wǎng)絡(luò)算法能有效的優(yōu)化單目標(biāo)問(wèn)題。另外，從計(jì)算復(fù)雜度上也可以看出BNSO算法雖然有較好的優(yōu)化效果，但計(jì)算復(fù)雜度并沒(méi)有增加。

表3 非旋轉(zhuǎn)函數(shù)在3×104函數(shù)評(píng)價(jià)后的均值和置信區(qū)間

表4旋轉(zhuǎn)函數(shù)在3×104函數(shù)評(píng)價(jià)后的均值和置信區(qū)間

表5非旋轉(zhuǎn)檢測(cè)函數(shù)計(jì)算時(shí)間3×104FES)(單位:秒)

5 結(jié)論

為了解決傳統(tǒng)進(jìn)化算法難以平衡全局搜索能力與局部搜索能力的問(wèn)題，本文提出一種具有生命演化和群體智能的生物社會(huì)網(wǎng)絡(luò)優(yōu)化算法（BNSO）。為了測(cè)試BNSO算法性能，我們選取11個(gè)單峰和多峰檢測(cè)函數(shù)來(lái)測(cè)試算法性能，結(jié)果表明BNSO優(yōu)化能力優(yōu)于PSO,ACO,GA算法。尤其BNSO算法在多峰檢測(cè)函數(shù)和旋轉(zhuǎn)的多峰檢測(cè)函數(shù)上表現(xiàn)出了極優(yōu)的運(yùn)行效果。因此，本文借鑒“生命=DNA+環(huán)境+環(huán)境與遺傳的交互作用”的思想，提出的生物社會(huì)網(wǎng)絡(luò)算法是解決單目標(biāo)優(yōu)化問(wèn)題的一種有效算法。