帝國(guó)競(jìng)爭(zhēng)算法(imperialist competitive algorithm, ICA )詳解+Java代碼

2020-07-11 15:55

程序猿聲

關(guān)注

算法解析

其實(shí)和群體進(jìn)化類(lèi)算法還是非常像的，只不過(guò)把個(gè)體的概念換成了國(guó)家而已。我們一步步來(lái)看。

1．初始化

ICA的個(gè)體是國(guó)家，相當(dāng)于遺傳算法中的染色體，對(duì)于一個(gè)N維的優(yōu)化問(wèn)題，國(guó)家可以表示成如下形式：

國(guó)家的勢(shì)力大小通過(guò)代價(jià)函數(shù)來(lái)衡量：

國(guó)家的勢(shì)力和代價(jià)函數(shù)值成反比，即代價(jià)函數(shù)值越小，國(guó)家勢(shì)力越大。初始帝國(guó)的產(chǎn)生分為以下幾個(gè)步驟：

STEP 1：首先，隨機(jī)產(chǎn)生個(gè)國(guó)家，從中選出勢(shì)力較大的前個(gè)國(guó)家作為帝國(guó)主義國(guó)家，剩下的個(gè)國(guó)家作為殖民地。

STEP 2：其次，根據(jù)帝國(guó)主義國(guó)家的勢(shì)力大小劃分殖民地。每個(gè)帝國(guó)的殖民地個(gè)數(shù)按照式（1）～（3）計(jì)算：

其中，是第個(gè)帝國(guó)主義國(guó)家的代價(jià)函數(shù)值。是它的標(biāo)準(zhǔn)化代價(jià)。是它的標(biāo)準(zhǔn)化勢(shì)力大小。是第個(gè)帝國(guó)的初始殖民地個(gè)數(shù)。最后，對(duì)于每個(gè)帝國(guó)主義國(guó)家，從個(gè)殖民地中隨機(jī)選擇相應(yīng)的個(gè)數(shù)分配給它，最終形成初始的個(gè)帝國(guó)。［2］

不過(guò)這里解釋一下，一個(gè)國(guó)家其實(shí)可以看成一個(gè)解的表示，與遺傳中染色體類(lèi)似。國(guó)家的勢(shì)力通常由該國(guó)家所表示的解的好壞決定的。一般可以采用隨機(jī)或者貪心的方式生成初始國(guó)家，然后計(jì)算目標(biāo)函數(shù)，計(jì)算勢(shì)力，再劃分帝國(guó)主義國(guó)家和殖民地國(guó)即可。

2．殖民地同化

帝國(guó)主義國(guó)家為了更好地控制其殖民地國(guó)家，將自己的思想模式及文化風(fēng)俗推廣到殖民地國(guó)家的過(guò)程，稱為同化。ICA中通過(guò)所有殖民地向其所屬帝國(guó)主義國(guó)家移動(dòng)來(lái)模擬同化過(guò)程。［2］當(dāng)然這個(gè)移動(dòng)可以看出解在解空間上的移動(dòng)，與鄰域搜索那個(gè)移動(dòng)也有點(diǎn)類(lèi)似，本質(zhì)還是解的變換。

一個(gè)同化的例子如下，其實(shí)跟GA中的交叉很相似：

3．殖民地革命

殖民地革命是對(duì)殖民地進(jìn)行一定的移動(dòng)，希望其能更靠近最優(yōu)解的位置。但通常而言，對(duì)于一個(gè)社會(huì)來(lái)講，不是說(shuō)有的革命都是成功的有益的。革命也可能導(dǎo)致資源內(nèi)耗，無(wú)法進(jìn)行有效的社會(huì)變革從而降低殖民地的力量（參照蘇聯(lián)）。一個(gè)殖民地革命的例子如下（和GA中的變異很像對(duì)不對(duì)）：