Code

Algorithms Inspired by Nature

Algorithms Inspired by Nature

Free Python Course ➞ Mini-course for beginners and experienced coders. 4 cool projects in your portfolio, live communication with the speaker. Click and find out what you can learn in the course.

Learn more

Numerous innovative technical solutions have been developed based on observations of nature, including animals and plants. For example, the design of bird wings inspired early aircraft designers, leading to the creation of modern airplanes. Research on burdock thorns also played a key role in the development of Velcro fasteners, which are widely used today in the textile industry and everyday life. Such examples highlight the importance of biomimetics in technological progress and demonstrate how nature can serve as a model for solving complex engineering problems.

Computer scientists explore the world around them in search of optimal solutions. They use algorithms and models inspired by nature, which are called bioinspired. These methodologies aim to apply principles from nature to solve complex problems in various fields of science and engineering. Bioinspired algorithms open new horizons in the development of efficient and adaptive technologies, making them key to modern scientific progress.

Artificial neural networks, which mimic the functioning of the human brain, are the most well-known bioinspired model. In this article, we will consider less common, but no less interesting algorithms: the ant algorithm and the bee colony algorithm. These models were developed by scientists based on observations of the behavior of thousands of insects that collaborate to solve complex problems. The study of these algorithms opens new horizons in the field of optimization and problem solving applied in various fields, from logistics to artificial intelligence.

Swarm Intelligence

Ants are often perceived as surprisingly intelligent creatures. They build large nests, are engaged in "cattle farming" and other activities. and even capture other ants as slaves. However, when examined individually, it becomes clear that individual ants possess rather primitive reflexes. Their true strength lies in teamwork, which allows them to achieve impressive results. These insects cooperate with each other, demonstrating astonishing efficiency in their actions. Thus, the collective intelligence of ants becomes a key factor in their successful life. For many years, scientists have been studying the mechanisms of ant society, paying particular attention to one interesting feature: ants always choose the shortest route from the anthill to the food source. Initially, this behavior was explained by hypotheses about some kind of mental interaction between ants. However, further research has shown that ants use simpler and more effective navigation methods, such as pheromones and visual cues, which allow them to optimize their route. These discoveries deepen our understanding of the social behavior of insects and their ability to make collective decisions.

Belgian researcher Marco Dorigo developed a mathematical model that scientifically describes the process of swarm intelligence. In his doctoral dissertation, published in 1992, he presented this model in the form of a computer algorithm known as Ant Colony Optimization (ACO). Dorigo became a pioneer in this field, and his work inspired many scientists to further explore the concept of swarm intelligence, opening new horizons in the fields of optimization and artificial intelligence.

Swarm intelligence is a concept that characterizes systems consisting of many agents. These agents can be either physical robots or virtual entities in computer simulations. Interaction between agents is carried out according to certain rules, allowing them to jointly find optimal solutions to complex problems. Swarm intelligence has applications in a variety of fields, including robotics, artificial intelligence, and complex systems modeling, making it an important tool for solving today's pressing problems.

In the 30 years since the discovery of the ant algorithm, scientists have developed numerous bioinspired models. Among these, swarm intelligence-based algorithms that emulate the behavior of various natural colonies, including bee colonies, fireflies, and schools of fish, are particularly noteworthy. These models, such as the Firefly Algorithm and Fish School Search, demonstrate effectiveness in solving complex optimization problems using principles observed in nature.

Pheromone Trail

Research shows that ants choose the shortest path to a food source using pheromones. These chemicals secreted by insects serve as markers indicating the route they have taken. One important characteristic of pheromones is their ability to evaporate quickly, which leads to a decrease in their scent over time. This makes foraging more efficient, as ants can quickly adapt to changes in the environment and find optimal routes to resources.

Ants' foraging process begins with a scout ant exploring the surrounding area, gradually moving away from the nest. Upon discovering a food source, such as an apple fallen to the ground, it returns to the nest. On its return journey, the ant marks the route to the food it has found with pheromones. This allows other ants to follow the scent and quickly find food, facilitating the efficient collection of resources for the colony.

The scent left by the scout attracts other ants. However, the route it has chosen may not be the most optimal. The ants follow it in search of food, but some may occasionally stray from the main path. This random deviation may lead the ants to discover new food sources, thereby expanding their search routes. However, the main group will strive to return to the original path to avoid losing the trail.

All alternative routes discovered by the ants are also marked with pheromones. This allows each ant moving from the nest to the apple to continually encounter forks in the path marked with pheromones. The ant chooses its path based on a simple principle: it follows the path with the most intense pheromone scent. This mechanism ensures effective communication between ants and allows them to optimally navigate to the food source.

Pheromones evaporate quickly. This means that more ants travel along the short route per unit of time than along the long one. Each new ant's passage makes the short path more fragrant and attractive, while ineffective long routes gradually disappear due to the evaporation of pheromones. Thus, ants optimize their routes, choosing the most efficient paths for finding food and communicating with the colony.

An example with ants that follow between points A and E. They can go around the obstacle on the right (along side C) or on the left (along H). The shorter path © deposits more pheromones, and the ants choose it more and more often. Image: M. Dorigo, V. Maniezzo, A. Colorni / "Ant System: Optimization by a colony of cooperating agents. IEEE Trans Syst Man Cybernetics — Part B" / PubMed, 1996

Over time, most insects will begin to follow the shortest route. Even if some individuals lose their way, this will not affect the overall process: the swarm will continue to move along the pheromone trail, maintaining its intense aroma. This mechanism allows the insects to navigate efficiently in space and reach their destination as quickly as possible.

The ants solve a problem similar to the traveling salesman problem. This problem involves visiting several cities, passing through each exactly once, and then returning to the starting point, while minimizing the total distance. Studying the methods ants use to find the optimal route can provide useful insights into solving this complex problem.

The traveling salesman problem is a complex combinatorial optimization problem where, even with a limited number of cities, it can take a computer billions of years to enumerate all possible routes. However, using the ant colony algorithm significantly speeds up the process of finding the optimal solution. This method, inspired by the foraging behavior of ants, allows for efficient finding of shorter routes between cities, reducing the time to solve the problem. The use of the ant colony algorithm in optimization problems is becoming increasingly popular due to its high efficiency and ability to handle large volumes of data.

To optimize the road network along which the traveling salesman (in this case, an ant) ​​moves, a graph model is used. In this model, vertices represent cities, and edges represent roads connecting these cities. When implementing the ant colony algorithm, the software inputs data on the number of vertices and the lengths of all routes. This allows us to effectively solve routing problems and find optimal paths using principles based on ant behavior.

A graph in which points correspond to cities, and the edges connecting them correspond to roads between cities. Infographics: Maya Malgina / Skillbox Media. Source: Alexander Tsurikov

Before starting the algorithm, it is necessary to set constants, including the pheromone evaporation coefficient and the coefficient of its influence on the selection of a new route. These parameters play a key role in optimizing the route selection process and ensure the efficiency of the algorithm. Correctly setting these coefficients allows achieving better results in problems related to routing and finding optimal solutions.

Let's create variables to store real numbers that will represent the amount of pheromones on each edge of the graph. Each possible path between points will be characterized by two values: length and the amount of pheromones. The path length remains constant, while the amount of pheromones will change with each iteration of the loop. This will allow dynamic tracking of changes and optimization of path selection depending on current conditions.

One iteration of the loop corresponds to one complete pass of the ant along the closed route. Increasing the number of iterations allows more ants to traverse the road network, increasing the likelihood of finding the shortest route. Once the exit condition is met, for example, a predetermined number of iterations, the loop terminates, and the program records the optimal route.

Pseudocode is a simplified description of an algorithm used to plan and document software solutions. It allows developers to focus on the logic of the program without being distracted by the syntax of a specific programming language. Pseudocode is not a formal language, so its structure can vary. However, it should be clear and easy to read so that anyone familiar with algorithms can easily interpret it.

When writing pseudocode, it is important to follow several basic principles. First, simple and understandable constructs should be used to reflect the main steps of the algorithm. Second, excessive detail should be avoided while maintaining sufficient clarity. Third, it's recommended to use comments to clarify complex points. Using pseudocode in software development helps improve the understanding of algorithms, facilitates teamwork, and speeds up the coding process. Furthermore, it can serve as a basis for documenting and explaining the logic behind software solutions. Pseudocode is an essential tool for programmers and analysts, allowing them to effectively communicate ideas and concepts.

Infographics: Maya Malgina / Skillbox Media. Source: Alexander Tsurikov

Note that at each iteration, the ants are re-initialized. This allows us to simulate the process of finding a path from a new point, which is made possible by the fact that we are searching for a closed route. This approach provides flexibility in exploring different paths and allows us to find optimal solutions for routing problems.

At each node in the graph, the ant decides whether to continue its movement based on a simple rule. It chooses the next route with a probability proportional to the amount of pheromone along the path and inversely proportional to the path's length. This process allows for efficient graph exploration, optimizing the path based on the pheromones deposited. Thus, ants are able to find the shortest routes, which makes their behavior interesting for studying in the context of optimization algorithms and graph theory.

An ant chooses a path by evaluating the length and the smell of pheromones. Image: M. Dorigo, M. Birattari, T. Stützle / Ant Colony Optimization / IEEE Computational Intelligence Magazine, 2006

After completing its route, an ant returns to the starting point, which updates the values ​​of the variables responsible for the amount of pheromones on each edge of the graph. This process is important for route optimization and improved search, since increasing the pheromone concentration on more successful paths allows other ants to find better routes faster. Thus, updating pheromones contributes to the efficiency of algorithms based on ant behavior.

Ants interact with the environment, reducing the pheromone concentration based on a fractional evaporation coefficient, which acts as a constant. This leads to lower pheromone levels in certain areas. Along the routes taken by the ant, the amount of pheromone increases inversely proportional to the path length: the shorter the path, the more pheromones are added. Thus, ants effectively use pheromones to optimize their routes, allowing them to find the best paths to food sources.

The iterative process involves ants starting from new nodes in the graph. The pheromone levels associated with each edge contain information about the previous routes of the virtual ants. After completing the cycle, the route with the highest pheromone concentration is recognized as optimal. This method effectively finds the best paths in various optimization problems, such as routing and resource allocation, by leveraging the collective behavior of ants to improve results.

Several variants of the ant colony algorithm exist, among which models with elite individuals stand out. These individuals have the ability to move along the most optimal routes and leave more pheromones compared to regular ants. This accelerates the process of finding the best solution and improves the algorithm's efficiency in solving optimization problems. Using elite individuals in the ant colony algorithm significantly increases the probability of finding higher-quality solutions and reduces computation time.

Scientists have confirmed the convergence of several versions of the ant colony algorithm. This means that by increasing the time spent by ants moving between graph nodes, the algorithm is able to find more optimal solutions. Long-term route exploration improves the quality of output data and increases the efficiency of finding solutions in optimization problems.

Dancing and Bees

Bees have amazing abilities to find optimal solutions. These striped workers locate abundant flower clusters to collect nectar and pollen, located several kilometers from the hive. They then communicate the location of food sources to their fellow bees using a unique dance, which serves as a kind of communication language within the bee community. This dance not only communicates the distance to flowering plants but also indicates their direction, demonstrating the bees' high degree of organization and intelligence. Research shows that this form of communication plays a key role in resource collection efficiency and colony survival. Bees have a unique ability to communicate the location of nectar sources through rhythmic dances. These dances contain "geographic coordinates," allowing other bees to estimate the distance and direction to flowering plants. The intensity of the dance movements indicates the number of flowers in the area: the more flowers, the more active and energetic the dance. This remarkable phenomenon was discovered in the mid-20th century by insect researcher Karl Frisch, who received the Nobel Prize for his discoveries. Understanding the language of bees helps us better understand their role in the ecosystem and the importance of preserving these industrious insects.

For many years, research into bee foraging methods remained largely the preserve of biologists. However, in 2005, Professor Dervis Karaboga of the Department of Computer Science at Erciyes University in Turkey joined this research. In his scientific paper, he presented a model of swarm intelligence inspired by bee dances. This model, known as the Artificial Bee Colony (ABC), opened new horizons in the field of optimization and computing technology, demonstrating how nature can serve as a source of effective solutions to complex problems.

All bees are divided into three main types: scouts, workers, and observers. In the beginning, scouts fly out of the hive in random directions to find nectar. Having discovered a food source, they return to the hive and, using a "dance floor," inform observer bees of the locations of their discoveries. This unique communication method allows the colony to efficiently locate resources and optimize nectar collection.

Based on the intensity of their dance, observer bees select scouts that have found the richest nectar areas and head toward them. At the nectar collection site, observer bees become worker bees. They survey the area and estimate the number of flowers. Two scenarios are then possible.

A bee discovers a new, flower-rich area nearby and begins collecting nectar from this location, abandoning the previous one. After completing its nectar collection, it returns to the hive, where it dances to communicate the precise coordinates of the new nectar source to the observer bees. This dance plays a key role in communication within the hive, allowing other bees to quickly locate new resources. Nectar foraging efficiency and the ability to communicate about new food sources are important aspects of bee life, contributing to their survival and prosperity. A bee cannot find a more suitable place to forage for nectar and continues to forage in its original location. Upon returning to the hive, it shares information about its chosen location with other bees, facilitating efficient resource search. This communication between bees plays a vital role in their lives and helps optimize the nectar foraging process.

Bee colony algorithm: thick lines are the flight paths of scouts, thin lines are the refinement of decisions by worker bees. Image: Wikimedia Commons

The process of nectar extraction in bees occurs cyclically. Upon arrival at the hive, worker bees use a dance to communicate the coordinates of the location where nectar was collected. They then act as observers, analyzing the information received from their fellow bees. In the next stage, based on their dance signals, the bees select a new promising location for nectar collection, fly there, and resume work. This complex mechanism of communication and cooperation allows bees to efficiently locate food sources and ensures their survival and prosperity.

Over time, bees begin to focus on collecting pollen and nectar from the most productive sources, neglecting less flower-rich locations. This behavior is associated with their desire to optimize effort and maximize results, which improves resource collection efficiency.

Algorithm pseudocode is a simplified representation of an algorithm that allows developers and researchers to more easily understand and visualize the program's logic. It is used to describe the steps required to solve a problem without being tied to a specific programming language. This makes pseudocode a versatile tool suitable for a variety of fields, such as software development, data analysis, and educational purposes. Pseudocode helps focus on the algorithmic structure, which facilitates more efficient code planning and implementation. It is important to remember that pseudocode does not have strict syntactic rules, allowing you to focus on the logic of the algorithm rather than technical details.

The best solutions can be stored in a fixed-length array, which will act as a "dance floor." The loop will continue until its termination conditions are met. This approach allows for efficient data management and optimizes the performance of algorithms. Using a fixed array also simplifies access to elements and minimizes memory management overhead.

There is a community of specialists working on the development of the Bee Colony Algorithm. Pseudocode for this algorithm is available at this link. On the community's official website, you can find implementations of the model in programming languages ​​such as Java, C#, Python, and others.

Where can it be used?

Swarm intelligence models are actively used in situations where it is necessary to select the optimal solution from multiple options. These approaches find application in various fields, including project management, data analysis, and decision making under uncertainty. Swarm intelligence allows for the efficient processing of information and the finding of the best paths to achieving goals, making it an indispensable tool in the modern world.

  • Search and rescue operations. Scientists from the Kurchatov Institute programmed a group of robots using swarm intelligence. The robots find objects scattered around the location and drag them to the collection point along the shortest route. The ant colony algorithm is well suited for devices moving on the ground, while the bee colony algorithm is suitable for flying devices (drones, quadcopters).
  • Road freight transportation. The European company Ant Optima develops systems that optimize the transportation of goods by road. Its programmers have written a number of computer programs based on the ant colony algorithm for the delivery of food, medicine, and petroleum products to cities and retail outlets. Ant Optima's software tracks the quantity of goods in warehouses, monitors the situation on European roads, and helps select the optimal route for cargo delivery.
  • Civil aviation. Swarm intelligence helps Southwest Airlines select parking spots and optimize the flow of passengers purchasing tickets and checking in. This is how the airline combats queues at ticket offices and check-in counters.
  • Urban planning and science. Using an ant algorithm, scientists determine the optimal location of power plants, transformers, and transmission lines, and design the shape of portable antennas.

British scientists have developed a method for creating three-dimensional drawings using ant and bird algorithms. This approach is called "swarm art." Swarm art is an innovative technique for creating unique visual compositions inspired by natural processes and animal behavior.

The researchers created simple outlines of objects and launched a virtual swarm that moved along these lines. Through multiple iterations of the algorithm, the virtual animals transformed the two-dimensional drawings into three-dimensional forms. This experiment demonstrates how algorithmic modeling can influence the perception and visualization of objects, opening new horizons in the field of computer graphics and artificial intelligence.

Swarm Art: on the left is the original drawing, on the right is the result of the swarm algorithm. Image: M. M. Al-Rifaie, J. M. Bishop, A. Aber / Creative or Not? Birds and Ants Draw with Muscles / AISB 2011: Computing and Philosophy, 2011

Large IT companies are increasingly looking for specialists in the field of artificial intelligence. Take an online bachelor's degree in Data Science and Machine Learning to become a highly qualified IT specialist with a degree from a state university. The knowledge and skills you gain will open up broad career opportunities in the rapidly developing technology sector.