生物社會網絡算法研究

袁 戀,陳 明,劉衍民*

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

1 引言

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

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

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

2 相關工作

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

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

遺傳算法是由J.H.Holland首次提出，該算法是一類以達爾文進化論和孟德爾遺傳學說為理論基礎的仿生型算法。GA使用群體搜索技術，將種群代表一組問題的解，通過對當前種群執(zhí)行選擇、交叉、變異等遺傳操作來產生一個適合生存的種群，以此來求解出優(yōu)化問題的全局最優(yōu)解。

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

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

3 生物社會網絡算法

3.1 提出生物社會網絡算法

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

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

圖1 生物社會網絡的規(guī)則

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

3.2 生物社會網絡算法的建立

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

基于生命進化行為基礎上，我們利用BA無標度網絡來作為生物社會網絡的基礎，將個體看作生物社會網絡中的一個結點，細胞自身形成細胞周期網絡，環(huán)境看作個體所處的社會群體，它會對個體產生宏觀（自身適應能力的改變）和微觀（基因突變、基因重組等）的影響。采用BA無邊度網絡對種群個體影響過程如下：

(2)優(yōu)先連接：一個新的節(jié)點與一個已經存在的節(jié)點 相連的概率與節(jié)點 的度之間的關系為=/(+++…+)，其中為網絡中的節(jié)點的總個數(shù)。

(3)節(jié)點決策：給出每一個節(jié)點的概率分布，作用是通過產生0(1之間的隨機數(shù)來做出決策。

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

圖2給出基于不同種群規(guī)模的度分布圖?？梢钥闯?，當節(jié)點初始規(guī)模為種群規(guī)模的60%時效果最佳，因此，在本文提出的算法中，采用種群規(guī)模的60%作為初始增長節(jié)點。

3.3 生物社會網絡算法過程

圖2 種群BA網絡度分布圖

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

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

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

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

種群中的個體根據公式（6）進行個體間的信息交流。

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

種群中的個體根據公式（7）獲取有利于種群進化的遺傳信息.

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

種群中的個體通過結合個體與個體間的交流信息和個體與群體的交流信息，根據公式（8）實現(xiàn)進化。

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

3.4 生物社會網絡算法流程

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

生物社會網絡算法（BNSO）的流程如圖3所示。具體的步驟如下：

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

步驟2：計算每個個體的適應值.

步驟3：執(zhí)行個體與環(huán)境的交互機制.對種群中的個體以一定的概率進行擾動操作，產生新的個體，運行無標度BA網絡。

步驟4：執(zhí)行個體與細胞的交互機制。對種群中的個體執(zhí)行突變、變異、重組一系列的操作產生新的個體。

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

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

步驟7：進化。通過結合個體與個體間的交流信息和個體與群體的交流信息實現(xiàn)進化。

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

圖3 BNSO流程圖

4 實驗仿真及其分析

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

圖4 非旋轉檢測函數(shù)收斂圖

圖5 旋轉檢測函數(shù)收斂圖

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

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

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

另外，為測試不同算法的計算復雜度，采用用Matlab 2013軟件中的(tic,toc)命令來測試算法運行時間，表 5和表 6分別給出非旋轉檢測函數(shù)在 3(104FES函數(shù)評價后的運行時間。

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

表3 非旋轉函數(shù)在3×104函數(shù)評價后的均值和置信區(qū)間

表4旋轉函數(shù)在3×104函數(shù)評價后的均值和置信區(qū)間

表5非旋轉檢測函數(shù)計算時間3×104FES)(單位:秒)

5 結論

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