The term "herd mentality" is not often used in a positive sense. Meanwhile, in nature, organisms with relatively low individual intelligence often gather in communities that behave more intelligently and methodically than each of their individual members. This led mathematicians and physicists in the late 20th century to start thinking about using swarm intelligence (ie, collective intelligence) to solve complex problems in our lives.
"Whales in the Sky", a flock of birds flying over a field in the English countryside
Imagine a pizza delivery man who needs to deliver orders to different locations in the city and then return to the restaurant he left. How can he best construct his route? Mathematicians call it the traveling salesman problem. Methods for solving such problems are divided into exact and heuristic ones. The first, also called classical, are based on an exhaustive enumeration of all possible solutions, which in turn makes them inefficient in the case of a large number of variables or points to visit: finding the answer can take many years.
It turns out that most practical problems of combinatorial optimization (e.g., truck routing) require a special approach. Heuristic methods, including swarm algorithms, perform a relatively limited search for solutions and find a solution that may not be the best but is definitely close "by trial and error" in a reasonable amount of time. The best modern algorithms allow finding solutions that are 95-99% close to optimal.
At this point we should stop and explain how we calculate the effectiveness of these decisions.
- First, for most problems it is possible to obtain a higher (or lower, depending on the task) estimate of the global optimum without being able to find the global optimum itself. For example, we are faced with the task of optimally loading a product of complex shape and large mass into a car - the theoretical optimum is achieved when using 100% of the load capacity and the car, but the optimization problem cannot be answered without violating other constraints . If the swarm algorithm finds a solution that reaches 95% of the load capacity, this can be considered a rough estimate of the accuracy of the algorithm.
- Secondly, sometimes we can find the optimal value of function , but at the same time, the value of independent variable when the function reaches the optimal value is of practical value and can only be found by solving the optimization problem. For example: There is a complex production process with a lot of reallocation. We know that the minimum cost to produce a batch of products can be 95 rubles , but we do not know how to set up the equipment and in what order to process the products to achieve this cost level. The swarm algorithm provides settings and a series of operations, the cost of which is 100 rubles. Therefore, the algorithm has an estimated accuracy of 95%.
Now imagine that there are organisms in the animal kingdom that certainly don't know what mathematics is, but act every day in an optimal and efficient way without even knowing it. The lives of some of these animals inspired scientists to develop the algorithm . Such algorithms are called biomimetic algorithms because they mimic the behavior of animals or natural phenomena. So, for example, an individual bird or fish would not even question whether the flock in which it lives is behaving reasonably. Each individual (in the algorithm - a particle) changes its position in space, focusing on its experience and the positions of its neighbors. This helps the birds not collide with each other and fly along the optimal route to the right place.
This systematic behavior of animals illustrates the concept of "auto-synchronization", the "five percent law", which also exists in the human world. If in some societies 5% of the participants perform a certain action simultaneously, for example, they start clapping for the artist on stage, then the rest automatically start doing the same thing: first separately, then synchronously . The ant algorithm works similarly: an ant searches for the best path from food or building materials to a house over a long period of time. But a group of ants gathered in a colony quickly found the best solution. The secret lies in the pheromones these insects secrete. The faster you walk back and forth, the more ants there will be, and the smell of secretions will be stronger, as if to say: "Follow me."
However, heuristic algorithms include more than just swarm algorithms. Some of them were inspired by the strict hierarchies of the animal kingdom, where people are connected vertically rather than horizontally like groups. For example, in the world of bees, there is a scout who first goes around hive to find nectar and transmits the coordinates to the base. The more suitable flowers it finds on the lawn, the longer and brighter the bee's dance will be. The remaining inhabitants of the hive, if the information satisfies them, have been sent to collect nectar. Scouts, on the other hand, fly off in search of other open spaces, with the search radius increasing with each run. If we talk about bee algorithm, the search stops when the bee finds the best position or the best solution in all aspects.
The Gray Wolf algorithm developed in 2014 also contains a similar agent leader. In the wild, the hierarchy and division of responsibilities in groups are relatively clear, which directly affects the hunting behavior of predators. This forms the basis of the algorithm. When a wolf searches for prey (the optimal solution), it is assumed that the alpha male (the best candidate) and the beta wolf have a clearer, more correct idea of where the prey might be. Therefore, the rest of the package adjusts its behavior and position based on where the best search agent is.
Wolf Pack, Yellowstone Park, USA
The choice of the required algorithm depends on the task at hand, there is no general approach here. The Free Lunch Theorem (NFL), for example, holds that if an algorithm performs well on a certain class of problems, then this must be balanced by degraded performance on the remaining set of problems. Furthermore, the computational cost, the availability of the software, and the time allotted for finding the solution must be considered in order to choose the right algorithm. But even in this case, the algorithm cannot guarantee that you have found the optimal solution, which is scientifically called the global optimal solution. In theory, only the quantum computer can always search for the global optimum within a reasonable time. Although small quantum processors already exist, they are not yet capable of dealing with large numbers of variables, and unfortunately, all practical problems are exactly the same.
If we already had a powerful enough quantum computer, we could use it to solve larger, more complex optimization problems quickly and accurately, but it doesn't exist yet. However, we can use heuristics that have been successfully applied to ordinary machines. Furthermore, even in this case we can use phenomena from quantum physics in natural algorithms. So, for example, the quantum-inspired particle swarm algorithm uses tunneling to overcome high obstacles.
For clarity, imagine you are playing in a bowling alley and the pins are placed behind a hill. At the same time, you are not strong enough to roll the ball from the top to the other side. There is only one way out of our world - don't play such a weird bowling alley . In the quantum world, smart people don't go uphill, they dig tunnels. When the total energy is not enough to climb the hill, the particles move through it. This contradicts the laws of classical mechanics and shows the quantum nature of the phenomenon used by modern algorithms. This effect speeds up the calculation process and helps not to get stuck in local optima when searching for the global optimum.
Quantum-inspired algorithms for pharmacology , industry, logistics, finance and materials discovery. That is, as long as you can optimize a path, plan, or some process. So far, quantum-inspired algorithms are thought to have the greatest economic impact. However, there are no limits to perfection, and while a traveling salesman, working away from home, may no longer be confused about routes (at least 95-99%), there are still many unsolved problems from various fields of science, business and everyday life . These have yet to be solved by quantum-inspired algorithms.
