采用進(jìn)化計(jì)算的高維多模態(tài)特征選擇

摘要：針對(duì)特征選擇問題中的多模態(tài)特性和高維特性，引入新的種群初始化策略對(duì)大規(guī)模多模態(tài)多目標(biāo)優(yōu)化算法進(jìn)行改進(jìn)，提出了一種基于進(jìn)化多目標(biāo)優(yōu)化的高維多模態(tài)特征選擇算法。對(duì)原始的連續(xù)優(yōu)化算法進(jìn)行離散化處理，用于評(píng)價(jià)離散優(yōu)化問題中的個(gè)體，并在6個(gè)高維特征選擇數(shù)據(jù)集上進(jìn)行驗(yàn)證。結(jié)果表明：所提算法提升了初始種群的質(zhì)量并加快了算法的收斂；相比于其他同類算法，所提算法獲得了更優(yōu)的帕累托前沿，其超體積指標(biāo)值整體最優(yōu)，并且在不影響分類精度的前提下可獲得平均2.53個(gè)等效特征子集，表明所提算法具有最好的分類精度和最多樣化的等效特征子集。

關(guān)鍵詞：分類；特征選擇；進(jìn)化計(jì)算；多模態(tài)多目標(biāo)優(yōu)化；高維多模態(tài)特征選擇

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)志碼：A

DOI：10.7652/xjtuxb202409012 文章編號(hào)：0253-987X（2024）09-0117-12

High-Dimensional Multimodal Feature Selection Based on Evolutionary Computation

DING Zhuanlian1， HU Xi1， CAO Lüe1， SUN Dengdi2， ZHANG Xingyi3， WANG Chenxu4

（1. School of Internet， Anhui University， Hefei 230039， China; 2. School of Artificial Intelligence，

Anhui University， Hefei 230601， China; 3. School of Computer Science and Technology，

Anhui University， Hefei 230601， China; 4. School of Software Engineering， Xi’an

Jiaotong University， Xi’an 710049， China）

Abstract：Aiming at multimodal and high-dimensional characteristics in feature selection problems， a new population initialization strategy is introduced to improve the large-scale multimodal multiobjective optimization algorithm， and a high-dimensional multimodal feature selection algorithm based on evolutionary multiobjective optimization is proposed. The original continuous optimization algorithm is discretized to evaluate individuals in discrete optimization problems. This approach is validated across six high-dimensional feature selection datasets. Results demonstrate that the proposed algorithm improves the quality of the initial population and accelerates algorithm convergence. Compared to other algorithms， the proposed algorithm yields the superior Pareto front with the best overall hypervolume value. It can obtain an average of 2.53 equivalent feature subsets without compromising classification accuracy. These results show the proposed algorithm’s ability to achieve optimal classification accuracy and the most diverse equivalent feature subsets.

Keywords：classification; feature selection; evolutionary computation; multimodal multiobjective optimization; high-dimension multimodal feature selection

特征選擇是機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘中的一項(xiàng)重要技術(shù)，是當(dāng)前信息領(lǐng)域的研究熱點(diǎn)之一［1］。特征選擇旨在從眾多的候選特征中選出某些最有效的特征，其目標(biāo)是得到令人滿意的分類精度且使用的特征數(shù)量較少［1］。在真實(shí)世界中，很多分類問題的原始特征集中無關(guān)或冗余的特征數(shù)量較多，這些特征在擾亂學(xué)習(xí)過程的同時(shí)嚴(yán)重影響分類精度，因此特征選擇問題得到廣泛的關(guān)注和研究。

經(jīng)過多年研究，大量的特征選擇方法被提出，包括傳統(tǒng)特征選擇方法［2-3］和基于進(jìn)化計(jì)算的特征選擇方法［4］。傳統(tǒng)特征選擇辦法一般存在諸如嵌套效應(yīng)、難以確定重要參數(shù)、容易陷入局部最優(yōu)等問題。例如，序列前向選擇［2］和序列后向選擇［3］這類常用的封裝式特征選擇方法會(huì)受到嵌套效應(yīng)的影響。進(jìn)化計(jì)算模擬生物的演化過程，是一種隨機(jī)全局優(yōu)化方法。由于進(jìn)化計(jì)算在全局搜索方面發(fā)揮出巨大作用，故而在特征選擇問題中應(yīng)用廣泛［5］。進(jìn)化計(jì)算方法的優(yōu)勢(shì)主要在于：作為一種基于種群的方法，能夠綜合探索整個(gè)搜索空間；在搜索過程中對(duì)特征的選擇沒有限制，能克服嵌套效應(yīng)和容易陷入局部最優(yōu)問題；能同步搜索多個(gè)解，具有強(qiáng)大的并行搜索能力。

對(duì)于特征選擇問題，決策者希望在獲取較高分類精度的同時(shí)使用較少數(shù)量的特征，因此特征選擇問題是一個(gè)多目標(biāo)優(yōu)化問題［6］。同時(shí)，由于具有相同特征數(shù)量的不同特征子集往往可以得到相同或相似的分類精度，因此這種特征選擇問題是一類多模態(tài)多目標(biāo)優(yōu)化問題。如果一個(gè)多目標(biāo)優(yōu)化問題至少有兩個(gè)等效的全局帕累托最優(yōu)解，它們對(duì)應(yīng)帕累托前沿上同一點(diǎn)，則稱該問題為多模態(tài)多目標(biāo)優(yōu)化問題，此類問題具有多模態(tài)特性［7］。在一些現(xiàn)實(shí)應(yīng)用中，經(jīng)常會(huì)出現(xiàn)同時(shí)需要多個(gè)等效的全局或局部最優(yōu)特征子集的情況，因?yàn)槟硞€(gè)最優(yōu)特征子集可能會(huì)包含過于昂貴的特征，這種特征子集在現(xiàn)實(shí)中不會(huì)被選擇。為了給決策者提供更多的可供選擇的方案，一些學(xué)者致力于研究特征選擇中的多模態(tài)多目標(biāo)優(yōu)化問題并取得了較好的結(jié)果［7-8］。然而，真實(shí)世界中問題的規(guī)模通常是不可控的。面對(duì)高維特征，傳統(tǒng)的多模態(tài)優(yōu)化方法無法獲得令人滿意的結(jié)果，因?yàn)樗鼈儾荒苡行?yīng)對(duì)高維數(shù)據(jù)所帶來的“維數(shù)災(zāi)難”問題。近年來，一些求解高維特征選擇問題的大規(guī)模多目標(biāo)優(yōu)化算法被提出，如SparseEA［9］和SLMEA算法［10］。然而遺憾的是，這些算法并不能處理特征選擇問題中的多模態(tài)特性。由于目前這方面的工作還很少，因此研究高維多模態(tài)特征選擇問題的求解具有重要意義。

1 相關(guān)工作

1.1 多模態(tài)特征選擇問題

特征選擇中有兩個(gè)主要待優(yōu)化目標(biāo)，即分類精度和選擇特征的數(shù)量。多目標(biāo)特征選擇問題［6］通常在數(shù)學(xué)上定義為

minx f1（x）=1D∑Di=1xi

minx f2（x）=ErrorRate（x） （1）

式中：決策變量x表示一個(gè)特征子集；D表示初始特征的個(gè)數(shù)；f1（x）表示選擇的特征數(shù)量占候選特征數(shù)的比例；f2（x）表示每種特征組合對(duì)應(yīng)的模型分類錯(cuò)誤率。

在多目標(biāo)特征選擇中，通常難以通過單個(gè)解使其所有目標(biāo)達(dá)到最優(yōu)，對(duì)此可以通過進(jìn)化算法來找到多個(gè)目標(biāo)之間的最優(yōu)解集。這些解集中可能包含多個(gè)不同的特征子集，但這些特征子集擁有的特征數(shù)量和實(shí)現(xiàn)的分類精度都是相同的，這便是多模態(tài)特征選擇問題［2］。如圖1所示，兩個(gè)待優(yōu)化的目標(biāo)f1和f2分別代表選擇的特征數(shù)量和分類錯(cuò)誤率，虛線表示的是這個(gè)多目標(biāo)優(yōu)化問題的帕累托前沿，F(xiàn)1～F5是為決策者提供的5個(gè)可選特征，其中藍(lán)色意味著該特征被選擇，白色則表示該特征未被選擇。從圖1不難發(fā)現(xiàn)，在f1=1、f2=0.8時(shí)存在{F1}、{F4}這兩個(gè)等效的特征子集。類似地，在f1=3、f2=0.35時(shí)有兩個(gè)等效的特征子集{F2， F3， F4}、{F1， F2， F3}。一般的進(jìn)化計(jì)算方法只會(huì)給出一個(gè)特征子集，而無法給出等效的特征子集。舉個(gè)簡(jiǎn)單的例子，假設(shè){F1， F2， F3}是一個(gè)細(xì)胞的形態(tài)特征（如體積、面積、質(zhì)量等），{F4}是這個(gè)細(xì)胞的光學(xué)特征（如吸收光譜的長(zhǎng)度等），在現(xiàn)實(shí)世界中，由于獲取細(xì)胞的形態(tài)特征會(huì)比獲取細(xì)胞的光學(xué)特征更加容易，因此用戶可以根據(jù)自己的偏好或?qū)嶋H情況進(jìn)行選擇?？梢?，求解多模態(tài)特征選擇問題時(shí)，為決策者提供更多可選擇的解決方案是必要的。

此外，真實(shí)世界中的高維度大規(guī)模數(shù)據(jù)集會(huì)引起維度災(zāi)難。具有高維度大規(guī)模特征的多模態(tài)特征選擇問題稱之為高維多模態(tài)特征選擇問題。由于要同時(shí)考慮高維特性和多模態(tài)特性，因此解決此類問題需要特殊的多模態(tài)多目標(biāo)優(yōu)化算法，這是一項(xiàng)具有挑戰(zhàn)性的任務(wù)。

1.2 多模態(tài)多目標(biāo)優(yōu)化

不失一般性，多目標(biāo)優(yōu)化問題（MOP）［7］在數(shù)學(xué)上可以定義為

minx f（x）=（f1（x），f2（x），…，fm（x））

s.t. x∈Ω （2）

式中：x=（x1，x2，…，xD）是一個(gè)在決策空間Ω中的D維決策向量；f（x）是一個(gè)包含m個(gè)沖突目標(biāo)的目標(biāo)函數(shù)。對(duì)于決策空間Ω中的兩個(gè)不同的解x1和x2，當(dāng)且僅當(dāng)滿足式（3），則稱x1支配x2，記為x1x2

（i：fi（x1）≤fi（x2））∧（j：fj（x1）lt;fj（x2）） （3）

式中：i，j∈1，2，…，m。此外，如果一個(gè)解沒有被任何解所支配，則稱這個(gè)解是一個(gè)帕累托（Pareto）最優(yōu)解。

多模態(tài)多目標(biāo)優(yōu)化問題（MMOP）是一類具有多模態(tài)特性的多目標(biāo)優(yōu)化問題，求解MMOP的目的是為相同的帕累托前沿（PF）找到所有等效的帕累托解集（PS）。在實(shí)際應(yīng)用中，往往存在約束條件或環(huán)境變化，而這些因素又難以在問題定義的公式中直接表示出來，因此一些解在實(shí)際中可能是不可行的。可見，有必要提供多個(gè)等效的PS作為決策者的替代選擇。

近年來，涌現(xiàn)出大量多模態(tài)多目標(biāo)優(yōu)化算法有效解決了MMOP［7］。其中，一些算法通過決策空間中的擁擠距離來完成環(huán)境選擇。例如，Omni-optimizer算法［11］同時(shí)引入決策空間和目標(biāo)空間中每個(gè)解的擁擠距離，以平衡兩個(gè)空間中Pareto最優(yōu)解的多樣性算法。除此之外，小生境策略在解決MMOP問題時(shí)候也被廣泛使用。例如，DN-NSGA-Ⅱ算法在交配池選擇中采用了基于決策空間的小生境方法，有助于為相同的PF找到多個(gè)等效的PS［12］；MO_Ring_PSO_SCD算法采用了環(huán)形拓?fù)浣Y(jié)構(gòu)用于形成穩(wěn)定的小生境并在進(jìn)化過程中使用特殊擁擠距離［13］；類似地，RHEA算法也采用了基于環(huán)形拓?fù)浣Y(jié)構(gòu)的方法，在解決尋找等效PS時(shí)收斂性和多樣性不平衡問題的同時(shí)能夠保留優(yōu)秀的局部PS［14］。另外，基于分解的策略也常受到研究者的關(guān)注。例如，MOEA/D-AD與MMEA-DES算法采用將一個(gè)或多個(gè)個(gè)體分配給同一個(gè)子問題的方法解決MMOP問題［15-16］。DESS算法是一種有效的子集選擇框架［17］，通過同時(shí)考慮決策空間和目標(biāo)空間的多樣性來選擇解集，用以提高各種MMEAs算法的性能。此外，還有很多其他方法被用來解決MMOP問題。例如，CoMMEA算法通過引入多樣性存檔和收斂性存檔協(xié)同進(jìn)化獲得全局和局部PS［18］；CMMO算法通過兩個(gè)種群協(xié)同進(jìn)化平衡目標(biāo)空間和決策空間的多樣性和收斂性［19］；HREA算法采用了層次排名的方法求解多模態(tài)問題。聚類方法也常被用于求解多模態(tài)問題［20］，如GSMPSO-MM算法采用K均值聚類［21］，MMODE_CSCD算法使用基于聚類的特殊擁擠距離［22］。此外，許多優(yōu)秀的多模態(tài)多目標(biāo)優(yōu)化方法也相繼被提出以提高算法性能。

實(shí)際應(yīng)用中的一些多模態(tài)多目標(biāo)優(yōu)化問題含有非常多的決策變量，這類問題稱之為大規(guī)模多模態(tài)多目標(biāo)優(yōu)化問題。雖然采用上述多模態(tài)多目標(biāo)優(yōu)化方法求解MMOP均取得了較好的效果，但是這些方法在應(yīng)用于高維問題時(shí)還面臨一些挑戰(zhàn)。現(xiàn)有的多模態(tài)多目標(biāo)優(yōu)化方法由于難以在高維的搜索空間中度量種群多樣性，同時(shí)搜索能力變?nèi)酰茈y找到所有等效的PS，因此無法滿足求解大規(guī)模多模態(tài)多目標(biāo)優(yōu)化問題的要求。此外，現(xiàn)實(shí)世界中很多問題的Pareto最優(yōu)解具有稀疏特性，即大多數(shù)決策變量為0。高維搜索空間和問題未知的稀疏特性給求解此類多目標(biāo)求解問題帶來了很大的挑戰(zhàn)?？傮w而言，這類問題的研究仍處在初級(jí)階段。到目前為止，僅MP-MMEA［23］和HHC-MMEA［24］算法專注于解決這類問題。

現(xiàn)實(shí)世界中存在很多大規(guī)模多模態(tài)多目標(biāo)優(yōu)化問題，如神經(jīng)網(wǎng)絡(luò)權(quán)值訓(xùn)練、神經(jīng)網(wǎng)絡(luò)架構(gòu)搜索及上述特征選擇等問題。然而，到目前為止，針對(duì)高維多模態(tài)特征選擇問題的研究非常少，該問題的求解還需要深入研究。高維多模態(tài)特征選擇的難點(diǎn)在于如何在高維的搜索空間中找到盡可能多的等效特征子集。傳統(tǒng)的多目標(biāo)優(yōu)化方法只能找到一個(gè)特征子集，且在優(yōu)化過程中找到等效的特征子集也會(huì)被丟棄，因此傳統(tǒng)方法難以實(shí)現(xiàn)多模態(tài)特征選擇在決策空間中解集分布具有多樣性的需求。由于大規(guī)模多模態(tài)多目標(biāo)優(yōu)化方法具有較強(qiáng)的探索能力及能夠在一次運(yùn)行中找到多個(gè)合適的解，因此該類方法可以被認(rèn)為是求解高維多模態(tài)特征選擇問題的有力工具。然而，由于該類問題的困難與復(fù)雜，目前多模態(tài)多目標(biāo)優(yōu)化算法在該問題上應(yīng)用的效果依舊有著巨大的提升空間。HHC-MMEA算法中的多種群協(xié)同進(jìn)化機(jī)制以及引入的混合層次聚類技術(shù)能夠有效區(qū)分進(jìn)化中的不同等效特征子集，提高算法的搜索能力，促使算法找到更多的等效特征子集。因此，本文對(duì)大規(guī)模多模態(tài)多目標(biāo)優(yōu)化算法HHC-MMEA進(jìn)行改進(jìn)，提出了一種基于進(jìn)化多目標(biāo)優(yōu)化的高維多模態(tài)特征選擇算法（FS-HHC-MMEA）。該算法采用HHC-MMEA算法框架，引入新的種群初始化策略來加快算法的收斂。另外，本文對(duì)連續(xù)優(yōu)化算法HHC-MMEA進(jìn)行了離散化處理用于求解特征選擇問題。

2 基于進(jìn)化多目標(biāo)優(yōu)化的高維多模態(tài)特征選擇

2.1 算法描述

本文所提FS-HHC-MMEA算法使用改進(jìn)的HHC-MMEA算法來搜索具有多模態(tài)特性的等效特征子集，算法總體流程如算法1所示。

算法1 FS-HHC-MMEA（N）

輸入：種群大小N

輸出：等效特征子集P

1 G← 獲取全局指導(dǎo)向量;

2 P←Initialization（N，G）; //算法2

3 K=1; //初始子種群數(shù)量

4 while{未達(dá)到最大迭代次數(shù)} do

5" for i=1 to K do

6"" I←更新第i個(gè)子種群的局部指導(dǎo)向量;

7"" 計(jì)算每個(gè)個(gè)體的特征個(gè)數(shù)和分類錯(cuò)誤率;

8"" Q←根據(jù)二元錦標(biāo)賽選擇2N/K個(gè)父代;

9"" offerspring←自適應(yīng)交叉變異產(chǎn)生子代;

10"" subPi←環(huán)境選擇（subPi∪offerspring）;

11" end for

12" ［K，subP1，…， subPk］←每隔一定代數(shù)進(jìn)行混合層次聚類;

13 end while

14 P←subP1∪…∪subPk;

15 P←根據(jù)P中非支配解集獲得等效特征子集;

16 return P

首先，將數(shù)據(jù)集劃分成80%訓(xùn)練數(shù)據(jù)和20%測(cè)試數(shù)據(jù)［9］。其次，采用決策變量分析方法［9］獲得全局指導(dǎo)向量（每個(gè)決策變量的得分），并利用新的種群初始化策略初始化種群個(gè)體。然后，計(jì)算每個(gè)個(gè)體的兩個(gè)目標(biāo)值，即選擇的特征個(gè)數(shù)和利用KNN分類器得到的預(yù)測(cè)分類錯(cuò)誤率。最后，采用HHC-MMEA算法中的子種群協(xié)同進(jìn)化搜索多個(gè)等效特征子集。子種群的協(xié)同進(jìn)化主要由以下幾部分組成。首先，利用文獻(xiàn)［23］提出的方法獲得局部指導(dǎo)向量來確定每個(gè)子種群的搜索方向。然后，根據(jù)非支配前沿等級(jí)和解的擁擠度距離采取二元錦標(biāo)選擇策略選擇交配父本。接著，使用基于全局指導(dǎo)向量和局部指導(dǎo)向量的自適應(yīng)交叉及變異策略生成子代解，并利用改進(jìn)的環(huán)境選擇策略保留質(zhì)量好的解。最后，使用混合層次聚類技術(shù)有效區(qū)分不同等效特征子集的分支從而將其盡可能地劃分到不同子種群中，實(shí)現(xiàn)多個(gè)子種群間的高效合作以及協(xié)同進(jìn)化。

2.2 新的種群初始化策略

相關(guān)研究表明，好的初始化策略對(duì)于提高算法的性能至關(guān)重要［25］。對(duì)于高維多模態(tài)特征選擇問題，多模態(tài)最優(yōu)特征子集在整個(gè)決策空間中分布非常稀疏，即大部分決策變量位的值都是0。在高維多模態(tài)特征選擇中，隨機(jī)初始化可能無法產(chǎn)生良好的效果，需要考慮初始解在多目標(biāo)空間中的分布。原始HHC-MMEA算法中的拉丁超立方體采樣種群初始化僅考慮初始解在特征數(shù)量上分布的均勻性，卻忽略了特征的質(zhì)量。新的種群初始化策略在原有的均勻采樣基礎(chǔ)上，基于全局指導(dǎo)向量，根據(jù)每個(gè)決策變量的得分采用類似二元錦標(biāo)賽的方法來初始化種群，同時(shí)考慮了特征數(shù)量和特征質(zhì)量，進(jìn)而從解的多樣性和解的質(zhì)量方面提供更好的初始解。新的種群初始化策略的詳細(xì)流程如算法2所示。

算法2 Initialization（N，G）

輸入：種群大小N，全局指導(dǎo)向量G

輸出：初始種群P

1 D←決策變量的數(shù)量;

2 ［r1， r2， …， rN］←隨機(jī)生成N個(gè)實(shí)值向量;

3 ［b1， b2， …， bN］←使用拉丁超立方均勻采樣生成N個(gè)二進(jìn)制向量;

4 r←G;

5 for i=1 to N

6" for j=1 to R×D //R表示介于0和1之間均勻分布的隨機(jī)數(shù)

7"" ［m， n］←隨機(jī)挑選兩個(gè)決策變量位;

8"" if rmgt;rn then

9""" bmi←0;

10"" rm←rm－1;

11"" else

12"" bni←0;

13"" rn←rn－1;

14"" end if

15" end for

16 end for

17 P←［r1，r2，…，rN］和［b1，b2，…，bN］對(duì)應(yīng)位置的元素逐個(gè)相乘;

18 return P

該算法采用雙層編碼的方式進(jìn)行優(yōu)化。首先，隨機(jī)生成決策空間中的實(shí)值向量，利用拉丁超立方體均勻采樣生成二進(jìn)制向量。然后，在拉丁超立方體均勻采樣的基礎(chǔ)上根據(jù)決策變量的重要性程度對(duì)決策位進(jìn)行翻轉(zhuǎn)。輔助向量r首先初始化為全局指導(dǎo)向量，然后每次隨機(jī)挑選兩個(gè)決策變量位，比較其對(duì)應(yīng)的輔助向量r上的得分值（決策變量得分值越高說明該特征的重要性越低），將重要性較低的決策變量位置為0，同時(shí)將其對(duì)應(yīng)的得分減1。該策略在初始化階段可以篩選掉一些不重要的特征，從而可以生成具有較高質(zhì)量的初始解，加快算法的收斂。

為了驗(yàn)證新的種群初始化策略的有效性，圖2給出了HHC-MMEA算法所采用的原始拉丁超立方體采樣初始化策略與本文提出的FS-HHC-MMEA算法采用的新的種群初始化策略，在標(biāo)準(zhǔn)大規(guī)模多模態(tài)測(cè)試問題SMMOP1［23］上產(chǎn)生的初始解的二進(jìn)制變量的統(tǒng)計(jì)結(jié)果。可以看出，拉丁超立方體采樣初始化策略產(chǎn)生的初始解在特征數(shù)量目標(biāo)上分布非常均勻，但未考慮到特征的重要性差異。圖中SMMOP1問題對(duì)應(yīng)等效PS的個(gè)數(shù)為4，決策變量數(shù)為100，其中第1維到40維對(duì)應(yīng)重要決策變量位。新的種群初始化策略不僅考慮了種群分布的多樣性，也考慮了特征的重要性差異，篩選掉了一些不重要的特征，因此新的種群策略所包含的特征數(shù)量相較于原始策略會(huì)顯著變少，加快了算法的收斂。

圖3展示了兩種初始化策略對(duì)應(yīng)的算法在標(biāo)準(zhǔn)大規(guī)模多模態(tài)測(cè)試問題SMMOP1、SMMOP6、SMMOP7和SMMOP8［23］上的決策空間反世代距離（IGDX）［8］收斂曲線。該問題對(duì)應(yīng)等效PS的個(gè)數(shù)為4，決策變量數(shù)為100。從圖3不難發(fā)現(xiàn)，與原始拉丁超立方體采樣初始化策略相比，新的種群初始化策略在初始時(shí)擁有更低的反世代距離（值越小越好），表明其在進(jìn)化初始階段種群擁有更好的起點(diǎn)。新的種群初始化策略既考慮了初始解在特征數(shù)上分布的均勻性，又考慮了特征對(duì)目標(biāo)函數(shù)值的貢獻(xiàn)度，提高了所產(chǎn)生的初始解的質(zhì)量，從而達(dá)到加快算法收斂的目的。

2.3 個(gè)體評(píng)價(jià)

因?yàn)樵嫉腍HC-MMEA算法是連續(xù)優(yōu)化算法，不能直接用來求解特征選擇這類離散組合優(yōu)化問題，所以要對(duì)其進(jìn)行特殊處理。圖4展示了經(jīng)處理的算法對(duì)每個(gè)個(gè)體目標(biāo)值的計(jì)算方式。通過選定閾值0.5，將實(shí)數(shù)映射為0或1二進(jìn)制位，其中0表示該特征不被選擇，1表示該特征被選擇。當(dāng)某一維度的特征值大于0.5時(shí)，表示該維特征被選擇，反之，表示該維特征被舍棄。例如，圖4中選擇的特征子集為{F1， F4}，將選擇的特征子集送入到分類器中得到分類精度，這里采用廣泛使用的KNN分類器，其中K值被設(shè)置為3［9］。這樣就得到了選擇的特征數(shù)量以及分類錯(cuò)誤率兩個(gè)目標(biāo)值，完成了一個(gè)個(gè)體的評(píng)價(jià)。

2.4 復(fù)雜度分析

對(duì)于FS-HHC-MMEA算法，時(shí)間復(fù)雜度主要由以下幾個(gè)部分組成。假設(shè)種群的大小為N，目標(biāo)空間和決策空間的維度分別為M和D，子種群的數(shù)量為K，種群初始化的時(shí)間復(fù)雜度為O（ND），所有個(gè)體非支配排序的時(shí)間復(fù)雜度為O（MN2），子種群引導(dǎo)向量的更新和子代解的生成具有O（ND）的時(shí)間復(fù)雜度，環(huán)境選擇時(shí)間復(fù)雜度為O（ND），混合層次聚類的時(shí)間復(fù)雜度為O（ND），最終得到FS-HHC-MMEA算法的時(shí)間復(fù)雜度為O（MN2+ND）。

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

為了驗(yàn)證新的種群初始化策略解決高維多模態(tài)特征選擇問題的有效性，圖5給出了新的種群初始化策略與拉丁超立方體采樣初始化策略在lung_discrete、Colon數(shù)據(jù)集特征選擇問題上的初始解。由圖5可見，新的種群初始化策略得到的解支配了拉丁超立方體采樣初始化策略所得到的多數(shù)解，且后者明顯含有更少的特征數(shù)量。因此，新的種群初始化策略可以產(chǎn)生特征數(shù)量更少、質(zhì)量更好的初始解。

為了驗(yàn)證算法解決高維多模態(tài)特征選擇的有效性，本文在來自亞利桑那州立大學(xué)（ASU）的6個(gè)基準(zhǔn)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，數(shù)據(jù)集的信息如表1所示。每個(gè)數(shù)據(jù)集被劃分成訓(xùn)練集（80%）和測(cè)試集（20%），實(shí)驗(yàn)采用常用的KNN分類器預(yù)測(cè)分類精度，其中K設(shè)置為3。由于實(shí)際問題的真實(shí)帕累托前沿未知，因此本文采用廣泛使用的超體積指標(biāo)［26］作為算法的性能指標(biāo)。超體積指標(biāo)估計(jì)了解集中的點(diǎn)與參考點(diǎn)所圍成區(qū)域的超體積，值越大表示解集的多樣性和收斂性越好。關(guān)于超體積指標(biāo)中參考點(diǎn)的選取可參考文獻(xiàn)［27］。

本文對(duì)比了MO_Ring_PSO_SCD［13］、MP-MMEA［23］、HREA［20］和SLMEA［10］4種算法以證明FS-HHC-MMEA算法在求解高維多模態(tài)特征選擇問題上的有效性， 其中MO_Ring_PSO_SCD和HREA算法是具有代表性的多模態(tài)多目標(biāo)優(yōu)化算法，MP-MMEA算法是一種先進(jìn)的大規(guī)模多模態(tài)多目標(biāo)進(jìn)化算法，SLMEA算法代表稀疏大規(guī)模多目標(biāo)優(yōu)化算法。為了保證公平，對(duì)于所有算法，種群大小設(shè)置為800，評(píng)價(jià)次數(shù)設(shè)置為500000。除特別說明外，每個(gè)算法的參數(shù)采用其在相關(guān)文獻(xiàn)中的推薦設(shè)置。MO_Ring_PSO_SCD算法基于粒子群優(yōu)化生成子代［13］，其中參數(shù)C1、C2、W分別設(shè)置為0.5，0.5和0.1。對(duì)于其他算法，采用單點(diǎn)交叉和位變異產(chǎn)生二進(jìn)制變量的子代解，采用模擬二進(jìn)制交叉和多項(xiàng)式變異生成實(shí)數(shù)變量的子代解，其中交叉概率設(shè)置為1，變異概率設(shè)置為1/D（D為決策變量維數(shù)），交叉和變異的分布指數(shù)均設(shè)置為20。所有算法的最終結(jié)果只輸出非支配解。

表2列出了所有算法在6個(gè)數(shù)據(jù)集上分別進(jìn)行30次獨(dú)立運(yùn)行得到的平均超體積指標(biāo)。圖6、圖7和圖8展示了所有算法在不同數(shù)據(jù)集上得到的帕累托前沿。從表2可以看出，除了MO_Ring_PSO_SCD與HREA算法外，其他3種算法在6個(gè)數(shù)據(jù)集上都取得了較好的超體積指標(biāo)。從圖6、圖7和圖8可以看出，除了MO_Ring_PSO_SCD與HREA算法外，其他3種算法在目標(biāo)空間都能夠獲得較優(yōu)的帕累托前沿。

由于MP-MMEA、SLMEA和FS-HHC-MMEA這3種算法都是大規(guī)模多目標(biāo)優(yōu)化算法，因此在解決高維問題時(shí)都獲得了較高的超體積指標(biāo)值與較優(yōu)的帕累托前沿。FS-HHC-MMEA算法的超體積指標(biāo)值在6個(gè)數(shù)據(jù)集上獲得了5個(gè)具有競(jìng)爭(zhēng)力的結(jié)果，整體上取得了最好的結(jié)果，說明目標(biāo)空間得到多樣性和收斂性更好的解集。從圖8的帕累托前沿可看出，F(xiàn)S-HHC-MMEA算法得到的特征子集具有最好的分類精度和最多樣化的特征數(shù)量。

MO_Ring_PSO_SCD多模態(tài)優(yōu)化算法在面對(duì)高維問題時(shí)很難收斂到最優(yōu)的帕累托前沿，從而可看出MO_Ring_PSO_SCD算法不適用于高維問題，因此接下來的實(shí)驗(yàn)部分將不再展示MO_Ring_PSO_SCD算法的性能。HREA多模態(tài)優(yōu)化算法在325維的lung_discrete數(shù)據(jù)集上能夠收斂到帕累托前沿，而在2000維的Colon數(shù)據(jù)集上無法收斂到帕累托前沿，且在維度數(shù)量更多的其他數(shù)據(jù)集上，HREA算法運(yùn)行都超時(shí)（超過24h），無法運(yùn)行出實(shí)驗(yàn)結(jié)果，表2中用空白表示這種情形。HREA同樣難以面對(duì)高維問題所帶來的挑戰(zhàn)，因此下面將不再展示HREA算法性能。

圖9展示了MP-MMEA、SLMEA和FS-HHC-MMEA這3種算法在6個(gè)數(shù)據(jù)集上獲得的等效特征子集個(gè)數(shù)。圖10展示了各算法在每個(gè)數(shù)據(jù)集上獲得的平均等效特征子集個(gè)數(shù)。從圖9和圖10可以看出，SLMEA算法并不存在等效特征子集，因?yàn)镾LMEA算法沒有能力保存等效特征解，無法求解多模態(tài)多目標(biāo)優(yōu)化問題。在不影響分類精度的前提下，多模態(tài)多目標(biāo)優(yōu)化算法MP-MMEA能給出一些等效特征子集（所有數(shù)據(jù)集上的等效特征子集平均個(gè)數(shù)是1.50），而FS-HHC-MMEA算法能找到更多的等效特征子集（所有數(shù)據(jù)集上的等效特征子集平均個(gè)數(shù)是2.53）。例如，在CLL_SUB_111數(shù)據(jù)集上，當(dāng)特征個(gè)數(shù)為1和6時(shí)，F(xiàn)S-HHC-MMEA算法分別找到2個(gè)等效特征子集，而MP-MMEA算法只能找到1個(gè)特征子集。

表3展示了FS-HHC-MMEA算法在6個(gè)數(shù)據(jù)集上尋找到的帕累托最優(yōu)解集。由表3可以看出，算法找到的帕累托最優(yōu)解集不僅具有多模態(tài)特性，而且具有稀疏特性。具體來說，在Colon數(shù)據(jù)集上，{F317}、{F302}、{F842}和{F1623}4個(gè)特征子集所包含的特征個(gè)數(shù)相同，而且分類錯(cuò)誤率也相等，都為0.0833。因此，該結(jié)果為特征選擇問題提供了多個(gè)可選的最優(yōu)特征子集，決策者可根據(jù)問題領(lǐng)域的成本和限制來選擇合適的特征子集。FS-HHC-MMEA算法在其他數(shù)據(jù)集中也找到了多個(gè)等效的特征子集。結(jié)合圖8和圖9及表3來看，在保證較理想的稀疏多模態(tài)解搜索能力的先決條件下，F(xiàn)S-HHC-MMEA算法能同時(shí)得到較優(yōu)的帕累托前沿。綜合來看，F(xiàn)S-HHC-MMEA算法是一種有效求解高維多模態(tài)特征選擇問題的算法。

4 結(jié) 論

針對(duì)特征選擇問題中的多模態(tài)特性和高維特性帶來的挑戰(zhàn)，本文基于改進(jìn)的大規(guī)模多模態(tài)進(jìn)化算法對(duì)高維多模態(tài)特征選擇問題進(jìn)行有效求解，結(jié)合實(shí)驗(yàn)驗(yàn)證，得出如下結(jié)論。

（1）引入新的種群初始化策略對(duì)大規(guī)模多模態(tài)多目標(biāo)優(yōu)化算法進(jìn)行改進(jìn)，實(shí)驗(yàn)結(jié)果表明新的種群初始化策略可以產(chǎn)生質(zhì)量更好的初始解，加速了算法的收斂。

（2）對(duì)原始的多模態(tài)多目標(biāo)優(yōu)化算法進(jìn)行離散化處理，用于評(píng)價(jià)特征選擇問題中的個(gè)體，并使用離散化的多模態(tài)多目標(biāo)優(yōu)化算法搜索具有多模態(tài)特性的特征子集。6個(gè)高維特征選擇數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文算法能夠找到更多的多模態(tài)特征子集并且獲得更優(yōu)的帕累托前沿。

值得注意的是，本文算法中的編碼并不能反映特征之間的相關(guān)性和相似性，因此一種更加有效的編碼方法有待進(jìn)一步研究。另外，本文僅考慮搜索高維多模態(tài)特征選擇問題中的多個(gè)最優(yōu)特征子集，而忽略了次優(yōu)特征子集的優(yōu)化，最優(yōu)和次優(yōu)最優(yōu)特征子集共存的高維多模態(tài)特征選擇問題的研究也是將來的努力方向之一。

參考文獻(xiàn)：

［1］商立群， 李洪波， 侯亞東， 等. 基于特征選擇和優(yōu)化極限學(xué)習(xí)機(jī)的短期電力負(fù)荷預(yù)測(cè) ［J］. 西安交通大學(xué)學(xué)報(bào)， 2022， 56（4）： 165-175.

SHANG Liqun， LI Hongbo， HOU Yadong， et al. Short-term power load forecasting based on feature selection and optimized extreme learning machine ［J］. Journal of Xi’an Jiaotong University， 2022， 56（4）： 165-175.

［2］劉彪， 劉金長(zhǎng). 基于用戶畫像分析預(yù)測(cè)電費(fèi)敏感型客戶的建模實(shí)踐 ［J］. 電力大數(shù)據(jù)， 2017， 20（8）： 20-24.

LIU Biao， LIU Jinchang. Modeling practice of forecasting electricity fees sensitive customers based on user profile analysis ［J］. Power Systems and Big Data， 2017， 20（8）： 20-24.

［3］PUDIL P， NOVOVICOV J， KITTLER J. Floating search methods in feature selection ［J］. Pattern Recognition Letters， 1994， 15（11）： 1119-1125.

［4］王艷麗. 基于多模態(tài)進(jìn)化計(jì)算的特征選擇算法研究 ［D］. 鄭州： 鄭州大學(xué)， 2020.

［5］王艷麗， 梁靜， 薛冰， 等. 基于進(jìn)化計(jì)算的特征選擇方法研究概述 ［J］. 鄭州大學(xué)學(xué)報(bào)（工學(xué)版）， 2020， 41（1）： 49-57.

WANG Yanli， LIANG Jing， XUE Bing， et al. Research on evolutionary computation for feature selection ［J］. Journal of Zhengzhou University（Engineering Science）， 2020， 41（1）： 49-57.

［6］張夢(mèng)婷， 杜建強(qiáng)， 羅計(jì)根， 等. 多目標(biāo)優(yōu)化特征選擇研究綜述 ［J］. 計(jì)算機(jī)工程與應(yīng)用， 2023， 59（3）： 23-32.

ZHANG Mengting， DU Jianqiang， LUO Jigen， et al. Research on feature selection of multi-objective optimization ［J］. Computer Engineering and Applications， 2023， 59（3）： 23-32.

［7］岳彩通， 梁靜， 瞿博陽， 等. 多模態(tài)多目標(biāo)優(yōu)化綜述 ［J］. 控制與決策， 2021， 36（11）： 2577-2588.

YUE Caitong， LIANG Jing， QU Boyang， et al. A survey on multimodal multiobjective optimization ［J］. Control and Decision， 2021， 36（11）： 2577-2588.

［8］ZHOU Aimin， ZHANG Qingfu， JIN Yaochu. Approximating the set of Pareto-optimal solutions in both the decision and objective spaces by an estimation of distribution algorithm ［J］. IEEE Transactions on Evolutionary Computation， 2009， 13（5）： 1167-1189.

［9］TIAN Ye， ZHANG Xingyi， WANG Chao， et al. An evolutionary algorithm for large-scale sparse multiobjective optimization problems ［J］. IEEE Transactions on Evolutionary Computation， 2020， 24（2）： 380-393.

［10］TIAN Ye， FENG Yuandong， ZHANG Xingyi， et al. A fast clustering based evolutionary algorithm for super-large-scale sparse multi-objective optimization ［J］. IEEE/CAA Journal of Automatica Sinica， 2023， 10（4）： 1048-1063.

［11］DEB K， TIWARI S. Omni-optimizer： a procedure for single and multi-objective optimization ［C］//Evolutionary Multi-Criterion Optimization. Berlin， Heidelberg： Springer Berlin Heidelberg， 2005： 47-61.

［12］LIANG J J， YUE C T， QU B Y. Multimodal multi-objective optimization： a preliminary study ［C］//2016 IEEE Congress on Evolutionary Computation （CEC）. Piscataway， NJ， USA： IEEE， 2016： 2454-2461.

［13］YUE Caitong， QU Boyang， LIANG Jing. A multiobjective particle swarm optimizer using ring topology for solving multimodal multiobjective problems ［J］. IEEE Transactions on Evolutionary Computation， 2018， 22（5）： 805-817.

［14］LI Guoqing， SUN Mengyan， WANG Yirui， et al. A ring-hierarchy-based evolutionary algorithm for multimodal multi-objective optimization ［J］. Swarm and Evolutionary Computation， 2023， 81： 101352.

［15］TANABE R， ISHIBUCHI H. A decomposition-based evolutionary algorithm for multi-modal multi-objective optimization ［C］//Parallel Problem Solving from Nature： PPSN ⅩⅤ. Cham， Switzerland： Springer International Publishing， 2018： 249-261.

［16］SUN Yu， ZHANG Shen. A decomposition and dynamic niching distance-based dual elite subpopulation evolutionary algorithm for multimodal multiobjective optimization ［J］. Expert Systems with Applications， 2023， 231： 120738.

［17］PENG Yiming， ISHIBUCHI H. A diversity-enhanced subset selection framework for multimodal multiobjective optimization ［J］. IEEE Transactions on Evolutionary Computation， 2022， 26（5）： 886-900.

［18］LI Wenhua， YAO Xingyi， LI Kaiwen， et al. Coevolutionary framework for generalized multimodal multi-objective optimization ［J］. IEEE/CAA Journal of Automatica Sinica， 2023， 10（7）： 1544-1556.

［19］MING Fei， GONG Wenyin， WANG Ling， et al. Balancing convergence and diversity in objective and decision spaces for multimodal multi-objective optimization ［J］. IEEE Transactions on Emerging Topics in Computational Intelligence， 2023， 7（2）： 474-486.

［20］LI Wenhua， YAO Xingyi， ZHANG Tao， et al. Hierarchy ranking method for multimodal multiobjective optimization with local Pareto fronts ［J］. IEEE Transactions on Evolutionary Computation， 2023， 27（1）： 98-110.

［21］LI Guoqing， WANG Wanliang， ZHANG Weiwei， et al. Grid search based multi-population particle swarm optimization algorithm for multimodal multi-objective optimization ［J］. Swarm and Evolutionary Computation， 2021， 62： 100843.

［22］LIANG Jing， QIAO Kangjia， YUE Caitong， et al. A clustering-based differential evolution algorithm for solving multimodal multi-objective optimization problems ［J］. Swarm and Evolutionary Computation， 2021， 60： 100788.

［23］TIAN Ye， LIU Ruchen， ZHANG Xingyi， et al. A multipopulation evolutionary algorithm for solving large-scale multimodal multiobjective optimization problems ［J］. IEEE Transactions on Evolutionary Computation， 2021， 25（3）： 405-418.

［24］DING Zhuanlian， CAO Lve， CHEN Lei， et al. Large-scale multimodal multiobjective evolutionary optimization based on hybrid hierarchical clustering ［J］. Knowledge-Based Systems， 2023， 266： 110398.

［25］BANGYAL W H， NISAR K， AG IBRAHIM A A B， et al. Comparative analysis of low discrepancy sequence-based initialization approaches using population-based algorithms for solving the global optimization problems ［J］. Applied Sciences， 2021， 11（16）： 7591.

［26］ISHIBUCHI H， IMADA R， MASUYAMA N， et al. Comparison of hypervolume， IGD and IGD+ from the viewpoint of optimal distributions of solutions ［C］//Evolutionary Multi-Criterion Optimization. Cham， Switzer-land： Springer International Publishing， 2019： 332-345.

［27］CHEN Huangke， TIAN Ye， PEDRYCZ W， et al. Hyperplane assisted evolutionary algorithm for many-objective optimization problems ［J］. IEEE Transactions on Cybernetics， 2020， 50（7）： 3367-3380.

（編輯 亢列梅）