MHCSSA：一種基于多群分層協作策略的社會蜘蛛算法

張德成，王明星，王 楊，趙傳信

(1.蚌埠醫(yī)學院公共基礎學院，安徽蚌埠 233000；2.安徽師范大學計算機與信息學學院，安徽蕪湖 241002)

近年來，隨著信息技術的飛速發(fā)展，全局優(yōu)化技術在經濟模型、圖像處理、機械設計及環(huán)境工程等眾多領域中受到廣泛的應用。目前解決全局優(yōu)化問題主要分為兩個方面：進化算法(EAs)和基于群智能的優(yōu)化算法。進化算法包括遺傳算法(Genetic Algorithm，GA)、遺傳規(guī)劃(Genetic Programming，GP)、進化策略(Evolution Strategy，ES)和差分進化(Differential Evolution，DE)等改進算法[1]。群智能算法是一種模擬自然界生物群體行為來構造的隨機優(yōu)化算法，主要研究自然動物和昆蟲的行為來解決問題。研究人員設計了模仿螞蟻、蜜蜂的行為，以及細菌、螢火蟲和其它生物的優(yōu)化算法。創(chuàng)造這種算法的動力是不斷增長的需求，以解決最優(yōu)化問題。群智能算法具有清晰的結構、簡單的操作和較強的尋優(yōu)能力，可有效地解決一些傳統(tǒng)優(yōu)化算法無法在合理時間內解決的問題。主要群智能算法包括蟻群優(yōu)化(the Ant Colony Optimization algorithm，ACO)[2]和粒子群優(yōu)化(the Prticle Swarm Optimization algorithm，PSO)[3]等。目前，群智能算法已被廣泛應用于自然科學、經濟金融、醫(yī)療和工程技術等領域，并吸引了越來越多的研究者。

雖然蜘蛛已成為仿生工程領域的一個重要研究課題，然而大多數與蜘蛛相關的研究都集中在模仿其行走模式上。其主要原因是在大多數情況下人們觀察到的蜘蛛都是獨立活動的，不構成群居的特性。但是在科學家觀察和描述的35000種蜘蛛中[4]，有些蜘蛛是具有群居性的，它們生活在一個群體中。針對這些群居的蜘蛛，James J Q Yu,et al[5]提出了一種模擬群居型蜘蛛搜尋食物行為的群智能算法，即社會蜘蛛算法(Society Spider Algorithm，SSA)。盡管SSA算法被提出的時間相對較短，但是James J Q Yu,et al通過對幾組基準測試

函數進行仿真實驗，證明SSA算法比ACO算法和PSO算法都具有較快的收斂速度，且能有效地避免早熟收斂和跳出局部最優(yōu)值。但是SSA算法在高維復雜函數特別是在旋轉多峰函數上的表現并沒有優(yōu)勢。SSA算法采用隨機游走的方式來保證種群的多樣性，同時實現向最優(yōu)狀態(tài)的轉移，從而限制了優(yōu)化算法的收斂速度；另一方面，優(yōu)化策略容易陷入局部最優(yōu)值。

為了保證優(yōu)化算法的全局收斂性，需要保證種群的多樣性，加快收斂速度就會帶來過早陷入局部最優(yōu)值。為了提高算法的收斂速度并防止早熟收斂問題，提高全局優(yōu)化效率，本文提出一種多群分層協作社會蜘蛛算法(Multi-swarm Hierarchical Cooperative Society Spider Algorithm，MHCSSA)基準測試函數[5-6]。仿真實驗表明，運用MHCSSA算法的多群分層協作方法和主群的貪婪搜索策略在保證收斂速度的同時防止過早進入早熟收斂。

1 SSA算法描述與分析

1.1 SSA算法描述

SSA算法將優(yōu)化問題的搜索空間作為一張多維的蜘蛛網，蜘蛛網上的每個位置表示一個可行的優(yōu)化問題的j解決方案，所有可行的解決方案在蜘蛛網上都有相應位置。同時蜘蛛網也是蜘蛛產生振動的傳輸媒介。蜘蛛網上的每個蜘蛛都有其對應的位置信息和對應的適應值(位置信息基于目標函數計算產生，它代表了這個位置能找到食物的潛力)。蜘蛛在網上可以自由行走，當蜘蛛個體移動到新的位置時，它會產生振動在蜘蛛網上傳播，每個振動都包含了一只蜘蛛的信息，其它蜘蛛在感應到振動后就會獲得這些信息。每個蜘蛛個體通過判斷自己位置的振動和感應來自其它蜘蛛傳遞來的信息來搜索食物，最終達到尋優(yōu)目的。

1.2 蜘蛛個體

蜘蛛作為SSA算法執(zhí)行優(yōu)化的代理，在算法開始時，一群被預先定義的蜘蛛被放到蜘蛛網上。每個蜘蛛s都攜帶一些信息，存儲以下內容：①蜘蛛s在蜘蛛網上的位置；②依據當前位置計算得到的適應值；③前一次迭代蜘蛛s獲得的目標振動；④蜘蛛s最終改變其目標振動所經歷的迭代次數；⑤前一次迭代蜘蛛s所執(zhí)行的移動；⑥用于指導蜘蛛s在前一次迭代中運動的指導向量m。

前兩類信息描述了蜘蛛個體的情況，而后幾類信息涉及指導蜘蛛s移動到新位置。由于蜘蛛具有非常精確的振動感，同時它們可以在蜘蛛網上傳遞不同的振動并感應各自的強度。在SSA算法中，當蜘蛛到達一個新位置時，它會產生一個振動。振動會在蜘蛛網上傳播，其它蜘蛛能夠感應到這些振動，從而與其它蜘蛛分享個人信息，形成信息共享。

1.3 振動

振動是SSA算法區(qū)別于其它算法的重要概念。在SSA算法中，使用兩種特征來定義振動，即振動的源位置和強度。源位置是由優(yōu)化問題的搜索空間定義的。SSA算法定義了范圍為[0，+)的振動強度。每當蜘蛛移動到新位置，會在此位置產生一個振動。定義蜘蛛個體a在時間t的位置為Pa(t)(或者簡單表示為Pa)。同時定義I(Pa,Pb,t)為蜘蛛在時間t位置Pb感應到的來自位置Pa的振動強度，由此使用I(Ps,Ps,t)表示蜘蛛s在源位置產生的振動強度。源位置的振動強度與其位置的適應值有關，定義強度值為：

(1)

其中，C是一個比所有可能的適應值都小的常數；f(Pi)是根據目標函數和位置信息計算得到的適應值。

考慮到以下幾個問題：①優(yōu)化問題的所有可能振動強度都是正數；②有更好適應值的位置，即最小化問題的最小值，比較差的適應值的位置有更大的振動強度；③當解接近全局最優(yōu)值時，振動強度不會過大增加。

定義蜘蛛a和b之間的距離為D(Pa,Pb)，SSA算法使用曼哈頓距離計算D(Pa,Pb)：

(2)

定義距離上的振動衰減：

(3)

其中，σ表示每個維度上所有蜘蛛位置的標準差，ra是控制距離的振動強度衰減率的參數，ra∈(0,)。

1.4 搜索模式

SSA算法有三個階段：初始化、迭代和輸出。這三個階段按順序執(zhí)行，從初始化階段開始，然后以迭代的方式執(zhí)行搜索，最后終止算法并輸出所找到的解決方案。

在初始化階段，該算法定義目標函數及其解空間并設置參數，之后算法創(chuàng)建初始蜘蛛種群。由于在模擬SSA時，蜘蛛總數不變，所以分配一個固定大小的內存來存儲它們的信息。在搜索空間中隨機生成蜘蛛的位置，計算并存儲它們的適應值。種群中各蜘蛛的初始目標振動被設置在其當前位置，且振動強度為零。每個蜘蛛存儲的所有其它屬性也用0初始化。初始化階段結束后，算法開始進入迭代階段，由創(chuàng)建的人工蜘蛛進行搜索。

在迭代階段，算法執(zhí)行多次迭代。在每次迭代中，蜘蛛網上的所有蜘蛛都移動到一個新位置，并評估它們的適應值。每一次迭代可以進一步分為以下幾個步驟：適應度評估、振動生成、指導向量改變、隨機游走和約束處理。

隨后算法操作蜘蛛s朝vtar隨機游走。使用維度向量m指導蜘蛛的移動。每個蜘蛛個體都持有一個維度向量m，它是一個長度為優(yōu)化問題維度D的0-1向量，初始時m的所有值都為0。在每一次迭代中，蜘蛛s都有1-pc的概率改變m，其中pc∈(0,1)是一個用戶定義的參數，用來描述改變m的概率。如果m被決定改變，向量的每個位都有pm的概率被設置為1，1-pm的概率被設置為0。pm∈(0,1)也是用戶定義的參數。m的每一位都是獨立改變的，與先前的值沒有任何關系。如果所有位都為0，則掩碼的一個隨機值將更改為1。類似地，如果所有值都是1，則將一個隨機位分配給0。

(4)

(5)

其中，⊙表示向量的乘法，R是和優(yōu)化問題同維度的0-1向量。

迭代階段循環(huán)直到停止條件匹配為止。停止標準可以定義為達到的最大迭代次數、所使用的最大CPU時間、達到一定錯誤率、最大迭代次數在最佳適應值上沒有改進等。在迭代階段后，算法以最佳適應度輸出最優(yōu)解。上述三個階段構成了完整的SSA算法。

1.5 SSA算法分析

雖然SSA算法和粒子群(PSO)算法一樣都是根據群體覓食行為設計的算法，但是兩者確有明顯的區(qū)別。

粒子群(PSO)算法同SSA算法一樣，最初也是為解決連續(xù)優(yōu)化問題而提出的,它也受到動物行為的啟發(fā)。然而，SSA算法和PSO算法之間的第一個關鍵區(qū)別在于個體跟隨模式。在粒子群算法中，所有粒子都遵循一個全局最優(yōu)位置和各自的最佳位置。然而，在SSA算法中，所有蜘蛛跟隨的位置都是由種群其它蜘蛛當前位置和自身歷史位置構建的。此位置不能保證以前會被其它蜘蛛訪問過，不同的蜘蛛可以有不同的跟隨位置。由于全局最優(yōu)位置和蜘蛛當前位置在優(yōu)化過程的大部分時間內差異很大，這兩種模式導致了不同的搜索行為。這可能削弱SSA算法的收斂能力，但有可能加強大量的局部最優(yōu)解求解多峰優(yōu)化問題的能力。

在信息傳播方法方面,粒子群(PSO)算法與SSA算法也存在區(qū)別。在粒子群(PSO)算法中，信息傳播方法被忽略，每個粒子被假定為知道系統(tǒng)所有信息而不損失。SSA算法是通過蛛網上的振動來模擬信息的傳播過程，這個過程形成了一個具有信息損失的通用知識系統(tǒng)。

SSA算法在保持種群多樣性和收斂速度的平衡上采用了蜘蛛個體朝著目標位置隨機游走的策略。這種方法雖然能保證在一定收斂速度下種群多樣性不會丟失，但是也在一定程度上限制了算法的收斂速度和處理局部最優(yōu)值跳出早熟收斂的能力。

2 貪婪多群分層協作社會蜘蛛算法

2.1 MHCSSA算法描述

和大多數群智能算法一樣，SSA算法同樣也有種群多樣性和算法收斂速度存在矛盾的現象。SSA算法的種群蜘蛛隨機游走策略平衡了種群多樣性的損失，使算法在跳出多個局部最優(yōu)值方面表現突出。但是由此帶來的是收斂速度的降低。貪婪多群分層協作社會蜘蛛算法(MHCSSA)在子群保持隨機游走策略的基礎上采用多群分層協作的思想來保持種群多樣性。同時，蜘蛛個體根據劃分的不同適應值范圍分配到不同的分群中搜索，使得不同適應值水平的個體能公平地進行“捕食”競爭。

MHCSSA算法主要設置一個主群和數個子群[6]，子群的劃分依據適應值范圍分級劃分。每個子群都依據其適應值范圍設置一個移入閾值和移出閾值，移出閾值決定個體是否應該移動到更高適應值范圍的子群或者主群中。下一級子群的移出閾值即為上一級子群的移入閾值。符合移入移出條件的個體同步或異步地跨越主群和子群。蜘蛛個體在子群間的移入移除如圖1所示，并采取如下的搜索原則：

主群：主群中依據貪婪策略[7]，即指導蜘蛛向有前途的區(qū)域移動。當主群陷入早熟收斂，將局部最優(yōu)的個體移出主群，移入到合適適應值范圍的子群中。主群中的貪婪方法保證快速收斂。

子群：子群中依然依據標準的SSA進行搜索，若子群的蜘蛛個體適應值優(yōu)于子群的移出閾值時，將此個體移出子群移入到更合適適應值范圍的子群或主群中繼續(xù)搜索。

2.2 種群劃分與層次結構

為了保證算法的全局收斂性，就要維持種群中個體的多樣性，避免有效基因的丟失。為了加快收斂速度，就要使種群較快地向最優(yōu)狀態(tài)轉移，這又會減少群體的多樣性，容易陷入局部極值點。如何較快地找到最優(yōu)解并防止早熟收斂問題是群智能算法中一個較難解決的問題。SSA算法在保持多樣性上采取了蜘蛛隨機游走的機制，這樣就會限制收斂速度。MHCSSA算法采用多群劃分的方式，且在子群中依然維持蜘蛛隨機游走的機制來保證種群的多樣性。

(6)

其中，Nl為分群的總數。由此得到主群的適應值范圍[fmax,fmax-σf]、最低子群的適應值范圍(-,fμ]和其余Nl-2個分群的適應值范圍，每個子群的適應值范圍的上限即為移出閾值，下限即為移入閾值。將初始化的種群體分配到合適適應值范圍的分群中。

2.3 主群貪婪搜索策略

MHCSSA算法采用多群分層協作的思想保持了種群的多樣性，且子群和SSA算法一樣采用隨機游走策略，大大降低了算法的收斂速度。采用種群分級劃分方法，使算法在結束輸出時依據主群搜索獲得最優(yōu)值。本文在主群中采用貪婪搜索策略來加快算法的收斂速度。

當主群中的蜘蛛個體接受到來自其它所有蜘蛛的震動后，其運動方式由隨機游走變?yōu)橹笇渫駝幼顝姷奈恢靡苿印Ｍ琒SA算法類似,采用一個D維的0-1向量指導蜘蛛個體的移動，每個蜘蛛個體都持有一個運動向量，且每次迭代之后都會依據收到的種群最大振動強度的目標位置Ptar改變搜索方向。貪婪搜索移動后的新位置第i維值計算依據為：

(7)

其中，⊙表示向量的乘法，R是和優(yōu)化問題同維度的0-1向量。

2.4 多種群分層協作

MHCSSA算法在主群中采用貪婪搜索策略來指導蜘蛛向有前途的位置移動而不是隨機游走。這樣雖然加快了算法的收斂速度，但是同樣會帶來早熟收斂的快速發(fā)生。當有蜘蛛個體發(fā)生早熟收斂現象時，則將此個體移出主群并移入到合適的適應值范圍的子群中。多群分層協作主要采用如圖3所示方法。分層協作的方法主要有兩方面：①當主群的個體陷入早熟收斂后并不是立馬移出主群，而是復制此個體存儲的信息并按照其當前適應值大小判斷哪個子群的適應值范圍適合此個體移入。當找到合適的適應值范圍的子群后則將此個體移出主群并移入到子群中。②當子群的個體適應值達到子群的移出閾值時，若此子群非最高級子群,則根據個體的適應值大小判斷其移入哪個適應值范圍的子群中，若此個體適應值優(yōu)于最高級子群的移出閾值，則將其直接移入主群,否則移入到合適適應值范圍的子群中；若此子群為最高級子群，則將個體直接移入主群中。

同SSA算法一樣，MHCSSA算法分為初始化、迭代和輸出三個階段。MHCSSA算法是在SSA算法初始化階段加入多種群劃分從而達到種群的分層結構。在迭代階段MHCSSA算法引入主群的貪婪策略和多種群分層協作的思想。MHCSSA算法的主體描述如下：

①設置算法參數，依據SSA方式初始化種群。

②依據種群初始的適應值降序排列，劃分種群層次結構，并將種群個體分配到合適適應值范圍的種群中，同時設置子群移入移除閾值。

While (不滿足算法終止條件)

For蜘蛛個體in主群

③根據公式(7)對主群執(zhí)行貪婪搜索策略，更新主群個體。

If (主群個體滿足早熟收斂條件)

④將蜘蛛個體標記并復制其存儲的信息。

End If

End for

For each子群

⑤根據公式(5)執(zhí)行隨機搜索，更新各子群個體。

For 蜘蛛個體in子群

If (個體適應值達到子群移出閾值)

⑥將蜘蛛個體標記并復制其存儲的信息。

End If

End For

End For

⑦將標記的主群個體移出主群并移入到合適適應值范圍的子群中。同步或異步地將子群中標記所有個體移出子群移入到合適適應值范圍的子群或直接移入主群中。

⑧更新蜘蛛種群，更新蜘蛛子群移入移除閾值。

⑨迭代次數T=T+1。

End While

⑩輸出結果，算法結束。

2.5 主群早熟收斂判斷

對于復雜的實際優(yōu)化問題，不能通過確定性分析來確定目標函數是否陷入局部最優(yōu)點而早熟收斂。本文提出以下方法判定主群個體是否陷入局部最優(yōu)點。

①利用種群適應值方差來判定蜘蛛個體的收斂程度。設主群規(guī)模為Nmain，fi為第i個蜘蛛個體的適應值，favg為平均適應值，σ2為種群適應值方差。

(8)

種群適應值方差σ2反應了蜘蛛群的個體密集程度，σ2越小，則表明算法越趨于收斂，反之則處于搜索狀態(tài)。如果算法不滿足終止條件，則σ2變小將使種群陷入局部最優(yōu)值而導致早熟收斂。因此設定常數λ，當σ2<λ時標志主群陷入早熟收斂。

②個體平均適應值favg連續(xù)t1次迭代沒有改變或者改變很小且不滿足終止條件。

③全局最優(yōu)fg_best值在經歷t2次迭代后不改變或者改變很小且不滿足終止條件。

3 實驗仿真

為了驗證MHCSSA算法的優(yōu)化性能，在python仿真平臺設置優(yōu)化問題維度為50維，采用表1所示的10種基準測試函數[5-6]，比較MHCSSA算法和SSA算法的性能。同時將實驗結果與其它優(yōu)秀的超啟發(fā)式算法，如自適應協方差矩陣進化策略算法(CMA-ES)[9]、特征矩陣聯合近似對角化(JADE)[10]、自適應差分進化算法(SaDE)[11]和Global-Local實時編碼遺傳算法(GL-25)[12]等進行比較，這些超啟發(fā)式算法都是在CEC 2013(Competition on Real-Parameter Single Ob jective Optimization Problems)中表現非常優(yōu)秀的算法。它們主要用來測試MHCSSA與優(yōu)秀的超啟發(fā)式算法在優(yōu)化問題上的競爭力。MHCSSA算法基礎參數的設置和種群規(guī)模的大小同SSA設置相同。這些基準測試函數可被分為兩組，其中f1～f4為單峰函數，f5～f10為多峰函數。單峰函數主要測試MHCSSA算法的快速收斂能力，而多峰函數由于有多個局部極值點，主要用來測試MHCSSA算法跳出局部最優(yōu)點和防止早熟收斂的能力。所有的基準測試函數在0處取全局最小值,同時適應度下限取值為10-8 [5-6]。對所有基準測試函數獨立運行100次來獲取平均的全局最優(yōu)值和迭代次數。

3.1 單峰函數對比實驗

運用單峰函數組f1～f4來驗證MHCSSA算法在50維度情況下的收斂速度。圖4所示為單峰數組的函數收斂曲線，表2所示為實驗的對比結果。

表2 50維度的單峰函數測試對比

從圖4單峰函數實驗結果中可以看出，MHCSSA算法的收斂速度明顯快于SSA算法。特別是f2函數，MHCSSA算法僅需要少數迭代步驟即達到較小的目標值。比較f1和f3函數，迭代到10000代時，MHCSSA所得目標函數數量級優(yōu)于103倍數。因為SSA算法在執(zhí)行隨機游走的同時進行搜索和開發(fā)，保持種群多樣性和收斂精度的平衡，而MHCSSA算法在以多子群搜索結構保持種群多樣性的基礎上在主群采用貪婪搜索策略,使得MHCSSA算法在收斂速度上明顯快于SSA算法。

從表2可以看出，在f1～f3結果中MHCSSA算法都能獲得全局最優(yōu)解。在f4的結果中MHCSSA算法獲得了比SSA算法更好的結果，與CMA-ES算法和SaDE算法相比，MHCSSA算法有明顯優(yōu)勢。雖然在f4實驗結果中MHCSSA算法沒有獲得比JADE算法和GL25算法更優(yōu)的結果，但是其結果卻十分具有競爭力。

3.2 多峰函數對比實驗

為了進一步驗證MHCSSA算法跳出局部最優(yōu)和避免早熟收斂的能力，在50維度情況下用多峰函數組f5～f10與SSA算法進行實驗對比。圖5所示為多峰函數組的函數收斂曲線，表3所示為實驗對比結果。

表3 50維度多峰函數測試對比

從圖5所示的多峰函數實驗結果可以看出，MHCSSA算法的收斂速度同樣明顯快于SSA算法。同時在跳出局部最優(yōu)值和避免早熟收斂方面也比SSA算法表現出了更好的性能。因為SSA算法雖然在避免早熟收斂方面表現突出，但是SSA算法為了防止收斂精度的丟失和收斂速度的下降采用了隨機游走的這種平衡兩者的方式，使得在避免早熟收斂的方面受到限制。

從表3的實驗結果數據可以看出，在f5、f6、f7和f9的結果中MHCSSA算法同其它算法一樣獲得了全局最優(yōu)解。同時在f8的結果中，MHCSSA算法獲得了比SSA算法更好的結果，且結果與JADE算法、SaDE算法和GL25算法表現同樣優(yōu)秀。雖然在f8實驗結果中MHCSSA算法沒有獲得比CMA-ES算法獲得更優(yōu)的結果，但是其結果卻并沒有相差很多。在f10的結果中，MHCSSA算法結果比SSA算法、CMA-ES算法、SaDE算法和GL25算法都優(yōu)秀，且與JADE算法結果十分接近。從整個實驗結果可以看出，MHCSSA算法表現都比SSA算法更好，且在大多數情況下與其它優(yōu)秀的超啟發(fā)式算法表現同樣優(yōu)秀。雖然在函數結果中MHCSSA算法并不是最優(yōu)秀的結果，但是與獲得最好結果的超啟發(fā)式算法結果非常接近，具有很強的競爭力。

4 結語

為了改進SSA算法在收斂速度和處理局部收斂方面的性能，本文提出了MHCSSA算法。通過多種群劃分協作的方法保證了種群的多樣性，同時在主群中引入貪婪搜索策略來優(yōu)化算法快速收斂的能力。在主群中的個體達到局部最優(yōu)情況時將被移出主群并移入到合適適應值范圍的子群中，而子群的個體達到子群設置的移出閾值時將會被移入到更高級分群中，保證了算法避免局部最優(yōu)和跳出早熟收斂的能力。仿真實驗結果顯示，MHCSSA算法的收斂速度和跳出早熟收斂能力比SSA算法表現更優(yōu)。同時在與CMA-ES、JADE、SaDE和GL-25等算法比較時，MHCSSA算法在優(yōu)化能力上同樣表現得非常優(yōu)秀，將會是非常有用的優(yōu)化工具。