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

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

0 引 言

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

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

和其他算法相比，原始BBO算法也存在一些較明顯的問題：遷移過程中對較優(yōu)解的直接復制，種群的多樣性不高；候選解受適應度值高的個別解強烈吸引，迭代后期出現(xiàn)多個解相近或是超級個體現(xiàn)象；算法早熟收斂等。因而學者專家也不斷對BBO算法進行不同程度的改進。在BBO算法的優(yōu)化方面，通常可分為以下幾類：基于遷移和突變操作的優(yōu)化[2-3]；與其他智能算法或精確算法雜交[4-6]；建立多種群或局部拓撲的BBO[7-8]。

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

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

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

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

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

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

圖1 BBO算法線性模型

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

(1)

(2)

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

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

(3)

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

2 共生生物搜索算法

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

(1)互利階段

(4)

(5)

(6)

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

(2)共棲階段

(7)

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

(3)寄生階段

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

3 改進的生物地理學優(yōu)化算法

3.1 改進思路

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

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

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

由于初始種群的生成是隨機且無向的，首先根據(jù)共生生物搜索算法中的互利操作，使初始種群進行初步優(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é)同進化生成的新的棲息地；Hi與Hj為隨機選取的棲息地；MV為兩個棲息地之間的互利向量；BF1和BF2∈{1, 2}為獲利因子。初始種群優(yōu)化過程如圖2所示。原始種群在可行域內(nèi)生成的位置是無向且隨機的，因而存在如圖中Hj遠離最優(yōu)解的解。而互利操作可以使Hi與Hj以不同的程度向最優(yōu)解靠近，從而使初始種群向最優(yōu)解范圍進化，進化程度由rand×(Hbest-MV×BF1或2)決定，這個程度是隨機的，并不會降低初始種群的隨機性。該優(yōu)化操作有利于減小初始解生成的隨機無向性，并加速對最優(yōu)解的尋找過程。

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

3.3 遷移算子改進

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

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

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

(11)

(12)

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

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

圖3 式(11)～(12)實驗結(jié)果

表1 pdmax和pdmin的取值

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

3.3.2 互利遷移算子

其他算法中針對遷移算子的改進如表2所示。

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

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

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

圖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é)同進化時一方進化程度高、一方進化程度低的情況，因而BF1和BF2∈{1, 2}，而Hceil(rand×(MV×BF1或2-1))則反映了當前棲息地和最優(yōu)棲息地之間的關(guān)系，進化過程表現(xiàn)了向最優(yōu)棲息地進化的過程;Hi_migration和Hk_migration為遷移生成的新的棲息地。這種協(xié)同進化的過程避免了單一棲息地的直接遷移復制的缺點，使兩個棲息地能夠協(xié)同進化，有利于增強種群的多樣性，并加速對最優(yōu)解的尋找過程。

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

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

(16)

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

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

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

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

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

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

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

改進的遷移算子偽代碼(算法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ù)變異概率進行變異，但是這種變異是隨機進行的，并不具有有向性，可能向好的方向變異，也可能向不好的方向變異，同時該過程對于提供優(yōu)秀解的貢獻較小。

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

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

圖7 突變算子修改

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

改進的突變算子偽代碼(算法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: 設置相關(guān)算法參數(shù)，初始化種群。

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

Step 3：開始迭代。

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

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

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

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

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

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

4 實驗與分析

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

表3 測試函數(shù)

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

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

表4 參數(shù)設置

對比算法分別為BBOPSODE[15]，BBO，ANLGBBO[8]，DGBBO[16]，如表5所示。對比數(shù)據(jù)分別為獨立運行30次后所求最優(yōu)值的平均值與標準差，粗體表示不同算法中的最優(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ù)。在標準差中，可以發(fā)現(xiàn)f1、f2、f5、f6的標準差結(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ù)。在標準差中，f3、f4、f7函數(shù)所得的標準差都最優(yōu)，而f8函數(shù)的標準差僅次于BBOPSODE算法。

由于不可分離函數(shù)相對于可分離函數(shù)而言，其適應度值由不同變量之間組合得到；而多峰函數(shù)相對于單峰函數(shù)更為復雜，有多個極值點。因而不可分離函數(shù)與多峰函數(shù)相對更加貼近于工程實際問題。從以上算法結(jié)果分析可得，針對多峰函數(shù)，SBBO算法的優(yōu)化均值結(jié)果和最小值在總多峰函數(shù)中占比為50%，標準差占比為75%；針對不可分離函數(shù)，SBBO算法的優(yōu)化均值、最小值、標準差結(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)象可得，該算法在前期收斂速度慢，增加了種群的多樣性，對未知解空間進行更多探索，從而使算法在后期能夠提升求解精度。同時，在迭代不同階段采用不同的選擇壓力，使前期收斂速度慢，后期收斂速度快。

圖10 不同BBO算法變化趨勢

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

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

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

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

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

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

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

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

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

4.4 SBBO算法復雜度分析

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

4.5 SBBO算法收斂速率分析

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

(18)

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

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

圖11 SBBO算法收斂速率圖

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

5 實例分析

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

5.1 反導WTA模型

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

(19)

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

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

5.2 戰(zhàn)局假設

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

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

5.3 結(jié)果分析

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

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

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

圖12 SBBO算法迭代趨勢圖

6 結(jié) 論

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

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