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

洪曉敏，王帥群，孔薇

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

0 引言

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

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

1 帝國主義競爭算法

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

1.1 個體和帝國初始化

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

衡量一個國家的強弱用成本值來體現，成本值由成本函數 f來計算：

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

在帝國初始化階段，引入標準化成本值Cn，根據該成本值來衡量該帝國主義的比重，第n個帝國主義的實力占整個總實力的比例可以用下式表示：

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

1.2 殖民地同化

帝國初始化后，將進行殖民地的同化，這也是帝國主義競爭算法的核心。在同一個帝國中，殖民地通過向帝國主義學習而使其變的更優秀，殖民地向帝國主義的移動過程如圖1所示：

圖1 殖民地向帝國移動過程

在圖1中，殖民地向帝國主義移動了X個單位，X是隨機均勻分布的變量，滿足：

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

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

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

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

1.4 計算帝國總成本

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

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

1.5 帝國競爭

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

圖3 帝國競爭

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

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

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

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

2.1 多層學習機制

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

圖4 FICA算法的流程圖

2.2 變異因子的介紹

（1）高斯變異

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

不難發現，通過高斯隨機函數產生的高斯隨機數，范圍較??；換而言之，它能使個體在比較小的領域內進行仔細的搜索，所以當變異對象接近最優值或者已經陷入局部最優時，優先選擇它。

（2）柯西變異

柯西變異主要是依靠柯西分布函數，其表達式如下：

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

（3）Lateral變異

Lateral變異的執行，所參照的表達式如下：

其中學習比率 β∈[ ]0,1是一個均勻分布隨機數，它可以從種群當中隨機的選擇一個個體xkj,k≠i，利用該個體的信息特征來指導當前的搜索機制。因此，它可以更好地利用環境中的有效信息，這樣可以加快算法的收斂速度。

（4）Baldwinian學習

Baldwinian學習主要是通過多個個體之間的相互學習、相互調節和相互適應，從而不斷的對整個種群的進化起到一個推進作用。其表達式如下：

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

2.3 FICA的流程

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

步驟一：參數設置。

步驟二：在針對每一個目標函數所規定的搜索空間內隨機產生N個國家，維度為D。

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

步驟四：執行多層學習機制：產生一個隨機數，根據隨機數的大小，來確定每次迭代執行哪種變異算子，通過變異來得到更新后的帝國。

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

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

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

3 實驗結果

3.1 算法參數設置

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

為了與其他文獻進行比較，初始的種群個數設為88，并且設定帝國主義國家的個數為8，則殖民地個數為80，將基于多種變異機制的帝國主義競爭算法在23個基準函數[17]上進行仿真實驗，所有的仿真和統計結果均來自算法獨立運行20次，前13個高維函數，最大迭代次數為2000，后10個低維函數，最大迭代次數為100。

3.2 結果分析

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

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

4 結語

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

圖5 函數 f14的收斂圖

圖6 函數 f16的收斂圖

圖7 函數 f17的收斂圖

圖8 函數 f18的收斂圖

圖9 函數 f19的收斂圖

圖10 函數 f20的收斂圖

表1 橫向改進：FICA與原始帝國主義競爭算法的比較爭算法的比較

表2 縱向比較：改進的帝國競爭算法與其他優秀帝國主義競爭算法的比較