基于多種變異機(jī)制的帝國主義競爭算法

2018-10-25 01:21:08洪曉敏王帥群孔薇

現(xiàn)代計(jì)算機(jī) 2018年27期

洪曉敏，王帥群，孔薇

（上海海事大學(xué)信息工程學(xué)院，上海 201306)

0 引言

帝國主義競爭算法（Imperialist Competition Algo?rithm，ICA）是一種群智能優(yōu)化算法，由Atashpaz-Gar?gari和Lucas從帝國之間相互競爭的社會(huì)現(xiàn)象受到啟發(fā)，于2007年提出[1]。與其他所有的元啟發(fā)式優(yōu)化算法一樣，算法開始于種群初始化，每一個(gè)初始化的個(gè)體看作為一個(gè)國家，而國家又可以分為帝國主義和殖民地，隨后通過殖民地同化、帝國與殖民地位置互換、帝國競爭與帝國倒塌等一系列步驟，最后算法收斂于全局最優(yōu)值或近似收斂于全局最優(yōu)值。

帝國主義競爭算法作為一類比較新的隨機(jī)優(yōu)化算法，其在解決低維問題上表現(xiàn)出其優(yōu)勢，但是在解決高維問題上，還存在一系列的問題，例如：容易陷入局部最優(yōu)、收斂速度慢等。因此，很多學(xué)者致力于帝國主義競爭算法的改進(jìn)。2011年，Niknam[2]提出了用K均值優(yōu)化殖民地群體，用來避免算法未成熟先收斂。2014年，Yang采用混沌映射函數(shù)來初始化群體，使算法的搜索廣度大大增加[3]。2015年，Wang將國家之間可以自由貿(mào)易這一現(xiàn)象映射到帝國主義競爭算法中，提出了基于貿(mào)易機(jī)制的帝國主義競爭算法，加快了算法的收斂速度[4]。2016年，梁毅將微分進(jìn)化算子融入到帝國主義競爭算法中，用以避免個(gè)體過早收斂，并將改進(jìn)的帝國主義競爭算法應(yīng)用在分布式電源選址和定容的優(yōu)化問題中[5]。至今，帝國主義競爭算法已經(jīng)廣泛應(yīng)用在日常生活中的實(shí)際問題上：如土木工程中的結(jié)構(gòu)模態(tài)參數(shù)識(shí)別[6]、WSNs定位方案[7]、短期風(fēng)功率預(yù)測[8]、電網(wǎng)碳排放優(yōu)化模型[9]，以及無人機(jī)三維航線規(guī)劃[10]。本文就是在這樣的情況下產(chǎn)生的，擬在加快算法的收斂速度和跳出局部最優(yōu)之間做出平衡，因此，在同化過程中融入了四種變異因子，提出了基于多種變異機(jī)制的帝國主義競爭算法（FICA）。

1 帝國主義競爭算法

帝國主義競爭算法的基本流程如下：首先是種群和帝國的初始化，初始的個(gè)體稱作國家，根據(jù)適應(yīng)度的大?。▏覐?qiáng)弱）將其劃分為帝國主義和殖民地，適應(yīng)度大的為帝國主義，并且根據(jù)適應(yīng)度的大小，為其分配殖民地。這與其他的智能優(yōu)化算法不同，即是一種基于子種群的進(jìn)化策略。隨后，殖民地被帝國主義同化，即向優(yōu)秀的個(gè)體學(xué)習(xí)使自己變地更強(qiáng)大，在同化的過程中，學(xué)習(xí)能力較好的殖民地有可能優(yōu)于帝國主義，那么，當(dāng)前殖民地則與帝國主義進(jìn)行位置互換。而在帝國之間也存在競爭，較強(qiáng)的帝國主義通過侵略其他國家來使自己變得更強(qiáng)大，而較弱的帝國主義將會(huì)失去其殖民地，當(dāng)一個(gè)帝國失去所有的殖民地后，該帝國倒塌。當(dāng)算法達(dá)到預(yù)設(shè)結(jié)束條件，例如只剩下一個(gè)帝國主義或者最大迭代次數(shù)，算法將終止。帝國主義競爭算法執(zhí)行過程一共分為六個(gè)模塊，分別是個(gè)體和帝國初始化、殖民地同化、殖民地和帝國主義的位置互換、帝國總成本計(jì)算、帝國競爭和算法收斂。

1.1 個(gè)體和帝國初始化

帝國主義競爭算法的初始化個(gè)體稱為國家，在遺傳算法中稱作染色體，對于一個(gè)D維的優(yōu)化問題可以用一個(gè)D維的向量表示出來。如:

衡量一個(gè)國家的強(qiáng)弱用成本值來體現(xiàn)，成本值由成本函數(shù) f來計(jì)算：

初始化種群的數(shù)目設(shè)為N，帝國主義的個(gè)數(shù)設(shè)為Nimp，剩余的國家則為殖民地，其個(gè)數(shù)為Ncol，并根據(jù)帝國主義的適應(yīng)度大小為其分配殖民地。在最小優(yōu)化問題中，帝國主義的強(qiáng)弱與其成本值成反比，即成本值越大，帝國主義的勢力越弱。

在帝國初始化階段，引入標(biāo)準(zhǔn)化成本值Cn，根據(jù)該成本值來衡量該帝國主義的比重，第n個(gè)帝國主義的實(shí)力占整個(gè)總實(shí)力的比例可以用下式表示：

其中Cn，滿足Cn=cn-max{ci}，cn表示第n個(gè)帝國主義的成本函數(shù)值，max{ci}所有帝國主義的成本函數(shù)最大值，因此，第n個(gè)帝國所能分得的殖民地?cái)?shù)量如下式所示：

1.2 殖民地同化

帝國初始化后，將進(jìn)行殖民地的同化，這也是帝國主義競爭算法的核心。在同一個(gè)帝國中，殖民地通過向帝國主義學(xué)習(xí)而使其變的更優(yōu)秀，殖民地向帝國主義的移動(dòng)過程如圖1所示：

圖1 殖民地向帝國移動(dòng)過程

在圖1中，殖民地向帝國主義移動(dòng)了X個(gè)單位，X是隨機(jī)均勻分布的變量，滿足：

其中，α是大于1的數(shù)，d是殖民地與帝國主義之間的距離，a大于1可以保證殖民地從兩邊向帝國主義靠近。

1.3 殖民地和帝國主義位置交換

殖民地在同化的過程中，其勢力有可能超過其帝國主義，在最小優(yōu)化問題中，即殖民地的成本值有可能比帝國主義更低，則殖民地與帝國主義互換位置，如圖2所示：

圖2 殖民地取代帝國主義示意圖

1.4 計(jì)算帝國總成本

帝國的整體實(shí)力應(yīng)該由帝國主義與附屬的殖民地共同決定，如式（6）：

其中，n∈Nimp，Tn表示第n個(gè)帝國的總成本，ε是[0 ,1]之間的正數(shù)，不同ε值體現(xiàn)了帝國主義成本在總成本中對應(yīng)的權(quán)重。ε的值很小時(shí)，帝國主義的成本在很大程度上將決定整個(gè)帝國的成本，隨著ε值的增大，殖民地的比重將會(huì)增加，本文ε的值取0.1。

1.5 帝國競爭

在帝國主義競爭算法中，所有的帝國都試圖依靠競爭來占有其他帝國的殖民地。帝國之間的競爭將導(dǎo)致弱的帝國失去自己的殖民地，該殖民地將分配給其他較強(qiáng)帝國。在競爭過程中，所有的帝國都有可能擁有該殖民地，不過，越強(qiáng)大的帝國將有更大的機(jī)會(huì)占有該殖民地，實(shí)力越來越強(qiáng)大，最終只剩下一個(gè)強(qiáng)大的帝國存在。其過程如圖3所示：

圖3 帝國競爭

1.6 弱勢帝國倒塌和算法收斂

帝國主義的倒塌，是指由于帝國之間的相互競爭，實(shí)力低的帝國會(huì)被剝奪他們所擁有的所有殖民地，即弱勢帝國的崩塌。與此同時(shí)，強(qiáng)大的帝國會(huì)占有更多的殖民地，因此它們的勢力也越來越強(qiáng)大。經(jīng)過長時(shí)間的競爭，在本文當(dāng)中指的是隨著算法的迭代，會(huì)有一個(gè)帝國存留下來，這個(gè)帝國將會(huì)擁有所有的殖民地。與此同時(shí)，它與其所擁有的殖民地有相同的控制位置和成本。在這種情況下，帝國主義競爭算法將結(jié)束，而且算法收斂于最強(qiáng)大的帝國主義的位置值。

2 基于四種變異機(jī)制的帝國主義競爭算法

帝國主義競爭算法由于其在解決復(fù)雜問題的優(yōu)越性被廣大學(xué)者研究和關(guān)注，但它也存在一些缺陷，如容易陷入局部最優(yōu)等缺點(diǎn)。本文將“國家之間不但可以相互學(xué)習(xí)，還可以自力更生，發(fā)展經(jīng)濟(jì)”這一現(xiàn)象映射到帝國主義競爭算法中，通過豐富算法的搜索動(dòng)力學(xué)特性來使算法的性能更加優(yōu)越，致力于既能提高算法的收斂速度，又可以避免算法陷入局部最優(yōu)，一個(gè)好的變異機(jī)制能夠快速地指導(dǎo)算法搜索到接近全局最優(yōu)解的區(qū)域。在文獻(xiàn)[11-12]中列舉了很多變異因子，其中高斯變異因子[13]、柯西變異因子[14]、Lateral變異因子[15-16]和Baldwinian變異因子[17]，因?yàn)槠鋵?shí)現(xiàn)簡單和易操作，被廣泛研究和應(yīng)用，且它們的搜索動(dòng)力學(xué)特性不一樣，高斯變異和柯西變異是基于個(gè)體自身的變異，僅僅給予當(dāng)前個(gè)體一個(gè)步長，有利于跳出局部最優(yōu)；Lateral變異因子和Baldwinian變異因子是基于個(gè)體之間相互學(xué)習(xí)，即利用了環(huán)境的因素，因此，算法具有較快的收斂速度。直覺告訴我們，可以將多個(gè)變異因子結(jié)合起來，形成一個(gè)多層變異機(jī)制，可以在加快算法的收斂速度和避免算法陷入局部最優(yōu)之間做到很好的平衡。

2.1 多層學(xué)習(xí)機(jī)制

多層學(xué)習(xí)機(jī)制即多個(gè)變異因子都參與搜索過程，但在算法每次迭代過程中僅執(zhí)行一個(gè)變異算子，不增加算法的復(fù)雜度。因此，在多層變異機(jī)制中，需對變異因子分配一定的概率，通過每次產(chǎn)生0～1之間的隨機(jī)數(shù)和累計(jì)概率來控制每一次同化過程中選擇哪一種變異因子，多層變異機(jī)制如圖4所示。本文的終止條件指的是：算法迭代到指定次數(shù)，維度不同的函數(shù)最大迭代次數(shù)不一樣，在后文中分別列出，下邊將詳細(xì)介紹四種變異算子。

圖4 FICA算法的流程圖

2.2 變異因子的介紹

（1）高斯變異

高斯變異有兩個(gè)參數(shù)：均值 μ和方差θ決定著變異的步長，均值為 μ和方差為θ的一維高斯密度函數(shù)為：

不難發(fā)現(xiàn)，通過高斯隨機(jī)函數(shù)產(chǎn)生的高斯隨機(jī)數(shù)，范圍較??；換而言之，它能使個(gè)體在比較小的領(lǐng)域內(nèi)進(jìn)行仔細(xì)的搜索，所以當(dāng)變異對象接近最優(yōu)值或者已經(jīng)陷入局部最優(yōu)時(shí)，優(yōu)先選擇它。

（2）柯西變異

柯西變異主要是依靠柯西分布函數(shù)，其表達(dá)式如下：

與高斯分布函數(shù)相比，柯西分布函數(shù)具有較長的余尾，因此，具有比較大的步長，可以讓個(gè)體進(jìn)行較大幅度的變異，使得變異對象的搜索空間變大，因此它具有使算法跳出局部最優(yōu)的能力。

（3）Lateral變異

Lateral變異的執(zhí)行，所參照的表達(dá)式如下：

其中學(xué)習(xí)比率 β∈[ ]0,1是一個(gè)均勻分布隨機(jī)數(shù)，它可以從種群當(dāng)中隨機(jī)的選擇一個(gè)個(gè)體xkj,k≠i，利用該個(gè)體的信息特征來指導(dǎo)當(dāng)前的搜索機(jī)制。因此，它可以更好地利用環(huán)境中的有效信息，這樣可以加快算法的收斂速度。

（4）Baldwinian學(xué)習(xí)

Baldwinian學(xué)習(xí)主要是通過多個(gè)個(gè)體之間的相互學(xué)習(xí)、相互調(diào)節(jié)和相互適應(yīng)，從而不斷的對整個(gè)種群的進(jìn)化起到一個(gè)推進(jìn)作用。其表達(dá)式如下：

它可以充分利用環(huán)境中的變異對象之間的信息不同，進(jìn)而讓環(huán)境中的信息充分利用，可以加快算法的收斂速度。

2.3 FICA的流程

本文中提出的FICA的流程圖如圖4所示，主要操作如下：

步驟一：參數(shù)設(shè)置。

步驟二：在針對每一個(gè)目標(biāo)函數(shù)所規(guī)定的搜索空間內(nèi)隨機(jī)產(chǎn)生N個(gè)國家，維度為D。

步驟三：計(jì)算種群中每一個(gè)國家的適應(yīng)度 f(Xi)，適應(yīng)度較大的Nimp個(gè)國家作為帝國主義，其余的則為殖民地。

步驟四：執(zhí)行多層學(xué)習(xí)機(jī)制：產(chǎn)生一個(gè)隨機(jī)數(shù)，根據(jù)隨機(jī)數(shù)的大小，來確定每次迭代執(zhí)行哪種變異算子，通過變異來得到更新后的帝國。

步驟五：判斷同化后的殖民地是否優(yōu)于其帝國主義，倘若有，互換殖民地與帝國主義的位置。

步驟六：計(jì)算帝國總成本，并將最弱帝國的最弱殖民地分配給最有可能擁有它的帝國。

步驟七：判斷是否有帝國失去了所擁有的殖民地，假若有，則淘汰該帝國；假若沒有，繼續(xù)步驟四。當(dāng)算法達(dá)到最大迭代次數(shù)，即便還沒收斂（還剩下不止一個(gè)帝國），算法也終止了。

3 實(shí)驗(yàn)結(jié)果

3.1 算法參數(shù)設(shè)置

四種變異因子各有不同的搜索動(dòng)力學(xué)特性，在此通過引用多層學(xué)習(xí)機(jī)制，將它們聯(lián)合起來，并且嵌入帝國主義競爭算法中，讓所有的變異因子一起參與算法的搜索，才有可能更好地提高算法的性能。在本文中，對每一種變異機(jī)制都規(guī)定一定的執(zhí)行概率，通過產(chǎn)生一個(gè)隨機(jī)數(shù)，根據(jù)隨機(jī)數(shù)的大小，來確定當(dāng)前執(zhí)行哪種變異。在不影響算法的收斂速度的情況下，又盡可能地避免算法陷入局部最優(yōu)，在本文中高斯變異因子、柯西變異因子、Lateral變異因子和Baldwinian變異因子的執(zhí)行概率分別設(shè)置為0.1、0.1、0.4、0.4，產(chǎn)生的隨機(jī)數(shù)的大小在0到1之間。

為了與其他文獻(xiàn)進(jìn)行比較，初始的種群個(gè)數(shù)設(shè)為88，并且設(shè)定帝國主義國家的個(gè)數(shù)為8，則殖民地個(gè)數(shù)為80，將基于多種變異機(jī)制的帝國主義競爭算法在23個(gè)基準(zhǔn)函數(shù)[17]上進(jìn)行仿真實(shí)驗(yàn)，所有的仿真和統(tǒng)計(jì)結(jié)果均來自算法獨(dú)立運(yùn)行20次，前13個(gè)高維函數(shù)，最大迭代次數(shù)為2000，后10個(gè)低維函數(shù)，最大迭代次數(shù)為100。

3.2 結(jié)果分析

表1列舉了基于多種變異機(jī)制的帝國主義競爭算法FICA和原始的帝國競爭算法ICA在23個(gè)基準(zhǔn)測試函數(shù)上的仿真結(jié)果。從以上MATLAB的運(yùn)行結(jié)果可以發(fā)現(xiàn)，F(xiàn)ICA在函數(shù) f6，f9和 f11上均在指定的迭代次數(shù)內(nèi)得到了函數(shù)理論上的最優(yōu)解，而ICA還遠(yuǎn)遠(yuǎn)沒有達(dá)到，由此可以看出FICA在此三個(gè)函數(shù)上的收斂速度和跳出局部最優(yōu)的能力得到了加強(qiáng)。 f1,f2，f3，f4，f5，f7，f8，f10，f12，f13，f15雖然針對這幾個(gè)函數(shù)FICA并沒有在指定的迭代次數(shù)內(nèi)找到理論的最優(yōu)值，但是相比較于ICA，F(xiàn)ICA所求取的最大值與最小值均要比ICA小很多，也就意味著精度高很多。針對函數(shù)f14，f16，f17，f18，f19，f20，F(xiàn)ICA和ICA最后得到的收斂值是一樣的，也都到達(dá)了理論上的最優(yōu)值，但通過各自的收斂圖，可以看出FICA收斂。速度明顯要快，如圖 5、圖 6、圖 7、圖 8、圖 9、圖 10所示。針對 f21，f22，f23這3個(gè)函數(shù)，雖然FICA與ICA最后得到的收斂值相差不多，但是ICA的均值離理論值的絕對值要比FICA的大，同時(shí)其方差也更大一點(diǎn)。

這表明FICA要比ICA的值更加靠近理論值。

4 結(jié)語

本文提出了一種基于多種變異機(jī)制的帝國主義競爭算法，在帝國競爭算法的最核心步驟——殖民地同化的過程中，將Baldwinian學(xué)習(xí)因子、Lateral變異因子、高斯變異因子、柯西變異因子相融合實(shí)現(xiàn)殖民地的同化機(jī)制。高斯變異和柯西變異利用了自身的隨機(jī)擾動(dòng)，而Lateral變異和Baldwinian學(xué)習(xí)充分利用了環(huán)境中的信息，這樣使得融合后的變異機(jī)制具有更強(qiáng)的全局尋優(yōu)能力。本文將FICA和ICA應(yīng)用在23個(gè)基準(zhǔn)函數(shù)上，通過比較驗(yàn)證了FICA具有更快的收斂速度與跳出局部最優(yōu)的能力；同時(shí)在所有條件相同的情況下，F(xiàn)ICA所得實(shí)驗(yàn)結(jié)果與算法CICA、AICA在3個(gè)函數(shù)上進(jìn)行比較，通過比較驗(yàn)證FICA具有更好得跳出局部最優(yōu)的能力。在本文中，并沒有每個(gè)變異因子的執(zhí)行概率，展開討論，在后續(xù)的工作中，將探索更好的執(zhí)行概率值，以提高算法的性能。