萬有引力與群體狀態自適應的智能優化算法

許瀚譽，馮 翔，虞慧群

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

1 引言

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

物質是由群體組成，群體狀態自適應也是一種自然啟發和優化的過程[13]。從宏觀角度，物質在特定環境的作用下，總是從一個不穩定的狀態轉換到一個相對穩定的狀態。從微觀角度，物質是由粒子組成的，粒子受到特定環境的作用，總是趨向于彼此間距離更小，引力更大。這種群體狀態自適應的現象，既符合優化問題的一般規律，也可以應用在對數據的處理問題中。

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

2 問題模型

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

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

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

在求解最優類中心的過程中，本文將從文獻[15]給出的三個適應度函數中選取一個作為本模型的適應度函數，用于評價當前的分類模型。

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

3 算法模型與算法設計

3.1 算法物理模型

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

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

圖1 群體狀態自適應模型圖

3.2 引力策略

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

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

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

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

3.3 單粒子自撞運動

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

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

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

之后再對粒子結構中的其他維進行相同的操作得到最終的新粒子結構，放入到群體Pop中，保持群體大小不變。

算法1單粒子自撞運動

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 雙粒子融合運動

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

算法2雙粒子融合運動

3.5 單粒子分裂運動

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

對X 進行單粒子分裂運動算法。具體操作如下：

如果f(X1)＜f(X)，那么對X1中粒子結構是X 的部分進行單粒子自撞運動：

得到的新的粒子X1；如果f(X1)＜f(X)，那么對X2中粒子結構是X 的部分進行單粒子自撞運動：

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

算法3單粒子分裂運動

3.6 雙粒子交叉運動

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

那么就對X1和X2進行雙粒子交叉運動算法，具體操作如下：

算法4雙粒子交叉運動

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

4 理論分析

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

圖2 G-CSAO算法流程圖

（1）若V′(x,t)是負定的，那么這個系統在x0=0的狀態是一直逐漸穩定的。

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

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

5 實驗模擬與分析

本文根據問題模型，將實驗模擬分為兩個部分：全局優化問題的函數極值實驗和模式分類問題的UCI 數據集實驗。在函數極值實驗中，主要驗證G-CSAO 模型收斂速度和魯棒性等，以及在數據高維度下的優化能力；在模式分類實驗中，將基于G-CSAO 的最小距離分類器同經典的機器學習算法相比較，測試G-CSAO模型在大數據問題中的潛能。本文實驗環境為：Intel Core Quad 2.7 GHz CPU；8 GB RAM；G-CSAO 模型在Windows 10環境下用C++編碼。

5.1 函數極值實驗

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

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

表1 基準優化測試函數

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

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

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

表2 函數極值實驗尋優結果

圖3 六種算法的迭代尋優曲線圖

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

5.2 UCI數據集實驗

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

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

表3 列出了G-CSAO 使用不同的適應度函數時在各數據集上的實驗效果，最好的實驗結果被加粗列出。

從表中的數據可以看出，當G-CSAO 采用適應度函數f3，平均效果是最好的。因此，在實驗中將使用f3時的實驗結果與其他算法進行對比。

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

表3 不同適應度函數的分類錯誤率%

6 結束語

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

伴隨著網絡大數據的飛速發張和擴張，本文提出的G-CSAO 模型能夠應對優化問題復雜，數據量增大，數據維度變大和數據結構多樣性的情況。在對圖像、語音識別等領域將會是G-CSAO 今后的研究重點，希望可以在演化行為領域做出更大的貢獻。

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