Lecture
Swarm intelligence (SI) describes the collective behavior of a decentralized, self-organized system. It is considered in artificial intelligence theory as an optimization method. The term was introduced by Gerardo Beni and Jing Wang in 1989, in the context of a cellular robotic system. However, the idea had earlier been discussed in detail by Stanisław Lem in the novel «The Invincible» (1964) and the essay «Twenty-First Century Weapon Systems, or Evolution Upside Down» (1983).
Swarm intelligence systems typically consist of a population of agents (boids[en.]) interacting locally with one another and with their environment. The behavioral rules are usually inspired by nature, particularly by biological systems. Each boid follows very simple rules, and although there is no centralized control system dictating what each of them should do, local and, to some extent, random interactions lead to the emergence of intelligent group behavior unknown to the individual boids. A precise definition of swarm intelligence has still not been formulated. In general, SI should represent a multi-agent system exhibiting self-organizing behavior that, in aggregate, should display some form of intelligent behavior.
The application of swarm principles in robotics is called swarm robotics, while the concept of «swarm intelligence» refers to a broader set of algorithms. «Swarm forecasting» is used in solving certain forecasting problems.
Usually a swarm has no control center prescribing what each element of the swarm should do at a given moment. Each particle obeys fairly simple rules, but local interactions with a small random component nevertheless lead to the emergence of group behavior that is not controlled by the individual particles of the swarm. At present there is no precise definition of swarm intelligence, only a set of conditions that an algorithm must satisfy to be called a swarm algorithm:
The first two conditions are fairly obvious: the system must consist of several particles that obey certain rules set by the swarm's creator; the third one is less clear-cut. It is quite difficult to determine whether the behavior of a created swarm is «intelligent». The only thing that can be said with certainty is that the swarm's behavior must differ from a random search algorithm. Swarm algorithms are used to solve problems that have the following characteristics:
A swarm can be defined as a decentralized system consisting of simple, uniform elements interacting with one another in a certain way. Examples from the real biological world include ant colonies, bee swarms, flocks of birds, or schools of fish. Conceptually, such algorithms are built on the effect of additivity and synergy that emerges when particles are combined into a single system.
Evolutionary algorithms (EA), particle swarm optimization (PSO), differential evolution (DE), ant colony optimization (ACO) and their variants dominate the field of nature-inspired metaheuristics. This list includes algorithms published up to approximately the year 2000. A large number of later metaphor-inspired metaheuristics have begun to draw criticism from the research community for concealing their lack of novelty behind an elaborate metaphor. For algorithms published since then, see the List of metaphor-based metaheuristics.
Metaheuristics lack confidence in the solution. Once appropriate parameters are set and a sufficient degree of convergence is reached, they often find a solution that is optimal or close to optimal; nevertheless, if the optimal solution is not known in advance, the quality of the solution remains unknown. Despite this obvious drawback, these types of algorithms have been shown to work well in practice and have been thoroughly studied and developed. On the other hand, this drawback can be avoided by computing the solution quality for a special case where such a calculation is possible, and after such a run it becomes known that every solution at least as good as the solution of the special case has at least the same solution confidence that the special case had. One such example is a Monte Carlo algorithm modeled after Ant, for the minimum feedback arc set, where this was achieved probabilistically by hybridizing the Monte Carlo algorithm with the ant colony optimization method.
Particle swarm optimization, PSO, is a numerical optimization method that does not require knowledge of the exact gradient of the function being optimized. PSO was proposed by Kennedy, Eberhart and Shi, and was originally intended to simulate social behavior. The algorithm was simplified, and it was noted that it was suitable for performing optimization. The book by Kennedy and Eberhart describes many philosophical aspects of PSO and of so-called swarm intelligence. An extensive survey of PSO applications was made by Poli.
PSO optimizes a function by maintaining a population of candidate solutions, called particles, and moving these particles around in the solution space according to a simple formula. The movement follows the principle of the best position found so far in that space, which is continually updated as particles find more favorable positions.
Let 
be the objective function to be minimized, S be the number of particles in the swarm, each of which is assigned a coordinate 
in the solution space and a velocity
. Let also 
be the best known position of the particle with index 
, and 
be the best known state of the swarm as a whole. Then the general form of the particle swarm method is as follows.
do:
having a multidimensional uniform distribution, where 
and 
are the lower and upper bounds of the solution space, respectively.
.
, then update the swarm's best known state: i
.
. do:
.
, where the operation 
denotes componentwise multiplication.
by the velocity vector: 
. This step is performed regardless of whether the objective function value improves.
, then:
., then update the best known state of the swarm as a whole: . contains the best of the solutions found.The parameters 
, 
and 
are chosen by the practitioner and determine the behavior and efficiency of the method as a whole. These parameters are the subject of much research.
The stopping criterion may be: reaching the maximum allowed number of iterations, finding an acceptable solution, or the absence of significant improvement in the objective function value over a number of iterations.
Choosing the optimal parameters for the particle swarm method is the subject of a considerable body of research; see, for example, the works of Shi and Eberhart, Carlisle and Dozier, van den Bergh, Clerc and Kennedy, Trelea, Bratton and Blackwell, and Evers.
A simple and effective way of selecting the method's parameters was proposed by Pedersen and other authors. They also carried out numerical experiments with various optimization problems and parameters. This technique for choosing the parameters is called meta-optimization, since another optimization algorithm is used to «tune» the PSO parameters. The best-performing PSO input parameters turned out to contradict the basic principles described in the literature, and often yield satisfactory optimization results for simple PSO cases. Their implementation can be found in the open-source library SwarmOps.
New variants of the particle swarm algorithm are constantly being proposed to improve the method's performance. There are several trends in this research, one of which proposes creating a hybrid optimization method that uses PSO in combination with other algorithms, see for example. Another trend proposes speeding up the method's operation in some way, for example by backtracking or changing the order of particle movement. There are also attempts to adapt the behavioral parameters of PSO during the optimization process
The ant colony algorithm (ant colony optimization, ACO) is one of the efficient polynomial algorithms for finding approximate solutions to the traveling salesman problem, as well as similar route-finding problems on graphs. The approach was proposed by the Belgian researcher Marco Dorigo.
The essence of the approach lies in analyzing and using a model of the behavior of ants searching for paths from the colony to food. The algorithm is based on the behavior of an ant colony — marking successful routes with a large amount of pheromone. The work begins by placing ants at the vertices of the graph (cities), after which the ants begin to move — the direction is determined by a probabilistic method, based on the formula:
,
where:
Pi — the probability of choosing route i,
li — the length of the i-th transition,
fi — the amount of pheromone on the i-th transition,
q — a value that determines the «greediness» of the algorithm,
p — a value that determines the «herding» of the algorithm and
q+p=1.
Below are some of the most popular variations of the ant colony algorithm.
The Artificial Bee Colony algorithm (ABC) — a swarm algorithm based on a meta-heuristic algorithm introduced by Karaboga in 2005. It simulates the foraging behavior of honey bees. The ABC algorithm consists of three stages: employed bees, onlooker bees, and scout bees. The bees use a local search algorithm in the neighborhood of solutions selected through deterministic selection by the employed bees and probabilistic selection by the onlooker bees. The scout bee performs the abandonment of depleted food sources during the foraging process. By this analogy, solutions that are no longer useful for finding a solution are discarded and new solutions are added (analogous to exploring new regions in the search for food sources).
A schematic illustration of the two-dimensional space exploration strategy (bold lines — scout flights, thin lines — solution refinement by employed bees)
The nectar-gathering strategy of honey bees in nature - The main purpose of a bee colony's work in nature is to explore the space around the hive in order to find nectar and subsequently collect it. For this purpose, the colony includes various types of bees: scout bees and forager (employed) bees (besides them, the colony also has drones and a queen, which do not take part in nectar collection). Scouts explore the space surrounding the hive and communicate information about promising locations where the largest amounts of nectar have been found (a special mechanism called the bee dance exists for exchanging information within the hive).
An artificial immune system (AIS) — an adaptive computational system that uses models, principles, mechanisms and functions described in theoretical immunology, which are applied to solve applied problems.
Although natural immune systems are far from being fully understood, there are today at least three theories that explain the functioning of the immune system and describe the interaction of its elements, namely: the negative selection theory, the clonal selection theory, and the immune network theory. These formed the basis for the creation of three algorithms for AIS operation.
General methods are based on specific immunological theories that explain the functions and behavior of the mammalian adaptive immune system.
The Grey Wolf Optimizer (GWO) is a meta-heuristic optimization algorithm proposed by S. Mirjalili and A. Lewis in 2014. This algorithm is based on simulating the social behavior and hierarchy of wolves in nature.
The algorithm uses four types of wolves: alpha, beta, delta and omega. Alpha wolves dominate and make decisions about the direction of the hunt, beta wolves are subordinate and assist the alpha wolves, delta wolves help other wolves and follow the leaders, while omega wolves usually follow the rest and perform most of the work. This hierarchy is used in the algorithm to update the wolves' positions and search for the global optimum.
At each iteration of the algorithm, the alpha, beta and delta wolves update their positions in the solution space using their own best solutions and the best solutions of other wolves. Omega wolves update their positions by following the best wolves.
Like other biomimetic algorithms, the grey wolf optimization algorithm uses the behavior and interaction of animals in nature to create effective methods for solving complex optimization problems.
The Gravitational Search Algorithm (GSA) — a search algorithm based on the law of universal gravitation and the concepts of mass interaction. The algorithm is based on the theory of attraction from Newtonian physics. Gravitational masses are used as search agents in the algorithm.
In recent years, various heuristic optimization algorithms have been developed. Many of these algorithms are based on natural phenomena. When compared to other algorithms, the gravitational search algorithm is one of the most effective at solving various nonlinear function optimization problems.
Researchers from Switzerland have developed an algorithm based on Hamilton's rule of kin selection. The algorithm shows how altruism in an individual within a swarm can evolve over time and lead to more effective swarm behavior.
The work on creating altruistic robots was carried out by EPFL robotics professor Dario Floreano and University of Lausanne biologist Laurent Keller.
«Testing the evolution of altruism through quantitative studies on living organisms is largely impossible, because the experiments would have to span hundreds of generations, and there are too many variables», — states the EPFL press release. «However, Floreano's robots evolve rapidly using simulated gene and genome functions, allowing scientists to measure the costs and benefits associated with a trait».
Their paper was published in the journal Public Library of Science (PLoS) Biology. It confirms what is known as Hamilton's rule of kin selection, developed in 1964 by W. D. Hamilton. He proposed a precise set of conditions under which altruistic behavior can evolve. EPFL describes it as follows:
«If an individual family member shares food with the rest of the family, this reduces his or her personal chances of survival, but increases the chances of family members passing on their genes, many of which are shared throughout the family. Hamilton's rule simply states that whether an organism shares its food with another depends on its genetic relatedness (how many genes it shares) with the other organism.
«We showed that Hamilton's kin selection theory always accurately predicts the relationship between the evolution of altruism and the relatedness of individuals within a species», — explains Markus Waibel, lead author of the paper and a former doctoral student of Keller and Floreano.
Hamilton's rule has long been the subject of much debate, since its equation seems too simple to be true. «This study captures Hamilton's rule with remarkable accuracy in explaining when an altruistic gene is passed from one generation to the next, and when it is not», — says Keller.
The study will help biologists, but it has already had an impact on other robots at EPFL, particularly on swarms of flying robots. «We were able to take this experiment and extract an algorithm that we can use to develop cooperation in any type of robot», — says Floreano. «We are using this altruism algorithm to improve the control system of our flying robots, and we see that it allows them to cooperate effectively and fly in a swarm more successfully».
The Intelligent Water Drops algorithm (IWD) — a swarm-based optimization algorithm that uses the mechanisms of natural rivers and how they find near-optimal paths to their destination.
It finds optimal or near-optimal paths derived from the interactions between water drops as water flows along a riverbed. In the IWD algorithm, several artificial water drops depend on one another and are able to modify their environment in such a way that they find the optimal path along the path of least resistance. Thus, the IWD algorithm is a constructive, population-based optimization algorithm.
Its creation was inspired by the brood parasitism of some cuckoo species, which lay their eggs in the nests of other birds (other bird species). Some nest owners may enter into direct conflict with the cuckoos that intrude on them. For example, if a nest owner discovers that eggs are not its own, it will either throw out these foreign eggs or simply abandon the nest and build a new one somewhere else.
Some cuckoo species, such as the New World brood parasites, for example the striped cuckoo or the pheasant cuckoo (Tapera naevia), have evolved so that females very often specialize in mimicking the color and structure of the eggs of their chosen host bird species.
For simplicity in describing the new cuckoo algorithm, we will use the following three idealized rules:
The algorithm's scheme can be represented as follows:
At the same time, in the standard CS algorithm the probability pa and the Levy flight parameters are constants. There is an improved cuckoo algorithm (Improved Cuckoo Search, ICS) that uses dynamic values for these parameters. To improve accuracy, it is advisable to use larger values of pa and a during the initial iterations, and smaller values during later ones.
Methods based on swarm intelligence can be used in a number of applications. The US military is studying swarm methods to control unmanned aerial vehicles. The European Space Agency is considering an orbital swarm for self-assembly and interferometry. NASA is studying the use of swarm technology for planetary mapping. A 1992 paper by M. Anthony Lewis and George A. Bekey discusses the possibility of using swarm intelligence to control nanobots inside the body for the purpose of destroying cancerous tumors. In contrast, Al-Rifaie and Aber used stochastic diffusion search to assist in tumor detection. Swarm intelligence (SI) is increasingly being applied in Internet of Things (IoT) systems and in connection with intent-based networking (IBN) due to its ability to handle complex distributed tasks through decentralized self-organizing algorithms. Swarm intelligence is also applied to data mining and cluster analysis. Ant-based models are also the subject of modern control theory.
The use of swarm intelligence in telecommunications networks has also been explored in the form of ant-based routing. This was first proposed independently by Dorigo et al. and by Hewlett-Packard in the mid-1990s, and a number of variants exist. Essentially, it uses a probabilistic routing table that rewards/reinforces the route successfully traversed by each «ant» (a small control packet) that floods the network. Route reinforcement has been studied in the forward direction, the backward direction, and in both directions simultaneously: backward reinforcement requires a symmetric network and ties the two directions together; forward reinforcement rewards a route before the outcome is known (but then one could pay for the movie before knowing how good the film is). Because the system behaves stochastically and therefore lacks repeatability, there are major obstacles to commercial deployment. Mobile media and new technologies are capable of changing the threshold for collective action thanks to swarm intelligence (Rheingold: 2002, p. 175).
The placement of transmission infrastructure for wireless communication networks is an important engineering problem involving competing objectives. A minimal selection of locations (or sites) is required while ensuring adequate area coverage for users. A quite different, ant-inspired swarm intelligence algorithm, stochastic diffusion search (SDS), has been successfully used to provide a general model for this problem, related to circle packing and set covering. SDS has been shown to be applicable for finding suitable solutions even for large problem instances.
Airlines have also used ant-based routing to assign arriving aircraft to airport gates. At Southwest Airlines, the software uses swarm theory, or swarm intelligence — the idea that a colony of ants performs better than a single one. Each pilot acts like an ant searching for the best gates at the airport. «The pilot learns from experience what is best for him, and it turns out to be the best solution for the airline», — explains Douglas A. Lawson. As a result, the «colony» of pilots is always directed to the gates they can reach and depart from quickly. The program can even warn a pilot about backup aircraft before they are needed. «We can anticipate that this will happen, so we will have gates available», — says Lawson. [ 44 ]
Artists use swarm technology as a means of creating complex interactive systems or simulating crowds.
The «The Lord of the Rings» film trilogy used similar technology, known as Massive (software), during battle scenes. Swarm technology is particularly appealing because it is cheap, reliable and simple.
«Stanley and Stella in Breaking the Ice» was the first film to use swarm technology for rendering, realistically depicting the movements of groups of fish and birds using the Boids system.
Tim Burton's film «Batman Returns» also used swarm technology to display the movements of a group of bats.
Airlines have used swarm theory to simulate passenger boarding of aircraft. Southwest Airlines researcher Douglas A. Lawson used an ant-based computer simulation, applying just six interaction rules to estimate boarding times using various boarding methods. (Miller, 2010, xii-xviii).
Networks of distributed users can be organized into «human swarms» through the introduction of real-time closed-loop control systems. Developed by Louis Rosenberg in 2015, human swarming, also called artificial swarm intelligence, allows harnessing the collective intelligence of interconnected groups of people over a network. The collective intelligence of a group often surpasses the capabilities of any individual member of the group.
Stanford University School of Medicine published a study in 2018 showing that groups of human physicians, combined together using real-time swarming algorithms, could diagnose diseases with significantly higher accuracy than individual physicians or groups of physicians working together using traditional crowdsourcing methods. In one such study, groups of radiologists combined together were tasked with diagnosing chest X-rays, and they demonstrated a 33% reduction in diagnostic errors compared to traditional human methods and a 22% improvement compared to traditional machine learning.
The University of California, San Francisco (UCSF) School of Medicine published a preprint in 2021 on diagnosing MRI images using small groups of collaborating physicians. The study found a 23% increase in diagnostic accuracy when using artificial swarm intelligence (ASI) technology compared to majority voting.
Swarm grammars — are swarms of stochastic grammars that can be evolved to describe complex properties, such as in art and architecture. These grammars interact as agents behaving according to the rules of swarm intelligence. Such behavior can also involve deep learning algorithms, in particular when mapping such swarms onto neural circuits is considered.
In a series of works, Al-Rifaie et al. successfully used two swarm intelligence algorithms — one imitating the foraging behavior of a single ant species ( Leptothorax acervorum ) (stochastic diffusion search, SDS), and another algorithm imitating the flocking behavior of birds (particle swarm optimization, PSO) — to describe a new integration strategy that uses the local search properties of PSO together with the global behavior of SDS. The resulting hybrid algorithm is used to create sketches of new drawings from an input image, using the artistic tension between the local behavior of «birds flocking together» — as they strive to follow the input sketch — and the global behavior of «ants searching for food» — as they strive to induce the swarm to explore new areas of the canvas. The «creativity» of this hybrid swarm system was analyzed in the philosophical light of the «rhizome» in the context of Deleuze's «Orchid and Wasp» metaphor.
A more recent work by Al-Rifaie et al., «Swarmic Sketches and Attention Mechanism», presents a new approach that deploys an «attention» mechanism by adapting SDS to selectively attend to detailed regions of a digital canvas. Once the swarm's attention is drawn to a particular line on the canvas, the capability of PSO is used to create a «swarmic sketch» of the line in question. The swarms move across the digital canvas in an attempt to satisfy their dynamic roles — attending to areas with more detail — associated with them through their fitness function. By linking the rendering process to concepts of attention, the performance of the participating swarms creates a unique, non-identical sketch every time the «artist» swarms set about interpreting input line drawings. In other works, while PSO is responsible for the sketching process, SDS controls the swarm's attention.
In a similar work, «Swarm Paintings and Colour Attention», non-photorealistic images are created using the SDS algorithm, which in the context of this work is responsible for attention to color.
« Computational creativity » of the aforementioned systems is discussed through two preconditions for creativity (i.e. freedom and constraints) in two well-known phases of swarm intelligence: exploration and exploitation.
Michael Theodore and Nikolaus Correll use an intelligent swarm art installation to explore what it takes to make engineered systems appear alive.
Swarm intelligence algorithms and the software implementing them have been successfully applied to the task of extracting informative descriptors. It is clear that the role of computer modeling at various stages of new drug development will keep growing, and improving the selection of an optimal set of descriptors will make it possible to minimize experimentation, making drug design more efficient, faster and cheaper. In the 1960s, Hansch created a QSAR (Quantitative Structure–Activity Relationship) model, using various molecular descriptors of physical, chemical and biological properties aimed at providing computational estimates of the biological activity of molecules. The correct construction of a QSAR model depends on the quality of the initial set of active/inactive compounds. Conducting QSAR studies requires source data consisting of a set of chemical structures with known activity values. (This work is carried out under the grant "Computer-aided molecular design of drugs based on immune network modeling" (2015–2017) at the Institute of Information and Computational Technologies of the SC MES RK, Samigulina G. A., Masimkanova Zh. A.)
When searching for "structure – activity" relationships of chemical compounds, a pressing task is choosing the optimal set of descriptors on which the QSAR model is built. The goal of selecting an optimal set of descriptors is to reduce the dimensionality of the descriptor space. Building an adequate model based on an optimal set of descriptors increases the likelihood of making correct decisions.
An important direction in the field of QSAR has been the application of artificial intelligence approaches, which provide high prediction accuracy for chemical compounds with given structures. Artificial intelligence methods make it possible to process large volumes of data. Therefore, artificial intelligence methods such as neural networks, evolutionary algorithms, artificial immune systems, and swarm intelligence algorithms have found application in solving the problem of selecting informative features.
Swarm intelligence (SI) methods belong to the class of decentralized algorithms that imitate the behavior of biological systems, such as anthills, flocks of birds and schools of fish. Their main advantage – the ability to solve complex optimization and search problems under conditions of uncertainty. Let us compare the main SI methods: the ant colony algorithm (ACO), the particle swarm algorithm (PSO), as well as less well-known but promising methods such as the artificial bee colony algorithm (ABC) and the firefly algorithm (FA).
Principle of operation:
The algorithm is based on modeling the behavior of ants that lay paths from the colony to a food source, leaving pheromones. Pheromones are reinforced if the path is optimal, which makes it possible to find the shortest route.
Advantages:
Disadvantages:
Principle of operation:
The algorithm simulates the movement of a swarm of particles, each of which updates its position based on its own best result and the swarm's global result.
Advantages:
Disadvantages:
Principle of operation:
The method is based on modeling the behavior of honey bees, which search for nectar sources, exchange information in the hive, and redistribute effort to explore the most promising areas.
Advantages:
Disadvantages:
Principle of operation:
This algorithm simulates the behavior of fireflies, which are attracted to one another depending on the brightness of their light, which is associated with the quality of the solution.
Advantages:
Disadvantages:
| Method | Problems | Convergence | Scalability | Resistance to local minima | Computational complexity |
|---|---|---|---|---|---|
| ACO | Combinatorial optimization | Medium | Medium | High | High |
| PSO | Continuous optimization | High | High | Low | Low |
| ABC | Problems with a large number of extrema | Medium | Medium | Medium | Medium |
| FA | Universal problems | High | Low | High | Medium |
Each swarm intelligence method has its own strengths and weaknesses. The choice of a suitable method depends on the type of problem, the characteristics of the optimization space, and the available computational resources. The ACO and PSO algorithms are well suited to specific problems (combinatorial and continuous, respectively), while ABC and FA are versatile but require more tuning to achieve high efficiency.
Comments