廉侃超

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

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

中圖分類號(hào)：TP18

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

文章編號(hào)：1006-8228（2017）01-47-04

0.引言

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

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

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

1.云模型和柯西變異

1.1云模型

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

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

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

1.2柯西變異

1.2.1柯西分布

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

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

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

2.混合智能算法

2.1算法思想

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

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

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

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

從表2可見(jiàn)，對(duì)f₁、f₄、30和50維的f₃，MEDE可搜到最優(yōu)，但對(duì)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時(shí).MEDE的最大迭代次數(shù)分別為1000，2000，5000。對(duì)函數(shù)f₁～f₄的各維，本文算法都可穩(wěn)定精確收斂于理論最優(yōu)，且算法參數(shù)不因函數(shù)維數(shù)的增加而變化，始終保持表1的設(shè)置，迭代次數(shù)均為2。可見(jiàn)，相對(duì)目前搜索結(jié)果較好的MEDE，本文算法具有更好的尋優(yōu)性能、穩(wěn)定性和魯棒性。

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

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

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

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

4.結(jié)論與展望

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