求解高維函數(shù)優(yōu)化的混合智能算法

廉侃超

摘要：針對幾個高維函數(shù)優(yōu)化進(jìn)行了研究，提出一種混合智能算法。借鑒人口遷移算法的進(jìn)化體制，精簡了算法步驟；鑒于云模型的云滴在隨機(jī)中帶有穩(wěn)定傾向性，將人口進(jìn)化過程中初始人口群體由云模型的云滴代替，人口流動轉(zhuǎn)化為上一代云滴產(chǎn)生新一代云滴的過程；為防止尋優(yōu)陷入局部極值，借用柯西分布的強擾動性，對優(yōu)惠區(qū)域的人口實施柯西變異。幾個典型高維函數(shù)的仿真實驗表明，算法求解質(zhì)量高、性能穩(wěn)定，甚至對幾個維數(shù)高達(dá)10000維的超高維函數(shù)，算法都可以穩(wěn)定收斂到理論最優(yōu)。

關(guān)鍵詞：人口遷移算法；云模型；柯西變異；高維函數(shù)優(yōu)化

中圖分類號：TP18

文獻(xiàn)標(biāo)志碼：A

文章編號：1006-8228（2017）01-47-04

0.引言

求解高維函數(shù)時，隨著維數(shù)的增加，解空間及問題的復(fù)雜度呈指數(shù)級增加，甚至產(chǎn)生維數(shù)災(zāi)難，高維函數(shù)又常有多個局部最優(yōu)，增加了問題求解的欺騙性。遺傳算法、粒子群算法、蟻群算法等傳統(tǒng)智能算法，在求解小規(guī)模低維優(yōu)化問題時性能較好，對高維或超高維函數(shù)的優(yōu)化卻效果不佳。人類是自然界最具智慧的，人類的生息必然蘊藏著高智能的算法。人口遷移算法（Population Migration Algorithm，PMA）就是從人類活動中總結(jié)、抽象出來的一種智能算法，于2003年由我國學(xué)者周永華、毛宗源提出。這兩位學(xué)者通過對人類的社會活動進(jìn)行研究，發(fā)現(xiàn)當(dāng)人類的經(jīng)濟(jì)重心發(fā)生轉(zhuǎn)移時，人口密度也隨之轉(zhuǎn)移，根據(jù)人類活動的這種機(jī)理他們提出了人口遷移算法。算法進(jìn)化的過程由人口流動、人口遷移和人口擴(kuò)散組成，實驗表明算法的全局搜索能力較強，且文獻(xiàn)證明了算法是收斂的。但在高維函數(shù)的求解中，人口遷移算法易陷入局部極值，尋優(yōu)速度有所下降。

云模型是一個定性、定量轉(zhuǎn)換模型，由我國學(xué)者李德毅教授提出。該模型既是對模糊理論的創(chuàng)新，也是對隸屬函數(shù)概念的發(fā)展，它的云滴體現(xiàn)了隨機(jī)性和穩(wěn)定性的有機(jī)結(jié)合。云模型一經(jīng)提出，就受到多方學(xué)者的關(guān)注，已成功應(yīng)用于多個領(lǐng)域。柯西分布是概率論與數(shù)理統(tǒng)計中的一種常見分布，相比高斯分布，柯西分布下降至零的速度慢得多。因此，柯西變異的擾動性比高斯變異強很多，更易使搜索跳出局部極值，從而可進(jìn)一步提高算法的全局尋優(yōu)能力。

在原人口遷移算法的基礎(chǔ)上，有機(jī)結(jié)合云模型和柯西變異，提出一種可求解高維函數(shù)優(yōu)化的混合智能算法（hybrid intelligence algorithm，簡稱HIA）。典型的高維函數(shù)測試表明，算法求解質(zhì)量高、性能穩(wěn)定，甚至對幾個維數(shù)高達(dá)10000維的函數(shù)也表現(xiàn)出了極好的尋優(yōu)效果。

1.云模型和柯西變異

1.1云模型

定義設(shè)u是一個用精確數(shù)值表示的論域（一維或多維的），u上對應(yīng)著定性概念A(yù)，對于論域中的任意一個元素x，都存在一個有穩(wěn)定傾向的隨機(jī)數(shù)y=u_A（x），叫作x對概念A(yù)的確定度，u_A（X）在u上的分布稱為云模型，簡稱云。當(dāng)u_A（x）服從正態(tài)分布時，稱為正態(tài)云模型。

定性概念A(yù)的定量特征由云的三個數(shù)字特征（期望Ex、熵En、超熵He）來體現(xiàn)（如圖l所示）。

生成云滴的算法或硬件稱為云發(fā)生器。文獻(xiàn)[7]闡述了基本云發(fā)生器的算法步驟。

1.2柯西變異

1.2.1柯西分布

柯西分布和高斯分布是概率論與數(shù)理統(tǒng)計中的常見分布。標(biāo)準(zhǔn)柯西、高斯分布概率密度函數(shù)圖如圖2所示。

由圖2知，柯西變異的擾動能力顯然強于高斯變異，用它對人口變異，更易跳出局部極值，從而提高搜索速度和全局尋優(yōu)能力。

由隨機(jī)變量生成函數(shù)定理呻知，式中Cauchy（0，1）=tan[（∈-0.5）π]，其中∈是[o，1]上服從均勻分布的隨機(jī)變量。

2.混合智能算法

2.1算法思想

人口遷移算法是一種基于隨機(jī)搜索的智能仿生算法，初始群體在搜索空間隨機(jī)產(chǎn)生，人口流動是在鄰域內(nèi)隨機(jī)變動，人口遷移是在優(yōu)惠區(qū)域隨機(jī)變動，隨機(jī)性一定程度上存在盲目性和不穩(wěn)定性，從而影響了算法的尋優(yōu)效果。從云模型示意圖可知，隨機(jī)的云滴具有穩(wěn)定傾向的特點，如果適當(dāng)調(diào)整云模型的三個數(shù)字特征（期望Ex，熵En和超熵He），還可調(diào)整云滴的隨機(jī)性范圍和穩(wěn)定性程度。混合算法采用人口遷移算法的進(jìn)化體制，用整個搜索空問的云滴作為人口遷移算法的初始群體，去掉人口擴(kuò)散精簡算法步驟，用在鄰域范圍內(nèi)產(chǎn)生云滴代替人口流動，為了避免算法限入局部極值，對優(yōu)惠區(qū)域的人口實施苛西變異。從前面的分析知，柯西變異具有很強的擾動能力，對優(yōu)惠區(qū)域人口進(jìn)行柯西變異，提高了算法跳出局部極值的可能性，使算法具有更強的尋優(yōu)能力。將云模型、柯西變異與人口遷移相結(jié)合也是一種新的嘗試。

2.2融合柯西變異、云模型和人口遷移算法的混合智能算法（HlA）

3.混合智能算法（HIA）性能分析

本文所用實驗環(huán)境為：操作系統(tǒng)為Windows XPProfessional SP3，硬件為Intel（R）Core（TM）2 Due CPUT5870～2GB內(nèi)存、wDc WD2500BEVS-08VAT2硬盤的ThinkPad SL400筆記本電腦，編程軟件為Matlab 2012b。

實驗中，為便于比較，對函數(shù)f_i～f_s的維數(shù)取30，50，100時進(jìn)行了實驗，對函數(shù)f₄的維數(shù)分別為10、20、30時進(jìn)行了實驗，每個函數(shù)的各維獨立計算30次，取最好解（best）、最差解（worst）、數(shù)學(xué)期望（average）和標(biāo)準(zhǔn)差（Std.Dev.）作為評價參數(shù)，將實驗數(shù)據(jù)與文獻(xiàn)的MEDE進(jìn)行了比較，結(jié)果如表2所示。

從表2可見，對f₁、f₄、30和50維的f₃，MEDE可搜到最優(yōu)，但對f₂和100維的f₃，MEDE的搜索結(jié)果只是接近于理論最優(yōu)。由文獻(xiàn)[11]知，當(dāng)函數(shù)f₁-f₃的維數(shù)為30，50.100及函數(shù)f₄的維數(shù)為10.20，30時.MEDE的最大迭代次數(shù)分別為1000，2000，5000。對函數(shù)f₁～f₄的各維，本文算法都可穩(wěn)定精確收斂于理論最優(yōu)，且算法參數(shù)不因函數(shù)維數(shù)的增加而變化，始終保持表1的設(shè)置，迭代次數(shù)均為2。可見，相對目前搜索結(jié)果較好的MEDE，本文算法具有更好的尋優(yōu)性能、穩(wěn)定性和魯棒性。

實驗中，還對f₁～f₄的100維、200維進(jìn)行了測試，本文算法的參數(shù)仍保持表1的設(shè)置。測試結(jié)果與文獻(xiàn)[11]的MEDE、DefirDE、DEfirSPX進(jìn)行比較，文獻(xiàn)[HI中幾個算法的迭代次數(shù)對f₁～f₃為50000，對f₄同文獻(xiàn)[12]。比較結(jié)果如表3所示。

從表3可以看出，對于100維和200維的f₁～f₄，本文算法比目前結(jié)果較好的文獻(xiàn)nu中的幾個算法的求解質(zhì)量都要好，平均值和標(biāo)準(zhǔn)差都明顯優(yōu)于其他幾個算法，且本文算法的群體規(guī)模為3，迭代次數(shù)為2，比其他幾個算法少得多，但卻達(dá)到了更好的尋優(yōu)效果。而且隨著維數(shù)的增加，這種優(yōu)勢越來越明顯。

3.2超高維函數(shù)測試

為進(jìn)一步驗證算法的性能，對函數(shù)f₁～f₄的超高維（1000，2000，5000，10000）進(jìn)行了實驗。對如此高維函數(shù)的測試，目前基本都是在性能非常好的并行機(jī)上運行，而本文的實驗仍然是在個人筆記本上運行。實驗時，HIA的各參數(shù)仍保持表1的設(shè)置不變，算法對每個函數(shù)的各超高維均運行10次。實驗結(jié)果令人鼓舞：隨著函數(shù)維數(shù)的增加，問題的復(fù)雜度大大增加，但算法的參數(shù)和求解質(zhì)量卻不受影響，避免了維數(shù)災(zāi)難。事實上，每一次實驗，算法都可精確收斂到各超高維函數(shù)的理論最優(yōu)。可見，混合智能算法求解質(zhì)量高，性能穩(wěn)定。

4.結(jié)論與展望

原人口遷移算法步驟多，搜索速度慢，易陷入局部最優(yōu)，不利于求解高維或超高維函數(shù)。正態(tài)云模型的云滴既具有隨機(jī)性又具有穩(wěn)定性，穩(wěn)定性可在一定程度上保護(hù)歷史較好個體，隨機(jī)性可幫助個體跳出局部極值。柯西變異相對高斯變異具有更強的擾動能力，可幫助個體擴(kuò)大搜索范圍。將改進(jìn)后的人口遷移算法與云模型和柯西變異有機(jī)融合：借用改進(jìn)人口遷移算法的搜索機(jī)制，初始群體為搜索空間產(chǎn)生的云滴，人口流動為鄰域內(nèi)產(chǎn)生云滴的過程，人口遷移后對優(yōu)惠區(qū)域的人口進(jìn)行柯西變異。所以，混合智能算法既保留了改進(jìn)人口遷移算法的較好尋優(yōu)機(jī)制，又充分利用了云模型的隨機(jī)穩(wěn)定性和柯西變異的強擾動力，提高了算法的尋優(yōu)能力。仿真實驗表明，混合智能算法尋優(yōu)性能好，求解效率和質(zhì)量高，且性能穩(wěn)定。