基于殖民地位置信息的自適應(yīng)帝國(guó)主義競(jìng)爭(zhēng)算法

劉阿建+梁鳳梅

摘 要： 在元啟發(fā)式算法中，問題優(yōu)化的質(zhì)量取決于算法參數(shù)的精準(zhǔn)設(shè)定，而參數(shù)的設(shè)定通常沒有一個(gè)確定的標(biāo)準(zhǔn)，重復(fù)實(shí)驗(yàn)又耗時(shí)耗力。偏離角度是帝國(guó)主義競(jìng)爭(zhēng)算法（ICA）中的一個(gè)重要參數(shù)，盲目選取可能會(huì)導(dǎo)致算法陷入局部最優(yōu)解，出現(xiàn)早熟收斂現(xiàn)象。為了克服該缺陷，提出一種基于殖民地位置信息概率密度函數(shù)的自適應(yīng)帝國(guó)主義競(jìng)爭(zhēng)算法。在帝國(guó)主義者同化殖民地過程中，根據(jù)殖民地密度函數(shù)動(dòng)態(tài)地調(diào)整其向帝國(guó)主義者運(yùn)動(dòng)的偏離角度，提高殖民地脫離局部最優(yōu)解探尋全局最優(yōu)解的能力。另一方面，帝國(guó)主義者通過及時(shí)掠取殖民地位置中的有用信息降低自己的成本函數(shù)，延伸了原算法中殖民地與帝國(guó)主義者位置互換的步驟，加快了算法的收斂速度。在一系列的基準(zhǔn)函數(shù)測(cè)試中，所提算法在收斂速度和優(yōu)化性能上均優(yōu)于原ICA和另外幾種經(jīng)典的遺傳算法。

關(guān)鍵詞： 帝國(guó)主義競(jìng)爭(zhēng)算法； 同化政策； 概率密度模型； 偏離角度； 殖民地位置； 全局優(yōu)化

中圖分類號(hào)： TN911?34； TP391.4 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2018）02?0124?06

Abstract： In the meta?heuristic algorithm， the quality of problem optimization depends on the setting precision of algorithm parameters， but there is no definitive standard for parameter setting， and repeated trials consume time and strength. Deviation angle is an important parameter in imperialist competitive algorithm （ICA）， and blind selection tends to make the algorithm trapped into local optimal solution， resulting in early convergence. To overcome this defect， an adaptive imperialist competitive algorithm based on the probability density function of colony location information is proposed. In the colony assimilation process of imperialists， the deviation angle that the colony moves to the imperialist is dynamically adjusted according to the density function of the colony so as to improve the colony′s capability of separating from the local optimal solution and seeking for the global optimal solution. The imperialists reduce their cost functions by timely capturing useful colony location information， which extends the procedures of location interchange between colonies and imperialists in the original algorithm， and speeds up the convergence of the algorithm. A series of benchmark function tests were carried out. The results show that the proposed algorithm has advantage in convergence speed and optimization performance in comparison to the original ICA and several other classical genetic algorithms.

Keywords： imperialist competitive algorithm； absorption policy； probability density model； deviation angle； colony location； global optimization

0 引 言

全局優(yōu)化問題已經(jīng)在科學(xué)、工程、商業(yè)等領(lǐng)域廣泛存在。目前為止，研究者們已經(jīng)提出多種進(jìn)化算法解決全局優(yōu)化問題。進(jìn)化算法的靈感來自自然進(jìn)化，它通過模擬生物種群不斷調(diào)整適應(yīng)環(huán)境變化的過程來探尋全局最優(yōu)解，主流的進(jìn)化算法如下所述。第一次由Holland提出的遺傳算法（GA）并由Goldberg研究與推廣，然而該算法由于其在解決大規(guī)模問題時(shí)計(jì)算復(fù)雜度較高而使用受限。粒子群優(yōu)化算法（PSO）[1]由Eberhart和Kennedy第一次提出，是一個(gè)典型的基于種群的進(jìn)化算法，靈感來自鳥和魚捕食的行為，該算法中每個(gè)個(gè)體代表一個(gè)問題的解決方案，并且根據(jù)自身的位置和最優(yōu)同伴的位置不斷調(diào)整自己的飛行速度，形成群體尋優(yōu)的正反饋機(jī)制，最終尋找到問題的最優(yōu)解。算法規(guī)則簡(jiǎn)單、收斂速度快使得其在工程上廣泛應(yīng)用，但是容易產(chǎn)生早熟收斂、局部尋優(yōu)能差。靈感來自螞蟻爬行的蟻群算法（ACO）是一個(gè)概率論法[2]，Mohan和Baskaran研究了蟻群算法在工程領(lǐng)域中的大量應(yīng)用，取得了理想的效果[3]。Geem等人首先提出的和聲搜索算法（HS）也是一種新的種群優(yōu)化算法[4]，它模擬音樂尋找更好和諧狀態(tài)的過程，相比于其他算法不僅計(jì)算能力高，而且內(nèi)存要求小。大規(guī)模鄰域搜索（VLNS）是基于觀察的尋找大規(guī)模鄰域內(nèi)高質(zhì)量的局部最優(yōu)解，因此全局VLNS得到的結(jié)果更好，該算法已經(jīng)在很多NP優(yōu)化問題中廣泛應(yīng)用[5]。Atashpaz?Gargari和Lucas首先提出帝國(guó)主義競(jìng)爭(zhēng)算法（ICA）[6]，該算法是由模擬生物進(jìn)化過渡到模擬社會(huì)行為，靈感來自帝國(guó)主義者侵占殖民地并相互競(jìng)爭(zhēng)的行為。它有傳統(tǒng)種群優(yōu)化算法無法比擬的優(yōu)點(diǎn)，不需要梯度函數(shù)、強(qiáng)大的局部搜索能力、允許所有的帝國(guó)相互競(jìng)爭(zhēng)的并行進(jìn)化機(jī)制，已經(jīng)廣泛應(yīng)用在各個(gè)領(lǐng)域的問題優(yōu)化中[7?9]。但是該算法存在缺陷，第一是同化過程中偏離角度需要人為設(shè)定，盲目選擇可能會(huì)導(dǎo)致算法陷入局部最優(yōu)；第二是對(duì)于高維的問題優(yōu)化收斂速度慢。針對(duì)這兩個(gè)問題，研究者們已經(jīng)進(jìn)行了多種改進(jìn)，Bahrami等人利用混沌映射理論確定殖民地被同化過程中的偏離角度[10]，提高了原算法的全局搜索能力，有效地避免了算法陷入局部最優(yōu)解的缺陷，但是需要事先確定混沌映射函數(shù)；Zhang等人通過殖民地移動(dòng)后隨機(jī)地選擇一部分更新他們的位置來避免算法陷入局部最優(yōu)解[11]；Lin等人提出了一種擾動(dòng)的ICA算法并用人造的帝國(guó)主義者去替代迭代中權(quán)利最小的帝國(guó)主義者從而提高帝國(guó)之間的信息交互[12]。以上算法的改進(jìn)，在一定程度上提高了原算法全局搜索的能力，但是共同的缺陷是人為干涉算法的進(jìn)行，AA Khaled等人提出一種模糊自適應(yīng)帝國(guó)主義競(jìng)爭(zhēng)算法（FAICA）[13?14]，在搜尋過程中使用一個(gè)模糊控制器動(dòng)態(tài)地調(diào)整偏離角度；Wang Shuaiqun等人提出一種具有交易機(jī)制的帝國(guó)主義競(jìng)爭(zhēng)算法[15]，將現(xiàn)實(shí)生活中強(qiáng)國(guó)與弱國(guó)的相互交易、共同進(jìn)步現(xiàn)象引入到原算法中，實(shí)現(xiàn)帝國(guó)主義與殖民地之間交易有用信息來相互提升的機(jī)制，有效地提高了算法的收斂速度。endprint

本文提出一種基于殖民地位置信息的自適應(yīng)帝國(guó)主義競(jìng)爭(zhēng)算法。在每次殖民地向其帝國(guó)主義者移動(dòng)過程中，根據(jù)其概率密度函數(shù)動(dòng)態(tài)地調(diào)整偏離角度的大小，平衡局部和全局的尋優(yōu)能力。其次在原算法中，帝國(guó)主義者提升自身權(quán)利僅僅通過跟殖民地互換位置來實(shí)現(xiàn)，限制了收斂速度，本文外延該步驟，根據(jù)殖民地的位置信息及時(shí)更新帝國(guó)主義者的位置，不只是殖民地成本函數(shù)低于帝國(guó)主義者時(shí)才更新帝國(guó)主義者位置，這樣可以有效地提高原算法的收斂速度。最后通過對(duì)比實(shí)驗(yàn)部分論證本文算法在收斂速度和全局尋優(yōu)能力上的優(yōu)越性。

1 帝國(guó)主義競(jìng)爭(zhēng)算法

1.1 初始化帝國(guó)

帝國(guó)主義競(jìng)爭(zhēng)算法以一個(gè)初始隨機(jī)種群開始，每個(gè)個(gè)體為一個(gè)國(guó)家，對(duì)于一個(gè)維的優(yōu)化問題，每個(gè)國(guó)家表示為一個(gè)的向量，其中每一維代表國(guó)家的一個(gè)社會(huì)屬性，如下：

且每個(gè)國(guó)家有自己的成本函數(shù)，第個(gè)帝國(guó)主義者的成本函數(shù)定義為：

在開始算法之前，先生成一個(gè)數(shù)量為個(gè)國(guó)家的局面并計(jì)算每個(gè)國(guó)家的成本函數(shù)，其中成本函數(shù)與權(quán)力成反比，選擇最有權(quán)利的個(gè)國(guó)家為帝國(guó)主義者，剩下的個(gè)國(guó)家稱為殖民地，按帝國(guó)主義者權(quán)利大小給他們分配殖民地，標(biāo)準(zhǔn)化帝國(guó)主義者的成本函數(shù)，如下：

則第個(gè)帝國(guó)主義者標(biāo)準(zhǔn)化后的權(quán)利表示為：

則初始化后給第個(gè)帝國(guó)主義者分配的殖民地?cái)?shù)為：

初始化帝國(guó)如圖1所示，其中一種顏色代表一個(gè)帝國(guó)，五角星為帝國(guó)的帝國(guó)主義者，大小代表權(quán)利的大小，一共有8個(gè)帝國(guó)，紅色五角星帝國(guó)最大，殖民地?cái)?shù)量最多。

1.2 帝國(guó)主義者同化過程

初始帝國(guó)形成后，殖民地開始向其帝國(guó)主義者移動(dòng)，該過程為帝國(guó)主義者同化其殖民地，如圖2所示，殖民地沿方向向其殖民地移動(dòng)，為某一均勻分布上的隨機(jī)變量，定義為：

式中，為殖民地與其帝國(guó)主義者之間的距離。

在同化過程中，引入偏離角度可以提高殖民地向其帝國(guó)主義者運(yùn)動(dòng)時(shí)的全局搜索能力，避免陷入局部最優(yōu)解，且平衡著算法在空間搜索上的強(qiáng)度和廣度，原算法[6]中定義為：

1.3 殖民地革命過程

與GA算法相似，ICA算法也允許殖民地突變自己的社會(huì)屬性，稱為革命過程，該過程可以有效地防止算法在早期迭代中陷入局部最優(yōu)解，且隨著迭代次數(shù)的增加，突變率逐漸降低，其中革命率為，下降因子為，突變后的殖民地由新生成的國(guó)家代替。

1.4 殖民地與其帝國(guó)主義者互換位置

同化和革命后，重新計(jì)算每個(gè)國(guó)家的成本函數(shù)，如果有任何殖民地成本函數(shù)小于其帝國(guó)主義者，則互換其位置。

1.5 計(jì)算帝國(guó)的總成本函數(shù)

帝國(guó)的總權(quán)利大小與其成本函數(shù)成反比，第個(gè)帝國(guó)總成本函數(shù)由帝國(guó)主義者和殖民地的成本函數(shù)計(jì)算，如下：

式中，為殖民地總成本函數(shù)均值對(duì)其帝國(guó)主義成本函數(shù)的影響因子，原算法中取值為0.1。

1.6 帝國(guó)主義者競(jìng)爭(zhēng)

ICA中最核心的步驟為帝國(guó)主義者的相互競(jìng)爭(zhēng)，每個(gè)帝國(guó)主義者都設(shè)法侵占其他帝國(guó)的殖民地來提升自身的權(quán)利，每次迭代中，最弱帝國(guó)中的最弱殖民地會(huì)被侵占，為了確定侵占原則，根據(jù)每個(gè)帝國(guó)主義者的權(quán)利分別計(jì)算其侵占該殖民地的概率，首先根據(jù)式（9）計(jì)算第個(gè)帝國(guó)標(biāo)準(zhǔn)化后的成本函數(shù)，再計(jì)算第個(gè)帝國(guó)主義者的侵占概率，如下：

因?yàn)樵撝趁竦刈罱K不一定被侵占概率大的帝國(guó)主義者侵占，所以將侵占概率生成一個(gè)的向量，定義為：

再生成一個(gè)與同型矩陣，定義如下：

則在此選擇向量中元素最大值的索引為侵占該殖民地的帝國(guó)主義者：

1.7 瓦解沒有殖民地的帝國(guó)主義者

隨著競(jìng)爭(zhēng)的進(jìn)行，最終最弱帝國(guó)主義者的殖民地會(huì)被侵占完，它也淪為其他帝國(guó)的殖民地，最后的狀態(tài)為只有一個(gè)帝國(guó)主義者存在，其余國(guó)家均為其殖民地。該帝國(guó)主義者的位置即為算法的最優(yōu)解，部分過程見圖3。

2 自適應(yīng)帝國(guó)主義競(jìng)爭(zhēng)算法

與其他GA算法一樣，ICA在問題搜索空間缺乏一定的全局搜索能力，可能會(huì)遠(yuǎn)離全局最優(yōu)解而陷入局部最優(yōu)解，出現(xiàn)早熟收斂現(xiàn)象。本文提出一種基于殖民地位置信息動(dòng)態(tài)平衡殖民能力和搜索能力的自適應(yīng)帝國(guó)主義競(jìng)爭(zhēng)算法，在原ICA的同化過程中，殖民地向其帝國(guó)主義者移動(dòng)的偏離角度是一個(gè)隨機(jī)變量，一旦確定將不再變化，因此陷入局部最優(yōu)解時(shí)逃脫不出來，這是造成早熟收斂的主要原因。為了解決該問題，定義一個(gè)自適應(yīng)的偏離角度，在同化過程中動(dòng)態(tài)地調(diào)整自己的大小，并根據(jù)殖民地位置信息及時(shí)更新帝國(guó)主義者的位置加快收斂速度。

2.1 自適應(yīng)偏離角度

本文中提取當(dāng)前殖民地位置的統(tǒng)計(jì)信息來自適應(yīng)調(diào)整，具體做法如下：

1） 建立當(dāng)前殖民地位置信息的高斯概率模型，并由每個(gè)國(guó)家的邊緣概率分布乘積得到聯(lián)合概率分布，如下：

2） 在每次迭代中，由式（14）計(jì)算國(guó)家的概率密度，計(jì)算值如下：

2.2 更新帝國(guó)主義者位置

在原ICA算法中，只有當(dāng)殖民地成本函數(shù)小于其帝國(guó)主義者時(shí)，通過互換位置來提高帝國(guó)主義者的權(quán)利，然而現(xiàn)實(shí)生活中，雖然弱國(guó)的綜合實(shí)力小，但不一定任何方面都比強(qiáng)國(guó)弱，同理，當(dāng)弱國(guó)的綜合實(shí)力大于強(qiáng)國(guó)后，也不一定任何方面都比強(qiáng)國(guó)強(qiáng)?；诖?，對(duì)于一個(gè)維的優(yōu)化問題，應(yīng)該考慮到每一維，當(dāng)殖民地成本函數(shù)高于帝國(guó)主義者時(shí)，應(yīng)該檢測(cè)是否有哪一維優(yōu)于帝國(guó)主義者，同理，當(dāng)殖民地恒本函數(shù)低于帝國(guó)主義者時(shí)，應(yīng)該保留優(yōu)于殖民地的信息，而不是完全被殖民地代替。所以根據(jù)殖民地的當(dāng)前位置信息及時(shí)更新帝國(guó)主義者可以加快收斂速度，外延了原算法中的互換位置這一步。根據(jù)上述原理，為了將更新殖民地位置融入原算法中，偽代碼如下：

1） Input empires；

2） for i = 1 ： numel（empires）

3） for j = 1 ： numel（empires（i）.colonies）endprint

4） for k = 1 ：

5） if cost（empires（i）.imperialist） <

cost（empires（i）.colonies（j））

6） if cost（empires（i）.colonies（j）（k）） <

cost（empires（i）.imperialist（k））

7） empires（i）.imperialist（k） =

empires（i）.colonies（j）（k）；

8） end if

9） else

10） if cost（empires（i）.imperialist（k）） <

cost（empires（i）.colonies（j）（k））

11） empires（i）.colonies（j）（k） =

empires（i）.imperialist（k）；

12） end if

13） end

14） end

15） end

16） end

2.3 自適應(yīng)帝國(guó)主義競(jìng)爭(zhēng)算法流程

本文算法流程圖如圖4所示。

3 分析對(duì)比實(shí)驗(yàn)結(jié)果

為了驗(yàn)證本文算法在收斂速度和性能的優(yōu)越性，采用表1給出4種常用的基準(zhǔn)函數(shù)來測(cè)試，圖5為4種基準(zhǔn)函數(shù)的三維圖（其中優(yōu)化問題的維數(shù)為2），可知，每個(gè)基準(zhǔn)函數(shù)都有局部最小值和全局最小值。在問題優(yōu)化方面，采用中等大小為30的維度來進(jìn)行實(shí)驗(yàn)，且每次實(shí)驗(yàn)重復(fù)進(jìn)行10次取基準(zhǔn)函數(shù)值的平均值，結(jié)果如表2所示，算法的停止條件設(shè)定為達(dá)到最大迭代次數(shù)，本文取1 000次。ICA和本文算法參數(shù)設(shè)置為，，，，PSO算法中，，，種群數(shù)為100，突變和交叉率分別為0.3和0.95。

圖6為三種算法求4種基準(zhǔn)函數(shù)的全局最小值，其中行坐標(biāo)表示迭代次數(shù)，縱坐標(biāo)為成本函數(shù)值。

圖6a）中，三種算法得到的全局最小值相差不大，但本文算法在迭代340次左右達(dá)到全局最小值，收斂速度明顯優(yōu)于另外兩種；圖6b）中，傳統(tǒng)ICA與PSO算法相繼陷入局部最小值，雖然傳統(tǒng)ICA算法有較強(qiáng)的局部搜索能力，取到優(yōu)于PSO算法的最優(yōu)解，但本文通過設(shè)置自適應(yīng)偏離角度的ICA算法在跳出局部最優(yōu)解方面明顯優(yōu)于另外兩種；圖6c）中，不僅體現(xiàn)出ICA算法在全局最優(yōu)解方面優(yōu)于PSO算法，更能看出本文算法通過及時(shí)更新帝國(guó)主義者位置在收斂速度方面獲得的優(yōu)勢(shì)；圖6d）中，傳統(tǒng)ICA和PSO算法幾乎陷進(jìn)了同一個(gè)局部最小值，但本文算法沒有陷入該局部最小值且在迭代次數(shù)為300和600左右時(shí)分別跳出三個(gè)局部最小值達(dá)到全局最小值。

4 結(jié) 語

本文提出一種基于殖民地位置信息的自適應(yīng)帝國(guó)主義競(jìng)爭(zhēng)算法，首先根據(jù)殖民地的概率密度函數(shù)動(dòng)態(tài)地調(diào)整殖民地向其帝國(guó)主義者運(yùn)動(dòng)的偏離角度，有效地提高了全局搜索能力，避免了算法陷入局部最小值，其次根據(jù)殖民地的當(dāng)前位置信息及時(shí)更新帝國(guó)主義者位置，可以加快收斂速度。實(shí)驗(yàn)結(jié)果表明，本文算法切實(shí)可行，但殖民地位置的概率密度函數(shù)選取對(duì)算法性能的影響將是今后探索的方向。

參考文獻(xiàn)

[1] EBERHART R， KENNEDY J. A new optimizer using particle swarm theory [C]// International Symposium on Micro Machine and Human Science. Nagoya： IEEE， 2002： 39?43.

[2] DORIGO M， MANIEZZO V， COLORNI A. Positive feedback as a search strategy [J/OL]. [2017?07?02]. https：//wenku.baidu.com/view/3a6125e881c758f5f61f67b3.html.

[3] MOHAN B C， BASKARAN R. A survey： ant colony optimization based recent research and implementation on several engineering domain [J]. Expert systems with applications， 2012， 39（4）： 4618?4627.

[4] MAHDAVI M， FESANGHARY M， DAMANGIR E. An improved harmony search algorithm for solving optimization problems [J]. Applied mathematics & computation， 2007， 188（2）： 1567?1579.

[5] VADLAMANI S， HOSSEINI S. A novel heuristic approach for solving aircraft landing problem with single runway [J]. Journal of air transport management， 2014， 40： 144?148.

[6] ATASHPAZ?GARGARI E， LUCAS C. Imperialist competitive algorithm： an algorithm for optimization inspired by imperialistic competitive [C]// IEEE Congress on Evolutionary Computation， 2008， 21： 4661?4667.endprint

[7] CHEN C H， CHEN W H. United?based imperialist competitive algorithm for compensatory neural fuzzy systems [J]. IEEE transactions on systems man & cybernetics systems， 2016， 9（46）： 1?10.

[8] TALATAHARI S， RAHBARI N M. Enriched imperialist competitive algorithm for system identification of magneto?rheological dampers [J]. Mechanical systems & signal processing， 2015， 62： 506?516.

[9] MAHMOODABADI Z， ABADEH M S. CADICA： Diagnosis of coronary artery disease using the imperialist competitive algorithm [J]. Journal of computing science & engineering， 2014， 8（2）： 87?93.

[10] BAHRAMI H， FAEZ K， ABDECHIRI M. Imperialist competitive algorithm using chaos theory for optimization （CICA） [C]// Proceedings of International Conference on Computer Modelling and Simulation. Washington： IEEE， 2010： 98?103.

[11] ZHANG Y， WANG Y， PENG C. Improved imperialist competitive algorithm for constrained optimization [C]// Proceedings of International Forum on Computer Science?Technology and Applications. Washington： IEEE， 2009， 1： 204?207.

[12] LIN J L， CHO C W， CHUAN H C. Imperialist competitive algorithms with perturbed moves for global optimization [J]. Applied mechanics & materials， 2013， 284/287： 3135?3139.

[13] KHALED A A， HOSSEINI S. Fuzzy adaptive imperialist competitive algorithm for global optimization [J]. Neural computing & applications， 2015， 26（4）： 813?825.

[14] ARISH S， AMIRI A， NOORI K. FICA： fuzzy imperialist competitive algorithm [J]. Journal of Zhejiang University， 2014， 15（5）： 363?371.

[15] WANG S， AORIGELE， LUO J， et al. Imperialist competitive algorithm with trading mechanism for optimization [C]// Proceedings of International Conference on Computational Intelligence， Networked Systems and Their Applications. [S.l.]： Springer Berlin Heidelberg， 2014， 462： 87?98.endprint