What is swarm intelligence?
What is swarm intelligence?
A swarm of insects or birds or fishes are incredible, amazingly complex, social systems. A huge number of entities work together, move together, and interact with one another, none of which has a clue what they are doing. This is not only about the animals or insects but could also be molecules, particles, or any other entities that maintain sort of "balance", from a physical balance between particle's charges to a social balance. The term “swarm intelligence” refers to an intelligent behavior of a swarm of “agents”, including insects (e.g., bees), artificial systems (e.g., robots), or points in a search space (e.g., candidate solutions), that cooperate with one another to accomplish a task.
The social interaction followed by a swarm of things leads to the accomplishment of surprisingly complex tasks that might not be easy to formulate, or even impossible to do by one single somewhat intelligent entity. The co-operation between the entities in the swarm manifests sort of intelligence. For example, a colony of ants works together to move food from a source to their nest, optimizing the path between the nest and the food during the process. This then is very similar to the optimization of packets sent in a computer network. Hence, a simulated version of ants can be used for network routing quite efficiently, with a minimum attempt at designing any optimization algorithm for the matter. This opened up an opportunity for computer scientists to mimic co-operative systems of animals or insects and use them to solve problems.
Swarm intelligence for optimization:
The entities in a swarm of things move together to accomplish a purpose. What if that purpose is to search for the best solution for a problem? An abstract design of the entities of a swarm can then be a simple solution to a problem. The swarm of these solutions may move together in the "problem space" (formally the search space) with the aim of finding a better solution. This goes very well with the generic framework for optimization methods. In fact, each entity uses its own experience about the problem, combines it with others experiences, and decides to "move" in the problem space to a new position, that is hopefully better. Although various swarm-based methods for optimization have been proposed, most of these methods are similar at an abstract level, see [1]. Some examples of swarm intelligence methods are Ant Colony Optimization, Particles Swarm Optimization, Intelligent Water Drops, etc.
Note that, the term "Swarm intelligence" should not be mistaken with "swarm robotics", although they are very closely related. Swarm intelligence refers specifically to swarm-inspired methods for optimization purposes, while swarm robotics might not be related to optimization.
What is the difference between swarm intelligence optimization and classical optimization methods?
SI methods usually replace the first and second order information of the problem with an information share strategy. Numerical computation methods often use first or second order information of the problem to find candidate movement (towards optimum) directions. As an example, in Luvenburge-Marquardt optimization method, a very complex and heavy (in terms of runtime and needed memory) method, uses this information for optimization. So what is the problem with using this information?
For one, the calculation of this information is very complicated and even impossible in some cases (e.g., the formulation of the problem is not available). Even if the complete equation of the optimization problem is given, you still need the first and second order (first and second derivative) of that equation too to be able to use these methods effectively. Being continuous and differentiable are also conditions that need to be satisfied. Derivative-free methods (finite difference) could be useful here, however, for a large number of dimensions they are not practical. Finally, these methods are not useful for discrete space problems.
[1] Z. Michalewicz, "Quo Vadis, evolutionary computation? On a Growing Gap between Theory and Practice," in Advances in Computational Intelligence, ed: Springer, 2012, pp. 98-121
[2] https://www.mitpressjournals.org/doi/abs/10.1162/EVCO_r_00180
By R. Bonyadi
A swarm of insects or birds or fishes are incredible, amazingly complex, social systems. A huge number of entities work together, move together, and interact with one another, none of which has a clue what they are doing. This is not only about the animals or insects but could also be molecules, particles, or any other entities that maintain sort of "balance", from a physical balance between particle's charges to a social balance. The term “swarm intelligence” refers to an intelligent behavior of a swarm of “agents”, including insects (e.g., bees), artificial systems (e.g., robots), or points in a search space (e.g., candidate solutions), that cooperate with one another to accomplish a task.
The social interaction followed by a swarm of things leads to the accomplishment of surprisingly complex tasks that might not be easy to formulate, or even impossible to do by one single somewhat intelligent entity. The co-operation between the entities in the swarm manifests sort of intelligence. For example, a colony of ants works together to move food from a source to their nest, optimizing the path between the nest and the food during the process. This then is very similar to the optimization of packets sent in a computer network. Hence, a simulated version of ants can be used for network routing quite efficiently, with a minimum attempt at designing any optimization algorithm for the matter. This opened up an opportunity for computer scientists to mimic co-operative systems of animals or insects and use them to solve problems.
A flock of Starlings
Swarm intelligence for optimization:
The entities in a swarm of things move together to accomplish a purpose. What if that purpose is to search for the best solution for a problem? An abstract design of the entities of a swarm can then be a simple solution to a problem. The swarm of these solutions may move together in the "problem space" (formally the search space) with the aim of finding a better solution. This goes very well with the generic framework for optimization methods. In fact, each entity uses its own experience about the problem, combines it with others experiences, and decides to "move" in the problem space to a new position, that is hopefully better. Although various swarm-based methods for optimization have been proposed, most of these methods are similar at an abstract level, see [1]. Some examples of swarm intelligence methods are Ant Colony Optimization, Particles Swarm Optimization, Intelligent Water Drops, etc.
Ant System (AS), proposed by Dorigo and his colleagues, was the first ant-based swarm algorithm used for optimization. The algorithm mimics the ants’ behavior in finding the shortest path between two points. As ants move on the ground, they leave a pheromone trail behind that is used as part of a collective information-sharing strategy. To select between various possible paths between two points, each ant uses a probabilistic model based on the intensity of pheromone trails on the paths. As the paths are marked by all ants, the shortest paths from the nest to food are marked more frequently that makes them more probable to be selected by more ants. Clearly, AS is a good candidate for finding the shortest path in routing problems such as the traveling salesman problem.
Another popular swarm-based optimization algorithm is Particle Swarm Optimization (PSO). PSO simulates the interaction among a group of “birds” (known as particles in the PSO) to solve an optimization problem. The position of a particle in the space corresponds to a candidate solution that is evaluated based on the objective function of the problem at hand. Particles communicate basic information (e.g., the best location they have experienced) to one another through a communication graph, known as the topology of the swarm. Each particle collects the incoming information, marries them with its own information, and decides to move to a new location. Although PSO has limitations to solve some optimization problems (see [2]), it has been successful in solving many engineering optimization problems such as scheduling and load dispatching.
The behavior of individuals in the swarm of ants or particles depends on their cognitive (e.g., movement patterns, optimum speed of movement) and social (e.g., cooperation strategy, topology) parameters.
Taken from Wikipedia page
Note that, the term "Swarm intelligence" should not be mistaken with "swarm robotics", although they are very closely related. Swarm intelligence refers specifically to swarm-inspired methods for optimization purposes, while swarm robotics might not be related to optimization.
What is the difference between swarm intelligence optimization and classical optimization methods?
SI methods usually replace the first and second order information of the problem with an information share strategy. Numerical computation methods often use first or second order information of the problem to find candidate movement (towards optimum) directions. As an example, in Luvenburge-Marquardt optimization method, a very complex and heavy (in terms of runtime and needed memory) method, uses this information for optimization. So what is the problem with using this information?For one, the calculation of this information is very complicated and even impossible in some cases (e.g., the formulation of the problem is not available). Even if the complete equation of the optimization problem is given, you still need the first and second order (first and second derivative) of that equation too to be able to use these methods effectively. Being continuous and differentiable are also conditions that need to be satisfied. Derivative-free methods (finite difference) could be useful here, however, for a large number of dimensions they are not practical. Finally, these methods are not useful for discrete space problems.
[1] Z. Michalewicz, "Quo Vadis, evolutionary computation? On a Growing Gap between Theory and Practice," in Advances in Computational Intelligence, ed: Springer, 2012, pp. 98-121
[2] https://www.mitpressjournals.org/doi/abs/10.1162/EVCO_r_00180
By R. Bonyadi
Comments
Post a Comment