求解大尺度優化問題的學生t-分布估計算法

王豫峰 董文永 董學士 王 浩

1(武漢大學計算機學院 武漢 430072) 2(南陽理工學院軟件學院 河南南陽 473000) 3 (巖土力學與工程國家重點實驗室(中國科學院武漢巖土力學研究所) 武漢 430071) (wangyufeng@whu.edu.cn)

求解大尺度優化問題的學生t-分布估計算法

王豫峰1,2董文永1董學士1王 浩3

1(武漢大學計算機學院 武漢 430072)2(南陽理工學院軟件學院 河南南陽 473000)3(巖土力學與工程國家重點實驗室(中國科學院武漢巖土力學研究所) 武漢 430071) (wangyufeng@whu.edu.cn)

針對處理大尺度全局優化問題，提出一種基于自適應t-分布的分布估計算法(EDA-t).該算法不僅求解效果良好，而且求解速度也比同類型算法快.其基本思想是：在迭代搜索過程，首先利用期望最大化算法對演化種群進行概率主成分分析，然后根據得到的概率隱變量建立算法的概率模型，并通過t-分布自由度自適應方法，在算法收斂停滯時跳出局部最優.由于在構建模型時進行了數據降維，在不影響算法求解精度的前提下，其計算開銷得到了明顯降低.通過和目前主流的演化算法在大尺度優化測試函數上的仿真實驗和分析，驗證了所提算法的有效性和適用性.

概率主成分分析；學生t-分布；分布估計算法；大尺度全局優化；最大期望算法

分布估計算法(estimation of distribution al-gorithm, EDA)[1]，是元啟發算法的重要分支之一.它最開始被用于求解組合優化問題，后來擴展到求解連續優化問題.EDA是一種隨機優化算法，通過對有希望的候選解采樣來建立概率模型，從而探索潛在的解空間[2].通過學習的模型(單變量模型、雙變量模型、多變量模型、混合變量模型)，EDA可以提取變量中的一些隱藏的關系[3].例如：PBIL[4],UMDAG c[5]，MIMIC[6]，BMDA[7]，BOA[8]，IDEA[9]，GMM-EDA[10]等.它們都被成功應用到很多低維優化問題中.

然而，當優化問題的維度增加時，由于問題變量之間的強相關性和高復雜度，原始的元啟發算法面臨著巨大的挑戰.大尺度優化問題(large scale global optimization, LSGO)極難被處理，主要有2方面原因：1)維度災難.隨著問題維度的增長，搜索空間指數級地增長.2)問題維度的增長導致問題的特性(多峰、奇異點等)變得更加復雜.比如：Rosenbrock函數在兩維空間中是一個單峰問題，但是，隨著問題維度的增加，該函數變成多峰問題[11].當問題的維度增長時，EDA的性能下降非常快.為了克服這一個問題，一些EDA的變體算法被提出.Posik[12]提出利用獨立成分分析方法對原始坐標系進行變換的遺傳算法.Dong等人[13]提出一種基于模型復雜度控制的分布估計算法框架，它通過利用識別變量的弱相關行進行子空間建模.Kaban等人[14]提出一種基于隨機投影的分布估計算法，它通過隨機投影方式對原始協方差矩陣進行壓縮.

本文提出一種基于自適應t-分布的分布估計算法(adaptive estimation of student’st-distribution algorithm, EDA-t).EDA-t利用t-分布的重尾特性在全局搜索中探索更多的解空間.在整個演化過程中，利用概率主成分分析方法學習當前最優種群的主特征隱變量空間.在學習過程中，通過期望最大值估計(expectation maximization, EM)算法代替原來的特征值分解方法，來學習當前種群主特征值的概率隱空間.根據得到的概率隱空間構建算法的概率模型，從而減少生成模型的計算開銷，并加快算法收斂速度.通過對t-分布自由度的自適應，幫助算法在收斂停滯時跳出局部最優.本文提出的算法主要有3點創新：1)由傳統的基于高斯分布的EDA算法擴展到學生t-分布；2)在概率模型參數的估計方面，采用EM算法來降低原始EDA估計參數的復雜度；3)由于學生t-分布的自由度參數可以控制分布的形狀，自適應調整該參數能夠很好地解決基于種群算法的“探索”與“開發”之間的矛盾.

1 相關工作

1.1EDA框架

EDA從提出到現在，它的變體算法使用了很多種不同的概率模型，也有很多種實現方法.但是，EDA的基本框架可以總結如算法1所示.

算法1. EDA的基本框架.

輸入: 種群大小N、種群選擇數K；

輸出: 最優種群Popg.

①Pop0←InitialPop(N)； /* 初試化種群，隨機生成N個個體*/

②F0←f(Pop0)； /*求出Pop0每個個體的函數值*/

③ repeat

⑥Popg←getSamplePop(pg(x))； /*根據選擇的個體生成概率分布*/

⑦Fg←f(Popg)； /*求出Popg每個個體的函數值*/

⑧Popg←Combine(Popg-1,Popg)； /*根據函數值，將種群Popg-1,Popg中的最優個體進行合并*/

⑨ until a stopping criterion is met.

1.2學生t-分布

學生t-分布是一種統計分布.它的分布曲線呈對稱鐘形形狀，并且曲線的圖形與它的自由度υ大小有關.當υ比較小的時候，t-分布曲線中間較低，兩側尾部翹得較高；當υ增大時，分布曲線接近正態分布曲線；當υ→+∞時，t-分布曲線即為標準正態分布曲線.合理利用t-分布的這個重尾特性，能夠設計出一個非常好的概率模型.

假設x是通過多元學生t-分布S(x|μ,Σ,υ)生成的D維隨機變量:

(1)

其中，μ代表均值；Σ代表正定內積矩陣；υ代表自由度，υ>0；(x-μ)TΣ-1(x-μ)代表x到μ關于Σ的馬氏距離的平方；Σ-1是矩陣Σ的逆；Γ(x)代表伽馬函數.當υ<2時，方差不存在.當υ>2時，Συ/υ-2就是協方差矩陣.正態分布N(μ,Σ)實際也就等于S(x|μ,Σ,∞).

Fig. 1 Comparison between the univariate Gaussian and Students t-distributions圖1 單變量t-分布和標準高斯分布對比圖

為了更加清楚地理解t-分布，我們給出不同自由度下的單變量t-分布和標準高斯分布的概率密度函數圖對比，如圖1所示.其中，所有分布均值為0，固定方差為1.從圖1中可以看到，當自由度υ比較小的時候，t-分布比高斯分布的尾部更翹.從而導致生成的個體比高斯分布有更高的概率遠離均值，具有較強的全局搜索能力.在求解多峰問題的時候，更加容易逃離局部最優點，跳出停滯區.但是，它在均值點的概率密度更低，意味著減少局部搜索時間，局部微調能力降低.因此，t-分布的重尾特性有利也有弊.

2 EDA-t算法

本文提出一種新的求解大尺度優化問題的分布估計算法.算法使用基于概率隱空間建立的多元t-分布模型代替傳統的高斯分布模型.通過對t-分布的自由度調整來控制算法搜索的特性.同時，引入EM算法對模型參數進行估計.和傳統的PCA相比，大大減少了計算過程中的時間復雜度.

2.1概率主成分分析

傳統的主成分分析需要計算數據集的均值μ和協方差矩陣Σ，然后進行特征值分解，尋找矩陣Σ的前M個最大特征值所對應的特征向量[15].而在計算特征值分解的時候，對D×D矩陣進行特征值分解的代價為O(D3).當D增大時，算法復雜度增長特別快[16].

概率主成分分析可以視為概率隱變量模型的最大似然解.其主要思想是：先根據隱變量的先驗分布p(z)中生成隱變量z.然后，通過對隱變量z進行線性變換和附加噪聲的方式生成觀測數據點x[17].噪聲服從給定隱變量下的數據變量的某個條件概率分布p(x|z).

p(z)=S(z|0,I,θ)，

(2)

其中，z是一個M維隱變量，S為學生t-分布，θ為t-分布自由度，設置為固定值θ=20.

p(x|z)=S(x|Wz+μ,σ2I,υ)，

(3)

W是D×M的因子載荷，μ為D維樣本均值，υ為t-分布的自由度.

x=Wz+μ+ε，

(4)

ε為D維噪聲變量.

p(ε)=S(ε|0,I,θ).

(5)

式(4)中有4個參數W,μ,σ2和υ，其中，υ為固定值，μ可以直接根據種群算出.W和σ2需要通過EM算法進行估計.根據概率的加和規則和乘積規則，邊緣概率分布的形式為

(6)

由于這對應于一個線性t-分布模型，所以，邊緣概率分布還是t-分布，即：

p(x)=S(x|μ,C,υ)，

(7)

其中，D×D的協方差矩陣C被定義為

C=WWT+σ2I.

(8)

在進行特征值分解計算的過程中，需要對C求逆，即需要對D×D的矩陣求逆：

C-1=σ-2I-σ-2WB-1WT，

(9)

其中，M×M的矩陣B為

B=WTW+σ2I，

(10)

由于我們對B求逆，而不是直接對C求逆.因此，計算C-1的算法復雜度從O(D3)減小到O(M3).

2.2模型參數估計方法

(11)

(12)

ωi∈+,1≤i≤N，是種群組合權重系數.當ωi=1/N時，式(11)就是計算所有種群的平均值.

EM是一種迭代算法.首先，通過使用舊的參數值計算隱變量的后驗概率分布求期望.然后，最大化完整數據對數似然函數的期望就會產生新的參數值，直到迭代終止.完整數據的對數似然函數的形式為

lnp(X,Z|μ,W,σ2,υ)=

(13)

其中，矩陣Z的第n行由zn給出.均值μ由式(11)計算.分別使用式(2)和式(3)給出的隱變量概率分布和條件概率分布，對隱變量上的后驗概率分布求期望，于是有：

E[lnp(X,Z|μ,W,σ2,υ)]=

(14)

在E步，利用舊的參數去計算期望值:

(15)

(16)

在M步，估計新的參數值:

(17)

(18)

算法輪流執行E步和M步，一直到收斂.

2.3自由度自適應策略

對于t-分布，當υ=1時，t-分布就是標準柯西分布C(0,1)；當υ→+∞時，t-分布趨近標準高斯分布N(0,1).柯西分布的全局探索能力較強，能夠保持種群的多樣性；而高斯分布的局部開發能力較強，可以保證種群的收斂精度.為了綜合兩者優點，通過采取自由度自適應的方法來提高算法的靈活性和求解精度.

算法在每一次迭代計算完成后，設定一個進化狀態監視器U，記錄當前種群中最優個體.當連續k代最優個體函數值變化為0時，出現收斂停滯狀態，算法按比例α減小自由度，擴大算法全局探索能力，跳出局部最優值區域.

(19)

2.4算法框架

算法2展示了EDA-t的偽代碼，算法由4個部分組成：初始化、抽樣、選擇和參數估計.其中，行①為初始化部分.參數W是D×M的旋轉矩陣，從隱空間變化到種群原始空間，初始設置為D×D的單位矩陣前M列，參數σ初始設置為1；代碼行③④為樣本抽樣部分；代碼行⑤～⑨為樣本選擇部分；代碼行⑩～為參數估計部分，利用新獲取的種群對概率模型的參數進行估計；

算法2. EDA-t算法.

輸入: 種群大小N、隱空間大小M、混合率ω、自由度υ；

輸出: 最優種群Popg.

① 以隨機方式初始化μ，W，σ，g=0，α=0.2，k=15；

② while 未達到終止條件時 do

③ 依據式(2)生成N個M維隱變量Z；

④ 依據式(3)生成N個D維個體X；

⑤ ifg>0 then

⑦ else

⑨ end if

2.5算法復雜度分析

設問題維度為D，種群大小為N，隱變量大小為M.算法2中行③初始化隱變量Z的算法復雜度為O(NM)；行④生成觀測變量X的算法復雜度為O(ND)；行⑤～⑨對種群進行重新選擇組合，算法復雜度為O(N)；行⑩計算種群均值算法復雜度為O(N)；行通過EM算法估計參數W和參數σ.其中，EM算法的迭代次數為k，算法的復雜度為O(kNDM)；在本算法中，去除所有低階項，算法2的時間復雜度為O(kNDM).由于k、N和M都為固定值并且遠遠小于D，所以，整個算法的復雜度是遠遠小于基于特征值分解的算法O(D3).

3 仿真實驗與分析

為了充分驗證EDA-t算法在不同維度下的性能，實驗選取了13個測試函數進行了實驗分析.其中，F1-F2是可分離單峰問題；F3-F10是不可分離并且有極少(≤2)局部最優問題；F11-F13是多峰并且具有多局部最優問題.函數具體情況如表1所示，詳細函數的設置見文獻[13].

3.1實驗設置

在對比實驗中，測試問題維度為1000維，函數的最大評估次數FEs=2.5×106，實驗中每一個算法對于每一個測試函數均獨立運行25次.實驗系統環境為64位的Windows 7系統，CPU為Intel?CoreTMi3 3.60 GHz、內存為4 GB、代碼運行環境為Matlab R2015a.

Table 1 Benchmark Functions表1 基準測試函數

在1000維實驗中，選取了4個知名算法進行比較，分別是SaNSDE[18],DECC-G[19],EDA-MCC[13]和RP-EDA[14]，算法參數保持與原文獻一致的設置.EDA-t算法中，種群大小N=200、隱空間大小M=3、混合率ω=0.8，詳細參數設置見3.4節.

為了客觀公正的評價EDA-t算法的性能，采用Wilcoxon秩和檢驗和Friedman檢驗方法對實驗結果進行統計分析.Wilcoxon秩和檢驗的顯著性水平為0.05，在表2的底部的符號“-”，“+”和“≈”分別表示劣于、優于和相當于EDA-t的結果.

Table 2 Mean Error, Standard Deviation and Comparison Results Based on Wilcoxon’s Rank Sum Test

Continued (Table 2)

Fig. 2 Convergence curve of five algorithms on functions F1,F4,F6,F7,F8 and F9圖2 各算法在函數F1,F4,F6,F7,F8和F9上的收斂曲線

3.2實驗結果分析

通過表2、表3、圖2和圖3分析可發現，EDA-t算法在收斂速度、收斂精度和運行時間方面，與其他算法相比占有較大優勢.特別是在F1,F2,F5,F6,F8和F9測試函數上，EDA-t算法可以快速收斂，并取得最優解.

Fig. 3 CPU time per run of five algorithms圖3 各算法的運行時間

Fig. 4 Fitness value of five algorithms on different dimensions圖4 各個算法在不同維度下收斂精度

AlgorithmRankSaNSDE4．69DECC?G3．50EDA?MCC3．58RP?EDA3．08EDA?t1．38

在表2中，EDA-t除F3,F7和F13三個函數外均全面優于SaNSDE和DECC-G.SaNSDE采用鄰域搜索的差分演化算法，該算法對低維的優化問題能取得較好的解.但是，對高維優化問題的搜索代價過大，往往不能得到很好的解.DECC-G是采用隨機分組的協同演化算法，對于大尺度可分離優化問題能夠得到較好的解.但是，對于非可分的優化問題，求解效果不太好.因此，EDA-t在求解大尺度全局優化問題全面優于這2種算法.

EDA-t在F1,F2,F5,F6,F9,F11和F12七個函數上要優于EDA-MCC和RP-EDA，在F3,F4,F7,F8,F10和F13六個函數上表現相似.EDA-MCC通過識別變量之間的弱相關性來控制模型的復雜度，而變量之間的相關性識別準確率直接影響算法的求解精度.RP-EDA通過將個體隨機投影到低維空間，然后在低維空間抽樣再還原到原始空間的方式進行演化，在演化的過程中具有很大的隨意性.EDA-t是通過隱空間建立概率模型，在全局搜索的過程按當前種群主成分方向進行引導搜索，進而搜索更有效率，帶來更優解.

從表2底部的Wilcoxon秩和檢驗的統計結果可以看出，EDA-t算法相對于其他近幾年出現的國際知名算法更具有明顯的優勢.表3給出了EDA-t和其他算法的Friedman檢驗排名，EDA-t排在第一，從統計學上說明了DECC-CLV算法的優勢.從圖3可以看出，EDA-t算法和其他EDA優化算法(EDA-MCC和RP-EDA)相比，算法單次運行時間大大降低.并且，基于非分解策略的EDA-t算法運行時間已經比較接近基于分解策略的協同演化算法DECC-G.

綜合以上實驗分析可以說明EDA-t算法具有較快的收斂速度、較強的收斂精度和較好的函數適用性，有效提高了對大尺度全局優化問題的收斂效率.

3.3算法的穩定性分析

為了測試算法在不同維度下的表現穩定性情況，我們將所有對比算法分別在不同問題維度D=[50,100,300,500,700,1 000]情況下，進行對比實驗.由于篇幅有限，我們從大尺度的測試函數中選F1,F5和F9三個函數進行測試.

從圖4可以看出，對于大尺度全局優化問題，當問題維度小于300時，EDA-t劣于SaNSDE.因為SaNSDE是基于領域搜索的差分演化算法，在對待低維問題，可以充分發揮SaNSDE全局的搜索能力，求到最優解.但是，當問題維度增加時，基于領域搜索的策略導致SaNSDE算法搜索開銷增大，性能降低.當問題維度大于300的時候，EDA-t算法在不同維度下都要比其他各種算法表現要好，表現出了算法的穩定性.

3.4參數敏感性實驗

為了研究算法中參數的不同設置對于算法性能的影響.在本節中，首先對種群大小N的不同取值進行對比實驗.然后，在種群大小固定的前提下，通過使用不同的參數設置進行對比實驗.在本節對比實驗中，函數的最大評估次數FEs=1 000×D.

從表4可以看出，在不同的問題維度下，EDA-t取得最優值時，所需的種群大小也不一樣.因為，本文算法是在1000維下和其他知名算法進行對比實驗.所以，在實際計算中，種群大小設置為N=200.

Table 4 Experimental Results of Different N on F2表4 F2函數上不同種群大小N的對比實驗

我們對參數M,ω,υ進行正交對比實驗，隱空間大小M=[1,3,5,7]；混合率ω=[0.8,0.6,0.4]；自由度υ=[5,20,100,200].由于篇幅限制，文中只列出F5、F7和F11函數的實驗結果圖.

Fig. 5 Mesh grid of different parameters on functions F5圖5 不同參數在函數F5上的曲面網狀圖

Fig. 6 Mesh grid of different parameters on functions F7圖6 不同參數在函數F7上的曲面網狀圖

Fig. 7 Mesh grid of different parameters on functions F11圖7 不同參數在函數F11上的曲面網狀圖

從圖5～7可以看出，當M≥3時，算法的求解精度逐漸變好.但是，隨著M的變大，算法的復雜度也加倍變大.所以，當M=3時，可以較好地平衡求解精度和算法復雜度.當ω=0.8時，EDA-t算法采用不同參數設置所取得的最差求解精度，也要比ω=0.4和ω=0.6所得到的求解精度好，表現了較強的魯棒性.算法自由度υ從5變為20時，算法的求解精度明顯變好.但是，當υ繼續增大時，算法求解精度的變化不是很大.綜上分析，在綜合考慮算法計算代價與計算精度的平衡，算法參數可以取M≥3，ω=0.8和υ=20.

3.5自由度自適應策略有效性分析

為了研究t-分布的自由度自適應策略對算法性能的影響，在本節中，使用自由度固定的EDA-t算法和自由度自適應的EDA-t算法進行對比實驗.EDA-t中的固定自由度按3.4節中最優值進行設置，υ=20.對比實驗結果如表5所示.

從表5可以看出，EDA-t算法全面優于EDA-t算法，表明采取自由度自適應策略在整個演化過程中可以有效避免陷入局部最優.從而快速收斂到局部最優，并表現出較好的穩定性.

Table 5 Experimental Results of Fixed EDA-t andAdaptive EDA-t

3.6概率PCA的有效性分析

為了研究ED-t中使用概率PCA對算法性能的影響，在本節中，使用基于PCA的EDA-t算法和基于概率PCA的EDA-t算法進行對比實驗.對比實驗結果如表6、表7所示.

Table 6 Experimental Results of EDA-t Based on PCAand PPCA

從表6、表7中可以看出，當EDA-t使用PCA而不使用概率PCA的時候，算法求解精度變化不太大.但是，算法求解的時間隨著問題維度的增加而急劇增加，直接導致算法在問題維度大于500維的時候，因為運算超時而無法求解.

Table 7 CPU Time of EDA-t Based on PCA and PPCA

4 總 結

本文提出了一種新的基于自適應t-分布的分布估計算法EDA-t.它通過對t-分布自由度自適應的調節，提高了算法的全局探索能力和跳出局部最優停滯區的能力.通過使用隱空間的轉換，加快了算法的收斂速度.通過對13個大尺度全局優化進行測試，實驗結果表明與當前主流算法相比，本文算法在求解的精度與收斂速度上具有更優的性能.另外，如何將算法與實際問題相結合是未來研究工作的重點.

[1] Muhlenbein H, Bendisch J, Voigt H M. From recombination of genes to the estimation of distributions Ⅱ. Continuous parameters[C] //Proc of the Int Conf on Parallel Problem Solving From Nature Ⅳ. Berlin: Springer, 1996: 188-197

[2] Hauschild M, Pelkan M. An introduction and survey of estimation of distribution algorithms[J]. Swarm & Evolutionary Computation, 2011, 1(3): 111-128

[3] Zhang Bo, Hao Jie, Ma Gang, et al. Mixture of probabilistic canonical correlation analysis[J]. Journal of Computer Research and Development, 2015, 52(7): 1463-1476 (in Chinese)(張博, 郝杰, 馬剛, 等. 混合概率典型相關性分析[J]. 計算機研究與發展, 2015, 52(7): 1463-1476)

[4] Sebag M, Ducoulombier A. Extending population-based incremental learning to continuous search spaces[C] //Proc of the Parallel Problem Solving From Nature Ⅴ. Berlin: Springer, 1998: 418-427

[5] Larraaga P, Lozano J A. Estimation of distribution algorithms. A new tool for evolutionary computation[J]. IEEE Trans on Instrumentation & Measurement, 2002, 64(5): 1140-1148

[6] Bonet J S D, JR C L I, Viola P A. MIMIC: Finding optima by estimating probability densities[C] //Advances in Neural Information Processing Systems. Cambridge: MIT Press, 1997: 424-430

[7] Pelikan M, Muehlenbein H. The bivariate marginal distribution algorithm[M]. Berlin: Springer, 1998: 521-535

[8] Pelikan M, Goldberg D E, Cant E. BOA: The Bayesian optimization algorithm[C] //Proc of the 1st Conf on Genetic and Evolutionary Computation. San Francisco: Morgan Kaufmann, 1999: 525-532

[9] Bosman P A N, Thierens D. Expanding from discrete to continuous estimation of distribution algorithms: The IDEA[C] //Proc of the Int Conf on Parallel Problem Solving From Nature Ⅵ. Berlin: Springer, 2000: 767-776

[10] Lu Qiang, Yao Xin. Clustering and learning gaussian distribution for continuous optimization[J]. IEEE Trans on Systems Man & Cybernetics Part C Applications & Reviews, 2005, 35(2): 195-204

[11] Shang Yunwei, Qiu Yuhuang. A note on the extended Rosenbrock function[J]. Evolutionary Computation, 2006, 14(1): 119-126

[12] Posik P. On the utility of linear transformations for population-based optimization algorithms[C] //Proc of the 16th Congress of the Int Federation of Automatic Control. Prague: IFAC, 2005: 281-286

[13] Dong Weishan, Chen Tianshi, TINO P, et al. Scaling up estimation of distribution algorithms for continuous optimization[J]. IEEE Trans on Evolutionary Computation, 2013, 17(6): 797-822

[14] Kab N A, Bootkrajang J, Durrant R J. Toward large-scale continuous EDA: A random matrix theory perspective[J]. Evolutionary Computation, 2016, 24(2): 255-291

[15] Fang Minquan, Zhang Weimin, Zhou Haifang. Parallel algorithm of fast independent component analysis for dimensionality reduction on many integrated core[J]. Journal of Computer Research and Development, 2016, 53(5): 1136-1146 (in Chinese)(方民權, 張衛民, 周海芳. 集成眾核上快速獨立成分分析降維并行算法[J]. 計算機研究與發展, 2016, 53(5): 1136-1146)

[16] Zhang Cheng, Wang Dong, Shen Chuan, et al. Separable compressive imaging method based on singular value decomposition[J]. Journal of Computer Research and Development, 2016, 53(12): 2816-2823 (in Chinese)(張成, 汪東, 沈川, 等. 基于奇異值分解的可分離壓縮成像方法[J]. 計算機研究與發展, 2016, 53(12): 2816-2823)

[17] Bishop C M. Pattern recognition and machine learning[M]. Berlin: Springer, 2006, 571-586

[18] Yang Zhenyu, Tang Ke, Yao Xin. Self-adaptive differential evolution with neighborhood search[C] //Proc of IEEE World Congress on Computational Intelligence, NJ: IEEE, 2008: 1110-1116

[19] Yang Zhenyu, Tang Ke, Yao Xin. Large scale evolutionary optimization using cooperative coevolution[J]. Information Sciences, 2008, 178(15): 2985-2999

AdaptiveEstimationofStudent’st-DistributionAlgorithmforLarge-ScaleGlobalOptimization

Wang Yufeng1,2, Dong Wenyong1, Dong Xueshi1, and Wang Hao3

1(ComputerSchool,WuhanUniversity,Wuhan430072)2(SoftwareSchool,NanyangInstituteofTechnology,Nanyang,Henan473000)3(StateKeyLaboratoryofGeomechanicsandGeotechnicalEngineering(InstituteofRockandSoilMechanics,ChineseAcademyofSciences),Wuhan430071)

In this paper, an adaptive estimation of student’st-distribution algorithm (EDA-t) is proposed to deal with the large-scale global optimization problems. The proposed algorithm can not only obtain optimal solution with high precision, but also run faster than EDA and their variants. In order to reduce the number of the parameters in student’st-distribution, we adapt its closed-form in latent space to replace it, and use the expectation maximization algorithm to estimate its parameters. To escape from local optimum, a new strategy adaptively tune the degree of freedom in thet-distribution is also proposed. As we introduce the technology of latent variable, the computational cost in EDA-tsignificantly decreases while the quality of solution can be guaranteed. The experimental results show that the performance of EDA-tis super than or equal to the state-of-the-art evolutionary algorithms for solving the large scale optimization problems.

probabilistic PCA; student’st-distribution; estimation of distribution algorithm (EDA); large scale global optimization (LSGO); expectation maximization (EM) algorithm

Wang Yufeng, born in 1982. PhD candidate of Wuhan University. Student member of CCF. His main research interests include machine learning, evolutionary computation, data dimension reduction.

Dong Wenyong, born in 1973. Professor and PhD supervisor in Wuhan University. His main research interests include evolutionary computation, system control, machine learning, parallel computing.

Dong Xueshi, born in 1985. PhD candidate of Wuhan University. His main research interests include evolutionary computation, machine learning.

Wang Hao, born in 1972. PhD. Research Professor in the Institute of Rock and Soil Mechanics, Chinese Academy of Sciences, Wuhan. His main research interests include evolutionary computation, machine learning.

2017-03-17；

：2017-05-15

國家自然科學基金項目(61170305，61672024，41472288)；河南省高等學校重點科研項目計劃(17A520046) This work was supported by the National Natural Science Foundation of China (61170305,61672024,41472288) and the Key Research Program in Higher Education of Henan Province (17A520046).

董文永(dwy@whu.edu.cn)

TP301