基于共生搜索的生物地理學(xué)優(yōu)化算法

朱曉雯，范成禮，盧盈齊，齊 鋮，李 威

(空軍工程大學(xué)，西安 710051)

0 引 言

由于精確算法在尋找復(fù)雜問題全局最優(yōu)解中的表現(xiàn)不佳，近幾十年來，各種模擬自然界現(xiàn)象的元啟發(fā)式算法被不斷提出，如粒子群算法、遺傳算法、人工蜂群算法、蟻群算法等。

生物地理學(xué)優(yōu)化[1](Biogeography-Based Optimization，BBO)算法是美國學(xué)者Simon于2008年首次提出的一種啟發(fā)式算法。Simon證明，相較于常見的GA，PSO，ACO等算法而言，其對候選解具有良好的挖掘能力和全局搜索能力，因而受到了眾多國內(nèi)外學(xué)者的關(guān)注。不同算法在求解全局最優(yōu)問題中都體現(xiàn)出不同的優(yōu)勢，但是由于“沒有免費(fèi)的午餐”，沒有哪一種算法在任何方面都表現(xiàn)良好，因而當(dāng)前算法的改進(jìn)點(diǎn)都集中在提升求解精度和效率，并使其盡可能優(yōu)于其他相關(guān)算法。

和其他算法相比，原始BBO算法也存在一些較明顯的問題：遷移過程中對較優(yōu)解的直接復(fù)制，種群的多樣性不高；候選解受適應(yīng)度值高的個別解強(qiáng)烈吸引，迭代后期出現(xiàn)多個解相近或是超級個體現(xiàn)象；算法早熟收斂等。因而學(xué)者專家也不斷對BBO算法進(jìn)行不同程度的改進(jìn)。在BBO算法的優(yōu)化方面，通?？煞譃橐韵聨最悾夯谶w移和突變操作的優(yōu)化[2-3]；與其他智能算法或精確算法雜交[4-6]；建立多種群或局部拓?fù)涞腂BO[7-8]。

與其他智能算法或精確算法雜交是優(yōu)化算法的有效手段。本文引入共生生物搜索算法對原始BBO算法進(jìn)行優(yōu)化。共生生物搜索(Symbiotic Organisms Search，SOS)算法是Cheng等[9]于2014年提出的一種新型啟發(fā)式算法。該算法模擬了生物體在生態(tài)系統(tǒng)中生存和繁殖所采取的共生互動策略，具有較強(qiáng)的魯棒性和尋優(yōu)能力。

為解決原始BBO算法存在的問題，更好地平衡算法的集約化和多樣化搜索能力，本文汲取BBO算法和SOS算法的共性特點(diǎn)和互補(bǔ)優(yōu)勢，對BBO算法中的遷移和變異操作進(jìn)行改進(jìn)，提出基于共生搜索的生物地理學(xué)優(yōu)化算法。SOS算法與BBO算法都受進(jìn)化理論的啟發(fā)而產(chǎn)生，理論上具有同源性，兩種算法都不需要特定參數(shù)；BBO算法的優(yōu)勢在于不同棲息地之間的信息共享，SOS算法中生物共享優(yōu)勢協(xié)同進(jìn)化的功能可以較好地促進(jìn)BBO算法發(fā)揮特點(diǎn)。

反導(dǎo)WTA問題是經(jīng)典的復(fù)雜全局優(yōu)化問題，多種啟發(fā)式算法被應(yīng)用于求解該類問題。羅銳涵等[10]對BBO算法增加了三維變異操作，對火力分配方案進(jìn)行優(yōu)化，增加了對于方案的全局搜索能力。本文以導(dǎo)彈突防過程中的武器目標(biāo)分配為背景，進(jìn)行仿真實(shí)例應(yīng)用。實(shí)例中進(jìn)一步表明，該優(yōu)化算法相較于原始算法和其他相關(guān)算法，較好地平衡了全局搜索和局部搜索的能力，并且一定程度上有利于提升求解精度和效率。

1 原始的生物地理學(xué)優(yōu)化算法

BBO算法模擬了自然界中物種在不同島嶼之間的遷移，島嶼在BBO算法中被稱為“棲息地(Habitat)”，那些被認(rèn)為適合物種居住的棲息地有著較高的棲息地適宜指數(shù)(Habitat Suitability Index，HSI)，與這個指數(shù)有關(guān)的因素有降雨、植被多樣性等，這些因素被稱為適宜性指數(shù)變量(Suitability Index Variables，SIVs)。SIV可以看作是棲息地的自變量，HSI可以看作為因變量。

BBO算法線性模型如圖1所示。HSI高的棲息地物種數(shù)量多，遷入率低、遷出率高；HSI低的棲息地物種數(shù)量少，遷入率高，遷出率低。因而遷移率可以作為物種遷移的標(biāo)準(zhǔn)。

圖1 BBO算法線性模型

BBO算法的遷移過程可以描述為

(1)

(2)

式中：μk為第k個棲息地的遷出率；λk為第k個棲息地的遷入率；E為最大遷出率；I為最大遷入率；k為第k個棲息地當(dāng)前的物種數(shù)量；n為最大物種數(shù)量。遷入率和遷出率都取決于棲息地的物種數(shù)量。

此外，BBO算法中，為了實(shí)現(xiàn)種群的多樣性，種群的內(nèi)部會進(jìn)行變異操作，概率為

(3)

式中：m(k)為第k個棲息地的變異率；mmax為用戶定義的最大變異修改概率；Pk為當(dāng)前物種數(shù)量概率；Pmax=max(Pi)。

2 共生生物搜索算法

SOS算法體現(xiàn)了生態(tài)系統(tǒng)中的不同生物體互利共生、協(xié)同進(jìn)化的特點(diǎn)，主要由三個階段構(gòu)成：

(1)互利階段

(4)

(5)

(6)

式中：Xi與Xj為兩個候選解；rand為(0，1)之間的隨機(jī)數(shù)；由于兩個生物之間相互作用時(shí)總存在一方獲取收益大，另一方獲取收益小的情況，因而獲利因子BF1和BF2∈{1，2}；MV為生物之間的互利向量，體現(xiàn)了Xi與Xj之間的關(guān)系特征。

(2)共棲階段

(7)

式中：隨機(jī)選擇的候選解Xj與Xi進(jìn)行互動，生物Xi從與Xj的互動中獲益，而Xj未受到影響；(Xbest-Xj)體現(xiàn)了Xj幫助Xi提升至最優(yōu)解的最大程度。

(3)寄生階段

在此階段中，Xi為寄生變量，Xj為生態(tài)系統(tǒng)中隨機(jī)選擇的寄生變量的宿主，Xi試圖取代生態(tài)系統(tǒng)中的Xj。通過對Xi和Xj兩種生物體的適應(yīng)度進(jìn)行評估，如果Xi比Xj有更好的適應(yīng)性，則會替代Xj，否則Xj將保留。

3 改進(jìn)的生物地理學(xué)優(yōu)化算法

3.1 改進(jìn)思路

BBO算法存在一些固有的問題：(1)初始種群的生成具有隨機(jī)性；(2)遷移機(jī)制中在棲息地的選擇中使用輪盤賭的方式，存在很大的隨機(jī)性，且耗時(shí)長、計(jì)算復(fù)雜度高；(3)遷移操作中通過對已選擇的SIV特征進(jìn)行直接復(fù)制，導(dǎo)致在整個優(yōu)化迭代的過程中對新解的勘探能力有限，容易被個別HSI很高的精英解強(qiáng)烈吸引，從而出現(xiàn)超級個體或過早收斂的情況；(4)突變操作對種群后半部分較差解進(jìn)行變異，這個變異方向是隨機(jī)的，無法保證向優(yōu)質(zhì)解方向變異，且對于新解的探索貢獻(xiàn)不足。

針對以上問題，本文以BBO算法為主，引入SOS算法中的思想，對BBO算法的核心步驟：遷移操作和突變操作進(jìn)行改進(jìn)，提出SBBO算法。首先，對初始種群進(jìn)行優(yōu)化；其次，在遷移機(jī)制中，對棲息地選擇進(jìn)行動態(tài)調(diào)整，引入余弦自適應(yīng)框架，并與SOS算法中互利操作進(jìn)行融合；突變操作中，引入SOS算法中的共棲操作對原始突變進(jìn)行優(yōu)化。仿真實(shí)例表明，SBBO算法有利于擴(kuò)大種群多樣性，同時(shí)可提高算法的求解精度和效率。

3.2 初始種群優(yōu)化

由于初始種群的生成是隨機(jī)且無向的，首先根據(jù)共生生物搜索算法中的互利操作，使初始種群進(jìn)行初步優(yōu)化，便于對優(yōu)質(zhì)解的探索:

Hi_new=Hi+rand×(Hbest-MV×BF1)

(8)

Hj_new=Hj+rand×(Hbest-MV×BF2)

(9)

(10)

式中：Hi_new和Hj_new為經(jīng)過互利操作協(xié)同進(jìn)化生成的新的棲息地；Hi與Hj為隨機(jī)選取的棲息地；MV為兩個棲息地之間的互利向量；BF1和BF2∈{1, 2}為獲利因子。初始種群優(yōu)化過程如圖2所示。原始種群在可行域內(nèi)生成的位置是無向且隨機(jī)的，因而存在如圖中Hj遠(yuǎn)離最優(yōu)解的解。而互利操作可以使Hi與Hj以不同的程度向最優(yōu)解靠近，從而使初始種群向最優(yōu)解范圍進(jìn)化，進(jìn)化程度由rand×(Hbest-MV×BF1或2)決定，這個程度是隨機(jī)的，并不會降低初始種群的隨機(jī)性。該優(yōu)化操作有利于減小初始解生成的隨機(jī)無向性，并加速對最優(yōu)解的尋找過程。

圖2 初始種群優(yōu)化

3.3 遷移算子改進(jìn)

3.3.1 基于動態(tài)選擇的遷移算子

在BBO算法對遷出的棲息地選擇中，主要采取輪盤賭的方式，這種選擇概率都是隨機(jī)的，無法根據(jù)不同迭代階段進(jìn)行相應(yīng)的變化，容易造成種群的多樣性不高、算法過早局部收斂的問題。

因而本文設(shè)置了棲息地動態(tài)選擇策略，即在不同的階段中，進(jìn)行遷入遷出操作時(shí)，規(guī)定不同的選擇壓力。在早期, 縮小選擇壓力，使HSI值較低但可能含有優(yōu)秀SIV因素的棲息地能夠更多地參與到遷移過程中，保持種群的多樣性；在后期, 適當(dāng)增加選擇壓力，使種群能夠較快收斂，從而更加趨近最優(yōu)解。本文提出以下選擇概率：

(11)

(12)

式中：Pk為第k個解被選擇進(jìn)行遷出的概率；μk為當(dāng)前棲息地的遷出率；n為種群數(shù)量；μi為任意第i個棲息地的遷出率；G為當(dāng)前迭代次數(shù)；Gmax為最大迭代次數(shù)；a為選擇壓力因子；pdmax為選擇壓力因子的變化初始值；pdmin為選擇壓力因子的變化終值。

pdmax和pdmin為定常參數(shù)，為測試pdmax和pdmin對算法性能的影響，選擇具有代表性的多峰不可分Ackley測試函數(shù)進(jìn)行實(shí)驗(yàn)。表1和圖3顯示了不同取值的pdmax和pdmin對整體優(yōu)化效果的影響。可以看出，pdmax和pdmin取值對算法整體尋優(yōu)趨勢有較大的影響，當(dāng)pdmax=0.9，pdmin=0.1時(shí), 優(yōu)化效果最佳。其原因是在迭代前期收斂速度慢，后期收斂速度快，同時(shí)求解精度增加，符合壓力選擇的原則。

圖3 式(11)～(12)實(shí)驗(yàn)結(jié)果

表1 pdmax和pdmin的取值

改進(jìn)后, 動態(tài)棲息地選擇公式前期收斂速度慢，有利于進(jìn)行全局搜索；后期收斂速度快，有利于加強(qiáng)局部搜索，取得的結(jié)果也較優(yōu)，并且較原始BBO算法的棲息地選擇上有較大改善。

3.3.2 互利遷移算子

其他算法中針對遷移算子的改進(jìn)如表2所示。

表2 其他算法中BBO遷移算子修改回顧

表2中，α，F(xiàn)為文中確定的隨機(jī)參數(shù)；t為當(dāng)前迭代次數(shù)；T為最大迭代次數(shù)；k為最大種群數(shù)；k1,k2,k3為原文中選取的棲息地。

綜合以上遷移操作的修改來看，主要是通過將選擇的遷入地進(jìn)行修改或者是多個棲息地按照一定的比例進(jìn)行遷入，然而遷入和遷出的棲息地在進(jìn)化中并不是完全孤立的。在自然界中，兩個不同的棲息地也可能因?yàn)檫w入的物種而發(fā)生適應(yīng)性的變化，從而使兩者的適應(yīng)性程度得到提升。受這一思想啟發(fā)，本文引入SOS算法中的互利操作。如圖4所示，針對第j維的棲息地，左側(cè)是原始BBO算法的遷移過程，右側(cè)是對選擇的遷入地和遷出地進(jìn)行互利進(jìn)化，二者都吸收相互間的有利因素，通過互相學(xué)習(xí)和反饋，進(jìn)行協(xié)同進(jìn)化:

圖4 遷移算子修改

Hi_migration=Hceil(rand×(MV×BF1-1))

(13)

Hk_migration=Hceil(rand×(MV×BF2-1)

(14)

(15)

式中：Hi和Hk為選擇的遷入地和遷出地；MV為兩個棲息地之間的互利向量，體現(xiàn)了兩個棲息地之間的關(guān)系特征；BF1和BF2為獲利因子，體現(xiàn)了兩個棲息地協(xié)同進(jìn)化時(shí)一方進(jìn)化程度高、一方進(jìn)化程度低的情況，因而BF1和BF2∈{1, 2}，而Hceil(rand×(MV×BF1或2-1))則反映了當(dāng)前棲息地和最優(yōu)棲息地之間的關(guān)系，進(jìn)化過程表現(xiàn)了向最優(yōu)棲息地進(jìn)化的過程;Hi_migration和Hk_migration為遷移生成的新的棲息地。這種協(xié)同進(jìn)化的過程避免了單一棲息地的直接遷移復(fù)制的缺點(diǎn)，使兩個棲息地能夠協(xié)同進(jìn)化，有利于增強(qiáng)種群的多樣性，并加速對最優(yōu)解的尋找過程。

3.3.3 余弦自適應(yīng)框架的優(yōu)化遷移算子

為進(jìn)一步提升BBO算法在不同階段的搜索能力，在前期以互利遷移算子為主，后期以動態(tài)選擇策略遷移算子為主。本文利用余弦自適應(yīng)策略將互利遷移算子與動態(tài)選擇遷移算子融合，提出改進(jìn)的余弦動態(tài)自適應(yīng)因子：

(16)

圖5反映了余弦動態(tài)自適應(yīng)因子的變化趨勢，呈現(xiàn)震蕩的動態(tài)變化規(guī)律以及總體下降收斂的趨勢。當(dāng)隨機(jī)概率大于α?xí)r，采用基于動態(tài)選擇策略優(yōu)化的遷移算子進(jìn)行修改；當(dāng)隨機(jī)概率小于α?xí)r，采用互利遷移算子對棲息地進(jìn)行優(yōu)化。

圖5 遷移算子修改余弦動態(tài)自適應(yīng)因子變化趨勢

基于余弦自適應(yīng)框架的遷移算子有以下優(yōu)化性能：

(1)在迭代前期主要采用互利遷移進(jìn)行修改，該算子被選擇進(jìn)行修改棲息地的概率很大，有利于維持種群的多樣性，避免局部最優(yōu)的出現(xiàn)。

(2)在后期運(yùn)用動態(tài)選擇策略遷移算子進(jìn)行修改，這種動態(tài)選擇策略較大程度結(jié)合了原始算法的特點(diǎn)，利于算法收斂。

(3)余弦動態(tài)自適應(yīng)因子總體震蕩變化的趨勢避免了修改策略的單一性，同時(shí)也有利于對未知區(qū)域的探索，使棲息地中并不是特別優(yōu)秀的個體有一定的生存概率，避免了全部被修改替代從而出現(xiàn)相近和重復(fù)的現(xiàn)象。

該遷移算子偽代碼如下：Population為整個種群；rand為[0，1]中的隨機(jī)數(shù)；n為種群數(shù)量；d為種群維度；pmodify為遷移修改率；lp為變量取值下界；up為變量取值上界。

改進(jìn)的遷移算子偽代碼(算法1)如圖6所示。

Input: Population, n, d, λ, μ, α, pmodify, lp, up1 for i=1 to n do2 if rand > pmodify then3 continue4 for j=1 to d do5 if rand< λ then6 if rand<= α then7 Renovate habitati (SIVj) with equation(13)～(15) base on the restriction(lp, up)8 Else 9 Renovate habitati (SIVj) with equation(11)～(12) base on the restriction(lp, up)10 Else11 habitati(SIVj)=habitati(SIVj) Output: Population

3.4 共棲突變算子

原始BBO算法中的變異操作主要對HSI排序后較差的后一半解根據(jù)變異概率進(jìn)行變異，但是這種變異是隨機(jī)進(jìn)行的，并不具有有向性，可能向好的方向變異，也可能向不好的方向變異，同時(shí)該過程對于提供優(yōu)秀解的貢獻(xiàn)較小。

為減小變異的隨機(jī)性，引入SOS算法中的共棲思想，即針對后半部分的較差解，從前半部分較優(yōu)解中隨機(jī)選擇對象進(jìn)行互動，從而獲利并增強(qiáng)自身適應(yīng)性程度：

Hi_mutation=Hi+rand×(-1, 1)×(Hbest-Hk)

k=round(length(n/2)×rand)

s.t.i∈(n/2,n),k∈(0,n/2)

(17)

式中：Hi_mutation為當(dāng)前變異操作后新生成的棲息地；Hi為選擇的當(dāng)前進(jìn)行變異操作的棲息地；Hbest為當(dāng)前迭代過程中的最優(yōu)棲息地；Hk為隨機(jī)選擇的HSI前n/2中的一個棲息地。針對HSI排序較后的一半棲息地，通過向前變異，在HSI排序的前n/2個棲息地中隨機(jī)選擇共棲對象，通過與之互動從中獲益，(Hbest-Hk)體現(xiàn)了Hk幫助Hi提升至最優(yōu)解的最大程度，該變異過程如圖7所示。

圖7 突變算子修改

該突變算子偽代碼如下：Population為整個種群；n為種群數(shù)量；d為種群維度；lp為變量取值下界；up為變量取值上界；Pk為突變概率。

改進(jìn)的突變算子偽代碼(算法2)如圖8所示。

Input: Population, n, d, λ, μ, lp, up1 Use λk and μk to compute the probability Pk2 Use HSI to rank the population3 for i = n/2 to n do4 for j = 1 to d do5 if Pk > rand then6 Renovate habitati(SIVj)with equation(17)base on the restriction(lp, up) Output: Population

3.5 SBBO算法流程

SBBO算法流程圖如圖9所示，具體流程為

圖9 SBBO算法流程圖

Step 1: 設(shè)置相關(guān)算法參數(shù)，初始化種群。

Step 2: 計(jì)算每個棲息地的HSI值，并由優(yōu)到劣進(jìn)行排列。同時(shí)保留q個精英解。

Step 3：開始迭代。

Step 4：根據(jù)互利操作對初始解進(jìn)行優(yōu)化。

Step 5：根據(jù)算法1進(jìn)行遷移操作。

Step 6：根據(jù)算法2進(jìn)行突變操作。

Step 7：重新計(jì)算棲息地HSI并確保解可行性。

Step 8: 對棲息地重新排列，并將保存的q個精英解替換最差q個解。

Step 9: 判斷是否達(dá)到最大迭代次數(shù)，如果是，則輸出結(jié)果；如果不是，則返回Step 3。

4 實(shí)驗(yàn)與分析

為比較不同算法的優(yōu)劣，選取了包含單峰、多峰、可分、不可分離函數(shù)的測試集，如表3所示。該測試集來源為文獻(xiàn)[14]中的基準(zhǔn)測試函數(shù)，包含2個單峰函數(shù)、2個多峰函數(shù)、2個可分離函數(shù)、2個不可分離函數(shù)。類別一欄中，U表示單峰函數(shù)，M表示多峰函數(shù)，S表示可分離函數(shù)，N表示不可分離函數(shù)。本文主要從以下兩方面對算法進(jìn)行仿真實(shí)驗(yàn)和數(shù)據(jù)分析：(1)SBBO算法與BBO算法及變體的優(yōu)化性能進(jìn)行對比分析；(2)不同維度下SBBO算法的優(yōu)化性能分析。

表3 測試函數(shù)

4.1 與BBO算法及變體的優(yōu)化性能對比

在8個測試函數(shù)中，分別對包括BBO和SBBO在內(nèi)的5種BBO算法進(jìn)行優(yōu)化性能的實(shí)驗(yàn)。本實(shí)驗(yàn)隨機(jī)生成100個30維種群，迭代200次，并獨(dú)立運(yùn)行30次，相關(guān)參數(shù)及取值如表4所示。

表4 參數(shù)設(shè)置

對比算法分別為BBOPSODE[15]，BBO，ANLGBBO[8]，DGBBO[16]，如表5所示。對比數(shù)據(jù)分別為獨(dú)立運(yùn)行30次后所求最優(yōu)值的平均值與標(biāo)準(zhǔn)差，粗體表示不同算法中的最優(yōu)結(jié)果。分析表5可得，相同的測試環(huán)境中，SBBO算法所得的結(jié)果要明顯優(yōu)于其他幾種算法。

表5 不同BBO算法測試結(jié)果對比

針對單峰函數(shù)f1、f2、f5、f6而言，SBBO算法所得結(jié)果的均值與最小值都在幾種算法中最優(yōu)，并且相較于BBO算法，求解的精度有了明顯提升。其中，f1函數(shù)中體現(xiàn)最為明顯，SBBO算法所得的平均值約為原始算法的1/7。f1、f5為可分離函數(shù)；f2、f6為不可分離函數(shù)。在標(biāo)準(zhǔn)差中，可以發(fā)現(xiàn)f1、f2、f5、f6的標(biāo)準(zhǔn)差結(jié)果均優(yōu)于其他幾種算法。

針對多峰函數(shù)f3、f4、f7、f8而言，SBBO算法在f3、f4中的均值和最小值在幾種算法中最優(yōu)，而在f7、f8函數(shù)中得到的均值和最小值僅次于ANLGBBO算法。相較于BBO算法，SBBO算法求解精度也得到大幅度提升，其中f3函數(shù)得到的均值約為原始函數(shù)的1/2。f3、f7為可分離函數(shù)；f4、f8為不可分離函數(shù)。在標(biāo)準(zhǔn)差中，f3、f4、f7函數(shù)所得的標(biāo)準(zhǔn)差都最優(yōu)，而f8函數(shù)的標(biāo)準(zhǔn)差僅次于BBOPSODE算法。

由于不可分離函數(shù)相對于可分離函數(shù)而言，其適應(yīng)度值由不同變量之間組合得到；而多峰函數(shù)相對于單峰函數(shù)更為復(fù)雜，有多個極值點(diǎn)。因而不可分離函數(shù)與多峰函數(shù)相對更加貼近于工程實(shí)際問題。從以上算法結(jié)果分析可得，針對多峰函數(shù)，SBBO算法的優(yōu)化均值結(jié)果和最小值在總多峰函數(shù)中占比為50%，標(biāo)準(zhǔn)差占比為75%；針對不可分離函數(shù)，SBBO算法的優(yōu)化均值、最小值、標(biāo)準(zhǔn)差結(jié)果在總多峰函數(shù)中占比為75%?？傮w分析可得，相較于其他幾種優(yōu)化算法，SBBO算法在多峰函數(shù)和不可分離函數(shù)中總體表現(xiàn)良好。

圖10展示了8個測試函數(shù)在不同算法中經(jīng)過200次迭代后的變化趨勢。分析可得，在f1、f2、f3、f4、f5、f7函數(shù)中，SBBO算法所得結(jié)果優(yōu)于其他算法；在f6函數(shù)中，SBBO算法所得結(jié)果僅次于ANLGBBO算法，并且兩者結(jié)果極為接近。從圖10可以發(fā)現(xiàn)，SBBO算法在初期的迭代過程中求解精度與收斂速度有略次于其他算法的趨勢，但在迭代后期，SBBO算法的收斂速度和求解精度都明顯高于其他算法，符合本文算法提出的初衷。分析這種現(xiàn)象可得，該算法在前期收斂速度慢，增加了種群的多樣性，對未知解空間進(jìn)行更多探索，從而使算法在后期能夠提升求解精度。同時(shí)，在迭代不同階段采用不同的選擇壓力，使前期收斂速度慢，后期收斂速度快。

圖10 不同BBO算法變化趨勢

4.2 不同維度下BBO算法優(yōu)化性能對比

表6隨機(jī)選取了f1、f2、f4、f7函數(shù)在BBO算法與SBBO算法中不同維度下求解的結(jié)果，這4個函數(shù)分別為單峰可分離、單峰不可分離、多峰不可分離、多峰可分離函數(shù)。運(yùn)行參數(shù)設(shè)置同4.1節(jié)，分別獨(dú)立運(yùn)行30次。

分析表6可得，相較于原始BBO算法，SBBO算法在高維函數(shù)的求解中，性能普遍得到提高。在對f1、f2函數(shù)的30/50/100維、f4函數(shù)的30/100維、f7函數(shù)的30/50維下的求解結(jié)果中，SBBO算法所求的均值、標(biāo)準(zhǔn)差、最小值的結(jié)果均最優(yōu)。在f4函數(shù)的50維和f7函數(shù)的100維結(jié)果中，SBBO算法的標(biāo)準(zhǔn)差略高于原始BBO算法，穩(wěn)定性表現(xiàn)略有不足。綜合以上數(shù)據(jù)可得，在高維度下，SBBO算法在4種函數(shù)中表現(xiàn)均較為良好。

表6 不同維度算法測試結(jié)果對比

由于高維函數(shù)中，函數(shù)復(fù)雜度的數(shù)量級會相應(yīng)地提升，通過不同函數(shù)在30/50/100維的情況下進(jìn)行對比，所得結(jié)果驗(yàn)證了SBBO算法在求解高維問題中求解精度與效率的穩(wěn)定性，與改進(jìn)策略中對于新解的探索開發(fā)能力的提升有關(guān)。本文算法的優(yōu)化進(jìn)一步提升了算法的尋優(yōu)能力。

4.3 SBBO算法與其他不同算法性能對比

針對PSO，GA，ACO三種算法與SBBO算法進(jìn)行對比實(shí)驗(yàn)，測試函數(shù)與運(yùn)行參數(shù)同4.1節(jié)，分別獨(dú)立運(yùn)行30次，粗體表示對比實(shí)驗(yàn)中的較優(yōu)結(jié)果，如表7所示。

分析表7數(shù)據(jù)可得，在f1～f7測試函數(shù)中，SBBO算法在平均值、標(biāo)準(zhǔn)差與最小值幾個方面所得結(jié)果均優(yōu)于PSO，GA和ACO算法；在f8測試函數(shù)中，SBBO算法所得的標(biāo)準(zhǔn)差結(jié)果次于PSO, GA和ACO算法，而平均值和最小值優(yōu)于其他幾種算法。綜合以上數(shù)據(jù)，可以得到, SBBO算法求解精度要顯著優(yōu)于其他幾種算法。

表7 不同算法測試結(jié)果對比

4.4 SBBO算法復(fù)雜度分析

本文算法每一代復(fù)雜度主要由種群初始化、精英解保留、遷移操作、變異操作四部分組成。設(shè)種群規(guī)模為M，維度是N，則種群初始化時(shí)間復(fù)雜度為O(M)，精英解的保留過程時(shí)間復(fù)雜度為O(1)，遷移過程的時(shí)間復(fù)雜度為O(MN1)，變異過程時(shí)間復(fù)雜度為O(MN2)。在一個時(shí)間步驟中，總的實(shí)際復(fù)雜度最差為O(M)+O(1)+O(MN1)+O(MN2)=O(M+1+MN1+MN2)=O(MN), 與原始BBO算法的最差時(shí)間復(fù)雜度相差不大。

4.5 SBBO算法收斂速率分析

文獻(xiàn)[17]中提出新的度量進(jìn)化算法收斂速度的方法——平均收斂速度。具體操作過程為：針對最大化或者最小化問題，將進(jìn)化算法看作一個迭代過程，首先構(gòu)造一個初始解種群Φ0，然后生成一系列種群序列Φ1,Φ2,Φ3等，重復(fù)這個過程，并將找到的最佳解決方案存檔。用f(Φt)表示種群Φt的最佳適應(yīng)度值，因?yàn)槠涫请S機(jī)變量，因而考慮其均值ft=E[f(Φt)]，令fopt表示最佳適應(yīng)度值，則進(jìn)化算法在t次迭代后的平均收斂速率為

(18)

若出現(xiàn)f0=fopt的情況，則設(shè)R(t|Φ0)=1。

根據(jù)以上平均收斂速率定義選取Sphere，SumPower，Griewank，Rosenbrock四種不同類型的測試函數(shù)，運(yùn)行參數(shù)設(shè)置同4.1節(jié)，分別獨(dú)立運(yùn)行30次，可以得到如圖11所示的平均收斂速率圖像。

圖11 SBBO算法收斂速率圖

分析圖11可得，在本文提到的單峰、多峰、可分離、不可分離函數(shù)中，隨著迭代次數(shù)的增加，運(yùn)用本文算法均可使目標(biāo)函數(shù)收斂。

5 實(shí)例分析

反導(dǎo)過程中的武器目標(biāo)分配(weapon target assignment, WTA)問題對于作戰(zhàn)決策起著重要的作用，如何合理利用現(xiàn)有資源、分配已有兵力和武器單元來打擊敵來襲目標(biāo)，從而達(dá)到最優(yōu)作戰(zhàn)效果是WTA問題的主要內(nèi)容。由于反導(dǎo)WTA是一個NP-hard問題，因而本文將SBBO算法應(yīng)用于求解反導(dǎo)WTA問題。

5.1 反導(dǎo)WTA模型

反導(dǎo)WTA模型的目標(biāo)是在最大化毀傷目標(biāo)價(jià)值的基礎(chǔ)上最小化作戰(zhàn)代價(jià)。為簡化模型、便于分析，將打擊風(fēng)險(xiǎn)性作為作戰(zhàn)代價(jià)函數(shù)，提出最大化費(fèi)效比函數(shù)如下：

(19)

式中：Xij∈Z，i=1, 2, …,n,j=1, 2, …,m；maxE為最大化毀傷目標(biāo)價(jià)值；minR為最小化作戰(zhàn)代價(jià)；n為武器平臺的數(shù)量；m為第j個來襲目標(biāo)數(shù)量；Vj為第j批目標(biāo)的威脅度，0≤Vj≤1；Pij為第i個武器平臺被第j個目標(biāo)毀傷的直接概率，0≤Pij≤1；Xij為第i個武器平臺對第j個目標(biāo)使用的火力數(shù)量，形成關(guān)系矩陣[Xij]m×n；Rij為第i個武器平臺對第j個來襲目標(biāo)進(jìn)行打擊的風(fēng)險(xiǎn)性。

該函數(shù)模型約束條件有：每種反導(dǎo)武器系統(tǒng)可以同時(shí)打擊多個敵來襲目標(biāo)，且多種武器系統(tǒng)可以打擊同一敵來襲目標(biāo)；每個來襲目標(biāo)至少分配一個火力；每個武器平臺配備多個火力，同一作戰(zhàn)時(shí)間內(nèi)每個武器平臺對來襲目標(biāo)分配的火力不能超過該武器平臺的火力總數(shù)。

5.2 戰(zhàn)局假設(shè)

為考察SBBO算法求解武器分配問題的尋優(yōu)性能，給出以下實(shí)例：假設(shè)某次導(dǎo)彈突防過程中我方武器平臺數(shù)量4，敵方目標(biāo)數(shù)量4，對應(yīng)火力單元數(shù)量為(8，10，8，10)，不同目標(biāo)對于武器平臺的威脅度分別為(0.58，0.67，0.78，0.48)。武器-目標(biāo)分配參數(shù)如表8所示。參數(shù)設(shè)置為：種群100，突變率0.05，迭代300次。

表8 武器-目標(biāo)分配參數(shù)

5.3 結(jié)果分析

表9為應(yīng)用SBBO算法求解反導(dǎo)WTA問題得到的最終分配結(jié)構(gòu)。

表9 武器-目標(biāo)最終分配結(jié)構(gòu)

圖12為本文算法求解反導(dǎo)WTA問題的迭代趨勢圖，對比算法為原始BBO算法?？梢钥闯?，SBBO算法在前期收斂速度較慢，后期收斂速度加快且解的HSI值要更高，說明改進(jìn)后的遷移和突變算子在前期增加了解的多樣性，后期增加了解的求解精度，較原始BBO算法有更強(qiáng)的全局搜索能力和收斂速度。

圖12 SBBO算法迭代趨勢圖

6 結(jié) 論

生物地理學(xué)的優(yōu)化算法在解決全局優(yōu)化問題中具有無需參數(shù)、編碼簡單、靈活的優(yōu)點(diǎn)，但也存遷移機(jī)制中隨機(jī)性強(qiáng)、耗時(shí)較長、計(jì)算復(fù)雜度高、特征直接復(fù)制, 突變機(jī)制中變異方向隨機(jī)、對于新解的探索貢獻(xiàn)不足的缺點(diǎn)。

本文提出的SBBO算法，對初始隨機(jī)種群進(jìn)行了優(yōu)化，提出余弦自適應(yīng)框架下的動態(tài)選擇遷移和互利遷移優(yōu)化算子；同時(shí)，提出共棲變異算子，對原始BBO算法進(jìn)行優(yōu)化，一定程度上解決了原始BBO算法存在的問題，更好地平衡了算法的集約化和多樣化搜索能力?；鶞?zhǔn)測試函數(shù)與仿真實(shí)例表明，該優(yōu)化算法相較于原始算法和相關(guān)算法，較好地平衡了全局搜索和局部搜索的能力，并且有利于提升求解精度和效率，適應(yīng)高維復(fù)雜問題的求解，有利于解決復(fù)雜工程問題。