摘" 要： 差分進(jìn)化算法（DE）是一類基于種群搜索最優(yōu)解的全局優(yōu)化算法，具有收斂速度快、算法簡(jiǎn)單易懂、參數(shù)數(shù)量少和穩(wěn)定性高等特點(diǎn)。但DE算法的性能在很大程度上取決于參數(shù)值的設(shè)置、個(gè)體突變的方向和距離?？紤]到不同的種群密度對(duì)參數(shù)的需求不同，采用主成分分析技術(shù)將30或50維的數(shù)據(jù)降到2維；再采用DBSCAN算法，依據(jù)鄰域半徑和最小鄰域數(shù)將2維數(shù)據(jù)分類為簇，通過(guò)簇的數(shù)量判斷種群整體密度和個(gè)體之間的差異度，并在不同取值范圍內(nèi)生成合適的變異因子和交叉因子，以此來(lái)滿足不同種群的進(jìn)化需求。通過(guò)基準(zhǔn)函數(shù)測(cè)試集和多個(gè)檢驗(yàn)方法驗(yàn)證，證明了所提方法的尋優(yōu)能力和魯棒性均優(yōu)于另外5種先進(jìn)算法。

關(guān)鍵詞： DBSCAN； 差分進(jìn)化算法； 主成分分析； 數(shù)據(jù)降維； 變異因子； 交叉因子

中圖分類號(hào)： TN911?34； TP312" " " " " " " " " "文獻(xiàn)標(biāo)識(shí)碼： A" " " " " " " " " " " 文章編號(hào)： 1004?373X（2024）16?0171?09

Improved differential evolution algorithm based on PCA?DBSCAN classification

XUE Caiwen1， LIU Tong1， DENG Libao2， GU Wei1， ZHANG Baowu1

（1. College of Metrology and Measurement Engineering， China Jiliang University， Hangzhou 310018， China;

2. School of Information and Electrical Engineering， Harbin Institute of Technology， Weihai 264209， China）

Abstract： Differential evolution （DE） algorithm is a type of global optimization algorithm based on population search for the optimal solution. It has the characteristics of fast convergence speed， simple and easy?to?understand algorithm， few parameters， and high stability. However， the performance of the DE algorithm largely depends on the setting of parameter values and the direction and distance of individual mutations. Considering that different population densities have different requirements for parameters， the principal component analysis （PCA） technique is used to reduce 30 or 50?dimensional data to 2 dimensions. Then， the DBSCAN algorithm is used to classify the 2 dimension data into clusters based on the neighborhood radius and minimum neighborhood number. The number of clusters is used to determine the overall density of the population and the difference between individuals， and appropriate mutation factors and crossover factors are generated within different ranges to meet the evolutionary needs of different populations. The proposed algorithm is verified by means of benchmark function test sets and multiple validation methods， demonstrating its superior optimization ability and robustness comparied with five other advanced algorithms.

Keywords： DBSCAN; differential evolution algorithm; principal component analysis; data dimensionality reduction; mutation factor; crossover factor

0" 引" 言

啟發(fā)式算法因其簡(jiǎn)單易懂、性能優(yōu)異和較強(qiáng)的魯棒性等特點(diǎn)而備受關(guān)注。已有多種啟發(fā)式算法被提出，如蟻群算法[1]、粒子群優(yōu)化算法[2]、灰狼算法[3]和黑猩猩算法[4]、差分進(jìn)化算法（DE）等，差分進(jìn)化算法是其中比較重要的一個(gè)啟發(fā)式算法，由R. Stron和K. Price在1995年提出[5]，主要是用來(lái)解決連續(xù)空間的全局優(yōu)化問(wèn)題，是一種隨機(jī)的并行全局搜索算法。與上述算法的不同之處是：DE算法采用“優(yōu)勝劣汰，適者生存”的思想，依靠種群內(nèi)部個(gè)體的競(jìng)爭(zhēng)逐步淘汰劣質(zhì)個(gè)體，從而提升種群整體的實(shí)力與優(yōu)質(zhì)性。DE算法自提出以來(lái)，被應(yīng)用到多個(gè)科學(xué)技術(shù)領(lǐng)域，解決了許多技術(shù)問(wèn)題，如路徑規(guī)劃、電力系統(tǒng)控制、網(wǎng)路檢測(cè)等。DE算法能被廣泛應(yīng)用的主要原因有三個(gè)：首先，DE算法的性能十分優(yōu)越，算法的魯棒性和適應(yīng)性比較強(qiáng)，在解決復(fù)雜多維問(wèn)題時(shí)也有優(yōu)異的表現(xiàn)；其次，DE算法整體思路較為簡(jiǎn)單易懂，算法過(guò)程主要為種群初始化、變異、交叉、選擇四個(gè)步驟，算法也只包含種群規(guī)模NP、變異因子F、交叉因子CR三個(gè)受控參數(shù)，但這三個(gè)參數(shù)在很大程度上影響著算法的進(jìn)化效率；最后，DE算法的時(shí)間復(fù)雜度低，對(duì)目標(biāo)函數(shù)的性質(zhì)無(wú)特殊要求，方便求解大規(guī)模優(yōu)化問(wèn)題[6?9]。

DE算法雖有很多優(yōu)勢(shì)，但依舊存在不足之處，如進(jìn)化停滯、局部最優(yōu)、對(duì)控制參數(shù)敏感等。因此，自DE算法提出以來(lái)，許多的研究者也對(duì)其進(jìn)行了不同方面的改進(jìn)，提出了許多新的DE算法變體，使其性能更加優(yōu)越。如，Qin A K等提出基于多變異策略選擇的自適應(yīng)差分進(jìn)化算法SaDE，在SaDE中選取四種常用的突變策略，通過(guò)幾代的實(shí)驗(yàn)得到每種策略的成功率；在之后的變異中，根據(jù)成功率選取最優(yōu)策略作為本次的變異策略[10]。A. W. Mohamed等提出一種新的三角形變異算子，在種群中隨機(jī)選出最好、中等和最差向量，用于產(chǎn)生變異向量[11]。Zhang J等使用聯(lián)系更新的方式更新參數(shù)，通過(guò)在歷史迭代成功的F和CR中提取信息來(lái)更新下一代的高斯分布以及柯西分布的均值[12]。R. Tanabe等基于JADE，根據(jù)歷史記錄提出新的參數(shù)存儲(chǔ)機(jī)制[13]，其在文獻(xiàn)[14]的SHADE算法基礎(chǔ)上，增加了種群線性遞減的方案，進(jìn)一步優(yōu)化了算法性能。Qing A Y等提出將種群分成若干個(gè)子種群，每個(gè)子種群?jiǎn)为?dú)進(jìn)化，利用跨種群競(jìng)爭(zhēng)來(lái)實(shí)現(xiàn)物種個(gè)體多樣性[15]。劉靖明等提出一種基于粒子群的K均值聚類算法[16]。高平等提出了一種基于改進(jìn)差分進(jìn)化的K均值聚類算法[17]。王鳳領(lǐng)等針對(duì)K均值算法的不足，優(yōu)先選擇初始聚類中心，提出了基于差分進(jìn)化的加權(quán)K?means算法[18]。

綜上所述，優(yōu)化算法的改進(jìn)方法層出不窮、各具優(yōu)勢(shì)，且研究者也考慮到了將DE算法與聚類算法相結(jié)合。常見(jiàn)的聚類算法中，K均值聚類算法的原理簡(jiǎn)單，復(fù)雜度低，因此經(jīng)常被用來(lái)與DE算法相結(jié)合，達(dá)到增強(qiáng)算法搜索能力的目的，也在一定程度上緩解了K均值聚類算法對(duì)初始點(diǎn)的敏感性。但K均值聚類算法很容易受到噪聲影響，易陷入局部最優(yōu)情況，而且分類數(shù)量是固定值，需要人為設(shè)置，難以展示種群個(gè)體內(nèi)部的差異度。因此，為了了解種群個(gè)體分布情況，本文采用DBSCAN聚類算法，且考慮到DBSCAN算法難以應(yīng)對(duì)高維問(wèn)題，采用主成分分析技術(shù)（PCA）將種群的維度降低到2維，方便后續(xù)分類成簇。通過(guò)DBSCAN算法將種群按照個(gè)體距離分成簇后，根據(jù)簇的數(shù)量反映出種群個(gè)體之間的差異度，變異因子和交叉因子也將選取不同的取值范圍，保證種群的進(jìn)化效率。

1" DE算法和DBSCAN算法

1.1" 基本DE算法

DE算法有種群初始化和進(jìn)化迭代兩個(gè)大階段，其中進(jìn)化迭代可分為三個(gè)步驟：變異、交叉和選擇，具體操作如下所述。

1.1.1" 種群初始化

初始種群中一共有NP個(gè)個(gè)體，每個(gè)個(gè)體代表一個(gè)解，且每個(gè)個(gè)體的解都是一個(gè)D維的向量。于是，可以將種群中個(gè)體的表達(dá)式寫(xiě)為：

[Xi，0=xi，1，0，xi，2，0，…，xi，D，0，i=1，2，…，NP] （1）

初始種群的生成公式如下：

[Xi，j，0=xj，low+rand（0，1）?（xj，high-xj，low）] （2）

式中：rand（0，1）服從均勻分布，隨機(jī)生成0～1之間的實(shí)數(shù)；[xj，high]和[xj，low]分別是[Xi，j]的取值上下限。

1.1.2" 變異操作

變異操作是差分進(jìn)化算法中至關(guān)重要的一步，也是與其他算法顯著不同之處，種群中的每個(gè)目標(biāo)向量[XGi]通過(guò)變異策略對(duì)應(yīng)生成一個(gè)變異向量[VGi]，差分進(jìn)化算法中最常用的5種變異策略公式如下所示：

[DE/best/1：VGi=XGbest+F?（XGr1-XGr2）] （3）

[DE/rand/1：VGi=XGr1+F?（XGr3-XGr2）] （4）

[DE/rand?Best/1：VGi=XGi+F?（XGbest-XGi）+" " " " " " " " " " " " " " " " " " " " " " "F?（XGr1-XGr2）] （5）

[DE/best/2：VGi=XGbest+F?（XGr1-XGr2）+F?（XGr3-XGr4）] （6）

[DE/rand/2：VGi=XGr1+F?（XGr2-XGr3）+F?（XGr4-XGr5）] （7）

式中：i表示種群中個(gè)體的索引；r1，r2，r3，r4，r5∈[1，NP]，在閉集合[1，NP]內(nèi)隨機(jī)產(chǎn)生的一個(gè)整數(shù)，且隨機(jī)生成的整數(shù)也需要滿足r1≠r2≠r3≠r4≠r5的條件；F是變異因子，控制差分向量的大小，影響目標(biāo)向量向變異向量移動(dòng)的步長(zhǎng)；[XGbest]代表著當(dāng)代種群中最優(yōu)的個(gè)體，引導(dǎo)種群進(jìn)化。完成變異操作后的變異向量有時(shí)會(huì)超出解空間，也就是[xj，high]和[xj，low]的范圍之外，因此，每次變異操作后會(huì)進(jìn)行邊界處理，公式如下：

[vG+1i，j=vG+1i，j，" " vG+1i，j∈[xj，low，xj，high]xj，low+rand（0，1）?（xj，high-xj，low），" otherwise] （8）

變異向量在搜索范圍內(nèi)時(shí)保持不變，超出范圍則重新生成一個(gè)新的變異向量。

1.1.3" 交叉操作

為了保證種群整體的多樣性，在變異后需要進(jìn)行交叉操作，而交叉操作常用的兩種方法是二項(xiàng)交叉和指數(shù)交叉。由于指數(shù)交叉會(huì)過(guò)多地保留變異個(gè)體的信息，所以二項(xiàng)交叉應(yīng)用更廣泛。通過(guò)二項(xiàng)交叉將變異向量[VGi]與目標(biāo)向量[XGi]進(jìn)行交叉，得到試驗(yàn)向量[UGi]，二項(xiàng)交叉的具體操作如下：

[uG+1i，j=vGi，j，" " "randi，j（0，1）≤CR或j=jrandxGi，j，" " "otherwise] （9）

式中：[uG+1i，j]表示第G+1代第i個(gè)試驗(yàn)向量的第j個(gè)分量；CR為交叉概率，CR越大，變異向量保留的分量越多，值的變化范圍在[0，1]之間；[jrand]是[1，D]范圍內(nèi)隨機(jī)選取的一個(gè)整數(shù)，其作用是保證至少有一維向量來(lái)自變異向量，確保整個(gè)進(jìn)化過(guò)程中個(gè)體信息是在不斷更迭。

1.1.4" 選擇操作

選擇操作的核心是“貪婪”策略，將目標(biāo)向量與試驗(yàn)向量做對(duì)比，之后選擇適應(yīng)度值更優(yōu)的個(gè)體，從而生成下一代的初始種群。所用的選擇公式如下所示：

[XG+1i=UGi，" " f（UGi）≤f（XGi）XGi，" " otherwise] （10）

上述操作完成后，就完成了種群一代的進(jìn)化；之后不斷重復(fù)直至尋到最優(yōu)解或達(dá)到最大迭代次數(shù)為止。DE算法流程如圖1所示。

1.2" DBSCAN算法

聚類算法是一類用于將數(shù)據(jù)集中的對(duì)象劃分為不同組別（或稱為簇）的算法，旨在發(fā)現(xiàn)數(shù)據(jù)中的內(nèi)在結(jié)構(gòu)，使得同一組內(nèi)的對(duì)象在某種意義上相似，而不同組之間的對(duì)象則有所不同。常見(jiàn)的聚類算法有五種，分別為K均值聚類算法、DBSCAN算法、層次聚類、密度峰值聚類和高斯混合模型。表1列舉了五種聚類算法的優(yōu)缺點(diǎn)，通過(guò)對(duì)表1的分析，本文選擇采用DBSCAN算法為種群分類。該算法可以基于數(shù)據(jù)點(diǎn)的密度來(lái)發(fā)現(xiàn)任意形狀的聚類，同時(shí)也能有效識(shí)別噪聲點(diǎn)，對(duì)噪聲魯棒性強(qiáng)，運(yùn)行速度也比較快。DBSCAN算法的核心就是將高密度區(qū)域內(nèi)部緊密相連的數(shù)據(jù)點(diǎn)歸為同一類別，這與本文想要將進(jìn)化過(guò)程中的個(gè)體進(jìn)行歸類，從而分析種群整體差異性的想法不謀而合。

DBSCAN算法的具體操作過(guò)程如下。

1） 選擇參數(shù)。首先需要選擇兩個(gè)參數(shù)，即ε（鄰域半徑）和MinPts（最小鄰居數(shù)）。ε決定了在距離ε內(nèi)的點(diǎn)被認(rèn)為是鄰居，MinPts是指在鄰域半徑內(nèi)所需要的最少點(diǎn)的數(shù)量。

2） 初始化。隨機(jī)選擇一個(gè)未被訪問(wèn)的數(shù)據(jù)點(diǎn)作為起始點(diǎn)。

3） 找鄰居。找出起始點(diǎn)ε鄰域內(nèi)的所有點(diǎn)，如果這個(gè)鄰域內(nèi)的點(diǎn)的數(shù)量大于等于MinPts，則該點(diǎn)被標(biāo)記為核心點(diǎn)。

4） 生成簇。對(duì)于核心點(diǎn)，通過(guò)它們的鄰居繼續(xù)找到可達(dá)的核心點(diǎn)，將它們加入同一個(gè)簇中。重復(fù)這個(gè)過(guò)程，直到所有的核心點(diǎn)都被訪問(wèn)過(guò)。

5） 標(biāo)記噪聲。將未被訪問(wèn)的點(diǎn)標(biāo)記為噪聲點(diǎn)，這些點(diǎn)不屬于任何簇。

通過(guò)以上步驟，DBSCAN算法能夠找出數(shù)據(jù)集中密度高的區(qū)域，并將它們劃分為不同的簇，同時(shí)也能夠識(shí)別出噪聲點(diǎn)。但參數(shù)ε和MinPts的選擇對(duì)算法的效果影響很大，合適的參數(shù)選擇是確保算法有效性的關(guān)鍵。

2" PCA?DBSDE

在DE算法與聚類分析結(jié)合的研究中，大多數(shù)的研究者都是采用K均值聚類方法對(duì)算法進(jìn)行優(yōu)化。比如，高平等人提出一種基于Laplace分布的變異算子和Logistic變尺度混沌搜索的改進(jìn)差分進(jìn)化的K均值聚類算法；喻金平等利用最大最小距離積方法初始化種群，構(gòu)造出適用K均值聚類適應(yīng)度函數(shù)以及全局引導(dǎo)的位置更新公式的人工蜂群算法；Sheng Weiguo等人提出了一種基于自適應(yīng)小生境和K均值聚類的差分進(jìn)化算法，用于分區(qū)數(shù)據(jù)聚類。但使用K均值聚類時(shí)，算法容易收斂于局部最小值，且對(duì)初始的中心點(diǎn)敏感，不同的初始化對(duì)結(jié)果的影響也很大。因此，本文提出一種DBSCAN聚類算法與DE算法相結(jié)合的改進(jìn)算法。

2.1" PCA降維

在DE算法中，種群的維度一般都設(shè)置為30和50，但因DBSCAN不能很好地應(yīng)對(duì)高維數(shù)據(jù)，于是本文采用主成分分析（PCA）技術(shù)將種群信息矩陣的維度降到2維，方便進(jìn)行聚類分析。PCA方法的目的是生成既可以減少種群矩陣維度又可以保留種群信息的新特征矩陣，具體操作步驟如下。

首先需要對(duì)原始數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化，即去除初始種群矩陣的數(shù)據(jù)均值，并通過(guò)協(xié)方差計(jì)算出標(biāo)準(zhǔn)化后數(shù)據(jù)矩陣的特征值和特征向量，具體公式如下：

[Cov=1NP-1popTnorm·popnorm] （11）

[Cov（Xpop）=λXpop] （12）

式中：[popnorm]是標(biāo)準(zhǔn)化后的種群信息矩陣；NP是種群個(gè)體數(shù)量；Cov是求得的協(xié)方差矩陣；[λ]為Cov的特征值；[Xpop]為特征向量。

然后保留特征值最大的前兩個(gè)特征向量[Xpop1]和[Xpop2]；最后將標(biāo)準(zhǔn)化后的矩陣與保留的特征向量相乘，得到最終的降維結(jié)果[PCApop]。

為了方便可視化和理解，圖2展示了一組2維矩陣通過(guò)PCA方法降維到1維的過(guò)程。

2.2" DBSCAN種群分類

通過(guò)PCA將初始種群降維到2維后，種群的信息復(fù)雜度降低，方便使用DBSCAN方法對(duì)種群進(jìn)行分類。但進(jìn)行分類前，需要確定DBSCAN的ε和MinPts。在本文中，通過(guò)計(jì)算每個(gè)個(gè)體之間的歐氏距離并求平均值來(lái)確定ε。

MinPts則通過(guò)設(shè)置不同值，并統(tǒng)計(jì)出在種群數(shù)量為10 000的迭代過(guò)程中不同MinPts對(duì)種群分類數(shù)量的影響，以此來(lái)確定具體MinPts，如表2所示。由表2的數(shù)據(jù)可知：當(dāng)MinPts設(shè)置為4、5、6時(shí)，種群通過(guò)DBSCAN方法得到簇的數(shù)量集中在1和2，這意味著較高的MinPts會(huì)導(dǎo)致種群分類效果不明顯；而當(dāng)MinPts取2時(shí)，得到簇的種類過(guò)多，不利于判斷種群密度。因此，本文選擇將MinPts設(shè)置為3，有利于了解種群個(gè)體之間的差異度，從而方便選擇，更加有利于種群進(jìn)化的交叉因子和變異因子的設(shè)置。在統(tǒng)計(jì)過(guò)程中也發(fā)現(xiàn)，種群進(jìn)化過(guò)程中，相鄰的幾次DBSCAN分類得到的簇?cái)?shù)量往往是相同的，為了減少運(yùn)行時(shí)間，選擇[D10]進(jìn)行一次分類操作。

確定了ε和MinPts后，就可以對(duì)降維后的種群進(jìn)行分類操作，具體操作流程如圖3所示。

2.3" 變異因子和交叉因子的設(shè)置

在種群迭代過(guò)程中，種群個(gè)體之間的差異度不斷變化，適應(yīng)能力也不盡相同。因此，在通過(guò)DBSCAN分類后，根據(jù)簇的數(shù)量來(lái)判斷種群整體的差異程度，并根據(jù)差異程度，采用不同的交叉因子和變異因子的取值。當(dāng)個(gè)體之間差異度過(guò)高，即生成簇的數(shù)量過(guò)多，說(shuō)明種群可能陷入局部最優(yōu)或者未找到最優(yōu)解，因此需要相對(duì)較大的F和相對(duì)較小的CR來(lái)保證種群的空間搜索能力，提高步長(zhǎng)，幫助部分個(gè)體跳出局部最優(yōu)的情況；與之相反的情況則是DBSCAN生成的簇相對(duì)較少，種群內(nèi)個(gè)體較為集中，為了保持種群整體的進(jìn)化能力，保存更多的種群信息，F(xiàn)的取值相對(duì)較小，而CR的值相對(duì)較大。通過(guò)分析表2的數(shù)據(jù)，選擇簇?cái)?shù)量為3作為評(píng)判標(biāo)準(zhǔn)的分界點(diǎn)。具體取值公式如下：

[F=0.4×rand（NP，1）+" " " " "0.1×tan（π×（rand（NP，1）-0.5）），" numclt;30.5+0.4×（rand（NP，1））+" " " " "0.1×tan（π×（rand（NP，1）-0.5）），" otherwise] （13）

[CR=（0.5+0.5×rand（NP，1））×" " "sin（0.5×π×G）×（GG_max），" "numclt;30.1+0.4×（rand（NP，1））×sin（0.5×π×G）×（GG_max），" " " " otherwise] （14）

式中numc表示簇的數(shù)量，通過(guò)對(duì)F和CR取值的限定，從而更好地滿足種群迭代的要求。

本文提出的改進(jìn)方法具體流程如圖4所示。

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

PCA?DBSDE算法是由軟件Matlab編寫(xiě)完成，所用計(jì)算機(jī)的硬件配置為：ADM Ryzen 7 5800H with Radeon Graphics，頻率為3.2 GHz的CPU和16 GB的RAM。在上述實(shí)驗(yàn)環(huán)境中，通過(guò)對(duì)CEC2014測(cè)試集中的30個(gè)基準(zhǔn)函數(shù)進(jìn)行測(cè)試分析，得出結(jié)論。30個(gè)基準(zhǔn)函數(shù)的分類如表3所示。

3.1" 與其他DE改進(jìn)算法比較結(jié)果

將本文提出的PCA?DBSDE算法與其他5個(gè)先進(jìn)DE變體（JADE、SinDE、TSDE、AGDE、EFADE）進(jìn)行比較。所有算法的參數(shù)設(shè)置若無(wú)特殊說(shuō)明，則與原算法一致，NP表示種群的數(shù)量，一般為5D，D表示種群中個(gè)體的維度，在本文比較中，D取30和50；最大迭代次數(shù)G_max為10 000D，當(dāng)算法迭代次數(shù)達(dá)到G_max，則停止運(yùn)算。其他參數(shù)設(shè)置見(jiàn)表4。

將每個(gè)算法獨(dú)立運(yùn)行50次，記錄30個(gè)基準(zhǔn)函數(shù)50次結(jié)果的平均誤差（mean）和標(biāo)準(zhǔn)差（std）。各個(gè)算法在基準(zhǔn)函數(shù)的表現(xiàn)結(jié)果分別如表5和表6所示。

單峰函數(shù)：CEC2014中的F1～F3，函數(shù)特征是連續(xù)平滑不可分。種群個(gè)體維度不論是30還是50，PCA?DBSDE的表現(xiàn)都是最優(yōu)，測(cè)試結(jié)果的均值和標(biāo)準(zhǔn)差都明顯優(yōu)于其他算法，魯棒性和穩(wěn)定性都處于領(lǐng)先地位。

簡(jiǎn)單多模態(tài)函數(shù)：CEC2014中的F4～F16，該函數(shù)特征也是連續(xù)不可分離的，但存在許多局部最優(yōu)解。在D=30的測(cè)試中，從均值來(lái)看，PCA?DBSDE在8個(gè)函數(shù)上表現(xiàn)最優(yōu)，且測(cè)試F4、F7和F8時(shí)，都找到了最優(yōu)解。從標(biāo)準(zhǔn)差來(lái)看，PCA?DBSDE也有5個(gè)測(cè)試函數(shù)的標(biāo)準(zhǔn)差優(yōu)于其他算法。在D=50的測(cè)試結(jié)果中，PCA?DBSDE的表現(xiàn)略遜于D=30，有5個(gè)測(cè)試函數(shù)的均值和6個(gè)測(cè)試函數(shù)的標(biāo)準(zhǔn)差優(yōu)于其他5個(gè)算法。從測(cè)試結(jié)果的優(yōu)劣可以看出，PCA?DBSDE對(duì)局部最優(yōu)問(wèn)題有良好的解決方法。

混合函數(shù)：CEC2014中的F17～F22，函數(shù)特征較為復(fù)雜，并且不同的變量有不同的屬性。在D=30的測(cè)試中，PCA?DBSDE僅在F19的測(cè)試結(jié)果中劣于TSDE。但種群維度為50時(shí)，PCA?DBSDE測(cè)試結(jié)果與JADE平分秋色，皆有測(cè)試表現(xiàn)較好的函數(shù)。

組合函數(shù)：CEC2014中的F23～F30，這些函數(shù)不僅有多個(gè)局部最優(yōu)點(diǎn)，也包含不對(duì)稱的不同屬性的變量。在D=30的測(cè)試結(jié)果中，PCA?DBSDE表現(xiàn)優(yōu)越，有5個(gè)最優(yōu)的均值結(jié)果和標(biāo)準(zhǔn)差，遠(yuǎn)遠(yuǎn)優(yōu)于其他算法；位居其后的則是SinDE，但也僅有3個(gè)最優(yōu)均值；在D=50時(shí)，PCA?DBSDE也是表現(xiàn)最好，有6個(gè)測(cè)試結(jié)果優(yōu)于其他算法。通過(guò)對(duì)組合函數(shù)的測(cè)試結(jié)果可以看出，PCA?DBSDE在處理多種函數(shù)組合的問(wèn)題中有十分優(yōu)越的性能。

綜上所述，在D=30測(cè)試中，PCA?DBSDE表現(xiàn)十分優(yōu)越，在各類型的函數(shù)測(cè)試中都明顯優(yōu)于其他算法。但當(dāng)種群維度提高到50時(shí)，測(cè)試結(jié)果要稍稍遜于維度為30的表現(xiàn)，因?yàn)殡S著維度提高，PCA降維導(dǎo)致的信息丟失也會(huì)增多，導(dǎo)致種群內(nèi)部個(gè)體的分類出現(xiàn)錯(cuò)誤，從而影響測(cè)試結(jié)果。從整體的測(cè)試結(jié)果分析可知，PCA?DBSDE應(yīng)對(duì)各類函數(shù)時(shí)，表現(xiàn)結(jié)果都非常優(yōu)異，證明了PCA?DBSDE方法具有很強(qiáng)的可行性和競(jìng)爭(zhēng)性，能夠有效應(yīng)對(duì)種群進(jìn)化過(guò)程中陷入局部最優(yōu)的情況，加快種群進(jìn)化進(jìn)程，幫助找到最優(yōu)解。圖5所示為PCA?DBSDE與其他算法在某些函數(shù)上的最優(yōu)值的迭代曲線。

3.2" 檢驗(yàn)結(jié)果分析

除了觀察測(cè)試函數(shù)的結(jié)果外，也通過(guò)多個(gè)檢驗(yàn)方法驗(yàn)證了PCA?DBSDE的優(yōu)越性，其檢驗(yàn)結(jié)果如表7～表10所示。

表7采用了符號(hào)秩檢驗(yàn)和秩和檢驗(yàn)兩種方法，在顯著性水平ɑ為0.05時(shí)，將PCA?DBSDE與其他先進(jìn)算法進(jìn)行比較，“+”含義為在該函數(shù)測(cè)試結(jié)果上，PCA?DBSDE有95%的概率優(yōu)于比較算法，“=”表示PCA?DBSDE算法與比較算法相當(dāng)，“-”則表示劣于比較算法。從表7可以清楚地看出，PCA?DBSDE無(wú)論是符號(hào)秩檢驗(yàn)還是秩和檢驗(yàn)，都有一半以上的檢驗(yàn)結(jié)果是優(yōu)于其他算法的，至多也只有7個(gè)函數(shù)測(cè)試結(jié)果比SinDE差。

表8和表9則采用的是威爾克遜檢驗(yàn)方法，R+和R-表示正負(fù)秩和。從表中可知，R+的值都比R-大，說(shuō)明PCA?DBSDE算法的性能整體優(yōu)于其他算法。從測(cè)試結(jié)果可以看出，不論種群維度為30還是50，漸近值P都小于置信區(qū)間ɑ，說(shuō)明PCA?DBSDE測(cè)試結(jié)果優(yōu)于其他算法的假設(shè)是成立的。

表10所示為采用弗雷德曼檢驗(yàn)法得到的結(jié)果。從中可以很清楚地看出，無(wú)論D是30還是50，PCA?DBSDE的秩和值都為最小，驗(yàn)證了PCA?DBSDE算法的優(yōu)越性。

4" 結(jié)" 語(yǔ)

本文基于DE算法的基礎(chǔ)理論，提出通過(guò)PCA降維種群，并采用DBSCAN算法對(duì)種群進(jìn)行分類的PCA?DBSDE算法。該算法將種群的維度從30或50維降低到2維；再通過(guò)確定最小鄰域數(shù)和鄰域半徑將每代的初始種群分類成簇，通過(guò)判斷簇的數(shù)量分析目前種群內(nèi)個(gè)體的密度，從而采取不同的變異因子和交叉因子來(lái)適應(yīng)種群的進(jìn)化，幫助種群跳出局部最優(yōu)，保持種群進(jìn)化速度，防止進(jìn)化停滯現(xiàn)象發(fā)生。采用CEC2014測(cè)試集將PCA?DBSDE算法與其他先進(jìn)算法進(jìn)行了比較，也用弗雷德曼和威爾克遜方法進(jìn)行了檢驗(yàn)。實(shí)驗(yàn)結(jié)果表明，PCA?DBSDE算法在30維和50維的測(cè)試中占據(jù)領(lǐng)先地位，表現(xiàn)出了極強(qiáng)的競(jìng)爭(zhēng)力和魯棒性。

在后續(xù)的工作中，將繼續(xù)研究PCA?DBSDE算法的可行性，降低高維度問(wèn)題的信息丟失問(wèn)題，并推廣到其他算法中，進(jìn)一步研究該算法的理論依據(jù)。

參考文獻(xiàn)

[1] DORIGO M， MANIEZZO V， COLORNI A. Ant system： optimization by a colony of cooperating agents [J]. IEEE transactions on systems， man， and cybernetics， 1996， 26（1）： 29?41.

[2] KENNEDY J， EBERHART R C. Particle swarm optimization [C]// IEEE International Conference on Neural Networks. [S.l.]： Wiley， 1995： 1942?1948.

[3] LONG Wen， WU Tiebin， TANG Mingzhu， et al. A Grey wolf optimization algorithm based on lens imaging learning strategy [J]. Acta automatica sinica， 2020， 46（10）： 2148?2164.

[4] KHISHE M， MOSAVI M R. Chimp optimization algorithm [J]. Expert systems with applications， 2020， 149： 113338.

[5] STORN R， PRICE K. Differential evolution?a simple and effici?ent heuristic for global optimization overcontinuous spaces" [J]. Journal of global optimization， 1997， 11（4）： 341?359.

[6] ZHU T， HAO Y J， LUO W T， et al. Learning enhanced differential evolution for tracking optimal decisions in dynamic power systems [J]. Applied soft computing， 2018， 67： 812?821.

[7] ZHAO W J， LIU E X， WANG B， et al. Differential evolutionary optimization of an equivalent dipole model for electromagnetic emission analysis [J]. IEEE transactions on electromagnetic compatibility， 2018， 60（6）： 1635?1639.

[8] LIANG J， WANG P， GUO L， et al. Multi?objective flow shop scheduling with limited buffers using hybrid self?adaptive differential evolution [J]. Memetic computing， 2019， 11： 407?422.

[9] WU X， LIU X， ZHAO N. An improved differential evolution algorithm for solving a distributed assembly flexible job shop scheduling problem [J]. Memetic computing， 2019， 11（4）： 335?355.

[10] QIN A K， HUANG V L， SUGANTHAN P N. Differential evolution algorithm with strategy adaptation for global numerical optimization [J]. IEEE transactions on evolutionary computation， 2009， 13（2）： 398?417.

[11] MOHAMED A W， SUGANTHAN P N. Real?parameter unconstrained optimization based on enhanced fitness?adaptive differential evolution algorithm with novel mutation [J]. Soft computing， 2018， 22（10）： 3215?3235.

[12] ZHANG J， SANDERSON A C. JADE： adaptive differential evolution with optional external archive [J]. IEEE transactions on evolutionary computation， 2009， 13（5）： 945?958.

[13] TANABE R， FUKUNAGA A. Success?history based parameter adaptation for differential evolution [C]// 2013 IEEE Congress on Evolutionary Computation. Cancun， Mexico： IEEE， 2013： 71?78.

[14] TANABE R， FUKUNAGA A S. Improving the search performance of SHADE using linear population size reduction [C]// 2014 IEEE Congress on Evolutionary Computation （CEC）. [S.l.]： IEEE， 2014： 1658?1665.

[15] QING A Y. Electromagnetic inverse scattering of multiple perfectly conducting cylinders by differential evolution strategy with individuals in groups （GDES） [J]. IEEE transcation on antennas and propagation， 2004， 52（5）： 1223?1229.

[16] 劉靖明，韓麗川，侯立文.一種新的聚類算法：粒子群聚類算法[J].計(jì)算機(jī)工程與應(yīng)用，2005，41（20）：183?185.

[17] 高平，毛力，宋益春.基于改進(jìn)差分進(jìn)化的K?均值聚類算法[J].電腦知識(shí)與技術(shù)，2013，9（22）：5064?5067.

[18] 王鳳領(lǐng).基于差分進(jìn)化的加權(quán)k?means算法研究[J].智能計(jì)算機(jī)與應(yīng)用，2020，10（6）：238?242.