How ants solve the traveling salesman problem

Alexander Klimenkov

senior technical writer Bercut

In mathematics and programming are sometimes used unusual names of phenomena, objects and algorithms. But almost always these names allow you to quickly understand the essence of entities. Take, for example, a well-known problem of the traveling salesman problem is to find the shortest path between the specified points. Indeed, immediately imagines a traveling salesman who needs to get around all the houses in a small town, but spend a minimum of time and effort. This task has very wide application, because the optimization of the routes of the various processes is one of the most pressing problems in the modern, rapidly changing world. To solve this problem using different algorithms, one of them is called “ant”. With this title a bit more complicated. If you do not know what it is, you will be hard to understand how ants help to solve this problem. That’s what I want to tell you in this article. But in order to deal with this algorithm, we first need to look closely at the behavior of ants in their unusual world of organized.

Unusual world under our feet

Let’s try to imagine an ordinary ant in the forest is a small hill, which, at first glance, chaotic swarming ants. Somewhat reminiscent of a subway station at rush hour. On the outskirts of their nest becomes not so much the movement of individual ants appear to be more meaningful. It’s more like a lively prospect somewhere in the city centre. If to follow individual ants further, it is common to see a string of ants that crawl organized for each other: one side blank, the other with production. Something like a highway with the flow of trucks. A chain of ants — familiar to all of us the picture, it can be seen in many popular science programs and, of course, in cartoons. For example, in the classic “Tom and Jerry”, where this great procession annoyed resting in the hammock That.

From school we know that ants are highly organized creatures. They perform many different tasks: aphids are bred as Pets, organized transporterowych food supplies from one source in a special vault inside the nest, build and repair the nest, defend it from enemies. But how is it that ordinary insects are a meaningful collective activity? After all, according to some, in the brain of one ant only about 500 of the thousands of neurons. For comparison, a human has 86 billion. This means that the ant is unable to make a meaningful decision. The most that he can do is follow a simple program. A single brain centre of the nest, too no — it is not sitting leading a Superintelligent ant who wisely manages all the other ants. How can a unified system of “ant”? Science can not yet give a definite answer to all questions about ants, but research is ongoing, work is being done. The direction of these studies and some hypotheses about the structure of the ant “control,” for example, you can read the article in the journal “Science and life”. It is noteworthy that some scientific studies of ants have already reached the stage of wide practical application in technology and programming.

Follow this ant

Let’s return to our example with a chain of ants. Like ants “know” that a certain place is the source of nutrition and the need to move him on a particular route? Scientists long ago figured out quite how this happens. Based on the study of the behavior of the ants they managed to create one of the most efficient algorithms for fast solution of the problem. This algorithm is officially called “ant”, in English- ant colony optimization, abbreviated as ACO.

Watch one of the so-called ant-forager, whose task in the ant family is the production of food. As usual, he runs haphazardly through the countryside in search of something edible. At some point he finds a source of food, such as juicy appetizing fruit. Sam the ant, of course, this fruit to carry it to the nest may not. Then he takes a piece of prey and drags it into the nest. However, he marks his way with a special pheromone. Further we for simplicity will refer to this pheromone simply “mark”. Importantly, other ants, smelling the smell of the label, with big hunting run in the same way. For them it is a signal that this path will lead to something tasty and nutritious.

In the book of Igor Akimushkin “Problems of ethology” (1985) described such an interesting experience:

Take a sheet of paper and put it in the way of the ant, returning home with news of a rich discovery. When an ant crawl across the sheet, mark it the way a light touch of the pencil and turn the paper at a slight angle. The ants are called from the nest, always on the highway to the edge of the paper, rested in the place where the earlier route was to land on the sheet, but here is the cliff. You start to fuss at the gap, look for the track and when you find her in the side, run in a straight line. You will see that the path the ants will coincide with the marked pencil line.

A little about feedback

Unfortunately, we know all the good tends to end quickly. So what happens when the ants the pieces will take this fruit to the nest? The wise nature has provided it. The fact that the label gradually evaporates. While ants are the prey to the nest, they are constantly fueling the label on its path, because each of them returns with prey. But at some point, the ants will return with nothing — leave your mark they will not be. From the point of view of mathematics, the evaporation of the label provides negative feedback around the system.

Algorithms for finding paths in the graph

By the way, described the organization of the process gives ants another great “bonus” — the shortest way from fruit to the anthill. In principle, an ant is not obliged to choose the path with the tag. This way more attractive, but not the only one. The ant can move chaotically, leaving his mark on any trajectory. But over a period of time on the shortest path will be more ants than all other ways. This means that they are going the number of labels is more than all the other random trajectories. And this number will continue to increase due to the fact that other ants are more likely to choose this path. From a mathematical point of view this is a positive feedback.

From ants to the system

What do we have? Let’s list all the features of the resulting system:

  • the system is self-organizing, without a single control center;
  • the system is distributed — each ant uses only the available local information.
  • the system is stable — if a couple of ants losing their way, it will not affect the overall task;
  • the system successfully solves the problem of self-optimization — using negative and positive feedback ants find the shortest route.

In fact, the ants represent the implementation of a living algorithm for fast finding of the shortest path between two points. Why not formalize this algorithm and use it to find the optimal trajectory between any number of points? For the first time this problem was solved by French scientist Marco Dorigo. It was he who in his thesis in 1992 proposed the first version of “ant algorithm”.

Algorithmischen ants

Consider one of variants of implementation of the ant colony optimization algorithm. So, we have the specified number of points. The challenge lies in the fact that in a few iterations to find the shortest tour of all points. The number of ants equal to the number of points. Before each iteration the ants placed one in each point.

At each iteration, each ant traverses all points along a certain trajectory. In the preparation of its trajectory each ant a few times “chooses” a point at which he moves. To select the point to move is influenced by the following parameters:

  1. A list of points to enter which is impossible. Ant in an iteration may visit each point only once.
  2. A desire to visit the point with ant more willing to visit the nearest point. We denote this parameter as N. It will be equal to 1/D, where D is the distance to the considered point from the current position of the ant.
  3. The number of labels on the path between the point at which an ant is, and consider the point. We denote this parameter as T.

To decide at what point he is to move, the ant first makes a list of points where he was not. For each point the ant performs the following actions:

  • calculates the parameters N and T;
  • gets the index H = Tα·Nβ, where α and β are weighting factors, algorithm settings;
  • calculates the probability of moving to the point — P = H / (sum H of all points).

After that, the ant is given the probability P selects the point at which he needs to move. Imagine a roulette wheel where each point corresponds to a sector with area proportional to the probability P. using a hypothetical roulette ant and makes his choice.

After moving the ant between the points you need to increase the number of labels on this segment by an amount equal to Q / L, where L is the distance between the points, and Q — configurable parameter of the entire algorithm as a whole (it is selected of the same order with the average distance between the points).

Thus, in one iteration each ant along a certain trajectory traverses all the points. At the end of each iteration, we need to ensure evaporation of the label for each of the segments between the points. For this you need to multiply the amount by a constant value E (evaporation), which is greater than 0 but less than 1.

And of course, at the end of each iteration we need to choose the shortest route. If it is better than the shortest route in the previous iteration, select it as the current solution. And so iteration after iteration, while the shortest route for several iterations do not change. Then with a sufficient degree of confidence we can say that we have solved the task.

Experimenting with the algorithm

Here is a simplified presentation of the algorithm without complex formulas, but if you want more details, you can find them online. You can start for example here. You can also find many ready-made programs with an illustration of the algorithm. I liked the program, called Ant Colony Algorithm. In this program you can control the main parameters of the algorithm, view the results of each iteration, ask the test samples with any number of points. By the way, what do you think how to test this algorithm? How to understand that our ants have found the shortest route. This is a good test example: dots, arranged in a circle. For them the shortest path is always the same — a circle. In this program this location, select the mode “Automatic placement”. And this program allows you to try various modifications of the algorithm. If desired, this can be necessary to understand a source program in C.

“NP-easy” ants

What is so good algorithm that we have just studied? The fact that the traveling salesman problem refers to the so-called NP-hard. This means that it can be solved in a brute-force search only on a very small number of points. Even a slight increase in the number of points gives an unimaginable increase in the number of computations (namely, n! where n is the number of points). Therefore, several tens of points the task is simple brute force will not solve it. And then help methods, like ant colony optimization algorithm. Because they allow to solve this problem in just a minute, while a brute force search would have required millions of years.

By the way, with using ant colony optimization algorithm to optimize not only the distance. As a parameter optimization there may be price, time and any other indicators. In the article Adam HART “These clever ants” in the journal “Science in focus” (№5 [18], 2013) examples are given of the use of ant colony optimization algorithm: planning of truck routes in the company Air Liquide (USA), design the optimal scheme of wiring for artificial Earth satellites the company Clyde Space (Scotland), the calculation of optimal routes of spacecraft using gravitational maneuvers in the model developed by several universities in the UK.

The same article also described another task, which suggested to scientists the ants. It is the task of calculating the optimal number of packets needed to transmit information. The fact that ants are foragers follow a simple rule: the frequency of leaving the nest depends on the frequency with which the other ants return with food. This algorithm is now used successfully in all known TCP/IP Protocol. The high frequency of confirmation of delivery of the packet tells the sender about the wide bandwidth and the possibility of increasing the frequency of sending new packets.

Another area in which it is possible to apply ant colony optimization algorithm is optimization of various internal processes in high tech companies. How to plan production and the development, testing and documentation, implementation and support of complex systems for some departments and employees were not overloaded, and others were constantly doing? In the selection of optimal chains and deadlines can help the ant algorithm. Our company Bercut relatively well-established development process, tasks, consistently through all stages from development requirements prior to shipment of the finished solution to the customer. But the company is constantly developing, increasing the number of systems and customers, development time (time to market). Perhaps in the future to further optimize processes, we need to use an algorithm similar to the ant.

Software optimization of production and routes of transportation, selection of the optimal trajectory, planning of various interrelated activities — all this application area, in which you can successfully and effectively apply ant colony optimization algorithm. And it all started with the fact that someone carefully and thoughtfully looked at the usual chain of ants at his feet. In the world of mathematics and programming very much starts with simple observation and the ability to formalizability algorithmically to describe the world around us.

Go to our cases Get a free quote