劉阿建+梁鳳梅

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

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

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

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

1 帝國主義競爭算法

1.1 初始化帝國

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

且每個國家有自己的成本函數，第個帝國主義者的成本函數定義為：

在開始算法之前，先生成一個數量為個國家的局面并計算每個國家的成本函數，其中成本函數與權力成反比，選擇最有權利的個國家為帝國主義者，剩下的個國家稱為殖民地，按帝國主義者權利大小給他們分配殖民地，標準化帝國主義者的成本函數，如下：

則第個帝國主義者標準化后的權利表示為：

則初始化后給第個帝國主義者分配的殖民地數為：

初始化帝國如圖1所示，其中一種顏色代表一個帝國，五角星為帝國的帝國主義者，大小代表權利的大小，一共有8個帝國，紅色五角星帝國最大，殖民地數量最多。

1.2 帝國主義者同化過程

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

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

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

1.3 殖民地革命過程

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

1.4 殖民地與其帝國主義者互換位置

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

1.5 計算帝國的總成本函數

帝國的總權利大小與其成本函數成反比，第個帝國總成本函數由帝國主義者和殖民地的成本函數計算，如下：

式中，為殖民地總成本函數均值對其帝國主義成本函數的影響因子，原算法中取值為0.1。

1.6 帝國主義者競爭

ICA中最核心的步驟為帝國主義者的相互競爭，每個帝國主義者都設法侵占其他帝國的殖民地來提升自身的權利，每次迭代中，最弱帝國中的最弱殖民地會被侵占，為了確定侵占原則，根據每個帝國主義者的權利分別計算其侵占該殖民地的概率，首先根據式（9）計算第個帝國標準化后的成本函數，再計算第個帝國主義者的侵占概率，如下：

因為該殖民地最終不一定被侵占概率大的帝國主義者侵占，所以將侵占概率生成一個的向量，定義為：

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

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

1.7 瓦解沒有殖民地的帝國主義者

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

2 自適應帝國主義競爭算法

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

2.1 自適應偏離角度

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

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

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

2.2 更新帝國主義者位置

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

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 自適應帝國主義競爭算法流程

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

3 分析對比實驗結果

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

圖6為三種算法求4種基準函數的全局最小值，其中行坐標表示迭代次數，縱坐標為成本函數值。

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

4 結 語

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

參考文獻

[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