王艷麗，梁 靜，薛 冰，岳彩通

(1.鄭州大學(xué) 電氣工程學(xué)院，河南 鄭州 450001；2.新西蘭惠靈頓維多利亞大學(xué) 工程與計(jì)算機(jī)學(xué)院，新西蘭 惠靈頓 6140)

0 引言

隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)成為研究熱點(diǎn)，并受到了國內(nèi)外研究人員的廣泛關(guān)注。特征選擇(feature selection, FS)是從一組初始特征中挑選出一些具有代表性的特征以降低特征空間維數(shù)的過程，是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)的關(guān)鍵問題之一。對于數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)，一個好的學(xué)習(xí)樣本是訓(xùn)練分類器的關(guān)鍵，樣本中是否包含有不相關(guān)或冗余特征直接影響著分類器的性能。特征選擇的目的是尋找解決問題所必須的、足夠的最小特征子集。通過從原始特征集中剔除不相關(guān)和冗余特征以減少數(shù)據(jù)的維數(shù)，加速學(xué)習(xí)過程，簡化學(xué)習(xí)模型和提高學(xué)習(xí)算法的性能[1]。有效的特征選擇方法是找到一個最優(yōu)的特征子集的關(guān)鍵。

現(xiàn)實(shí)中的數(shù)據(jù)集通常由一組特征描述，這些特征包含許多信息，但也引入了冗余和噪聲。隨著數(shù)據(jù)維度的增加，搜索空間增大，選擇最優(yōu)特征子集變得尤為困難。比如對于一個有n個特征的數(shù)據(jù)集，特征子集的個數(shù)就有2n個[1]。隨著問題復(fù)雜性的增加，許多領(lǐng)域數(shù)據(jù)的特征維度都在逐漸增加，特征選擇變得更具挑戰(zhàn)性。在大多數(shù)情況下，窮舉搜索給定數(shù)據(jù)集的最優(yōu)特征子集幾乎是不可能實(shí)現(xiàn)的。目前已有許多搜索技術(shù)應(yīng)用于特征選擇，如完全搜索、貪婪搜索、啟發(fā)式搜索和隨機(jī)搜索[1-2]?，F(xiàn)有的搜索技術(shù)在特征選擇上取得了較大的成功，但大多數(shù)方法容易陷入局部最優(yōu)，并且計(jì)算成本較高[3]。因此，需要一種有效的全局搜索技術(shù)來更好地解決特征選擇問題。

進(jìn)化計(jì)算(evolutionary computation, EC)算法通過模擬自然界生物進(jìn)化機(jī)制，在一些可行解組成的種群中，通過迭代進(jìn)化尋求最優(yōu)解。EC技術(shù)因其強(qiáng)大的全局搜索能力和潛力備受研究者的關(guān)注，近年來更是廣泛應(yīng)用于特征選擇問題。然而，現(xiàn)有的文獻(xiàn)對近些年EC在特征選擇上的應(yīng)用缺乏全面而系統(tǒng)的討論。基于此，筆者對EC在特征選擇上應(yīng)用的相關(guān)文獻(xiàn)進(jìn)行了分析和總結(jié)，給感興趣的研究人員提供一些參考。

1 特征選擇的基本框架

特征選擇是從數(shù)據(jù)集特征的所有組合組成的搜索空間中選擇相關(guān)特征子集的過程[2]。迄今為止，許多研究者從不同的角度對特征選擇進(jìn)行定義。Koller 等[4]從傳統(tǒng)的角度定義，給定n個原始特征，特征選擇的任務(wù)是從所有大小為m的特征子集中(m

圖1 特征選擇的基本框架

從圖1可以看出，在特征選擇中，搜索機(jī)制和評價準(zhǔn)則是影響最終特征子集質(zhì)量的重要因素。

傳統(tǒng)的特征選擇方法可以分為：過濾式(filter)[7]、封裝式(wrapper)[8]和嵌入式(embedded)[9]。過濾式方法先對數(shù)據(jù)集進(jìn)行特征選擇，然后再訓(xùn)練學(xué)習(xí)器，一般直接采用所有訓(xùn)練數(shù)據(jù)的統(tǒng)計(jì)性能評估特征，速度快，但缺少學(xué)習(xí)算法的引導(dǎo)導(dǎo)致分類性能相對較低。封裝式方法利用學(xué)習(xí)算法的訓(xùn)練精度作為特征子集的評價準(zhǔn)則，偏差小，但是計(jì)算量大。嵌入式方法是將特征選擇過程嵌入到學(xué)習(xí)過程中，特征選擇過程和學(xué)習(xí)器訓(xùn)練過程同步進(jìn)行，因此花費(fèi)時間大幅減少，但不適合處理含有大量噪聲特征的數(shù)據(jù)。集成(ensemble)[10]是近幾年發(fā)展起來的一種新的學(xué)習(xí)方法，應(yīng)用于特征選擇問題，目的是獲取多個最優(yōu)特征子集，并聚合基于多個最優(yōu)特征子集的學(xué)習(xí)結(jié)果。

與傳統(tǒng)方法相比，基于種群的EC算法能并行搜索多個解，利用計(jì)算機(jī)技術(shù)自動搜索解決方案，不需要問題領(lǐng)域先驗(yàn)知識?；谶@些優(yōu)點(diǎn)，EC在特征選擇上獲得較大成功[11]。EC在特征選擇上的應(yīng)用研究始于1990年左右，但是自2007年以來，隨著許多領(lǐng)域的特征數(shù)量逐漸增多，EC技術(shù)以其強(qiáng)大的全局搜索能力而受到特征選擇領(lǐng)域的廣泛關(guān)注。如圖2所示。

圖2 進(jìn)化計(jì)算用于特征選擇的論文數(shù)量

圖2顯示EC算法在特征選擇上應(yīng)用的論文數(shù)量(數(shù)據(jù)來源Web of Science，2018.12)，這表明自2007年以來，進(jìn)化計(jì)算在特征選擇上的應(yīng)用呈整體增長趨勢。筆者對進(jìn)化計(jì)算在特征選擇上的代表性研究工作進(jìn)行討論，并對進(jìn)化計(jì)算在單目標(biāo)、多目標(biāo)特征選擇上的研究工作分別進(jìn)行詳細(xì)的介紹。

2 基于進(jìn)化計(jì)算的單目標(biāo)特征選擇

2.1 特征選擇的目標(biāo)和個體表達(dá)

特征選擇的目的是通過從原始特征集中刪除不相關(guān)和冗余的特征找到解決分類問題所必需和充分的最小特征子集。特征選擇有兩個主要目標(biāo)：最大化分類性能和最小化選擇特征的數(shù)量。

實(shí)際操作過程中，常用問題解的編碼有連續(xù)和二進(jìn)制兩種表示方法，具體如下：連續(xù)表示指一個含有n個實(shí)數(shù)的向量，其中n是數(shù)據(jù)集中可用特征的個數(shù)或搜索空間的維數(shù)。每個個體i的位置向量值.id與設(shè)定的閾值θ進(jìn)行比較。如果.id>θ，則特征d被選擇；否則，特征d未被選擇。每個個體采用二進(jìn)制字符串“0”和“1”表示，“1”表示個體對應(yīng)的特征被選擇，“0”表示未被選擇。

2.2 基于進(jìn)化算法的特征選擇

進(jìn)化算法包括遺傳算法(genetic algorithms, GA)、遺傳規(guī)劃(genetic programming, GP)、進(jìn)化規(guī)劃(evolution strategies, ES)和進(jìn)化策略(evolution programming, EP)等。目前，遺傳算法和遺傳規(guī)劃被廣泛應(yīng)用于特征選擇中，以尋找最優(yōu)特征子集。

2.2.1 遺傳算法

GA算法[12]是模擬達(dá)爾文生物進(jìn)化論的自然選擇和自然界生物進(jìn)化過程演化而來的隨機(jī)搜索最優(yōu)解的方法。Siedlecki等[13]采用GAs解決特征選擇問題，首次把EC技術(shù)應(yīng)用到特征選擇問題中。為了提高算法性能，研究者對GAs進(jìn)行了許多不同的改進(jìn)，主要集中在搜索機(jī)制、個體表達(dá)和評價機(jī)制等方面。

傳統(tǒng)的GAs由于遺傳算子簡單，降低了種群的多樣性。當(dāng)搜索空間很大時，GAs容易快速收斂而陷入局部最優(yōu)。為了避免這一問題，Li等[14]提出一種多種群GAs的特征選擇方法，即相鄰種群通過共享兩個個體來交換信息，以提高種群的搜索能力。此外，對每個種群中的最優(yōu)個體進(jìn)行局部搜索，進(jìn)一步提高算法性能。但是該方法僅在特征維數(shù)小于60的數(shù)據(jù)上是有效的。Lin等[15]提出了一種新的基于GAs的特征選擇方法，該方法首先利用先驗(yàn)知識對相似特征進(jìn)行分組，并對同一組中的所有特征進(jìn)行排序，然后采用GAs從每個組中搜索出最優(yōu)特征子集。近年來，GAs也被應(yīng)用在分層特征空間中選擇特征[16]。該算法提出了兩種新的變異算子處理分層空間中的冗余特征。最近基于GA的特征選擇方法被廣泛用于解決實(shí)際問題[17-18]。

Hong 等[19]提出一種二進(jìn)制向量表示每個個體，首先二進(jìn)制位預(yù)先定義的小數(shù)被轉(zhuǎn)換為整數(shù)，表明對應(yīng)的特征被選擇與否。該算法有效地降低數(shù)千特征的高維數(shù)據(jù)集上GA搜索空間的維度。同時，在算法中引入“透明適應(yīng)度共享”伸縮機(jī)制以避免GA 在搜索過程中出現(xiàn)早熟。通過分界線的動態(tài)變化來增加其他個體的選擇機(jī)會，并打散個體的分布以保持種群的多樣性。Chen等[20]提出一種改進(jìn)的二進(jìn)制表示方法，該方法包括兩部分：第一部分被轉(zhuǎn)換為整數(shù)，表示被選擇特征的數(shù)量；第二部分顯示哪些特征被選擇。該方法的缺點(diǎn)是需要預(yù)先定義特征的數(shù)量，但可能不是最佳大小。針對這一問題，Yahya等[21]開發(fā)了一種長度可變的表示方法，每一個個體只顯示所選擇的特征，并且不同的個體可能具有不同的長度，提出了一種新的遺傳算子來處理長度可變表示問題。

OA Silva 等[22]將分類精度和特征個數(shù)聚合成一個適應(yīng)度函數(shù)。Winkler 等[23]考慮特征個數(shù)、分類性能、分類特定精度以及利用所有初始特征的分類精度等提出了幾個適應(yīng)度函數(shù)。Sousa 等[24]利用貝葉斯分類器接收工作特性曲線下面積作為適應(yīng)度函數(shù)。

2.2.2 遺傳規(guī)劃

GP算法[25]是一種基于種群的進(jìn)化計(jì)算算法，在特征選擇中，GP算法具有靈活的表示形式，每個個體表示為一棵樹，每棵樹的所有葉節(jié)點(diǎn)都是原始特征，但只有一個葉節(jié)點(diǎn)特征被認(rèn)定是選擇的特征。

Sherrah等[26]首次將GP算法用于特征選擇問題，該算法采用廣義線性機(jī)作為分類器來評價所選特征的適應(yīng)度。隨后，Neshatian等[27]提出一種基于GP的封裝式特征選擇方法，采用改進(jìn)的貝葉斯算法進(jìn)行分類。該算法采用位掩碼編碼表示特征子集，算子集作為基本函數(shù)，利用GP將特征子集和算子集進(jìn)行組合，獲得最優(yōu)特征子集。Hunt等[28]提出一種新的GP超啟發(fā)式特征選擇方法，開發(fā)兩個去除和添加特征的函數(shù)算子。Viegas等[29]提出一種處理平衡和不平衡數(shù)據(jù)的策略，GP算法中的每個內(nèi)部節(jié)點(diǎn)表示一個集合算子，每個葉節(jié)點(diǎn)表示一個原始特征，每個樹的輸出是一組特征。結(jié)果顯示，該算法在不降低分類性能的前提下，可以有效地減少生物數(shù)據(jù)集98%的特征。

進(jìn)化算法應(yīng)用于特征選擇問題已有30多年的歷史，并在數(shù)百個特征問題上顯示出了較好的性能。然而對于數(shù)千特征的問題，進(jìn)化算法的效果并不是很理想。因此，使用進(jìn)化算法來處理這一問題，需要一種新的表示來減少搜索空間的維數(shù)。遺傳算子的設(shè)計(jì)，如交叉和突變，提供了辨別好的特征組及組合或調(diào)整互補(bǔ)特征以找到最優(yōu)特征子集的機(jī)會，但這是一項(xiàng)具有挑戰(zhàn)性的任務(wù)。

2.3 基于群集智能的特征選擇

群集智能算法是人們受自然規(guī)律或生物界規(guī)律的啟發(fā)，模仿某些規(guī)律而設(shè)計(jì)的求解實(shí)際問題的一類算法，它將復(fù)雜任務(wù)交給群體中大量的個體合作完成，具有概念簡單、實(shí)現(xiàn)方便的特點(diǎn)?；谶@些優(yōu)點(diǎn)，群集智能算法求解特征選擇問題受到了國內(nèi)外研究者的廣泛關(guān)注[11]。群智能算法包括蟻群優(yōu)化(ant colony optimization, ACO)、粒子群優(yōu)化(particle swarm optimization, PSO)、差分進(jìn)化(differential evolution, DE)、人工蜂群算法(artificial bee colony, ABC)等[30]。

Xue等[31]在PSO搜索過程中設(shè)計(jì)了新的初始化策略模擬典型的前向和反向特征選擇方法。結(jié)果表明，新的初始化策略顯著提高PSO特征選擇的性能。PSO中開發(fā)新的個體表示用于特征選擇的工作較少，研究者主要對典型表示進(jìn)行微小的修改，同時用分類算法進(jìn)行特征選擇和參數(shù)優(yōu)化，工作主要集中在對支持向量機(jī)核函數(shù)中的參數(shù)進(jìn)行優(yōu)化[32-35]。PSO中新的個體表示長度等于特征總數(shù)，主要有3種不同編碼方式：連續(xù)編碼[32]、二進(jìn)制編碼[33]和二進(jìn)制和連續(xù)編碼的混合[34-35]。PSO最初被提出用于連續(xù)優(yōu)化，因此連續(xù)編碼比其他兩種編碼方案具有更好的性能。

Vieira等[33]提出新的PSO粒子表示方法，并同時進(jìn)行特征選擇和SVM核參數(shù)優(yōu)化。該方法中每個粒子對應(yīng)一個初始特征或內(nèi)核參數(shù)，表示長度等于特征個數(shù)和內(nèi)核參數(shù)個數(shù)的和。結(jié)果顯示，所提算法比其他二進(jìn)制PSO特征選擇算法具有更好的分類性能，選擇的特征子集遠(yuǎn)小于GA算法。Lane等[36]提出了采用PSO和統(tǒng)計(jì)聚類方法解決特征選擇問題，將來自于相同簇的特征分配到一起，然后從每一簇中僅選擇一個特征，該方法顯著減少了所選特征的數(shù)量。隨后，Lane等[37]進(jìn)一步采用高斯分布從每個簇中選擇多個特征改進(jìn)了算法，提高了分類性能。Nguyen等[38]提出每一個個體的維度由期望的最大特征數(shù)目確定，該方法確定的個體維度遠(yuǎn)遠(yuǎn)小于典型解的代表維度，但是難點(diǎn)在于如何確定期望的特征數(shù)量。Tran等[39]提出粒子長度可變表示，從而定義了較小的搜索空間，提高了PSO算法的性能。利用變長機(jī)制，PSO可以跳出局部最優(yōu)，進(jìn)一步縮小搜索空間。

早熟收斂是PSO面臨的一個典型問題，容易使種群陷入局部最優(yōu)。為了避免這一問題，Chuang等[40]提出在有限次迭代中，最佳適應(yīng)度值不變，將gbest置零的重置機(jī)制。隨后，Tran等[41]將gbest重置機(jī)制與pbest局部搜索結(jié)合，通過被改變的特征來計(jì)算適應(yīng)度，加快局部搜索中的評價。Cheng等[42]在所提的PSO算法中，去掉了gbest和pbest，以避免PSO的過早收斂。通過粒子之間的競爭，獲勝者直接進(jìn)入新的種群。失敗者向獲勝者學(xué)習(xí)，根據(jù)獲勝者的位置更新它們的位置，然后進(jìn)入新的種群。該算法被稱為競爭群優(yōu)化算法，適用于大規(guī)模優(yōu)化問題。隨后，Gu等[43]將這種改進(jìn)的PSO算法應(yīng)用于特征選擇問題。

適應(yīng)度函數(shù)在PSO特征選擇中起著重要的作用。對于過濾式方法，適應(yīng)度函數(shù)通過使用不同的度量方法確定。而封裝式方法，許多現(xiàn)有的工作使用分類性能作為適應(yīng)度函數(shù)[3,40]，導(dǎo)致特征子集相對較大。然而，大多數(shù)適應(yīng)度函數(shù)采用不同的方式將分類性能和特征數(shù)相結(jié)合組成為一個適應(yīng)度函數(shù)[34,44]。但是，如果沒有先驗(yàn)知識，很難預(yù)先確定它們之間的最佳平衡。多目標(biāo)特征選擇可以同時優(yōu)化這兩個目標(biāo)以獲得一組折中解，從而有效地解決這一問題。

2008年以來DE一直被應(yīng)用于解決特征選擇問題。大部分工作主要集中在改進(jìn)DE的搜索策略和表示方法。Khushaba等[45]提出將DE用于搜索ACO得到的特征子集的最優(yōu)解的混合特征選擇方法。Ghosh等[46]提出采用自適應(yīng)DE算法用于生成特征子集。隨后，Khushaba等[47]將每個個體作為一個浮點(diǎn)數(shù)向量，并預(yù)先定義向量的長度，提出一種新的編碼方案。此外，研究表明，DE在大規(guī)模優(yōu)化方面也取得了成功[48]，但對于特征數(shù)量較多的高維問題，還面臨一些困難。

Hancer等[49]將基于相似性的進(jìn)化搜索機(jī)制引入到現(xiàn)存的二進(jìn)制 ABC 版本中，提出了新型二進(jìn)制 ABC算法用于特征選擇問題。模因算法將基于種群的搜索和局部搜索結(jié)合，為封裝式和過濾式方法提供好的機(jī)會。因此，在大多數(shù)模因特征選擇方法中，封裝式特征選擇采用進(jìn)化計(jì)算技術(shù)，過濾式特征選擇采用局部搜索算法。

總之，群集智能算法在特征選擇方面得到了迅速的發(fā)展。然而，作為一種種群優(yōu)化方法，群集智能用于特征選擇效率是有限的。開發(fā)新的PSO算法，特別是新的搜索機(jī)制、參數(shù)控制策略以及大規(guī)模特征選擇的表示，仍然是一個有待解決的問題。

2.4 基于協(xié)同進(jìn)化的特征選擇

協(xié)同進(jìn)化(cooperating coevolution，CC)是進(jìn)化計(jì)算領(lǐng)域的一種技術(shù)，從分治策略發(fā)展而來，其思想是首先將復(fù)雜的問題劃分成多個簡單子問題，然后對每個子問題應(yīng)用算法進(jìn)行求解，最后將子問題的解合并得到原問題的解。協(xié)同進(jìn)化策略可以嵌入到多種進(jìn)化算法中，具有很好的魯棒性，已成功應(yīng)用到許多大規(guī)模的組合問題中[50]。Derrac等[51]提出一種基于3種群遺傳算法的協(xié)同進(jìn)化特征選擇算法。算法將特征選擇和實(shí)例選擇同時放在一個過程中，減少了計(jì)算時間，對具有大量特征及噪聲實(shí)例的數(shù)據(jù)集效果顯著。隨后，Derrac等[52]進(jìn)一步采用協(xié)同進(jìn)化，對特征和實(shí)例進(jìn)行數(shù)據(jù)降維，提出了一種最近鄰分類特征選擇和實(shí)例選擇的進(jìn)化模型。Ebrahimpour等[53]提出一種新的基于全局搜索(利用分治策略)的特征選擇方法。該方法利用協(xié)同進(jìn)化概念，在特征維度上以隨機(jī)方式垂直劃分?jǐn)?shù)據(jù)集，使用過濾式準(zhǔn)則以二元引力搜索算法搜索解空間。

2.5 基于多模態(tài)的特征選擇

在實(shí)際問題中，決策者希望得到多個全局或局部最優(yōu)解，必要時可以在多個最優(yōu)或次優(yōu)解之間快速切換以保證系統(tǒng)正常穩(wěn)定運(yùn)行[54]。這類需要同時保留多個全局最優(yōu)或局部最優(yōu)解的問題屬于多模態(tài)優(yōu)化(multimodal optimization, MO)問題[55]，如機(jī)器學(xué)習(xí)中的分類問題[56]、特征選擇問題[57]等。

Kamyab等[58]研究了多模態(tài)優(yōu)化技術(shù)在特征選擇問題中的應(yīng)用效果。提出了基于動態(tài)適應(yīng)度共享(dynamic fitness sharing, DFS)、局部最優(yōu)粒子群算法(local best PSO)和GA_SN_CM等現(xiàn)有進(jìn)化算法的二進(jìn)制版本，用于從多個基準(zhǔn)數(shù)據(jù)集中選擇合適的特征。特征選擇本質(zhì)上是一個高維優(yōu)化問題，需要一個具有較高探索能力的求解器。另一方面，如果可以為問題提供可選的最優(yōu)解方案，則根據(jù)問題領(lǐng)域的成本和限制，實(shí)現(xiàn)階段會變得更具選擇性。MO方法具有較強(qiáng)的探索能力和解的保存能力，能夠在一次運(yùn)行中找到多個合適的解。因此，MO方法可以被認(rèn)為是尋找適合特征選擇問題的特征子集的有力工具。

3 基于進(jìn)化計(jì)算的多目標(biāo)特征選擇

在許多實(shí)際問題中，需要同時優(yōu)化兩個或兩個以上相互沖突的目標(biāo)，優(yōu)化其中一個目標(biāo)值，會導(dǎo)致其他目標(biāo)值的惡化，這類問題被稱為多目標(biāo)優(yōu)化問題[59]。對于多目標(biāo)優(yōu)化問題，無法找到單個解使它的每個目標(biāo)都達(dá)到最優(yōu)。在這種情況下，進(jìn)化算法能夠幫助決策者找到多個目標(biāo)之間最好的折中解集。

GA在實(shí)現(xiàn)多目標(biāo)特征選擇方面也得到了廣泛的應(yīng)用，但大多數(shù)都是基于非支配排序的GA II(NSGA-II)或其變體[60-62]。Mukhopadhay等[60]利用NSGA-II和支持向量機(jī)(SVM)提出識別微小RNA標(biāo)記物的多目標(biāo)的特征選擇方法。Vignolo等[63]應(yīng)用多目標(biāo)遺傳算法(MOGA)選擇人臉識別中最相關(guān)的一組特征。通過對多個可行選擇空間的探索，使特征子集的基數(shù)最小化，同時最大化特征子集的識別能力。結(jié)果顯示，MOGA得到的解選擇的特征較少，但精度與單目標(biāo)GA相近。Neshatian等[64]針對二分類問題，提出基于GP的多目標(biāo)過濾式特征選擇方法。與大多數(shù)只能測量單個特征與類標(biāo)簽相關(guān)性的過濾式方法不同，該算法能夠發(fā)現(xiàn)特征子集和目標(biāo)類別之間的隱藏關(guān)系，從而獲得更好的分類性能。

近年來，DE也被應(yīng)用于多目標(biāo)特征選擇[65]中，并將非支配解排序應(yīng)用到種群搜索中，研究者提出的多目標(biāo)方法在分類性能和特征個數(shù)上都優(yōu)于單目標(biāo)方法所獲得的特征子集。Hancer等[66]將ReliefF和FisherScore兩個過濾式準(zhǔn)則結(jié)合起來作為排序度量標(biāo)準(zhǔn)，歸一化交互信息作為相關(guān)性度量標(biāo)準(zhǔn)，并將這兩種度量方法視為兩個相互沖突的目標(biāo)。結(jié)果表明，該算法獲得較小的特征子集，且分類精度高于使用所有特征。DE雖然成功應(yīng)用于解決特征選擇問題，然而與PSO相比，應(yīng)用DE的特征選擇算法文章仍然較少。此外，研究顯示，DE在應(yīng)用于高維問題時還面臨一些困難[67]。

Xue等[68-69]首次將MOPSO應(yīng)用于特征選擇上，把分類性能和特征數(shù)量作為多目標(biāo)優(yōu)化問題的目標(biāo)函數(shù)進(jìn)行求解，并將連續(xù)和二進(jìn)制PSO算法在多目標(biāo)特征選擇上的性能進(jìn)行了對比。結(jié)果表明，MOPSO在特征選擇問題上優(yōu)于NSGA-II等。Xue等[70]以最小化特征數(shù)量，最大化所選特征和類標(biāo)簽之間的相關(guān)性為目標(biāo)，提出基于MOPSO的過濾式特征選擇方法。結(jié)果顯示，與單目標(biāo)特征選擇方法相比，該算法具有更高的分類性能。隨后，Nguyen等[71]通過引入插入、刪除和交換局部搜索機(jī)制提出了基于改進(jìn)多目標(biāo)PSO算法的特征選擇方法。該算法可以選擇數(shù)量較少的特征，并獲得很好的分類性能。

目前大多數(shù)的多目標(biāo)特征選擇算法采用基于帕累托(Pareto)支配的算法，這些算法通常集中在Pareto前沿的中心。針對這一問題，Paul等[72]將類間距離和類內(nèi)距離度量作為兩個相互沖突的目標(biāo)，利用模糊規(guī)則從最終的Pareto前沿提取單個解，提出一種MOEA/D過濾式特征選擇算法。

在EC技術(shù)中，GA算法的多目標(biāo)算法是最受歡迎的，但是這些工作只是簡單地應(yīng)用GA而不考慮特征選擇的特點(diǎn)[11]，因此對GA進(jìn)行多目標(biāo)特征選擇還需要進(jìn)行深入的研究。

4 總結(jié)與展望

近年來，進(jìn)化計(jì)算技術(shù)較為廣泛地應(yīng)用于特征選擇并取得了較大的成功。特征選擇也已成為EC的一個重要應(yīng)用領(lǐng)域。通過歸納已有研究工作，將未來EC技術(shù)在特征選擇上的研究問題歸納如下。

(1)隨著數(shù)據(jù)規(guī)模越來越大，許多領(lǐng)域的特征數(shù)量達(dá)到數(shù)千甚至數(shù)百萬，增加了計(jì)算成本。然而，僅靠通過增加計(jì)算能力是無法解決的，這就需要先進(jìn)的搜索機(jī)制。現(xiàn)有的基于進(jìn)化計(jì)算的大規(guī)模特征選擇方法大多采用兩階段方法，第一階段采用度量方法對單個特征進(jìn)行相關(guān)性評價，然后根據(jù)相關(guān)性值對其進(jìn)行排序。只有排名最靠前的(更好的)特征才會被用作第二階段的輸入，進(jìn)一步從中選擇特征。但是，第一階段刪除了排名較低的特征，并未考慮它們與其他特征的交互。為了解決這一問題，需要新的搜索算法和新的評價措施。

(2)大多數(shù)特征選擇方法由于涉及大量的評價，計(jì)算成本較高，是進(jìn)化計(jì)算在特征選擇上的一個關(guān)鍵問題。為了降低計(jì)算成本，需要高效搜索技術(shù)和快速評估措施。目前的方法中，評價過程占據(jù)了大部分的計(jì)算成本。因此，快速評價準(zhǔn)則比搜索技術(shù)影響更大。進(jìn)化計(jì)算的可并行性適合于網(wǎng)格計(jì)算、圖形處理單元和云計(jì)算，可以用來加速評價過程。

(3)特征選擇本質(zhì)上是組合優(yōu)化問題，隨著特征維數(shù)的增加會導(dǎo)致“維數(shù)災(zāi)難”，傳統(tǒng)的窮舉法容易陷入局部最優(yōu)，因此需要一種強(qiáng)大的全局搜索技術(shù)。EC算法是一種隨機(jī)方法，使用不同的起始點(diǎn)可能產(chǎn)生不同的解，即使解的適應(yīng)度值相同，也可能選擇不同的個體特征。這就要求新的搜索機(jī)制應(yīng)具有穩(wěn)定性。然而，算法的穩(wěn)定性不僅涉及適應(yīng)度值的差異，還涉及所選特征的一致性。因此，提出新的高穩(wěn)定性的搜索算法也是一項(xiàng)重要的任務(wù)。

(4)評價指標(biāo)構(gòu)成的適應(yīng)度函數(shù)，在很大程度上影響了計(jì)算時間、分類性能和搜索空間的分布，是特征選擇的關(guān)鍵因素。封裝式和過濾式的大部分計(jì)算時間都用在評估過程中。目前有一些快速評估方法，如交互信息，但它們都是單獨(dú)評估特征，而不是一組特征。如果忽略特征之間的交互會導(dǎo)致特征子集具有冗余性并缺少互補(bǔ)特征，從而無法在大多數(shù)領(lǐng)域中實(shí)現(xiàn)最佳分類性能。特征交互是一項(xiàng)復(fù)雜且具有挑戰(zhàn)性的任務(wù)，目前在這方面的工作還很少。

(5)大多數(shù)進(jìn)化計(jì)算方法中，傳統(tǒng)表示方法在特征選擇問題上存在很大的搜索空間。一個好的表示方法可以減少搜索空間的大小，從而有助于設(shè)計(jì)新的搜索機(jī)制來提高搜索能力。目前的表示方法通常只反映是否選擇了某個特性，而不顯示特征之間的交互信息。如果表示能夠反映特征組的選擇或刪除，則可以顯著提高分類性能。