# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Solve a combinatorial optimization problem using an Ant Colony Optimization (ACO) algorithm

Contributed by:
Lars Ulke-Winter

ResourceFunction["AntColonyOptimization"][ returns the minimum found result for the function | |

ResourceFunction["AntColonyOptimization"][ returns the intermediate optimization step results and optimization parameters as a summary Association. |

ResourceFunction["AntColonyOptimization"] is a global stochastic optimization method for the solution of combinatorial arrangement problems. It imitates the swarm communication behaviour of ants during foraging (Stigmergic Optimization).

The optimization is based on the exchange of information between individuals (randomly generated solutions) using a virtual pheromone trail for the information exchange.

ResourceFunction["AntColonyOptimization"] finds a solution of vector *x*, where the *i*^{th} element of *x* is chosen from the values of the *i*^{th} list in *array*, such that *fitness*[*x*] has the smallest positive value found.

The input *array* takes a List of lists with available values at each row. The lists need not have uniform length.

The *fitness* function to be minimized must return a positive scalar value. Therefore, the standard method of negating the objective function to convert a minimization problem into a maximization problem doesn’t work in this ACO implementation.

Limitation: This implementation does not consider dependencies of design variables among each other. The assignment of the design variables must be independent of the settings of the others. The definition of the search space is therefore possible using only a given *array* and does therefore not require a given tree or graph structure of the search space. Optimization problems such as the traveling salesman cannot be encoded in this way.

Optimization parameters given as options include:

"PopulationSize" | 500 | number of ants |

"MaxIterations" | 200 | maximum iterations |

"FinishAtPheromoneThreshold" | 0.95 | stop criterion |

"PheromoneFunction" | (1/#)& | pheromone concentration to be deposited depending on fitness |

"WeatheringFactor" | 0.05 | fraction of decreasing pheromone concentration (selection probability) per iteration |

"ProbabilitySelectBestPath" | 0.02 | proportion of generated solution alternatives that currently prefer the best solution |

The computation will stop if the selection probability for a variable state exceeds the value of "FinishAtPheromoneThreshold".

"PheromoneFunction" is a function whose result marks the selection probability for the next step. By default, larger *fitness* results receive lower marking values than smaller *fitness* results.

Optimization parameters control the runtime behavior and solution quality as a tradeoff between exploitation and exploration. These can be modified depending on the target function and the number of variables, e.g. by trial and error.

The option "ProbabilitySelectBestPath" takes values between zero and one. Smaller values use probabilistic selecting resulting in slower convergence but exploring more possibilities.

The current minimal selection probability for a variable state is monitored during the iterations. The smaller it is, the greater the ability to explore new solutions.

The output of ResourceFunction["AntColonyOptimization"] is a List representing the best found solution. Due to the stochastic search method, this optimum does not necessarily have to be global, thus better solutions may exist.

When the third argument is All, the output is an Association with keys:

"Best" | variable allocation which minimizes fitness |

"Iterations" | for each iteration step:
{arguments which minimize fitness,
normalized pheromone matrix,
and current minimal selection probability for a variable state} |

"NumberOfFunctionCalls" | number of calls made to the fitness calls |

Create an array of possible assignments:

In[1]:= |

Out[3]= |

Define an objective function to minimize:

In[4]:= |

Search for minimum:

In[5]:= |

Out[5]= |

Return the complete iteration process using the third argument of All:

In[6]:= |

In[7]:= |

Out[5]= |

Convergence behavior:

In[8]:= |

Out[8]= |

In[9]:= |

Out[9]= |

In[10]:= |

Out[10]= |

The above example with default options shown:

In[11]:= |

In[12]:= |

In[13]:= |

Out[13]= |

In[14]:= |

Out[14]= |

Terminate if a quarter of individuals have the same *fitness* value:

In[15]:= |

In[16]:= |

In[17]:= |

Out[17]= |

In[18]:= |

Out[18]= |

Have 50% of the individuals select the current shortest path (low exploration):

In[19]:= |

In[20]:= |

In[21]:= |

Out[21]= |

In[22]:= |

Out[22]= |

Use a lower pheromone marking at each step depending on individual *fitness* value (low convergence speed, high exploration):

In[23]:= |

In[24]:= |

In[25]:= |

Out[25]= |

In[26]:= |

Out[26]= |

Reduce the selection probability for less-used paths more slowly:

In[27]:= |

In[28]:= |

In[29]:= |

Out[29]= |

In[30]:= |

Out[30]= |

Total given mass:

In[31]:= |

Values for individual coins:

In[32]:= |

In[33]:= |

Fitness function (error function). In this problem the difference between the target coin weight and the calculated coin weight is minimized:

In[34]:= |

Matrix of possible coins in wallet:

In[35]:= |

Out[8]= |

Three optimization runs:

In[36]:= |

Out[36]= |

The *fitness* function must return a positive value. For maximization problems, *fitness* must be adjusted:

In[37]:= |

Out[37]= |

Optimize a structure geometry:

In[38]:= |

In[39]:= |

In[40]:= |

In[41]:= |

Out[41]= |

In[42]:= |

Restrictions:

In[43]:= |

In[44]:= |

In[45]:= |

Out[45]= |

Define helper functions:

In[46]:= |

In[47]:= |

In[48]:= |

In[49]:= |

The fitness function uses a penalty term to enforce constraints:

In[50]:= |

Search for minimum mass structure according to the displacement constraints:

In[51]:= |

Show the result:

In[52]:= |

Out[52]= |

In[53]:= |

Out[53]= |

In[54]:= |

Out[54]= |

Plot the result with deformed structure:

In[55]:= |

In[56]:= |

In[57]:= |

In[58]:= |

Out[58]= |

- Wikipedia–Ant colony optimization algorithms
- Solving Knapsack Problems with Mathematica–Wolfram Notebook Archive

- 1.0.0 – 13 February 2020

This work is licensed under a Creative Commons Attribution 4.0 International License