結(jié)合頭腦風(fēng)暴優(yōu)化的混合蟻群優(yōu)化算法

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

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

0 引言

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

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

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

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

1 相關(guān)理論

1.1 蟻群優(yōu)化

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

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

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

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

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

2 ABO算法

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

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

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

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

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

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

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

begin

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

while（未達(dá)到最大迭代次數(shù)）

for螞蟻a=1：M

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

評估當(dāng)前解的適應(yīng)度值；

end

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

end

end

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

2.2 信息交流檔案更新

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

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

begin

對檔案中的解按照生成時(shí)間由近及遠(yuǎn)進(jìn)行排序；

for第i個(gè)檔案解k2（i=1∶M）

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

else iff（k1）大于f（k2）且小于f（k2）+rif兩個(gè)解的生成時(shí)間相同

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

end

end

end

end

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

2.3 路徑-想法轉(zhuǎn)換算子

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

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

其中xh≠0且h∈Ζ+。

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

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

begin

while（未達(dá)到最大迭代次數(shù)）

通過聚類算法將M個(gè)想法解聚集成c個(gè)類；

隨機(jī)選擇1個(gè)或2個(gè)類生成新的想法解；

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

評估M個(gè)想法解；

end

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

end

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

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

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

2.5 算法描述及復(fù)雜性分析

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

begin

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

while（未達(dá)到最大迭代次數(shù)）

for螞蟻a=1：M

螞蟻根據(jù)式（1）搜索路徑解并進(jìn)行適應(yīng)度評估；

信息交流檔案更新；

end

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

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

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

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

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

end

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

end

返回最好的路徑解；

end

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

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)置

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

表1 實(shí)驗(yàn)數(shù)據(jù)集屬性Tab.1 Attributes of experimental datasets

由于ABO算法是一種混合優(yōu)化算法，因此選擇2個(gè)性能優(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］。同時(shí)，采用性能優(yōu)異的遺傳算法（Genetic Algorithm，GA）［21］進(jìn)行對比。

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

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

3.2 參數(shù)敏感性分析

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

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

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

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

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

3.3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

表3 查準(zhǔn)率比較 單位：%Tab.3 Comparison of precision unit：%

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

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

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

表5 F1指標(biāo)比較Tab.5 Comparison results of F1-measure

表6給出了5種算法在6個(gè)測試數(shù)據(jù)集上的運(yùn)行時(shí)間對比。

表6 五種算法運(yùn)行時(shí)間對比 單位：sTab.6 Comparison of running timeof fivealgorithms unit：s

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

4 結(jié)語

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

1）ABO算法在分類正確率、查準(zhǔn)率和F1指標(biāo)上具有較好的表現(xiàn)，且綜合性能較強(qiáng)；

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

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

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