Mechanisms in Social Insect Societies and their Use in Optimization. Ant Colony Applications for Vehicle Routing Problems with Time Windows

El pasadojueves día 14 de mayo se impartió una conferencia de título Mechanisms in Social Insect Societies and their Use in Optimization. Ant Colony Applications for Vehicle Routing Problems with Time Windows, por Elena Nechita, profesora del Department of Mathematics and Informatics University of Bacău, Romania . La charla versó sobre la aplicación a la gestión del transporte de vehículos de algoritmos basados en el estudio de los procedimientos naturales seguidos por colonias de insectos como las hormigas.

Ant Colony Optimization (ACO) is a metaheuristic inspired by the behavior of some species of ants that are able to find the shortest path to a food source through cooperation in a short period of time. Such algorithms are based on the concept known as estigmergia, which explains the communication between agents through the medium in which they are. In the case of the colonies of ants, each ant walking on the floor deposits a substance called pheromone that other ants can detect. When an ant reaches a fork in the different paths taken by the other peers, it tend to follow those paths that contain higher concentrations of pheromone. The pheromone evaporates after some time and therefore a higher concentration of the substance means that recently there has been a step along that path of ants, which are more likely to have found some source of food.

This metaheuristic was introduced by Dorigo et al. in 1991. ACO algorithms are inspired by this behavior to solve combinatorial optimization problems and use an artificial ant colony, or computational agents, that communicate with each other using pheromones. To solve a problem by ACO we must represent a solution by a graph with weights on its arcs. At each iteration, the ant builds a complete path by scrolling the graph. Once the path is built, the ant updates the pheromone trail according to the fitness value of the solution it represents. To move through the graph, each ant manages two types of information, memory information (pheromone) and heuristic information. The latter depends on the problem and is based on the use of prior knowledge of it (whose value does not change during the execution). In its motion by the graph, the ants usually choose those nodes with better value for the two reports, although, as in other bio-inspired algorithms, a stochastic component exists. This component allows an ant to move to nodes with smaller values to improve the exploration that is essential for solving complex combinatorial problems successfully. In this way all the ants cooperate to find the best solution to the problem, eg. what is in the best way.

The ant colony algorithm was initially presented in two models: the System of Ants (SH) [15] and the Ant colony system (SCH) , although both, applications and modifications have widely expanded over the past years