許瀚譽(yù)，馮 翔，虞慧群

華東理工大學(xué) 信息科學(xué)與工程學(xué)院，上海200237

1 引言

如今，隨著云計算、物聯(lián)網(wǎng)和人工智能等技術(shù)的興起，數(shù)據(jù)正以爆炸式的速度不斷地增長和累積，標(biāo)志著大數(shù)據(jù)的時代已經(jīng)到來[1]。在大數(shù)據(jù)時代，模式分類有著廣泛的應(yīng)用前景。現(xiàn)實(shí)生活中的很多問題都可以轉(zhuǎn)化成模式分類問題。面對數(shù)據(jù)量的增大、數(shù)據(jù)維度的變大以及數(shù)據(jù)結(jié)構(gòu)的復(fù)雜化，傳統(tǒng)的模式分類模型面臨越來越多的挑戰(zhàn)。近些年，用啟發(fā)式算法優(yōu)化現(xiàn)有的模式分類算法，在實(shí)際應(yīng)用中取得很好的效果。例如，與一些分類準(zhǔn)則結(jié)合構(gòu)造分類器，或者訓(xùn)練多層感知器用于地震預(yù)測等[2]。自然啟發(fā)式算法是根據(jù)確定性規(guī)則或者隨機(jī)性來模擬自然界中生物和物質(zhì)的行為。比如，模擬鳥群和魚群社會行為的粒子群算法（PSO）[3]；模擬蜜蜂合作行為的人工蜂群算法（ABC）[4]；模擬細(xì)菌覓食行為的細(xì)菌覓食算法（BFOA）[5]；模擬螢火蟲閃爍行為的螢火蟲優(yōu)化算法[6]；模擬布谷鳥生活方式的布谷鳥優(yōu)化算法（COA）[7-8]；模擬螞蟻群體覓食散發(fā)信息素行為的蟻群優(yōu)化算法[9]以及模擬天體間引力的萬有引力算法[10]等。但是，現(xiàn)有的自然啟發(fā)算法具有群體構(gòu)建和群體優(yōu)化操作單一的缺點(diǎn)，所以收斂速度較慢，魯棒性和穩(wěn)定性不高，對傳統(tǒng)的模式分類模型的優(yōu)化能力也有限，不能滿足問題和應(yīng)用需求。例如PSO[11-12]，它不能有效地探索整個解空間，所以往往會陷入局部最優(yōu)或失去多模態(tài)問題最優(yōu)解的多樣性。為了解決這個問題，一些算法使用控制參數(shù)來影響算法的搜索能力。它們的策略是將算法逐步從全局搜索轉(zhuǎn)變?yōu)榫植克阉?。一般來說，這是正確的，但是有時很難解決某些問題，例如具有許多最優(yōu)值的多模態(tài)函數(shù)，因?yàn)樗鼈冞^早地進(jìn)行了局部探測。也有其他方法使用調(diào)整種群大小來控制探索和探測之間的平衡，雖然這種方式可以簡單地保持多樣性，但它通常會得到一個不滿意的最優(yōu)解。因此，提出新的自然啟發(fā)式算法是十分有意義的。

物質(zhì)是由群體組成，群體狀態(tài)自適應(yīng)也是一種自然啟發(fā)和優(yōu)化的過程[13]。從宏觀角度，物質(zhì)在特定環(huán)境的作用下，總是從一個不穩(wěn)定的狀態(tài)轉(zhuǎn)換到一個相對穩(wěn)定的狀態(tài)。從微觀角度，物質(zhì)是由粒子組成的，粒子受到特定環(huán)境的作用，總是趨向于彼此間距離更小，引力更大。這種群體狀態(tài)自適應(yīng)的現(xiàn)象，既符合優(yōu)化問題的一般規(guī)律，也可以應(yīng)用在對數(shù)據(jù)的處理問題中。

在物理世界中，引發(fā)群體狀態(tài)變化的環(huán)境因素主要有兩種，溫度和引力。本文以萬有引力為環(huán)境條件模擬群體狀態(tài)自適應(yīng)的優(yōu)化過程，用于分群和群體優(yōu)化過程中全局搜索和局部探測的控制，并受化學(xué)反應(yīng)算法（CRO）[14]的啟發(fā)，提出四個種群操作子模型豐富群體內(nèi)部連接。除了上述貢獻(xiàn)外，本文理論分析了算法的收斂性，并在函數(shù)極值實(shí)驗(yàn)中驗(yàn)證了提出的模型的有效性，證明了模型具有收斂速度快和魯棒性高的特點(diǎn)；將提出的模型結(jié)合歐式距離準(zhǔn)則，提出新的最小距離分類模型，在UCI 數(shù)據(jù)集實(shí)驗(yàn)中與其他經(jīng)典的模型相比較，體現(xiàn)了提出的模型在大數(shù)據(jù)應(yīng)用中的潛力。

2 問題模型

本文將處理兩個問題，連續(xù)優(yōu)化問題和模式分類問題。由于最小化問題和最大化問題可以很容易地相互轉(zhuǎn)換，在本文定義一個全局優(yōu)化問題如下：

其中，f(X)為全局優(yōu)化問題的適應(yīng)度函數(shù)，對于最小化問題，如果f(X)越小，那么對應(yīng)的優(yōu)化效果就越好。對于一個具有n 個變量的優(yōu)化問題，本文用一個n 維矢量來表示問題的解，S 為此優(yōu)化問題的可行域。那么，全局優(yōu)化問題的關(guān)鍵就是尋找一個解X*，使得：

在模式分類問題中，本文是構(gòu)造基于距離的分類器。所以，如果一個數(shù)據(jù)集具有C 類樣本，每個樣本具有n個類屬性，可以將C 個類中心表示為下面公式所示的n×C 維矩陣。其中，列向量表示為該類對應(yīng)的類中心。這樣，分類模型求解過程可以被視作在n維空間中尋找C 個最優(yōu)類中心的優(yōu)化問題。

在求解最優(yōu)類中心的過程中，本文將從文獻(xiàn)[15]給出的三個適應(yīng)度函數(shù)中選取一個作為本模型的適應(yīng)度函數(shù)，用于評價當(dāng)前的分類模型。

其中，DTrain表示訓(xùn)練樣本的個數(shù)；CL(Xj)表示為根據(jù)當(dāng)前的分類模型，樣本j應(yīng)當(dāng)被劃分的類別；CLknown(Xj)表示為數(shù)據(jù)集中樣本j 的目標(biāo)類別；表示為第k 類的類中心；d 則為兩點(diǎn)之間的歐式距離。

3 算法模型與算法設(shè)計

3.1 算法物理模型

物質(zhì)一般存在三種基本狀態(tài)：氣態(tài)、液態(tài)和固態(tài)。物質(zhì)是粒子以群體形式的體現(xiàn)且群體狀態(tài)會根據(jù)環(huán)境發(fā)生變化。在恒溫的環(huán)境下，力就是引起群體狀態(tài)自適應(yīng)的唯一因素。在諸多力的計算公式中，最能表現(xiàn)群體狀態(tài)自適應(yīng)的是萬有引力[10]。本文將問題的解空間看作群體狀態(tài)自適應(yīng)的環(huán)境空間，問題的最優(yōu)解就是環(huán)境空間里的最優(yōu)粒子，最優(yōu)粒子將提供群體狀態(tài)自適應(yīng)的所需的因素，也就是粒子運(yùn)動的引力，且在環(huán)境空間中最穩(wěn)定的物質(zhì)狀態(tài)是固態(tài)。因此，問題求解的過程，初始的群體粒子，受到最優(yōu)粒子的引力作用，與其距離越來越近，作用力也越來越大，物質(zhì)的狀態(tài)從氣態(tài)逐步變化到最穩(wěn)定的固態(tài)。

群體狀態(tài)自適應(yīng)模型的物理模型如圖1。每一個小的粒子都是解空間的一個解。藍(lán)色表示氣體粒子，紅色表示液體粒子，綠色表示固體粒子。其中帶有數(shù)字的白色圓圈分別代表四種粒子運(yùn)動方式。

圖1 群體狀態(tài)自適應(yīng)模型圖

3.2 引力策略

在演化算法中，群體的構(gòu)建和優(yōu)化過程中全局探測和局部探索的平衡控制是十分重要的部分。在提出的算法中，使用萬有引力模型進(jìn)行群體的分群和判斷群體中個體的狀態(tài)，從而實(shí)現(xiàn)群體內(nèi)部信息的充分利用和優(yōu)化過程中探索和探測的平衡。首先算法在氣體狀態(tài)下主要是采取單粒子自撞運(yùn)動，進(jìn)行全局尋優(yōu)操作，尋找優(yōu)化最快的方向；然后算法在液體狀態(tài)下主要是采取雙粒子融合運(yùn)動、單粒子分裂運(yùn)動和雙粒子交叉運(yùn)動，全局尋優(yōu)和局部尋優(yōu)保持一個平衡狀態(tài)，保證收斂速度的同時也保證優(yōu)化的多樣性；最后算法在固體狀態(tài)下主要是采取單粒子自撞運(yùn)動和雙粒子交叉運(yùn)動，進(jìn)行局部尋優(yōu)操作，精化問題的最優(yōu)解，但是同時也保持跳出局部最優(yōu)值的能力。在G-CSAO 中引入萬有引力模型，計算公式為：

其中，G0=6.67×10-11是引力常數(shù)；m0是最優(yōu)粒子的質(zhì)量，為了計算方便設(shè)置為；M 是群體中粒子的質(zhì)量，大小與粒子的適應(yīng)度函數(shù)f(X)有關(guān)，在提出的算法中M=e-f(X)；r 是群體中粒子與最優(yōu)粒子的距離，大小也是與適應(yīng)度函數(shù)f(X)有關(guān)。最終，將各個因子代入公式（1），在提出的G-CSAO 中萬有引力模型的公式為：

大部分演化過程和優(yōu)化算法都是通過將現(xiàn)有解添加擾動來尋找新的解的方法進(jìn)行鄰域搜索操作。假設(shè)要處理的問題的維度間是相互獨(dú)立的，不存在彼此間的約束條件。鄰域搜索操作中的擾動有很多可以選擇的概率分布函數(shù)，提出的算法將采用最常用的Gaussian 概率分布。它的概率密度函數(shù)為：

這里μ是平均值，σ2是方差。擾動操作包含三個組成部分，初始點(diǎn)、方向和步長。在G-CSAO 中初始點(diǎn)就是粒子結(jié)構(gòu)。因?yàn)椴⒉恢绬栴}的全局最優(yōu)解，所以并不知道方向，Gaussian 概率分布是均勻的，將μ=0 可以使得擾動的方向是等概率的。此外，σ 影響μ傳播的寬度，σ 越大，擾動越大，因此σ 是模型中步長（不同物質(zhì)狀態(tài)時不同，一般液態(tài)為氣態(tài)的十分之一，固態(tài)為氣態(tài)的百分之一）。那么，新的粒子結(jié)構(gòu)X′中的第i維可以表示為：

3.3 單粒子自撞運(yùn)動

如圖1中圓圈1所示，在G-CSAO 中，粒子會吸引在同狀態(tài)下的微小粒子，結(jié)合自身的運(yùn)動發(fā)生自撞運(yùn)動，使得自身的質(zhì)量變大，形成新的粒子。具體是在粒子群體Pop 中選擇一個粒子通過萬有引力模型計算粒子與最優(yōu)粒子之間的引力大小F，如果F 滿足下面約束條件中的一條，就對X 進(jìn)行單粒子自撞運(yùn)動算法。

其中，F(xiàn)θ1是氣態(tài)和液態(tài)的閾值，F(xiàn)θ2是液態(tài)和固態(tài)的閾值，λ是一個隨機(jī)數(shù)，λ ∈(0,1)。單粒子自撞運(yùn)動算法的公式如下：

xi是粒子結(jié)構(gòu)X=(x1,x2,...,xi,...,xn)中的一維，i ∈[ 1,n]。如果新得到的粒子解比原粒子的解好，那么就保留新的粒子結(jié)構(gòu)，否則：

之后再對粒子結(jié)構(gòu)中的其他維進(jìn)行相同的操作得到最終的新粒子結(jié)構(gòu)，放入到群體Pop中，保持群體大小不變。

算法1單粒子自撞運(yùn)動

Input：one X in Pop

while i ≤n do

x′i=xi+η(0,σ2)

If f(X′)≤f(X)

x′i=xi-η(0,σ2)

end if

end while

Output：new X′in Pop

3.4 雙粒子融合運(yùn)動

如圖1 中圓圈2 所示。在群體狀態(tài)自適應(yīng)過程中，前一個狀態(tài)中的兩個粒子通過相互吸引和相互碰撞，距離越來越靠近，最后融合成為一個新的粒子。雙粒子融合運(yùn)動算法首先在粒子群體Pop 中選擇一個粒子進(jìn)行萬有引力模型計算引力大小F，如果F 滿足下面約束條件：

算法2雙粒子融合運(yùn)動

3.5 單粒子分裂運(yùn)動

如圖1中圓圈3所示。當(dāng)物質(zhì)在固定環(huán)境中達(dá)到穩(wěn)定狀態(tài)的過程中，群體中質(zhì)量較小的粒子受到群體中質(zhì)量較大的粒子的引力作用，可能會發(fā)生粒子分裂現(xiàn)象，分裂的兩部分會慢慢向質(zhì)量大的粒子靠近，最后成為兩個新的粒子。新的粒子與最優(yōu)粒子的引力更大，更加靠近最優(yōu)粒子。單粒子分裂運(yùn)動算法首先在粒子群體Pop 中隨機(jī)選擇一個粒子X 且不是群體中適應(yīng)度值最小的粒子Xopt，進(jìn)行萬有引力模型計算引力大小F，如果F 滿足下面約束條件：

對X 進(jìn)行單粒子分裂運(yùn)動算法。具體操作如下：

如果f(X1)＜f(X)，那么對X1中粒子結(jié)構(gòu)是X 的部分進(jìn)行單粒子自撞運(yùn)動：

得到的新的粒子X1；如果f(X1)＜f(X)，那么對X2中粒子結(jié)構(gòu)是X 的部分進(jìn)行單粒子自撞運(yùn)動：

將最終得到的兩個粒子X1和X2放入群體中，群體的大小加1。

算法3單粒子分裂運(yùn)動

3.6 雙粒子交叉運(yùn)動

如圖1中圓圈4所示。在物質(zhì)狀態(tài)漸漸接近穩(wěn)定狀態(tài)的時候，處于同一狀態(tài)下的兩個粒子受到相互之間的引力作用，會發(fā)生相互碰撞，兩個粒子的內(nèi)部結(jié)構(gòu)會發(fā)生交叉，得到兩個新的粒子。雙粒子交叉運(yùn)動算法首先在粒子群體Pop 中選擇兩個粒子X1和X2，通過萬有引力模型分別計算與最優(yōu)粒子間的引力大小F1和F2，如果滿足下面兩個約束條件中的一個：

那么就對X1和X2進(jìn)行雙粒子交叉運(yùn)動算法，具體操作如下：

算法4雙粒子交叉運(yùn)動

提出的算法的流程圖如圖2所示。

4 理論分析

根據(jù)Lyapunov 的第二穩(wěn)定性理論，將G-CSAO 的四種粒子運(yùn)動考慮成一個系統(tǒng)方程x′=f(x,t)，且穩(wěn)定狀態(tài)為x0=0。定義如下：如果一個正定函數(shù)V(x,t)是連續(xù)的一階偏導(dǎo)，滿足下面的條件：

圖2 G-CSAO算法流程圖

（1）若V′(x,t)是負(fù)定的，那么這個系統(tǒng)在x0=0的狀態(tài)是一直逐漸穩(wěn)定的。

（2）推 廣 可 得，隨 著||x||→∞，那 么 就 有V(x,t)→∞，那么這個系統(tǒng)在x0=0 的狀態(tài)是大致逐漸穩(wěn)定的。

對于G-CSAO的數(shù)學(xué)模型，可以定義為一個Lyapunov的系統(tǒng)L(R(t))。

5 實(shí)驗(yàn)?zāi)M與分析

本文根據(jù)問題模型，將實(shí)驗(yàn)?zāi)M分為兩個部分：全局優(yōu)化問題的函數(shù)極值實(shí)驗(yàn)和模式分類問題的UCI 數(shù)據(jù)集實(shí)驗(yàn)。在函數(shù)極值實(shí)驗(yàn)中，主要驗(yàn)證G-CSAO 模型收斂速度和魯棒性等，以及在數(shù)據(jù)高維度下的優(yōu)化能力；在模式分類實(shí)驗(yàn)中，將基于G-CSAO 的最小距離分類器同經(jīng)典的機(jī)器學(xué)習(xí)算法相比較，測試G-CSAO模型在大數(shù)據(jù)問題中的潛能。本文實(shí)驗(yàn)環(huán)境為：Intel Core Quad 2.7 GHz CPU；8 GB RAM；G-CSAO 模型在Windows 10環(huán)境下用C++編碼。

5.1 函數(shù)極值實(shí)驗(yàn)

為了測試G-CSAO 模型的全局優(yōu)化能力，本文選取常用的10 個具有代表性的基準(zhǔn)函數(shù)[16]進(jìn)行驗(yàn)證，基準(zhǔn)函數(shù)如表1。根據(jù)基準(zhǔn)函數(shù)的峰值特征不同，10 個函數(shù)可以分為兩類：一類是單模函數(shù)f1～f5，一類是多模函數(shù)f6～f10。

在G-CSAO 模型中有5 個可調(diào)參數(shù)，分別是Pop、epoch、σ、Fθ1和Fθ2。為了保證實(shí)驗(yàn)的公平性，在10 個函數(shù)極值測試中，G-CSAO 的參數(shù)也保持不變，設(shè)置為（20，10 000，10，1，5.5）。

表1 基準(zhǔn)優(yōu)化測試函數(shù)

為了能相對地了解G-CSAO 模型的優(yōu)化能力，將G-CSAO 同5 個經(jīng)典的自然啟發(fā)算法作比較，分別是RCCRO[16]、DE[17]、PSO[3]、ABC[4]以及CMAES[18]。在實(shí)驗(yàn)中，同樣對各個算法做參數(shù)分析，遵循與文獻(xiàn)[13]一樣的標(biāo)準(zhǔn)。對每一個測試函數(shù)，算法將運(yùn)行30 次得到平均值做對比，最優(yōu)結(jié)果用粗體標(biāo)出。

從表2 的對比結(jié)果和圖3 迭代曲線分析可以得出，G-CSAO 在單模和多模都有不錯的效果，在單模實(shí)驗(yàn)中，除了在f1、f2、f3的表現(xiàn)略遜于CMAES；在多模實(shí)驗(yàn)中，在f7的結(jié)果也是僅次于CMAES。從綜合排名可以看出，G-CSAO 的排名為第一，說明G-CSAO 模型在全局優(yōu)化問題的綜合表現(xiàn)是非常好的，具有收斂精度高，穩(wěn)定性好的特點(diǎn)。

為了更加直觀地了解G-CSAO 模型的特點(diǎn)，觀察G-CSAO 在宏觀下群體狀態(tài)自適應(yīng)情況和微觀下粒子運(yùn)動情況。根據(jù)G-CSAO 模型的屬性，刻畫出G-CSAO求解f1的實(shí)驗(yàn)過程。在同一時刻下，其中x軸為群體中所有粒子的合力的倒數(shù)，y 軸為群體中所有粒子的質(zhì)量均值倒數(shù)，z 軸為群體中所有粒子與最優(yōu)粒子的平均距離，原點(diǎn)的坐標(biāo)為（0，0，0.5），如圖4所示。

表2 函數(shù)極值實(shí)驗(yàn)尋優(yōu)結(jié)果

圖3 六種算法的迭代尋優(yōu)曲線圖

圖4 G-CSAO算法在宏觀和微觀視角中群體運(yùn)動過程

5.2 UCI數(shù)據(jù)集實(shí)驗(yàn)

在模式分類實(shí)驗(yàn)中，將基于G-CSAO 模型和最小距離分類模型來構(gòu)造一個分類器。并使用12 個UCI 數(shù)據(jù)集來測試該分類器的性能。在本實(shí)驗(yàn)中，G-CSAO 的參數(shù)設(shè)置與極值測試一致。首先，將使用問題模型中提到的三個適應(yīng)度函數(shù)來分別測試G-CSAO 在各數(shù)據(jù)集上的性能。之后，將選出在某個適應(yīng)度函數(shù)下分類效果最好的一組實(shí)驗(yàn)結(jié)果，將其與經(jīng)典分類算法進(jìn)行比較。對比算法的實(shí)驗(yàn)數(shù)據(jù)來自文獻(xiàn)[15]。為了保證可比性，本文中，使用5 折交叉驗(yàn)證，采用隨機(jī)抽樣的方式將各數(shù)據(jù)集分為5等份，每次抽取其中4份作為訓(xùn)練集，剩下的1 份作為測試集。取5 次實(shí)驗(yàn)結(jié)果的平均值，作為最終實(shí)驗(yàn)結(jié)果。為了有效使用歐式距離來區(qū)分各樣本的差異度，對各維度已經(jīng)轉(zhuǎn)化實(shí)數(shù)的數(shù)據(jù)集進(jìn)行歸一化處理。歸一化方法如下所示：

其中，xij表示數(shù)據(jù)集中第i 個樣本的第j 個屬性。歸一化后，各數(shù)據(jù)集各樣本的屬性值都在[0，1]之間。在實(shí)驗(yàn)中，使用錯分率作為最終分類效果的評價標(biāo)準(zhǔn)，如下所示：

表3 列出了G-CSAO 使用不同的適應(yīng)度函數(shù)時在各數(shù)據(jù)集上的實(shí)驗(yàn)效果，最好的實(shí)驗(yàn)結(jié)果被加粗列出。

從表中的數(shù)據(jù)可以看出，當(dāng)G-CSAO 采用適應(yīng)度函數(shù)f3，平均效果是最好的。因此，在實(shí)驗(yàn)中將使用f3時的實(shí)驗(yàn)結(jié)果與其他算法進(jìn)行對比。

從表4 列出的數(shù)據(jù)可以看出，G-CSAO 在Iris、Cancer、Heart、Balance 和Diabetes 等5 個數(shù)據(jù)集上的效果都是最好的，在Thyroid和Wine數(shù)據(jù)集上，G-CSAO的表現(xiàn)僅次于MlpAnn，在Cancer-Int 數(shù)據(jù)集上，G-CSAO的表現(xiàn)比MltBoost 算法差。在Credit 和Horse 數(shù)據(jù)集上，G-CSAO 的效果僅次于Bagging。在Dermatology 數(shù)據(jù) 集 上，G-CSAO 的 效 果 要 比MlpAnn 和Bagging 差。G-CSAO 在Glass 數(shù)據(jù)集上的效果比較一般。綜合來看，基于G-CSAO 構(gòu)造的分類器在這12 個數(shù)據(jù)集上取得了不錯的效果。

表3 不同適應(yīng)度函數(shù)的分類錯誤率%

6 結(jié)束語

在大數(shù)據(jù)的時代背景下，當(dāng)傳統(tǒng)的優(yōu)化算法和模式識別算法并不能滿足人們對數(shù)據(jù)分析的需求時，本文提出一種新型的自然啟發(fā)模型（G-CSAO），模擬群體狀態(tài)自適應(yīng)中逐漸達(dá)到穩(wěn)定狀態(tài)的過程，并與最小距離規(guī)則相結(jié)合形成新的模式分類分析模型。通過函數(shù)極值實(shí)驗(yàn)，多角度的分析，驗(yàn)證了G-CSAO 的有效性和穩(wěn)定性；通過UCI數(shù)據(jù)集實(shí)驗(yàn)，測試了G-CSAO 在模式分類問題中的性能，以12個數(shù)據(jù)集的分類結(jié)果同8個經(jīng)典的模型相比較，具有不錯的表現(xiàn)。說明G-CSAO 在大數(shù)據(jù)應(yīng)用中有很好的潛能。

伴隨著網(wǎng)絡(luò)大數(shù)據(jù)的飛速發(fā)張和擴(kuò)張，本文提出的G-CSAO 模型能夠應(yīng)對優(yōu)化問題復(fù)雜，數(shù)據(jù)量增大，數(shù)據(jù)維度變大和數(shù)據(jù)結(jié)構(gòu)多樣性的情況。在對圖像、語音識別等領(lǐng)域?qū)荊-CSAO 今后的研究重點(diǎn)，希望可以在演化行為領(lǐng)域做出更大的貢獻(xiàn)。

表4 各算法在12個UCI數(shù)據(jù)集上的分類錯誤率 %