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

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

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

0 引言

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

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

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

為了進(jìn)一步提升蟻群優(yōu)化求解特征選擇問(wèn)題的性能，提出一種結(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)性能。通過(guò)6組典型的二分類(lèi)數(shù)據(jù)集，對(duì)本文提出算法與其他2種混合優(yōu)化方法和經(jīng)典遺傳算法進(jìn)行對(duì)比實(shí)驗(yàn)，并對(duì)松弛因子和全局最優(yōu)解未更新次數(shù)進(jìn)行敏感性分析，實(shí)驗(yàn)結(jié)果表明ABO算法具有較強(qiáng)的優(yōu)越性。

1 相關(guān)理論

1.1 蟻群優(yōu)化

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

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

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

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

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

2 ABO算法

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

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

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

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

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

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

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

begin

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

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

for螞蟻a=1：M

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

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

end

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

end

end

進(jìn)一步解釋?zhuān)恐晃浵伆凑帐剑?）得到選擇每個(gè)可選特征的概率值，采用輪盤(pán)賭策略選擇某個(gè)特征，循環(huán)多次直到已選特征個(gè)數(shù)滿足特征解的個(gè)數(shù)要求，計(jì)算該特征解的適應(yīng)度值；對(duì)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)化算法搜索過(guò)程中生成解的歷史信息，提出基于松弛因子的時(shí)間最久優(yōu)先方法來(lái)動(dòng)態(tài)更新信息交流檔案。

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

begin

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

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

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

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

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

end

end

end

end

特別說(shuō)明的是，偽代碼中判斷兩個(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)化選擇特征子集的過(guò)程，需要將路徑解轉(zhuǎn)換為由n個(gè)域構(gòu)成的想法解，每個(gè)域中的值為一個(gè)實(shí)數(shù)值，且路徑解對(duì)應(yīng)的域值要大于其他特征（未選特征）對(duì)應(yīng)的域值。為了能夠使得轉(zhuǎn)換后想法解的域值在求解空間中盡量分散，ABO算法采用Fuch混沌映射的方法生成域值［18］。具體方式是，假設(shè)想法解中每個(gè)域的取值范圍為[Lmin，Lmax]，對(duì)于第z個(gè)路徑解，通過(guò)式（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算法將信息交流檔案中的路徑解通過(guò)路徑-想法轉(zhuǎn)換算子生成想法解，并作為頭腦風(fēng)暴優(yōu)化的初始化種群，在更廣闊的空間搜索較優(yōu)解。頭腦風(fēng)暴優(yōu)化搜索的偽代碼描述如下：

begin

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

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

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

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

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

end

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

end

頭腦風(fēng)暴優(yōu)化中的聚類(lèi)算法可以采用經(jīng)典的K均值、簡(jiǎn)單分組、近鄰傳播等方法，ABO算法使用K均值聚類(lèi)。有關(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)度評(píng)估；

信息交流檔案更新；

end

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

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

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

通過(guò)頭腦風(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é)通過(guò)實(shí)驗(yàn)分析ABO算法在特征選擇問(wèn)題上的性能。為了充分比較ABO算法的性能，按照特征數(shù)在100以下，100～1 000以及1 000以上選擇6個(gè)典型的二分類(lèi)數(shù)據(jù)集，數(shù)據(jù)集來(lái)源于UCI數(shù)據(jù)集（http：//archive.ics.uci.edu/m l/datasets.php）和ASU數(shù)據(jù)集（http：//featureselection.asu.edu/datasets.php），它們的相關(guān)屬性及對(duì)應(yīng)的來(lái)源如表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)化算法作為對(duì)比，即混合螢火蟲(chóng)粒子群優(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)行對(duì)比。

此外，為了說(shuō)明ABO算法的有效性，將不使用頭腦風(fēng)暴優(yōu)化的ABO算法記為ANBO算法，同時(shí)進(jìn)行比較。采用分類(lèi)正確率作為算法的優(yōu)化目標(biāo)，將采用歐氏距離的K近鄰分類(lèi)器作為實(shí)驗(yàn)分類(lèi)器（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代，類(lèi)簇個(gè)數(shù)為5，概率參數(shù)pgeneration=0.8，poneCluster=0.4，ptwoCluster=0.5。對(duì)比算法ANBO算法的參數(shù)設(shè)置與ABO算法一致。

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

在ABO算法中，松弛因子r和啟動(dòng)頭腦風(fēng)暴優(yōu)化搜索的閾值T是2個(gè)重要的參數(shù)變量，本節(jié)通過(guò)實(shí)驗(yàn)評(píng)估其參數(shù)敏感性。為了便于說(shuō)明，該部分實(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)，對(duì)運(yùn)行結(jié)果取均值，圖2給出了ABO算法在不同的r和T值上分類(lèi)正確率的變化。

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

如圖2（a）所示，當(dāng)T=5時(shí)，ABO算法的分類(lèi)正確率隨著松弛因子的增加總體上呈現(xiàn)先上升再下降的趨勢(shì)，當(dāng)松弛因子為0.07時(shí)達(dá)到最大值，當(dāng)T=10和T=30時(shí)總體上也具有該趨勢(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)化搜索的較好解包含的信息，從而能夠在探索和開(kāi)發(fā)之間達(dá)到較好的平衡。

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

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

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

下面通過(guò)實(shí)驗(yàn)對(duì)ABO算法的性能進(jìn)行評(píng)估。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)，對(duì)運(yùn)行結(jié)果取均值，5種算法在6個(gè)數(shù)據(jù)集上的分類(lèi)正確率、查準(zhǔn)率、查全率和F1指標(biāo)值如表2～5所示。

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

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

觀察表3中的查準(zhǔn)率，除了在RE數(shù)據(jù)集上GA的查準(zhǔn)率好于ABO算法，在其他5個(gè)測(cè)試數(shù)據(jù)集上ABO算法均取得了最好的結(jié)果，即使在RE數(shù)據(jù)集上，ABO算法相較其他三個(gè)算法的查準(zhǔn)率也得到了很大的提升，此外，在PDC數(shù)據(jù)集上，HFPSO算法好于ANBO算法，但劣于ABO算法；在IONO和PC數(shù)據(jù)集上，GA好于ANBO算法，但劣于ABO算法，說(shuō)明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é)果，可以推斷，通過(guò)HFPSO算法和PSOGSA選擇的特征子集訓(xùn)練的分類(lèi)器能夠分辨出更多正類(lèi)的數(shù)據(jù)，但分辨出的正類(lèi)中為真實(shí)正類(lèi)的數(shù)據(jù)比例較低，即其分類(lèi)超平面較差。而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)一步說(shuō)明ABO算法具有較好的性能，采用頭腦風(fēng)暴優(yōu)化搜索具有有效性。

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

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

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

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

4 結(jié)語(yǔ)

為了提升蟻群優(yōu)化求解特征選擇問(wèn)題的性能，本文提出結(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)化在更廣闊的空間中搜索較好解。通過(guò)6組典型的二分類(lèi)數(shù)據(jù)集進(jìn)行對(duì)比實(shí)驗(yàn)，可以得出以下結(jié)論：

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

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

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

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