帝國競爭算法(imperialist competitive algorithm, ICA )詳解+Java代碼
代碼黑科技的分享區(qū)
這段時間用過這個算法做過相關(guān)的工作，今天就介紹一下吧。雖然感覺效果嘛，勉勉強強啦。不過每種算法肯定有其適用的地方，用到了就Mark一下方便后人吧~
帝國競爭算法（imperialist competitive algorithm，ICA）是Atashpaz-Gargari和Lucas于2007年提出的一種基于帝國主義殖民競爭機制的進化算法，屬于社會啟發(fā)的隨機優(yōu)化搜索方法。目前，ICA已被成功應(yīng)用于多種優(yōu)化問題中，如調(diào)度問題、分類問題和機械設(shè)計問題等。[2]
帝國主義競爭算法，借鑒了人類歷史上政治社會殖民階段帝國主義國家之間的競爭、占領(lǐng)、吞并殖民殖民地國家從而成為帝國國家的演化，是一種全局性的優(yōu)化算法。該算法把所有初始化的個體都稱作國家，按照國家勢力分成帝國主義國家及殖民地兩種，前者優(yōu)勢大于后者。[1]
其實，從另一個角度來看，ICA可以被認為是遺傳算法(GA)的社會對應(yīng)物。ICA是基于人類社會進化的過程，而GA是基于物種的生物進化過程。二者其實有異曲同工之妙。
不過話說回來，大多數(shù)群體仿生類算法都有異曲同工之妙~
流程圖學(xué)習(xí)算法框架，當(dāng)然先搞懂流程圖啦。算法的流程圖我就不重新畫了，找了一篇文獻上的直接挪過來：[1]
整個流程大體如上，可能大家在其他地方看到的有些專有名詞可能對不上，但描述的都是一個東西，本質(zhì)是一樣的。我們下面來一步步分析這個過程吧。
算法解析其實和群體進化類算法還是非常像的，只不過把個體的概念換成了國家而已。我們一步步來看。
1. 初始化
ICA的個體是國家，相當(dāng)于遺傳算法中的染色體，對于一個N維的優(yōu)化問題，國家可以表示成如下形式：
國家的勢力大小通過代價函數(shù)來衡量：
國家的勢力和代價函數(shù)值成反比，即代價函數(shù)值越小，國家勢力越大。初始帝國的產(chǎn)生分為以下幾個步驟：
STEP 1：首先，隨機產(chǎn)生個國家，從中選出勢力較大的前個國家作為帝國主義國家，剩下的個國家作為殖民地。
STEP 2：其次，根據(jù)帝國主義國家的勢力大小劃分殖民地。每個帝國的殖民地個數(shù)按照式（1）~（3）計算：
其中，是第個帝國主義國家的代價函數(shù)值。是它的標(biāo)準(zhǔn)化代價。是它的標(biāo)準(zhǔn)化勢力大小。 是第個帝國的初始殖民地個數(shù)。最后，對于每個帝國主義國家，從個殖民地中隨機選擇相應(yīng)的個數(shù)分配給它，最終形成初始的個帝國。[2]
不過這里解釋一下，一個國家其實可以看成一個解的表示，與遺傳中染色體類似。國家的勢力通常由該國家所表示的解的好壞決定的。一般可以采用隨機或者貪心的方式生成初始國家，然后計算目標(biāo)函數(shù)，計算勢力，再劃分帝國主義國家和殖民地國即可。
2. 殖民地同化
帝國主義國家為了更好地控制其殖民地國家，將自己的思想模式及文化風(fēng)俗推廣到殖民地國家的過程，稱為同化。ICA中通過所有殖民地向其所屬帝國主義國家移動來模擬同化過程。[2] 當(dāng)然這個移動可以看出解在解空間上的移動，與鄰域搜索那個移動也有點類似，本質(zhì)還是解的變換。
一個同化的例子如下，其實跟GA中的交叉很相似：
3. 殖民地革命
殖民地革命是對殖民地進行一定的移動，希望其能更靠近最優(yōu)解的位置。但通常而言，對于一個社會來講，不是說有的革命都是成功的有益的。革命也可能導(dǎo)致資源內(nèi)耗，無法進行有效的社會變革從而降低殖民地的力量（參照蘇聯(lián)）。一個殖民地革命的例子如下（和GA中的變異很像對不對）：
當(dāng)一個殖民地國家通過同化和革命移動到一個新的位置后，殖民地的代價函數(shù)值可能比帝國主義國家小，也就是說殖民地的勢力更大。此時，交換殖民地和帝國主義國家的位置，即殖民地成為該帝國的帝國主義國家，而原來的帝國主義國家則淪為殖民地。[2]
完成上述步驟后，需要對帝國的權(quán)力進行重新計算。常見的計算方式是對帝國的權(quán)力和該帝國下的所有殖民地國家的權(quán)力進行加權(quán)。當(dāng)然你直接加總也應(yīng)該是可以的，具體還是取決于算法如何進行設(shè)計。
4. 帝國競爭
帝國競爭機制模擬的是現(xiàn)實社會中勢力較強的帝國占有并控制勢力較弱帝國的殖民地的過程。首先，需要計算帝國的總代價函數(shù)值，即勢力大小。帝國主義國家對整個帝國的勢力影響較大，而殖民地國家的影響非常小，因此ICA采用如下公式計算一個帝國的總代價：
其中， 是第個帝國的帝國主義國家；是第個帝國的總代價；，的大小決定了殖民地國家對整個帝國勢力的影響程度。選擇最弱的帝國中最弱的殖民地作為帝國競爭的對象，勢力越大的帝國越有可能占有該殖民地。[2]
一般的做法是將勢力最弱的那個帝國中最弱的殖民地重新分配給勢力最強的帝國。
5. 帝國消亡
帝國之間的競爭，使勢力大的帝國通過占有其他帝國的殖民地變得越來越強大，而勢力弱的帝國殖民地個數(shù)不斷減少，當(dāng)一個帝國丟失所有的殖民地時，帝國覆滅。隨著帝國的滅亡，最終剩下一個帝國，此時算法終止。[2]
動態(tài)演示
最后可以給大家看看該算法的一個動態(tài)演示過程：
大家也可以用電腦打開
https://tomsiemek.github.io/imperialistic-competitive-algorithm-visualisation/
進行訪問，可以看到該算法的詳細演示過程。可以看到，隨著迭代的進行，大國不斷吞并效果，最終剩下的帝國數(shù)量越來越少。正所謂分久必合嘛。最終剩下的幾個帝國就代表著算法搜索到的比較優(yōu)秀的解了。
代碼代碼從GitHub上找的，自己修改了一些地方確保能夠運行，原地址：
https://github.com/robinroche/jica
欲下載本文相關(guān)的完整代碼及算例，在公眾號后臺回復(fù)【ICAJAVA】不包括【】即可。
main函數(shù)寫在了TestICA.java里面。其中代碼是求解數(shù)學(xué)優(yōu)化問題的，其適應(yīng)度函數(shù)計算可以找到FitnessFunction.java中的getFitnessValue進行修改，比如Sphere function、Rastrigin function和Ackley function等。其他的大家就自己慢慢研究啦。
/**
* Returns the fitness of one country
* @param individual the solution to evaluate
* @return the fitness
*/
public double getFitnessValue(double[] individual)
{
double fitness = 0;
// Sphere function
for(int i=0; i
{
fitness = fitness + Math.pow(individual[i],
2);
}
// // Rastrigin function
// for(int i=0; i
// {
// fitness = fitness + (Math.pow(individual[i],2)-10*Math.cos(2*Math.PI*individual[i]));
// }
// fitness = 10*dimension + fitness;
// // Rosenbrock function
// for(int i=0; i
// {
// fitness = fitness + 100*Math.pow((Math.pow(individual[i],2)-individual[i+1]),2) + Math.pow((individual[i]-1),2);
// }
// // Ackley function
// double a = 20;
// double b = 0.2;
// double c = 2*Math.PI;
// double s1 = 0;
// double s2 = 0;
// for(int i=0; i
// {
// s1 = s1 + Math.pow(individual[i],2);
// s2 = s2 + Math.cos(c*individual[i]);
// }
// fitness = -a * Math.exp( -b * Math.sqrt(1/individual.length*s1)) - Math.exp(1/individual.length*s2) + a + Math.exp(1);
nbEvals++;
return fitness;
}
[1] 基于改進帝國主義競爭算法的城市軌道交通乘客路徑選擇方法技術(shù)
[2] 郭婉青，葉東毅.帝國競爭算法的進化優(yōu)化[J].計算機科學(xué)與探索，2014，8（4）：473-482
推薦閱讀：
干貨 | 想學(xué)習(xí)優(yōu)化算法，不知從何學(xué)起？
干貨 | 運籌學(xué)從何學(xué)起？如何快速入門運籌學(xué)算法？
干貨 | 學(xué)習(xí)算法，你需要掌握這些編程基礎(chǔ)（包含JAVA和C++）
干貨 | 算法學(xué)習(xí)必備訣竅：算法可視化解密
干貨 | 模擬退火、禁忌搜索、迭代局部搜索求解TSP問題Python代碼分享記得點個在看支持下哦～
