Ant Colony Optimization in MATLAB

Ant Colony Optimization (ACO) is a family of probabilistic metaheuristics inspired by the social behavior of ants. ACO is also a Swarm Intelligence method, because the algorithms simulate the behavior of ants.

The first ACO algorithm, called Ant System, was proposed by Marco Dorigo in his PhD thesis in 1992. Researchers have since proposed many versions, such as Max-Min Ant System, Ant Colony System, and ACOR, the ACO for continuous domains. To read more about ant algorithms, see the Wikipedia article (opens in a new tab).

How ACO works

Real ants leave a chemical trail, called pheromone, on the paths they use. Other ants tend to follow paths with more pheromone, and short paths collect pheromone faster because ants travel them more often. ACO uses the same idea to build good solutions to combinatorial problems.

Each artificial ant builds a complete solution step by step. In the Traveling Salesman Problem, for example, an ant at city $i$ chooses the next city $j$ among the cities it has not visited yet. The choice is random, with the probability

Here $\tau_{ij}$ is the pheromone on the edge from $i$ to $j$, $\eta_{ij}$ is the heuristic information (in the TSP, $\eta_{ij} = 1/d_{ij}$, the inverse of the distance), and $N_i$ is the set of cities the ant can still visit. The exponents $\alpha$ and $\beta$ set how much the ant trusts the pheromone and the heuristic.

When all ants have built their solutions, each ant $k$ adds pheromone to the edges it used. The amount is $Q/L_k$, where $L_k$ is the cost of its solution, so better solutions leave more pheromone. Then all pheromone values evaporate a little:

The evaporation rate $\rho$ lets the colony forget poor choices made early in the search. Over many iterations, the pheromone concentrates on the parts of good solutions, and the ants build better solutions more often.

What this post shares

This post shares a complete open-source MATLAB implementation of ACO. It has three projects, each solving one problem:

• Traveling Salesman Problem (TSP)
• Quadratic Assignment Problem (QAP)
• Binary Knapsack Problem

The algorithm is implemented in a structured way, so if you know MATLAB, you can easily use the code in your research projects.

The three projects

Each project is in its own folder, with main.m (the entry point), aco.m (the algorithm), CreateModel.m (the sample problem) and RouletteWheelSelection.m (the random choice by probability).

• 01 ACO for TSP. The sample model has 20 cities with fixed coordinates. The cost is the length of the closed tour (TourLength.m), and the heuristic is the inverse distance. PlotSolution.m draws the best tour in every iteration.
• 02 ACO for QAP. Seven facilities are assigned to 20 possible locations. The cost (MyCost.m) is the sum of the weights between pairs of facilities times the distances between their locations. Here the ants use only the pheromone, with no heuristic term.
• 03 ACO for Binary Knapsack Problem. There are 20 items with values and weights, and the capacity is 500. Each ant decides for every item whether to take it (1) or leave it (0). The cost in MyCost.m is the total value of the items left out, and a solution over the weight limit gets a penalty. The output marks a feasible best solution with *.

To run a project, open its folder in MATLAB and run main.m. The program prints the best cost in every iteration and plots the best cost against the iteration at the end. To solve your own problem, change CreateModel.m and the cost function.

Parameters in the code

The parameters are set at the top of each aco.m. The values for the TSP project are:

The other two projects use their own values. The QAP project uses MaxIt = 500, nAnt = 50, tau0 = 10, alpha = 0.3 and rho = 0.1. The knapsack project uses MaxIt = 300, nAnt = 40, tau0 = 0.1, alpha = 1, beta = 0.02 and rho = 0.1.

Check the result

Use the project-specific objective when interpreting the output. A TSP tour must contain each city once and include the return edge. A QAP solution must assign each facility to an allowed location without duplicates. For knapsack, check the total weight against capacity as well as the penalized cost. A lower penalty score does not by itself establish feasibility or prove that the global optimum has been found.

Applications

ACO was designed for problems where a solution is built from discrete choices, such as routes, orders and assignments. Typical uses are vehicle routing, scheduling, assignment problems and network routing. The Quadratic Assignment Problem post describes the QAP in more detail.

Mostapha Kalami Heris, Ant Colony Optimization in MATLAB (YPEA103), Yarpiz, 2015. https://yarpiz.com/ant-colony-optimization-ypea103

@misc{yarpiz-ypea103,
  author = {{Mostapha Kalami Heris}},
  title = {{Ant Colony Optimization in MATLAB}},
  howpublished = {Yarpiz},
  year = {2015},
  note = {Code YPEA103},
  url = {https://yarpiz.com/ant-colony-optimization-ypea103}
}