ACO for Continuous Domains in MATLAB

Ant algorithms were originally designed for discrete and combinatorial optimization problems. Several extensions of Ant Colony Optimization (ACO) handle problems defined in continuous domains. One of the most useful is ACOR, Ant Colony Optimization for Continuous Domains, proposed by Socha and Dorigo in 2008 (paper (opens in a new tab)).

ACOR is an Estimation of Distribution Algorithm (EDA). It looks for a probabilistic model that generates promising solutions with higher likelihood. At every iteration, the model is updated so that it generates even more promising solutions.

How ACOR works

In discrete ACO, the ants choose among a finite set of options, guided by a pheromone matrix. In a continuous space there is no finite set of options, so ACOR replaces the pheromone matrix with a solution archive: a sorted list of the $k$ best solutions found so far. The archive defines a mixture of Gaussian functions, one centered at each stored solution, and new solutions are sampled from this mixture.

Weights of the archive members

The solutions in the archive are sorted from best ($l = 1$) to worst ($l = k$). Solution $l$ gets the weight

and it is chosen with probability $p_l = w_l / \sum_{r=1}^{k} w_r$. The parameter $q$ sets the selection pressure. A small $q$ gives most of the weight to the best solutions, and a large $q$ spreads the weight more evenly.

Sampling a new solution

For each variable $i$, a Gaussian kernel $l$ is chosen with the probabilities $p_l$. Its mean is the value of that variable in archive solution $l$, $s_l^i$, and its standard deviation is the average distance from $s_l$ to the other archive members, scaled by $\zeta$:

The new value is then drawn from $\mathcal{N}(s_l^i, (\sigma_l^i)^2)$. When the archive members are spread out, the samples are spread out too. As the archive converges to a region, $\sigma$ shrinks and the search becomes more local.

Updating the archive

After the new samples are evaluated, they are added to the archive. The archive is sorted by cost again, and only the best $k$ solutions are kept. This step plays the role of the pheromone update in discrete ACO.

What is in the download

This post shares an open-source MATLAB implementation of ACOR. The code is structured, so if you know MATLAB, you will find it easy to use in your research projects.

The ACOR folder holds four files:

• acor.m: the algorithm, with the problem definition, the parameters, the main loop and the results.
• Sphere.m: the sample cost function, $f(x) = \sum_{i=1}^{n} x_i^2$.
• RouletteWheelSelection.m: chooses a Gaussian kernel by its probability.
• main.m: a one line entry point that runs acor.m.

To run the code, open the ACOR folder in MATLAB and run main.m. The program prints the best cost in every iteration and plots the best cost against the iteration on a logarithmic scale. New samples outside the bounds are clipped to VarMin and VarMax. The script creates the first archive with unifrnd, a function of the Statistics and Machine Learning Toolbox, so it probably needs that toolbox.

Parameters in the code

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 at the top of acor.m.

Check the result

The supplied Sphere problem has a known minimum of 0 at the origin. Check the returned coordinates and cost, then repeat runs to assess variability. Keep the archive size above 1 because the deviation formula divides by $k-1$. Very similar archive members produce small sampling deviations, so early concentration can reduce exploration even while the best cost appears stable.

Related posts

• The YPEA toolbox, Yarpiz Evolutionary Algorithms, also includes ACOR with a common problem definition.

Mostapha Kalami Heris, ACO for Continuous Domains in MATLAB (YPEA104), Yarpiz, 2015. https://yarpiz.com/acor-ypea104

@misc{yarpiz-ypea104,
  author = {{Mostapha Kalami Heris}},
  title = {{ACO for Continuous Domains in MATLAB}},
  howpublished = {Yarpiz},
  year = {2015},
  note = {Code YPEA104},
  url = {https://yarpiz.com/acor-ypea104}
}