Swarm Intelligence - Volume 1: Principles, current algorithms and methods
Swarm Intelligence (SI) is one of the most important and challenging paradigms under the umbrella of computational intelligence. It focuses on the research of collective behaviours of a swarm in nature and/or social phenomenon to solve complicated and difficult problems which cannot be handled by traditional approaches. Thousands of papers are published each year presenting new algorithms, new improvements and numerous real world applications. This makes it hard for researchers and students to share their ideas with other colleagues; follow up the works from other researchers with common interests; and to follow new developments and innovative approaches. This complete and timely collection fills this gap by presenting the latest research systematically and thoroughly to provide readers with a full view of the field of swarm. Students will learn the principles and theories of typical swarm intelligence algorithms; scholars will be inspired with promising research directions; and practitioners will find suitable methods for their applications of interest along with useful instructions. Volume 1 contains 20 chapters presenting the basic principles and current algorithms and methods of well-known swarm intelligence algorithms and efficient improvements from typical particle swarm optimization (PSO), ant colony optimization (ACO) and fireworks algorithm (FWA) as well as other swarm intelligence algorithms for swarm robotics. The companion volume 2 covers innovations, new algorithms and methods, and volume 3 covers applications of swarm intelligence algorithms. With contributions from an international selection of leading researchers, Swarm Intelligence is essential reading for engineers, researchers, professionals and practitioners with interests in swarm intelligence.
Inspec keywords: swarm intelligence; optimisation
Other keywords: ACO; particle swarm optimisation; robotics methods; ant colony optimisation; PSO; swarm intelligence algorithms
Subjects: Expert systems and other AI software and techniques; Optimisation techniques; Artificial intelligence (theory)
- Book DOI: 10.1049/PBCE119F
- Chapter DOI: 10.1049/PBCE119F
- ISBN: 9781785616273
- e-ISBN: 9781785616280
- Page count: 644
- Format: PDF
-
Front Matter
- + Show details - Hide details
-
p.
(1)
-
1 Survey of swarm intelligence
- + Show details - Hide details
-
p.
1
–28
(28)
In this chapter, a systematic survey of swarm intelligence is given to show the overview of swarm intelligence, along with some recent developments in swarm intelligence and swarm robotics. First, the concept of swarm intelligence is given. Then, some general researches and several classical algorithms and their developments are presented in detail. After that, some novel algorithms and their applications are reviewed individually. Finally, some developments in swarm robotics are given.
-
2 Generalization ability of swarm intelligence algorithms
- + Show details - Hide details
-
p.
29
–53
(25)
In this chapter, generalization ability of swarm intelligence algorithms solving problems with different number of dimensions is analyzed and discussed. Three algorithms, brain storm optimization in objective space (BSO-OS), fireworks algorithm (FWA), and particle swarm optimization (PSO) algorithm, are selected as illustrations to explain the definition of algorithm's generalization ability. The performance of BSO-OS, FWA, and PSO algorithm on solving problems with different number of dimensions is analyzed. Based on the experimental results, the algorithm's generalization ability was measured by the results ratio of algorithms with the same settings on problems with different number of dimensions. This generalization ability measurement could be extended to problems with different components. Without analysis on the landscape of problems, this measurement could give a practical illustration of the generalization ability of algorithms for solving problems with different number of dimensions or different components. Based on the analysis on the generalization of algorithms and the hardness of problems, we could have a better understanding of the relationship between problems and algorithms, and therefore design more effective algorithms to solve different problems.
-
3 A unifying framework for swarm intelligence-based hybrid algorithms
- + Show details - Hide details
-
p.
55
–83
(29)
This chapter is aimed at giving a classification and an analysis of various hybrid optimisers based on swarm intelligence optimisation algorithms (SIOAs) by the systematic taxonomy we proposed in a recent work. The taxonomy comprises five factors including the relationship between parent optimisers, hybridisation level, operation order, type of information transfer and type of transferred information. Based on the taxonomy, a unifying framework for SIOA-based optimisers is established. Some typical SIOA-based hybrids which are divided into two parts according to the combination patterns about global search and local search are analysed in accordance with the taxonomy. By the classification-based analysis, designers can gain an insight into various possibilities for hybrid design of SIOA-based optimisers.
-
4 Ant colony systems for optimization problems in dynamic environments
- + Show details - Hide details
-
p.
85
–120
(36)
Ant colony optimization (ACO) is an intelligent bionic algorithm which simulates the foraging behavior of ant colony. The conventional ACOs mainly deal with the static optimization problems. In other words, the environment of problem maintains invariant. Actually, the most problems in reality are dynamic, namely, the changing environments. The ACO can use its robustness and self-adaptability to resolve dynamic problems properly. In this chapter, the ACO with neighborhood search is introduced to address dynamic traveling salesman problem and the ACO with improved K-means clustering algorithm, which uses three immigrants schemes including random immigrants, elitism-based immigrants and memory-based immigrants, is used for dynamic location routing problem. Several conventional ACOs and other heuristic algorithms are utilized to compare with new ACOs in the corresponding dynamic problems. The comparative experiments demonstrate two novel ACOs are effective and efficient for respective dynamic optimization problems.
-
5 Ant colony optimization for dynamic combinatorial optimization problems
- + Show details - Hide details
-
p.
121
–142
(22)
The ant colony optimization (ACO) meta-heuristic was inspired from the foraging behaviour of real ant colonies. In particular, real ants communicate indirectly via pheromone trails and find the shortest path. Although real ants proved that they can find the shortest path when the available paths are known a prior, they may face serious challenges when some paths are made available after the colony has converged to a path. This is because the colony may continue to follow the current path rather than exploring the new paths in case a shorter path is available. For the ACO meta-heuristic, the challenges are similar when applied to dynamic optimization problems (DOPs). Once the algorithm converges, it loses its adaptation capabilities and may have poor performance in DOPs. Several strategies have been integrated with ACO to address difficult combinatorial DOPs. Their performance proved that ACO is a powerful computational technique for combinatorial DOPs once enhanced. This chapter investigates the applications of ACO for combinatorial DOPs.
-
6 Comparison of multidimensional swarm embedding techniques by potential fields
- + Show details - Hide details
-
p.
143
–167
(25)
Multidimensional embedding is a technique useful for characterizing spectral signature relations in hyperspectral images. However, such images consist of disjoint similar spectral classes that are spatially sensitive, thus presenting challenges to existing graph embedding methods. In this chapter, the multidimensional embedding techniques are interpreted by the potential fields method, where a sum of attraction and repulsion potential functions is minimized to find optimal energy configuration of embedding. Repulsion dominates at short distances, thereby emphasizing local relations. On the other hand, attraction dominates at long distances, stressing global relations. The formulations capture long-rangeand short-range-distancerelated effects often associated with living organisms and help to establish algorithmic properties that mimic mutual behavior for the purpose of dimensionality reduction. Widely used tSNE (stochastic neighbor embedding) and its variations are compared in terms of the potential field methods and their sources of weakness are discussed. As part of the evaluation, the embedding maps are visualized, their trajectories are plotted, and their semisupervised classifications are conducted for image scenes acquired by multiple sensors at various spatial resolutions over different types of objects.
-
7 Inertia weight control strategies for PSO algorithms
- + Show details - Hide details
-
p.
169
–198
(30)
Particle swarm optimization (PSO) is a stochastic population-based algorithm which was originally introduced by Kennedy and Eberhart [1]. This optimization algorithm is motivated by intelligent collective behavior of some animals such as flocks of birds or schools of fish. As in most of the metaheuristic optimization algorithms, in PSO, a population of individuals, known as particles, are evolved through successive iterations. The most important advantages of PSO, compared to other optimization strategies, are its easy implementation and few parameters requiring adjustment. Since the initial development of PSO by Kennedy and Eberhart, several variants of this algorithm have been proposed by researchers. The first modification was introducing an inertia weight parameter in the velocity update equation of the initial PSO-a PSO model which is now accepted as the global best PSO algorithm [2]. The goal of the inertia weight parameter is to balance the exploration and exploitation characteristics of PSO. Generally, large inertia weight values are expected to increase the velocity of the particles and improve the long-range exploration of the PSO algorithm, while low inertia values increase the short-range exploration. Due to the strong effect of the inertia weight on the performance of PSO, many researchers have investigated different inertia weight control approaches during the past decades, and many different strategies have been proposed. Various inertia weighting strategies can be categorized into three main classes (Figure 7.1): (1) constant or random, (2) time-varying, and (3) adaptive inertia weights. The first class contains strategies in which the value of the inertia weight is constant during the search or is determined randomly. In the second class, the inertia weight is defined as a function of time (iteration number), and hence these strategies are referred to as time-varying inertia weight strategies. These methods are not considered adaptive since they do not monitor the situation of the particles in the search space, and the value of the inertia weight in each iteration is known before the execution of the algorithm. The third class of the inertia weight strategies consists of those methods which use a feedback parameter to monitor the state of the algorithm and adjust the value of the inertia weight based on the feedback parameter's value. This chapter presents the major existing inertia weight control strategies in the above three categories and discusses examples of each category in detail. The remainder of this chapter is organized as follows. The next section gives a short review of the PSO algorithm, and the role ofthe inertia weight parameter in the velocity update equation. Sections 7.2-7.4 review the three groups of inertia weight strategies, constant or random, time-varying, and adaptive models. Section 7.5 reports some experimental evaluations of different inertia weight models. Finally, Section 7.6 concludes this chapter. A short description of the symbols frequently used in this chapter is shown in Table 7.1.
-
8 Robot path planning using swarms of active particles
- + Show details - Hide details
-
p.
199
–235
(37)
There exist a wide range of techniques that generate collision-free (optimal) trajectories, in an autonomous fashion, for mobile robotics. Probably, the most popular technique is that of artificial potential fields, where the robot is treated as a particle subject to a potential field that is generated by the obstacles and the goal position. The path generation problem is then treated as an optimization problem where gradient descent methods have been traditionally used. Particle swarm optimization has also been widely used to solve optimization problems, and although it has proven to be more efficient in the search of minima, it also suffers from early convergence, i.e. the swarm may get trapped in a local minima. Many of the modifications that cater for this weakness involve added complexity in the construction of the potential field and thus translates into ad-hoc algorithms. A particle swarm approach with the property of escaping local minima by forcing vortex-like dynamics when the gradient of the potential field is close to zero is proposed, proving to be more compact and intuitive than previously proposed algorithms.
-
9 MAHM: a PSO-based multiagent architecture for hybridisation of metaheuristics
- + Show details - Hide details
-
p.
237
–264
(28)
Hybridisation of metaheuristics is an important subject that has been explored by several researchers. Multiagent systems have been important tools to accomplish the task of hybridising metaheuristics. In those multiagent approaches, however, each metaheuristic is performed separately, and the potential of the hybridisation is not fully explored. In order to bridge this gap, this chapter presents MAHM (multiagent architecture for hybridisation of metaheuristics), a multiagent approach for metaheuristics hybridisation inspired on particle swarm optimisation (PSO). Introduced as a metaheuristic, PSO can be viewed as a multiagent system once particles can be thought as agents that interact and work together to achieve specific goals. In this context, particles are identified to autonomous virtual entities with social ability, reactivity, and pro-activeness. Each agent in MAHM may use different sets of predefined metaheuristics in different moments of the search to look for high-quality solutions of an optimisation problem. Thus, several elements of different metaheuristics can be found running in the swarm every MAHM iteration. In order to show the potentiality of the proposed architecture, computational experiments were carried out with the travelling salesman problem and the quadratic assignment problem, two important test grounds for algorithmic ideas.
-
10 The critical state in particle swarm optimisation
- + Show details - Hide details
-
p.
265
–295
(31)
Particle swarm optimisation (PSO) is a widely used meta-heuristic algorithm, which has been successfully applied to a large variety of problems in optimisation, prediction, classification, visualisation and robotics. However, the underlying mechanism that leads to good solutions in these domains is not well understood. A number of parameters influence the algorithm mainly by determining the balance between exploration and exploitation. In this chapter, we describe the behaviour of PSO as a product of random matrices, and use a Lyapunov exponent to precisely characterise the critical parameters for PSO. The theoretical results are discussed based on numerical experiments for standard benchmark problems.
-
11 Bounded distributed flocking control of nonholonomic mobile robots
- + Show details - Hide details
-
p.
297
–321
(25)
There have been numerous studies on the problem of flocking control for multiagent systems whose simplified models are presented in terms of point-mass elements. Meanwhile, full dynamic models pose some challenging problems in addressing the flocking control problem of mobile robots due to their nonholonomic dynamic properties. Taking practical constraints into consideration, we propose a novel approach to distributed flocking control of nonholonomic mobile robots by bounded feedback. The flocking control objectives consist of velocity consensus, collision avoidance, and cohesion maintenance among mobile robots. A flocking control protocol that is based on the information of neighbor mobile robots is constructed. The theoretical analysis is conducted with the help of a Lyapunov-like function and graph theory. Simulation results are shown to demonstrate the efficacy of the proposed distributed flocking control scheme.
-
12 Swarming in forestry environments: collective exploration and network deployment
- + Show details - Hide details
-
p.
323
–344
(22)
Landscape maintenance is a pivotal factor to reduce wildfire hazard potential. Being a difficult, time-consuming and generally expensive task, humans often face great difficulties to address the problem effectively. Considering its spatial distribution and exploration capabilities, swarm robotics presents itself as a natural solution to assist humans or other robotic agents in the reconnaissance of forestry environments and identification of fuel accumulation, such as forest debris. In this work, we propose an optimization framework for the exploration problem of forestry environments with a team of swarming robots, which also entails the deployment of a network infrastructure formed by the robots to assist agents during fire-prevention tasks. Experiments show the benefits of employing the multi-robot coordination algorithm described, which provides an effective solution for the exploration task and guarantees a final formation that maximizes network coverage for mission information exchange, considering obstacles density and other interfering factors. Thus, the system proposed might assist human operators with relevant forestry information acquired during exploration and maintain a fail-safe network for communication while agents operate in the field.
-
13 Guiding swarm behavior by soft control
- + Show details - Hide details
-
p.
345
–384
(40)
Guiding swarm behavior is one of important problems in the area of swarm intelligence. While in many multiagent systems, the local rules for each agent is difficult or impossible to be redesigned. Even for artificial systems, it is not easy to design simple local rules for each agent which can lead the group emerge desired collective behavior. In this chapter, we introduce a new method called “Soft Control” which does not need to change the underlying local rules of agents, but to add some special agents, called “shills” which can be controlled by us, into the system. It is a nondestructive intervention method because shills are still treated as normal agents by normal ones. The soft-control method is effectively applied to three different multiagent system models to guide the swarm behavior: (1) guide consensus of a Vicsek-like flocking model by adding one intelligent shill, (2) promote cooperation for a group of players that play the end-unknown repeated prisoner's dilemma game by adding a cooperating team of shill plays and (3) add one or some shills to guide the collective opinion of the DeGroot model system.
-
14 Agreeing to disagree: synergies between particle swarm optimisation and complex networks
- + Show details - Hide details
-
p.
385
–408
(24)
Due to its numerous applications in fields like systems biology, medicine, technology, engineering, or social sciences, the new science of complex networks (CNs) has become extremely popular over the last couple of decades. Particle swarm optimisation (PSO) and CN science have significant common ground, as they both deal with a set of agents (particles for PSOs, vertices for CNs) which interact according to an underlying topology. Moreover, one of the most important branches of CN science is represented by social networks, while PSO was originally conceived for optimisation through the simulation of social behaviour, thus further emphasising the strong tie between the two scientific fields. A prominent problem in CNs is the opinion dynamics in social networks. To this end, opinion interaction models are tested in order to verify if they can recreate a realistic social behaviour; a ubiquitous feature of such reallife social behaviours is persistent opinion disagreement. One of the most important characteristics of a social network which fosters disagreement is that it contains stubborn agents, namely vertices which never change their opinion. We discuss models of disagreement, such as that with stubborn agents and tolerance-based models, then offer a new perspective in exploring the frontiers between network science and PSO.
-
15 Ant colony algorithms for the travelling salesman problem and the quadratic assignment problem
- + Show details - Hide details
-
p.
409
–442
(34)
The ant colony optimization (ACO) is a metaheuristic, which has been successfully used to solve computationally difficult optimization problems, especially combinatorial optimization problems which belong to the class of non-deterministic polynomial (NP)-hard problems. This chapter explains ACO algorithms, their most important variants, and hybridization with local optimization methods. Practical considerations for successful ACO implementation and parameter setting are given. The working of the algorithm is explained in detail by using simple examples. The chapter ends with overview of research trends in ACO.
-
16 A review of particle swarm optimization for multimodal problems
- + Show details - Hide details
-
p.
443
–473
(31)
Particle swarm optimizations (PSOs) are population-based methods inspired from the flight of a flock of birds seeking food. After the development of over 20 years, PSOs have become a major branch of evolutionary algorithms (EAs) and have been successfully applied to solve many science and engineering optimization problems. Most of PSOs are designed to search one solution of a problem. However, many science and engineering optimization problems are complex and multimodal in nature. More and more researches are aiming to identify multiple global and local solutions of complex multimodal problems, and several competitions in recent international conferences had been set up to encourage researchers to develop more effective and efficient algorithms for exploring multiple solutions. There are several techniques in the literature which can be used by combining with an existing EA to solve multimodal optimization problems. Those techniques are called niching. The most commonly used niching techniques are crowding, fitness share, clustering and species conserving. PSO-related methods for multimodal problems are reviewed in this chapter, including hybrid PSO with other EAs. Additionally, the multimodal functions, including some challenge composition multimodal functions, are listed as references for researchers to test their new algorithms. The species conserving PSO is described in detail and used to solve some multimodal engineering optimization problems to demonstrate the power of niching in exploring multiple solutions.
-
17 Decentralized control in robotic swarms
- + Show details - Hide details
-
p.
475
–507
(33)
Robotic swarms are groups of autonomous and self-organized mobile robots interacting under a communication network in order to accomplish cooperative tasks. This chapter will provide an overview on main outcomes on decentralized control in robotic swarms based on applications and the degree of autonomy in the view of stability and control theory. Based on application, we will categorize various problems in the area of robotic swarms such as swarming, formation, and consensus/rendezvous. First path planning and collision avoidance approaches for mobile robots will be introduced. Then, swarming and swarm formation of mobile robots as most important problems in control of multirobot systems will be investigated. Finally, the consensus and rendezvous as important problems in multirobot systems will be studied. In each category, existing structures will be classified and explained.
-
18 PSO in ANN, SVM and data clustering
- + Show details - Hide details
-
p.
509
–549
(41)
In this chapter, one gives an introduction to different kinds of particle swarm optimization (PSO) algorithms. One also introduces artificial neural networks (ANNs), support vector machines (SVMs) and evolutionary computing to show how PSO may be used to determine optimal parameters using an ANN or SVM regime, for classification of DNA strings. In addition, PSO is used in the design of an SVM-based clustering algorithm. Ant colony optimization (ACO) algorithms are also introduced in the chapter. Using ACO algorithms has been of great success to solve many discrete optimization and non-deterministic polynomial (NP)-hard problems, for instance the travelling salesman problem. The behaviour of ants is also used, for instance, to design an algorithm for data clustering. We want to develop later a similar application based on this clustering algorithm and compare it with the SVM one using PSO.
-
19 Modelling of interaction in swarm intelligence focused on particle swarm optimization and social networks optimization
- + Show details - Hide details
-
p.
551
–581
(31)
Swarm intelligence is an important and popular branch of computational intelligence. This technique is based on the analysis of the collective behaviour of swarms in nature and of social phenomena, and it is aimed to solve highly non-linear problems. The optimization performances of these techniques are highly affected by the specific choice of the working parameters. In this chapter, the modelling of interaction in swarm intelligence is done by means of different models, and the space of the working parameter is finally divided accordingly to the specific dynamic behaviour of the swarm for each point of this space. In this analysis, the attention has been focused in two optimization algorithms: the well-known particle swarm optimization and the recently developed social network optimization.
-
20 Coordinating swarms of microscopic agents to assemble complex structures
- + Show details - Hide details
-
p.
583
–612
(30)
This chapter addresses the problem of coordinating very large swarms of microscopic agents to assemble complex, hierarchically structured physical systems. The agents might be microscopic robots or genetically engineered microorganisms. The approach we use is a form of artificial morphogenesis, which studies the self-organized morphogenetic processes in the developing embryo, by which billions of cells cooperate to create physical form and abstracts these processes to control microscopic agents to assemble desired physical structures. We use an approach based on the description of morphogenetic processes by partial differential equations, which ensures that our morphogenetic algorithms will scale up to arbitrarily large swarms (millions or more). We present several simulation experiments demonstrating the coordination of massive swarms to construct complex objects.
-
Back Matter
- + Show details - Hide details
-
p.
(1)