Imperialist Competitive Algorithm (ICA) in MATLAB

The Imperialist Competitive Algorithm (ICA), also known as the Colonial Competitive Algorithm (CCA), is a sociopolitical metaheuristic. It is inspired by the historical colonization (opens in a new tab) process and by competition among imperialists to capture more colonies.

The countries (solutions) in ICA are partitioned into several empires. Each empire contains one imperialist and several weaker countries, called colonies. The algorithm was proposed by Esmaeil Atashpaz Gargari and Caro Lucas in 2007, in this paper (opens in a new tab).

How ICA works

At the start, the best countries become imperialists, and the other countries are shared among them as colonies. A stronger imperialist (lower cost) receives more colonies. Then each iteration has four steps.

Assimilation

Each colony moves toward the imperialist of its empire. In the code of this post, the move is

where $r$ is a vector of uniform random numbers in $[0, 1]$ and $\beta$ is the assimilation coefficient. With $\beta > 1$, a colony can pass the imperialist and land on its other side, so the area around the imperialist is searched from both directions. The original paper also adds a random deviation angle to the direction of the move. The code does not use this angle.

Revolution

Revolution is the mutation step of ICA. Some colonies jump to new positions at random, which helps the empires escape from local minima. In the code, a colony takes part with probability pRevolution. A share mu of its variables, chosen at random, receive Gaussian noise. The code also tries the same change on each imperialist and keeps it only if it lowers the cost.

Competition

ICA has two competition mechanisms:

• Intra-empire competition: competition among the members of an empire. The strongest country becomes the imperialist (leader) of the empire.
• Inter-empire competition: competition among empires, based on the overall objective value of each empire.

The overall objective of an empire is a linear combination of the imperialist’s objective value and the mean objective value of its colonies:

Here $\zeta$ is a small positive number, so the imperialist has the largest effect on the total cost. After all empires are evaluated, the weakest empire is identified. The other empires then compete to capture the weakest colony of the weakest empire. An empire with a lower total cost has a higher chance to win it.

Elimination

An empire that loses all of its colonies is eliminated. In the code, its imperialist becomes a colony of another empire. Over time, the weak empires disappear, and the countries gather around the best solutions.

For more information, see the Wikipedia article on the Imperialist Competitive Algorithm (opens in a new tab).

MATLAB implementation

This post shares a structured, open-source implementation of ICA in MATLAB. If you know MATLAB, you should find the code easy to use in your research and projects.

What is in the download

The Imperialist Competitive Algorithm folder holds these files:

• ica.m: the main script, with the problem definition, the parameters, the main loop and the results.
• CreateInitialEmpires.m: creates the countries and forms the first empires.
• AssimilateColonies.m, DoRevolution.m, IntraEmpireCompetition.m, UpdateTotalCost.m and InterEmpireCompetition.m: one function for each step of the main loop.
• RouletteWheelSelection.m: picks an empire in proportion to its selection probability.
• Sphere.m: the sample cost function, $f(x) = \sum_{i=1}^{n} x_i^2$.
• main.m: a one line entry point that runs ica.m.

To run the code, open the Imperialist Competitive Algorithm folder in MATLAB and run main.m. The program prints the best cost of every iteration and then plots the best cost against the iteration number on a logarithmic scale.

The code uses unifrnd and randsample, two functions of the Statistics and Machine Learning Toolbox, so it probably needs that toolbox.

Parameters in the code

The selection pressure alpha sets how much a lower cost raises the chance of an empire: in the code, the probability is proportional to $e^{-\alpha\, c / c_{\max}}$, both when the first colonies are shared out and in the inter-empire competition. The Gaussian noise of revolution has a standard deviation of $0.1\,(\text{VarMax} - \text{VarMin})$. The script shares its settings with the step functions through two global structures, ProblemSettings and ICASettings.

To solve your own problem, write a cost function that takes a row vector and returns a number, and set CostFunction, nVar, VarMin and VarMax in the problem definition section of ica.m.

Check the result

For the Sphere example, inspect the best coordinates and their cost together. Keep the number of initial empires smaller than the number of countries so that colonies are available. The selection probabilities use a maximum-cost scale, so review zero or negative objectives before replacing the sample cost. Since the step functions use global settings, check that a fresh run uses the intended problem and parameters.

Related posts

• YPEA is a MATLAB toolbox that includes ICA and 14 other algorithms that share one problem definition.
• Invasive Weed Optimization in MATLAB is another metaheuristic proposed by Caro Lucas and a coauthor.

Mostapha Kalami Heris, Imperialist Competitive Algorithm (ICA) in MATLAB (YPEA118), Yarpiz, 2015. https://yarpiz.com/imperialist-competitive-algorithm-ypea118

@misc{yarpiz-ypea118,
  author = {{Mostapha Kalami Heris}},
  title = {{Imperialist Competitive Algorithm (ICA) in MATLAB}},
  howpublished = {Yarpiz},
  year = {2015},
  note = {Code YPEA118},
  url = {https://yarpiz.com/imperialist-competitive-algorithm-ypea118}
}