李蒙蒙，秦 偉，劉 藝*，刁興春

（1.中國人民解放軍軍事科學院國防科技創(chuàng)新研究院，北京 100071；2.天津（濱海）人工智能軍民融合創(chuàng)新中心，天津 300457）

0 引言

人工智能的發(fā)展、新基建的提出使得數據規(guī)模不斷增長，數據分類是重要的機器學習問題，它廣泛存在于各類應用中，如故障診斷、相似重復記錄檢測，以及目標檢測等［1-3］。特征選擇是常用的數據分類預處理方法，通過特征選擇能夠降低分類模型的訓練時間和數據的獲取復雜性，進一步減少數據的存儲需求，顯著提升分類算法的性能［4］。隨著數據分類研究的發(fā)展，特征選擇的研究也得到了廣泛的關注［5-7］。按照是否與分類器獨立，特征選擇可以分為過濾法（Filter）、包裝法（Wrapper）和混合法（Hybrid）。采用演化算法進行特征選擇是一類重要的包裝法，該類方法具有較好的性能且易于部署實現，在實際工程中得到了普遍的應用［8-10］。

蟻群優(yōu)化（Ant Colony Optimization，ACO）是一種成熟的演化算法，自提出以來已經在諸多領域發(fā)揮了作用，如路徑選擇問題、水氣交替注入、實體分辨，以及特征選擇等［11-14］。由于特征選擇是典型的離散優(yōu)化問題，而蟻群優(yōu)化是天然的離散優(yōu)化算法，因此特征選擇是蟻群優(yōu)化較為重要的研究方向。與其他演化算法相似，蟻群優(yōu)化在求解問題較為復雜時會陷入局部最優(yōu)，阻礙應用性能的進一步提升。

由Shi等［15］提 出 的 頭 腦 風 暴 優(yōu) 化（Brain Storm Optimization，BSO）是近年來出現的性能優(yōu)異的演化算法。與其他模仿生物遺傳和覓食等群體行為的演化算法不同，頭腦風暴優(yōu)化模擬人類通過交流互動提出新方法的頭腦風暴過程，能夠在全局探索（Exploration）和局部開發(fā)（Exploitation）之間達到較好的平衡。

為了進一步提升蟻群優(yōu)化求解特征選擇問題的性能，提出一種結合頭腦風暴優(yōu)化的混合蟻群優(yōu)化（Ant colony optimization with Brain storm Optimization，ABO）算法，設置信息交流檔案，提出基于松弛因子的時間最久優(yōu)先方法，動態(tài)維護一定數量的較好路徑解，提出基于Fuch混沌映射的路徑-想法轉換算子，在蟻群優(yōu)化的全局最優(yōu)解多次未更新時，將檔案中的路徑解轉換為想法解，并將其作為初始種群，采用頭腦風暴優(yōu)化在更廣闊的空間中搜索較好解，提升算法的尋優(yōu)性能。通過6組典型的二分類數據集，對本文提出算法與其他2種混合優(yōu)化方法和經典遺傳算法進行對比實驗，并對松弛因子和全局最優(yōu)解未更新次數進行敏感性分析，實驗結果表明ABO算法具有較強的優(yōu)越性。

1 相關理論

1.1 蟻群優(yōu)化

蟻群優(yōu)化的本質是，在尋找食物的過程中，每只螞蟻都會在訪問過的路徑上釋放一種稱為“信息素”的物質，信息素會隨著時間的推移不斷蒸發(fā)，蟻群中的螞蟻可以感知到每條路徑中的信息素濃度，并以較大概率選擇濃度較高的路徑，之后會沿著選擇的路徑搜索食物，并在該路徑上釋放信息素。通過該方式，螞蟻就能夠尋找到食物與巢穴之間的最短路徑。在特征選擇問題中，所有特征構成了解空間，螞蟻根據特征的先驗信息和其對應的信息素濃度，選擇可行的特征子集，通?？梢圆捎锰卣髯蛹姆诸愋阅茏鳛閮?yōu)化目標和信息素濃度更新依據，通過更新信息素濃度提升選擇較好特征的概率。

在演化算法中，連續(xù)域優(yōu)化算法較多，如遺傳算法、粒子群算法、蝙蝠算法等，它們在解決離散優(yōu)化問題時需要進行合適的離散化［16］。而蟻群優(yōu)化是天然的離散優(yōu)化算法，在解決離散優(yōu)化問題上具有較好的性能。它首先在旅行商問題上獲得了成功的應用，隨后被應用到背包問題、資源分配問題以及特征選擇問題等優(yōu)化問題中。同時，蟻群優(yōu)化釋放信息素的信息正反饋機制符合“優(yōu)化時學習”的準則，因此具有較強的搜索性能［17］。此外，在蟻群優(yōu)化中，所有螞蟻獨立地通過信息素和啟發(fā)式先驗信息生成路徑解，具有內在分布式的特性，從而可以進行大規(guī)模的并行計算。正是由于蟻群優(yōu)化的特點，使得該方法在特征選擇和其他離散優(yōu)化問題上得到了廣泛的使用。

1.2 頭腦風暴優(yōu)化

頭腦風暴優(yōu)化［15］的本質是，具有不同知識背景的人聚集在一起，將具有同樣或相似想法的人進行分組，并選出各組的代表，在各組內部的代表和組內的其他人可以通過討論提出新的想法（解），組間的人或各組的代表可以通過互相之間的交流提出更加具有廣度的新想法?？梢钥闯?，組內通過討論提出新想法是一種局部開發(fā)的過程，而組間的交流是全局探索過程，通過控制組間的交流與組內的討論，BSO能夠達到較好的平衡。具體地，頭腦風暴優(yōu)化采用聚類的方法進行分組，各組在對應的決策空間上搜索局部最優(yōu)解，通過各組的信息交換獲得全局最優(yōu)解，個體解通過利用不同類的信息進行更新，進一步提升了群體解的多樣性。

與其他模仿生物群體活動行為的演化算法不同，頭腦風暴優(yōu)化是一種更加貼近人類活動的算法，易于認知和理解，采用聚類分組的方式進行尋優(yōu)，在處理多峰高維的優(yōu)化問題上具有較好的優(yōu)勢，自提出以來，針對該算法的研究、發(fā)展和應用逐漸成為熱點。

2 ABO算法

2.1 路徑選擇概率與信息素更新

在蟻群優(yōu)化中，螞蟻需要根據信息素濃度和啟發(fā)式信息計算路徑轉移概率，從而選擇路徑，本次迭代完成后，采用較好的次優(yōu)解更新信息素。首先建立蟻群優(yōu)化求解特征選擇問題的模型，如圖1所示。

圖1 蟻群優(yōu)化特征選擇過程Fig.1 Ant colony optimization feature selection process

圖1中：f表示特征；n表示特征的個數；s表示螞蟻訪問的步數；q表示螞蟻最大訪問的步數（選擇特征的個數）；陰影部分表示已選特征，其他特征是螞蟻下一步的可選特征。蟻群優(yōu)化算法初始時，已選特征為空，螞蟻從第1步開始選擇特征，到第q步停止，每次按照輪盤賭的策略從可選特征中選擇一個未訪問過的特征。螞蟻a在第i步選擇第j個特征的路徑選擇概率計算如式（1）所示：

其中：τj表示第j個特征的信息素值；ηj表示第j個特征的啟發(fā)式信息；visita表示螞蟻a已經訪問的特征集合；α和β表示信息素和啟發(fā)式信息的影響因子。蟻群優(yōu)化中的啟發(fā)式信息設置需要根據優(yōu)化問題的實際情況來確定。

本次迭代結束，需要采用較好解更新信息素值，在t時刻的信息素更新方式如式（2）所示：

其中：ρ表示信息素的揮發(fā)系數；tabut表示需要更新的路徑解（特征子集）；F(tabut)表示該路徑解在目標函數上的評估值；Q為常量，是目標函數評估值的縮放因子，該因子值由信息素初始值，揮發(fā)系數和目標函數評估值共同決定。蟻群優(yōu)化特征選擇過程偽代碼描述如下：

begin

初始化特征信息素矩陣，特征啟發(fā)式信息；

while（未達到最大迭代次數）

for螞蟻a=1：M

每只螞蟻按照式（1）計算某一步滿足條件的路徑（特征）概率值，采用輪盤賭策略選擇某一個路徑（特征），最終生成一個路徑解（特征子集）；

評估當前解的適應度值；

end

采用較好解，按照式（2）更新信息素矩陣；

end

end

進一步解釋，每只螞蟻按照式（1）得到選擇每個可選特征的概率值，采用輪盤賭策略選擇某個特征，循環(huán)多次直到已選特征個數滿足特征解的個數要求，計算該特征解的適應度值；對M只螞蟻特征解的適應度值進行比較，選擇適應度值最好的特征解按照式（2）更新信息素矩陣，進入下一次迭代，直到滿足循環(huán)停止條件。

2.2 信息交流檔案更新

ABO算法設置了信息交流檔案，該檔案需要動態(tài)維護一定數量的歷史較好解，作為頭腦風暴優(yōu)化的初始種群。為了使得頭腦風暴優(yōu)化能夠在更廣闊的空間中搜索較好解，同時充分利用蟻群優(yōu)化算法搜索過程中生成解的歷史信息，提出基于松弛因子的時間最久優(yōu)先方法來動態(tài)更新信息交流檔案。

基于松弛因子的時間最久優(yōu)先方法的思想是，當兩個路徑解的目標函數評估值相近時（在松弛因子范圍內），優(yōu)先保留檔案中存在時間最長的解。這是由于隨著算法的運行，種群生成的解會逐漸收斂到一個次優(yōu)解附近，導致多樣性降低，陷入局部最優(yōu)，而檔案中存在時間較長的解會保留演化過程中的歷史信息，且與當前次優(yōu)解之間存在一定的多樣性；另一方面，如果通過精確地比較新生成的解與檔案解的評估值來更新檔案，會造成解的頻繁更新，也會導致檔案丟失一些有價值的歷史解，因此可以通過引入松弛因子來解決該問題。假設新生成的解為k1，檔案中的解有M個，松弛因子為r，信息交流檔案的更新過程偽代碼描述如下：

begin

對檔案中的解按照生成時間由近及遠進行排序；

for第i個檔案解k2（i=1∶M）

if新生成解的評估值f（k1）大于檔案解的評估值f（k2）+r將檔案解k2更新為新解k1；

else iff（k1）大于f（k2）且小于f（k2）+rif兩個解的生成時間相同

將檔案解k2更新為新解k1；

end

end

end

end

特別說明的是，偽代碼中判斷兩個解生成時間的原因在于，當f（k1）大于f（k2）且小于f（k2）+r時，需要考慮k1與k2是否均為本輪迭代生成的解，若兩個解都是在本次迭代生成的，需要保留較好的解。

2.3 路徑-想法轉換算子

在ABO算法中，當蟻群優(yōu)化的全局最優(yōu)解多次未更新時，需要將信息交流檔案中的路徑解轉換為頭腦風暴優(yōu)化的想法解，并作為初始化種群。ABO算法中的頭腦風暴優(yōu)化選擇特征子集時，將想法解的每個域（特征）按照值由大到小進行排序，并選擇前q個域作為選擇的特征子集。根據頭腦風暴優(yōu)化選擇特征子集的過程，需要將路徑解轉換為由n個域構成的想法解，每個域中的值為一個實數值，且路徑解對應的域值要大于其他特征（未選特征）對應的域值。為了能夠使得轉換后想法解的域值在求解空間中盡量分散，ABO算法采用Fuch混沌映射的方法生成域值［18］。具體方式是，假設想法解中每個域的取值范圍為[Lmin，Lmax]，對于第z個路徑解，通過式（3）進行路徑-想法轉換：

其中：ui為第i個域的轉換值；U為Fuch混沌映射值；subset（z）為第z個路徑解。由于Fuch值的取值范圍為［-1，1］，需要將其范圍轉換為[0，(Lmax-Lmin)2]，因此采用式（4）生成Fuch映射值U。

其中xh≠0且h∈Ζ+。

2.4 頭腦風暴優(yōu)化搜索

當算法陷入局部最優(yōu)時，ABO算法將信息交流檔案中的路徑解通過路徑-想法轉換算子生成想法解，并作為頭腦風暴優(yōu)化的初始化種群，在更廣闊的空間搜索較優(yōu)解。頭腦風暴優(yōu)化搜索的偽代碼描述如下：

begin

while（未達到最大迭代次數）

通過聚類算法將M個想法解聚集成c個類；

隨機選擇1個或2個類生成新的想法解；

新想法解與相同索引的想法解比較，保留較好的解；

評估M個想法解；

end

對最好的想法解按照域值降序排列，生成路徑解返回；

end

頭腦風暴優(yōu)化中的聚類算法可以采用經典的K均值、簡單分組、近鄰傳播等方法，ABO算法使用K均值聚類。有關頭腦風暴優(yōu)化的更多信息參考文獻［15］，本文不再贅述。

此外，啟動頭腦風暴優(yōu)化搜索的條件是ABO算法多次未更新全局最優(yōu)解，為了給予算法充分的時間利用頭腦風暴優(yōu)化的結果進行深入搜索，同時也為了降低算法的時間復雜度，ABO算法動態(tài)更新下一次啟動的條件，如式（5）所示：

其中：T為ABO算法首次啟動頭腦風暴優(yōu)化搜索的閾值；NC為ABO算法的最大迭代次數；it為當前的迭代次數。

2.5 算法描述及復雜性分析

首先給出ABO算法的描述，然后分析其時間復雜性。ABO算法的螞蟻個數、信息交流檔案解的個數均設置為M，ABO算法的偽代碼如下：

begin

初始化信息素矩陣，啟發(fā)式信息，信息交流檔案；

while（未達到最大迭代次數）

for螞蟻a=1：M

螞蟻根據式（1）搜索路徑解并進行適應度評估；

信息交流檔案更新；

end

更新全局最優(yōu)解；

if全局最優(yōu)解大于T次未更新；

采用路徑-想法轉換算子將信息交流檔案的路徑解轉換為想法解；

通過頭腦風暴優(yōu)化算法搜索；

更新全局最優(yōu)解；

end

采用式（2）更新信息素矩陣；

end

返回最好的路徑解；

end

現分析ABO算法的時間復雜度。假設ABO算法的最大迭代次數為NC，頭腦風暴優(yōu)化的最大迭代次數為MC，特征候選基數為n，螞蟻個數、信息交流檔案解的個數和頭腦風暴優(yōu)化的想法解個數均為M。蟻群優(yōu)化搜索路徑解的時間為O（n2），頭腦風暴優(yōu)化的運行時間為O（MC×M），在式（5）條件下，頭腦風暴優(yōu)化搜索最多啟動4次，因此ABO算法的時間復雜度為O(NC×n2+4×MC×M)。

3 實驗與結果分析

3.1 實驗設置

本節(jié)通過實驗分析ABO算法在特征選擇問題上的性能。為了充分比較ABO算法的性能，按照特征數在100以下，100～1 000以及1 000以上選擇6個典型的二分類數據集，數據集來源于UCI數據集（http：//archive.ics.uci.edu/m l/datasets.php）和ASU數據集（http：//featureselection.asu.edu/datasets.php），它們的相關屬性及對應的來源如表1所示，其中第4列表示算法選擇的特征個數。

表1 實驗數據集屬性Tab.1 Attributes of experimental datasets

由于ABO算法是一種混合優(yōu)化算法，因此選擇2個性能優(yōu)異的混合優(yōu)化算法作為對比，即混合螢火蟲粒子群優(yōu)化（Hybrid Firefly and Particle Swarm Optimization，HFPSO）算法［19］以及粒子群優(yōu)化與引力搜索算法（Particle Swarm Optimization and Gravitational Search Algorithm，PSOGSA）［20］。同時，采用性能優(yōu)異的遺傳算法（Genetic Algorithm，GA）［21］進行對比。

此外，為了說明ABO算法的有效性，將不使用頭腦風暴優(yōu)化的ABO算法記為ANBO算法，同時進行比較。采用分類正確率作為算法的優(yōu)化目標，將采用歐氏距離的K近鄰分類器作為實驗分類器（K=5）。

5種算法的種群數設置為30，迭代次數為300代，HFPSO算法和PSOGSA的其他參數值與文獻［19］和［20］中的參數設置一致。GA中交叉概率為0.4，變異概率為0.1。ABO算法的參數設置如下：τi（0）=100，α=4，β=1，ρ=0.05，Q=0.1，啟發(fā)式信息設置為特征的費舍爾判別率［13-14］，頭腦風暴優(yōu)化搜索迭代次數為200代，類簇個數為5，概率參數pgeneration=0.8，poneCluster=0.4，ptwoCluster=0.5。對比算法ANBO算法的參數設置與ABO算法一致。

3.2 參數敏感性分析

在ABO算法中，松弛因子r和啟動頭腦風暴優(yōu)化搜索的閾值T是2個重要的參數變量，本節(jié)通過實驗評估其參數敏感性。為了便于說明，該部分實驗分為（a）和（b）兩部分，以IONO數據集為例，實驗（a）中松弛因子r的變化范圍設置從0.01到0.1，取值間隔為0.01，T分別取5、10和30；實驗（b）中啟動頭腦風暴優(yōu)化搜索的閾值T的變化范圍設置從5到30，取值間隔為5，r分別取0.01、0.05和0.1，其他參數設置與3.1節(jié)一致。獨立運行30次，采用5重交叉檢驗，對運行結果取均值，圖2給出了ABO算法在不同的r和T值上分類正確率的變化。

圖2 ABO算法在不同r和T值時的分類正確率Fig.2 Classification accuracy of ABO algorithm under different valuesof r and T

如圖2（a）所示，當T=5時，ABO算法的分類正確率隨著松弛因子的增加總體上呈現先上升再下降的趨勢，當松弛因子為0.07時達到最大值，當T=10和T=30時總體上也具有該趨勢。這是因為松弛因子較小時，檔案中的解更新頻率較高，造成早期解的丟失，導致頭腦風暴優(yōu)化不能有效利用歷史解的信息；當松弛因子大于一定程度時，檔案中較差的歷史解不能及時更新，導致算法難以利用較好解進行進一步的搜索?？梢钥闯?，松弛因子能夠調節(jié)檔案中歷史解和近期較好解的比例，設置合適的松弛因子能夠讓頭腦風暴優(yōu)化充分利用歷史解和蟻群優(yōu)化搜索的較好解包含的信息，從而能夠在探索和開發(fā)之間達到較好的平衡。

如圖2（b）所示，當r為0.01時，ABO算法分類正確率震蕩比較明顯，產生的結果比較隨機，而當r為0.05或者0.1時，分類正確率隨著T的變化呈現先上升再下降的趨勢。這主要是由于當r=0.01時，檔案中的解更新頻率較高，有價值的歷史解具有較大概率被更新；而當r為0.05或0.1時，檔案中的解比較穩(wěn)定，兩條曲線呈現出相似的趨勢，更具說服力。此外，可以看出當T取10～15時ABO算法分類精度最大，這主要是由于當T較小時，ABO算法頻繁啟動頭腦風暴優(yōu)化搜索，導致蟻群優(yōu)化不能進行深入開發(fā)；當T較大時，頭腦風暴優(yōu)化搜索啟動較晚，導致ABO算法難以跳出局部最優(yōu)解。因此，設置合理的T值，能夠讓算法具有較好的綜合性能。

通過在其他5個數據集上的測試，能夠初步得出結果，T值在10～20，松弛因子r值在0.06～0.08時，ABO算法的性能較好。

3.3 實驗結果與分析

下面通過實驗對ABO算法的性能進行評估。ABO算法中啟動頭腦風暴優(yōu)化的參數T=10，信息交流檔案更新的松弛因子r=0.08，實驗中的其他參數設置保持不變。每種算法獨立運行30次，采用5重交叉檢驗，對運行結果取均值，5種算法在6個數據集上的分類正確率、查準率、查全率和F1指標值如表2～5所示。

表2 分類正確率比較 單位：%Tab.2 Comparison of classification accuracy unit：%

通過表2可以看出，ABO算法在6個測試數據上都取得了較好的分類正確率，ABO算法的結果普遍好于ANBO算法，而ABO算法與ANBO算法的差別在于是否采用頭腦風暴優(yōu)化進行增強搜索，因此可以說明ABO算法使用頭腦風暴優(yōu)化的有效性。進一步分析，PSOGSA和GA在LSVT數據集上好于ANBO算法，HFPSO算法在PDC數據集上好于ANBO算法，但是都劣于ABO算法的性能，從而進一步表明ABO算法通過路徑-想法轉換算子將信息交流檔案中的解轉換為初始種群并運用頭腦風暴優(yōu)化在更廣闊的空間中搜索較好解的有效性。最后，比較5種算法在PC和RE高維數據集上的分類正確率，HFPSO算法、PSOGSA和GA的性能出現了嚴重的惡化，表明它們不適用于高維數據的特征選擇，而ABO算法的分類正確率較高，說明ABO算法不但適用于低維數據也適合高維數據的特征選擇問題。

觀察表3中的查準率，除了在RE數據集上GA的查準率好于ABO算法，在其他5個測試數據集上ABO算法均取得了最好的結果，即使在RE數據集上，ABO算法相較其他三個算法的查準率也得到了很大的提升，此外，在PDC數據集上，HFPSO算法好于ANBO算法，但劣于ABO算法；在IONO和PC數據集上，GA好于ANBO算法，但劣于ABO算法，說明ABO算法相較ANBO算法具有一定的有效性。

表3 查準率比較 單位：%Tab.3 Comparison of precision unit：%

在表4中，ABO算法在4個數據集上的召回率好于其他4種算法，但是在PC和RE上弱于HFPSO算法和PSOGSA。結合表3的結果，可以推斷，通過HFPSO算法和PSOGSA選擇的特征子集訓練的分類器能夠分辨出更多正類的數據，但分辨出的正類中為真實正類的數據比例較低，即其分類超平面較差。而ABO算法的召回率與HFPSO算法和PSOGSA相比，差距小于0.5%，結合查準率的結果，ABO算法的綜合性能要好于HFPSO算法和PSOGSA。

表4 召回率比較 單位：%Tab.4 Comparison resultsof recall unit：%

最后觀察表5在F1指標上的運行結果，ABO算法在6個數據集上均取得了優(yōu)于其他4種算法的結果，且在PC和RE數據集上好于HFPSO算法、PSOGSA和GA，從而進一步說明ABO算法具有較好的性能，采用頭腦風暴優(yōu)化搜索具有有效性。

表5 F1指標比較Tab.5 Comparison results of F1-measure

表6給出了5種算法在6個測試數據集上的運行時間對比。

表6 五種算法運行時間對比 單位：sTab.6 Comparison of running timeof fivealgorithms unit：s

通過表6可以看出，在IONO數據集上GA運行速度最快，在其他5個測試數據集上，HFPSO算法的運行時間最短，在6個數據集上ABO算法的運行時間最長，ABO算法的運行時間基本是HFPSO算法運行時間的3倍左右。結合ANBO算法與HFPSO算法和PSOGSA運行時間的對比結果，可以得出結論，采用頭腦風暴優(yōu)化搜索是ABO算法運行時間較長的原因，這與“沒有免費午餐”定理相印證，即在提高算法性能的同時，時間復雜度也會相應提高。

4 結語

為了提升蟻群優(yōu)化求解特征選擇問題的性能，本文提出結合頭腦風暴優(yōu)化的混合蟻群優(yōu)化（ABO）算法。設置信息交流檔案，提出基于松弛因子的時間最久優(yōu)先方法動態(tài)更新檔案解，當蟻群優(yōu)化的全局最優(yōu)解多次未更新時，采用基于Fuch混沌映射的路徑-想法轉換算子將檔案中的路徑解轉換為想法解，并作為初始化種群，使用頭腦風暴優(yōu)化在更廣闊的空間中搜索較好解。通過6組典型的二分類數據集進行對比實驗，可以得出以下結論：

1）ABO算法在分類正確率、查準率和F1指標上具有較好的表現，且綜合性能較強；

2）在高維數據特征選擇上，ABO算法具有較好的性能；

3）采用頭腦風暴優(yōu)化搜索是有效的。

下一步將繼續(xù)優(yōu)化ABO算法的性能，特別是參數的魯棒性，以期提升算法的泛化能力；另一方面，將通過并行計算減少ABO算法的運行時間。