Authors: V. Savkin, O. Kaverina
Source:
V Международная научно–техническая конференция Современные информационные технологии в образовании и научных исследованиях
(СИТОНИ–2017)
– Донецк: ДонНТУ, 2017г. – с. 432.
What is ant colony optimization algorithm? Why it is so called? Let's find out.
The ant colony optimization algorithm is one of the effective polynomial algorithms for finding approximate solutions of the traveling salesman problem, as well as the solution of similar problems of finding routes on graphs. Dr. Marco Dorigo proposed the first version of the algorithm in 1992. Algorithm was aimed at finding the optimal path in the graph [1].
What is ant colony optimization algorithm? Why it is so called? Let's find out.
An ant cannot be called smart. A separate ant is not able to make the slightest decision. The fact is that it is arranged in a very primitive way: all its actions are reduced to elementary reactions to the environment and to its fellowmen. The ant is not able to analyze, draw conclusions and seek solutions.
Ants are able to achieve success due to their sociality. They live only in collectives – colonies. All the ants of the colony form the so-called swarm intelligence. The individuals making up the colony should not be clever: they must only interact on certain very simple rules, and then the colony will be fully effective.
There are no dominant individuals in the colony, there are no bosses or subordinates, no leaders who hand out directions and coordinate actions. The colony is completely self-organizing. Each of the ants has information only about the local situation, not one of them has no idea about the whole situation as a whole – that he learned himself or from his relatives, either explicitly or implicitly. The mechanisms for finding the shortest path from the anthill to the source of food are based on the implicit interactions of the ants.
Each time passing from the anthill to food and back, the ants leave a pheromone path behind them. Other ants, having felt such traces on the ground, will instinctively rush to him. Since these ants also leave pheromone paths behind them, the more ants pass along a certain path, the more attractive it becomes for their relatives. In this case, the shorter path to the source of food, the less time is required for the ants to it – and consequently, the faster traces left on it become noticeable.
How the ant colony optimization algorithm works and where it is applied?
Simulating the behavior of the colony of ants in nature, ant colony optimization algorithms use multi-agent systems, whose agents function according to extremely simple rules. They are extremely effective in solving complex combinatorial problems – such as, for example, the traveling salesman problem, the first one solved using this type of algorithms.
In modern computer systems in the majority it is applied not the classical ant colony optimization algorithm, but its modifications, the most famous of which are Elitist Ant System, Ant-Q, Ant Colony System, Max-min Ant System and ASrank [2].