Introduction To Swarm Intelligence PDF

3 Introduction to Swarm Intelligence Anand Nayyar and Nhu Gia Nguyen CONTENTS 3.1 Biological Foundations of Swarm Intelligence.................... 53 3.2 Metaheuristics.............................................. 56 3.2.1 The History of Metaheuristics....................... 56 3.2.2 Introduction to Metaheuristics....................... 57 3.2.3 Characteristics of Metaheuristics..................... 59 3.2.4 Classiﬁcation of Metaheuristics...................... 60 3.3 Concept of Swarm........................................... 62 3.4 Collective Intelligence of Natural Animals...................... 64 3.4.1 Principles of Collective Intelligence................... 65 3.4.2 Characteristics of Collective Intelligence............... 65 3.4.3 Types of Collective Intelligence...................... 66 3.4.4 Difference between Social Intelligence and Collective Intelligence............................. 68 3.5 Concept of Self-Organization in Social Insects.................... 68 3.6 Adaptability and Diversity in Swarm Intelligence................ 70 3.7 Issues Concerning Swarm Intelligence.......................... 71 3.8 Future Swarm Intelligence in Robotics – Swarm Robotics.................................................... 73 3.8.1 Advantages of Swarm Robotics...................... 73 3.8.2 Difference between Swarm Robotics and Multi-Robot Systems.............................. 74 3.9 Conclusion................................................. 75 3.1 Biological Foundations of Swarm Intelligence Swarm intelligence has attracted lots of interest from researchers in the last two decades. Many swarm intelligence-based algorithms have been intro- duced to various areas of computer science for optimization, gaining lots of popularity. The reasons behind the success of swarm intelligence–based algorithms are their dynamic and ﬂexible ability and that they are highly 53 54 Anand Nayyar and Nhu Gia Nguyen efﬁcient in solving nonlinear problems in the real world. Bonabeau, Dorigo, & Theraulaz (1999) deﬁned swarm intelligence as “The Emergent Collective Intelligence of groups of simple agents”. Swarm intelligence is regarded as a study of intelligent computational systems derived from “collective intelligence”. Collective Intelligence (CI) is deﬁned as the group intelligence that emerges from the cooperation or collaboration of a large number of swarm agents, acting out the same protocol within the same environment. Examples of homogeneous swarm agents are ants, ﬁsh, ter- mites, cockroaches, bats, and more. The two fundamental aspects, which are necessary properties of swarm intelligence are: self-organization and division of labour. Self-organization is regarded as a signiﬁcant property of natural systems; it is organization that takes place without any requirement of central coordinating authority to perform required tasks. Swarm agents exploit self-organization to attain the best work coordination, the agility to perform work at high speeds and, above all, fault tolerance. Self Organiza- tion is based on four fundamental elements: positive feedback, negative feedback, ﬂuctuations, and multiple interactions as deﬁned by Bonabeau et al. (1999). Positive feedback (ampliﬁcation) is basically deﬁned as the promotion of smart solutions by allocating more agents to the same work. Negative feedback (counterbalance) enables the swarm agents to avoid the same behaviour or involvement in the same state. Fluctuations are highly useful towards randomness, errors and random walks. Multiple interactions (sharing information) is the condition of sharing the infor- mation among all other agents of search area. There exists some con- tinuous agitation between positive and negative feedback, and it usually happens in various self-organizing conditions such as market analysis, the study of complex networks, neural networks, etc. The second prop- erty of swarm intelligence is termed division of labour, which is regarded as a parallel execution of various tasks by swarm agents. In general terms, swarm intelligence, which is regarded as sub-area of artiﬁcial intelligence (AI), is primarily concerned with a design and an implementation of intelligent multi-agent systems following the footsteps of behaviour of natural social insects and animals like ants, termites, bees, bats, cockroaches, ﬁsh, and more. Every single member of the colony is termed as unsophisticated, but they tend to accomplish com- plex tasks by cooperation with other swarm agents. Example: Ants roam in arbitrary fashion manner in an open environment searching for food, and after locating a food source, return to their nest to communicate with other members of the colony regarding the food source. Members of other colonies make a suitable and optimized path by laying pher- omone trail from their nest to the food source. Termites and wasps coordinate with each other to build sophisticated nests. The same is true for the ability of bees to orient themselves in an environment by generating awareness among other honey bees regarding a food source via the waggle dance. Introduction to Swarm Intelligence 55 The term swarm intelligence was ﬁrst coined by Beni (1988) with regard to cellular robotic systems, where simple agents utilize the principle of self-organization via the nearest-neighbour interaction. Swarm intelligence has led to the development of various models. From the point of view of computational intelligence, swarm intelligence models are computing models that have formulated algorithms for designing optimized solutions for distributed optimization problems. The primary objective of swarm intelligence is to design probability-based search algorithms. All the swarm agents working collectively have a number of general properties Bai and Zhao (2006). Communication among swarm agents is highly indirect and of short duration. Agents communicate in a distributed manner without any central coordinating authority. There is a high degree of robustness among agents working in an orderly fashion. Swarm intelligence models and methods are highly successful, especially in the area of optimization, which is suitable for various applications of computer science, industrial, and other scientiﬁc applications. Examples: student time table management systems, train transportation scheduling, the design of efﬁcient telecommunication networks, computational biology, neural networks, artiﬁcial intelligence, machine learning, and deep learning problems. The most basic optimization problem, which has led to the easiness of various test cases is the travelling salesman problem (TSP) Lenstra, Kan, and Shmoys (1985). The problem is simple: a salesman has to traverse a large number of cities, ensuring that the total distance between all traversed cities is minimal. It has been applied to various problems of biology, chemistry, and physics, and results were successful. In a general methodology, any optimization problem P can be deﬁned as integration of three components: S, Ω, f, where: S: A search space deﬁned over set of decision variables. These variables can deal with discrete or continuous optimization problems. Ω: The set of constraints on the variables. f: S → IR+ is the objective function used to assign a positive value to search element of S. The main objective of this chapter is to start with a brief discussion of the biological foundations and the concept of swarm intelligence. After that, various concepts revolving around swarm intelligence such as metaheuristics, collective intelligence of animals, and concepts revolving around swarm-self organization will be discussed. The chapter will embark a comprehensive coverage to the issues concerning swarm intelligence as well as concluding 56 Anand Nayyar and Nhu Gia Nguyen with a future direction of swarm intelligence by applying swarm intelligence to robotics i.e. Swarm Robotics. 3.2 Metaheuristics 3.2.1 The History of Metaheuristics Metaheuristics is a somewhat under-appreciated but widely used and adapted term. It is also regarded as a “search” or “optimization” algo- rithm. The true “metaheuristic” is regarded as a speciﬁc design pattern which instills knowledge and is applied to develop various optimization algorithms. Metaheuristics is a sub-area of “stochastic optimization”. Sto- chastic optimization is a combination of algorithms and techniques deploy- ing the highest degree of randomness to ﬁnd optimal solutions to hard problems. It is highly important to understand the history of metaheuristics (Sörensen, Sevaux, & Glover, 2018). Since the 1940s, many different metaheuristics have been proposed, and a few are in development today. Different problem-solving techniques have evolved since the inception of human beings, but using metaheuristics is regarded as scientiﬁc approach to solve the problems. The ﬁrst technique under metaheuristics was designed and developed by Igno Rechenberg, Hans-Pail Schwefel and their colleagues from Germany called it “evolutionary strategy” Osman and Laporte (1996). The main objective of this technique is to ﬁnd a solution to various optimization problems via computers. In the 1960s, Lawrence Fogel and his colleagues proposed “evolutionary programming” to use simulated evolution as learning process. In the 1970s, the genetic algorithm was proposed in a book titled Adaption in Natural and Artiﬁcial Systems (Holland, 1992). Later in 1970s, Fred Glover (1977) proposed the scatter search method, which created a signiﬁcant foundation for the design and development of various methods derived from recourse to randomization. These developments are called “evolutionary algorithms or computation”. The decades of the 1980s and 1990s saw a rapid development of various metaheuristic algorithms. Fred Glover, in 1980, proposed a metaheuristic algorithm called “tabu search” (Talbi, 2009), “simulated annealing” was proposed by S. Kirkpatrick, Gelatt, and Vecchi (1983). The artiﬁcial immune system (AIS) technique was developed by Farmer, Packard, and Perelson (1986). The major breakthrough came in the area of metaheuristics in 1992: Marco Dorigo proposed the ant colony optimization (ACO), based on a nature-inspired technique for optimization of problems, in his PhD thesis (1992). The technique is based on ants using a pheromone-based chemical trail to ﬁnd the Introduction to Swarm Intelligence 57 optimal path from their nest to a food source. In 1995, James Kennedy and Russel Eberhart proposed “particle swarm optimization (PSO)”. It is based on the movement of organisms such as a ﬂock of birds or a school of ﬁsh. The PSO algorithm works on the basis of a population called “swarm agents” within candidate solutions, known as particles. In 1994 in a book titled Genetic Programming (Koza, 1994), John Koza laid the foundations of the optimization technique called “machine learning,” which is highly utilized today in various branches of computer science. In 1997, R. Storn proposed “differential evolution” (Storn & Price, 1997), which is regarded as the best optimization technique in various applications, compared to genetic algorithms. Various signiﬁcant improvements have been seen from 2000 onward by various researchers proposing various metaheuristic-based algorithms. The following is the list of proposed algorithms. Signiﬁcant improvements have been observed since 1983 onwards. The following Table 3.1 enlists metaheuristic-based and swarm intelligence- based algorithms proposed by researchers since year 1983 to 2017. 3.2.2 Introduction to Metaheuristics The word “metaheuristics” is combination of two words “meta” and “heur- istics”. The Greek word “meta” means “beyond” or “upper level”. The word “heuristics” is derived from Greek word “heuriskein”, which means “to ﬁnd” or “to discover”. The term metaheuristics can be derived as “higher level discovery” which can perform better than “simple heuristics/discovery”. The word “metaheuristics” was coined by Dr. Fred Glover in his paper “Heuristics for integer programming using surrogate constraints” in Decision Sciences (Glover, 1977). In this article, he proposed “metaheuristics” as a powerful strategy which lays the foundation for other heuristics to produce optimal solutions as compared to normal solutions. Before his research, algorithms having stochastic components were called heuristics, but these days, they are termed “metaheuristics”. To date, the most clear and comprehensive deﬁnition of metaheuristics was proposed by Sörensen and Glover (2013), as: A metaheuristic is a high-level problem-independent algorithmic fra- mework that provides a set of guidelines or strategies to develop heuristic optimization algorithms. The term is also used to refer to a problem-speciﬁc implementation of a heuristic optimization algorithm according to the guidelines expressed in such a framework. The word “metaheuristic” is utilized for two different pruposes. One is a high-level framework in which varied concepts and methodologies are combined and lay a strong foundation for the development of various 58 Anand Nayyar and Nhu Gia Nguyen TABLE 3.1 Metaheuristics & Swarm Intelligence based algorithms Year Name of Algorithm Proposed by 1983 Simulated annealing Kirkpatrick et al. 1986 Tabu search Glover 1989 Memetic algorithms Moscato 1992 Ant colony optimization (ACO) Dorigo 1995 Particle swarm optimization (PSO) Kennedy & Eberhart 2000 Bacteria foraging algorithm Kevin Passino 2001 Harmony search Geem, Kim & Loganathan 2005 Artiﬁcial bee colony algorithm Karaboga Glowworm swarm optimization Krishnanand & Ghose Bees algorithm Pham 2006 Shufﬂed frog leaping algorithm Eusuff, Lansey & Pasha 2007 Imperialist competitive algorithm Atashpaz-Gargari & Lucas River formation dynamics Rabanal, Rodriguez & Rubio Intelligent water drops algorithm Shah-Hoseeini Monkey Search Mucherino & Seref 2009 Gravitational search algorithm Rashedi, Nezamabadi-pour & Saryazdi Cuckoo search Yang & Deb Group search optimizer He, Wu & Saunders 2010 Bat Algorithm Yang 2011 Spiral optimization algorithm (SPO) Tamura & Yasuda Galaxy based search algorithm Hameed Shah-Hosseini 2012 Flower pollination algorithm Yang Differential search algorithm (DS) Civicioglu 2013 Artiﬁcial cooperative search algorithm Civicioglu Cuttleﬁsh optimization algorithm Eesa, Mohsin, Brifcani & Orman 2014 Artiﬁcial swarm intelligence Rosenberg 2016 Duelist Algorithm Biyanto Killer whale algorithm Biyanto 2017 Rain water algorithm Biyanto Mass and Energy balances algorithm Biyanto Hydrological cycle algorithm Wedyan et al. Introduction to Swarm Intelligence 59 novel optimization algorithms. The second denotes speciﬁc implementa- tion of algorithm proposed on a framework to ﬁnd solution to a speciﬁc problem. According to Osman & Laporte (1996), Metaheuristics is formally deﬁned as an iterative generation process that guides a subordinate heuristic by combining intelligently different concepts for exploring and exploiting the search space; different learn- ing strategies are used to structure the information in order ﬁnd efﬁcient near-optimal solutions. In the last few decades, there has been signiﬁcant development and innovation of approximation solution methods – heuristics and metaheuristics. Various algorithms have been proposed on the basis of metaheuristics such as: simulated annealing (SA), tabu search (TS), the memetic algo- rithm (MA), the artiﬁcial immune system (AIS), ant colony optimization (ACO), genetic algorithms (GA), particle swarm optimization (PSO), and differential evolution (DE), which are utilized by researchers for opti- mizing and ﬁnding solutions to various problems of computer science. A metaheuristic algorithm is regarded as an iterative process that lays paths and innovates operations of sub-heuristics to deﬁne efﬁcient solutions. It manipulates a complete or incomplete single solution or set of solutions at each iteration. Today, the scope of metaheuristics has widened, and various methods have been proposed such as: ant colony systems, greedy randomized adaptive search, cuckoo search, genetic algorithms, differential evolution, bee algorithms, particle swarm opti- mization (PSO), etc. 3.2.3 Characteristics of Metaheuristics In the olden days, problem solving was done via heuristic or metaheuristic approaches – by trial-and-error methodology. Many important discoveries, even those still utilized today, are the result of “thinking outside of the box”, and sometimes merely arrived at by a simple accident; this approach is called heuristics. In our day-to-day life, we handle almost every problem via heuristics. But now, heuristics are being taken to the next level, i.e. metaheuristics. The major reason behind the popularity of metaheuristics is that all the algorithms are designed and developed by considering nature-based sys- tems, i.e., swarm agents, which include biological systems, and physical and chemical processes. The most important component of metaheuristics is that all the algorithms imitate the best features of nature. The two major components of all metaheuristic algorithms are: intensiﬁ- cation and diversiﬁcation, or exploration and exploitation. The 60 Anand Nayyar and Nhu Gia Nguyen intensiﬁcation, or exploration, phase revolves around searching the best possible solutions available and selecting the best solution among the available options. The diversiﬁcation, or exploitation, phase ensures that the search space is more efﬁciently explored. The overall efﬁciency of the algorithm depends on the balance of these two components. If there is a little exploration, the system will have limited boundaries and it will be difﬁcult to locate the global optimum. If there is too much exploration, the system will ﬁnd issues in reaching convergence, and the performance of search, in the overall algorithm will be reduced. The basic principle of best search is “only the best survives”, so a proper mechanism is required to achieve the best algorithm. The mechanisms should be run repeatedly in order to test the existing solution and locate new options to verify whether or not they are the best solutions. The primary foundations of metaheuristic algorithms are “nature based” and apply either a population or a single solution to explore the search space. Methods using single solution utilize local search-based metaheuristics such as tabu search and simulated annealing, which share the property of describ- ing a state in the search space during the search process. On the contrary, population-based metaheuristics, such as genetic algorithms, explore the search space through the evolution of a set of solutions in the search space. The following are some of fundamental properties which characterize metaheuristics in highly simple manner: Metaheuristics lay the stepping stone that “guides” the entire process of search. The ultimate goal is to explore the search space efﬁciently in order to determine the optimal solutions. Metaheuristic algorithms are approximate and non-deterministic in nature. Techniques integrating metaheuristic algorithms range from simple local search procedures to high-end complex learning processes. Metaheuristics are not problem-speciﬁc and avoid getting trapped in conﬁned areas of search space. Metaheuristic algorithms make use of domain-speciﬁc knowledge via heuristics and are controlled by upper-level strategy, and today’s meta- heuristics make use of search experience to achieve optimal solutions. 3.2.4 Classiﬁcation of Metaheuristics A metaheuristic algorithm can provide a highly optimized and efﬁcient solution to any optimization problem, but only if there exists a proper balance between the exploitation of the search experience and the search space exploration to identify the areas with high-quality solutions with Introduction to Swarm Intelligence 61 regard to problems. The only difference between various metaheuristic techniques is how they provide the balance. According to Talbi (2009), the following are different ways to classify metaheuristic algorithms: Nature-inspired versus non-nature-inspired algorithms The most active ﬁeld of research in the area of metaheuristics is design and development of nature-based algorithms. The most recent proposed meta- heuristics is “evolutionary computation-based algorithms”, which are based on natural systems. Examples include: simulated annealing, ant colony optimization (ACO), particle swarm optimization (PSO), and evolu- tionary algorithms. Non-nature-inspired metaheuristic algorithms include: tabu search (TS) and iterated local search (ILS). Population-based versus single-point search Another important basis that is used for classiﬁcation of metaheuristic algorithms is the total number of solutions used at the same time. Algo- rithms working on single solutions are termed as “trajectory methods” and include local search-based metaheuristics. Examples: tabu search, variable neighbourhood search, and iterated local search. Population-based methods are highly focused on the exploration of the search space. Examples: Genetic algorithms and particle swarm optimiza- tion (PSO). Dynamic versus static objective function Metaheuristics can also be classiﬁed on the basis of the methodology of which they make use; dynamic versus static objective function. Algorithms with a static objective function such as PSO keep the objective function in the problem representation. Algorithms with dynamic objective function like guided local search can modify the function during the search process. One versus multiple neighbourhood structures Most of the metaheuristic algorithms work on one single neighbourhood structure and don’t change their ﬁtness landscape topology during search. Example: iterative local search. Some metaheuristics make use of set of neighbourhood structures which can change the ﬁtness landscape topology during search. Example: vari- able neighbourhood Search (VNS). 62 Anand Nayyar and Nhu Gia Nguyen Iterative versus greedy Iterative metaheuristic algorithms are those that start from a particular set of solutions and keep on manipulating as the search process continues, such as particle swarm optimization (PSO) and simulated annealing (SA). Greedy metaheuristic algorithms are those that start from empty solu- tion, and at every stage a decision variable is assigned a value and is added to the solution set. Example: ant colony optimization. Memory Usage versus memory-less The most signiﬁcant parameter used to classify metaheuristic algorithms is memory usage or memory-less. Metaheuristic algorithms make use of search history, and it is important to know, whether they make use of memory or not. Memory-less algorithms are those that make use of Markov process to determine the next course of action in the current state. Example: simu- lated annealing. Memory-usage algorithms are those that keep track of all the moves and decisions undertaken, and they make use of memory. Nowadays, all the metaheuristic algorithms make use of memory, and they are termed powerful algorithms. Example: tabu search. 3.3 Concept of Swarm The concept of swarm is particularly a biological one and its deep roots can be found in ethology (the study of animal behaviour). Which has been engaged in since the nineteenth century. Ethology is a mixture of diverse ﬁelds, including zoology (classiﬁcation), anatomy (structure), and the study of ecosystems (context). Ethology brings together these three areas in order to understand how the living beings exist and interact with one another. Ethology involves not only studying speciﬁc animals, but also interactions within groups and between individuals, and also how they live with regard to environmental constraints. Ethology is primarily concerned with a study of natural living organisms such as ants, bees, ﬁreﬂies, bats, and many more. The study of social insects is somewhat complicated, but they make “intelligent social interactions cum structures” by performing division of labor, hierarchy of control, and task coordination. In ant colonies and bee colonies, there is ant queen or queen bee, respectively, as well as the proper top-down management of task allocation and all sorts of social functions, such as: army ants, worker ants, search ants; and likewise in the case of bees, onlooker bees, worker bees, etc. In ant colonies, various functions are performed like- foraging, pheromone split, optimal path trail. Other intelligent swarms also perform varied functions Introduction to Swarm Intelligence 63 like Nest building by wasps, coordinated ﬂashing by ﬁreﬂies and waggle dance in case of honey bees. In the same manner, the study of bird ﬂocking is another example of how efﬁcient organization happens without any sort of centralized control. It is a combination of the ethology and computer science which leads to the study of behaviour of birds and ﬁnding suitable applications for proposing solutions to complex problems. Swarm (Glover, 1977; Lévy, 1997) is generally regarded as group of similar animals having qualities of self-organization and decentralized control. According to Bonabeau et al. (1999) the following are typical character- istics of a swarm: A swarm consists of many individuals working collectively and has the characteristic of self-organization. Individuals of swarm are homogeneous (identical) such as a robotic swarm or some species of same animals. Individuals of the swarm, when compared with the abilities of whole swam, are of limited intelligence and possess fewer capabilities. The swarm of combined individuals is much more powerful than the individual members. Individuals in a swarm act and perform their respective tasks as per the rules and tasks allocated. The rules sometimes create complex beha- viour as in bird ﬂocks, where each individual stays within a certain distance to its neighbouring bird and ﬂies slightly to the rear of it. According to Bonabeau and Meyer (Bonabeau & Meyer, 2001) the follow- ing are the three main reasons of success of swarms: 1. Flexibility 2. Robustness 3. Self-organization Ants are highly ﬂexible living organisms in terms of adapting to changing environments, and ants soon ﬁnd an optimal path between a food source and the nest if any obstacle arises. Due to a large number of individuals in a swarm, the swarm has the characteristic of robustness. The swarm as a whole continues to exist, even if single individuals fail or become extinct. Self-organization is a property of many complex systems that consist of a great amount of interacting subsystems. One characteristic of self-organization is a spontaneous forming of structures and patterns under speciﬁc condi- tions,wherefore it is suitable to start analyzing self-organizing processes by studying these so-called “pattern formations”. In the honeybees’ colony it 64 Anand Nayyar and Nhu Gia Nguyen is easy to ﬁnd a multiplicity of such patterns. The organization in the hive arises from the partial systems as well, because the co-operating bees (the sub-systems) give structure to the system though they neither have knowl- edge of the global situation nor having a blueprint for the complete pattern in mind. Each individual works (blind for the holistic pattern) to the local rules, the global pattern results from the interaction of these single indivi- duals. Every single bee has the ability to perceive only a little part of the entirety of inﬂuencing stimuli, but the whole of bees appears as a “collective intelligence”. 3.4 Collective Intelligence of Natural Animals The concept of “collective intelligence” is very hard to understand. In order to develop and innovate information systems, it is highly important to gain complete control over the environment. The term “collective intelligence” is related to “intelligence” as a phenomenon. In order to develop a theory of collective intelligence, it is highly desirable to under- stand the general terminology of intelligence. A system is said to have “collective intelligence” when two or more “intelligent” sub-systems combine and interact with each other in an intelligent manner. The word intelligence is closely related to intelligent behaviour. Intelli- gent behaviour is regarded as various actions and results in response to queries to ensure the system’s reliability. Collective intelligence systems must have intelligent behaviour. The most obvious examples of collective intelligence are collective efforts of social organisms like ants, bees, ﬁsh, wasps, and termites when doing a particular task like collecting food, building nests, etc. Collective intelligence has two dimensions: the quality of intelligence of individual swarm agents operating in an environment, which is also termed “bio-intelligence”, and the number of swarm intelligence, which can range from billions to trillions, depending on the society. In addition to these, collective intelligence is also enforced by one more dimension, which involves a methodology of the systems integrated with and operat- ing in an environment. The concept of collective intelligence of an insect is not determined by its genetic behaviour, rather it emerges from continuous interactions of a large number of individuals that exhibit simple, stochastic behaviour and limited knowledge of the environment. Examples: the collective intelli- gence of ants – how the ants act as workers to locate the food dynami- cally in an environment, then come back to the nest, and other ants follow the trail from the nest to the food source in efﬁcient manner. The collective intelligence of bees – the waggle dance, which provides the Introduction to Swarm Intelligence 65 direction and distance from the nest of food, and its quality. The most important point is how chemical messages change the operating environ- ment of insects in colonies, and how they repeat the behaviour to accom- plish a particular task. Therefore, collective behaviour is simply a sum of individual actions; it shows new characteristics that emerge from self-amplifying interactions among individuals and between individuals and an environment. Another important aspect in collective intelligence is self-organization – how an individual swarm agent knows the work to perform without any coordinating authority. 3.4.1 Principles of Collective Intelligence According to Don Tapscott and Anthony D. Williams (2008), collective intelligence is also termed “mass collaboration”. The following are the four principles of collective intelligence: Openness: The foremost principle of collective intelligence is sharing ideas. All the swarm agents share common information with their respective colonies, which provides them with an edge and more beneﬁts from sharing information, and agents gain signiﬁcant control and improvement via collaboration. Peering: Peering lays a strong foundation for “self-organization”, a unique style of production that works more effectively than a hier- archy for performing all sorts of complex tasks like ant trailing, optimal route selection, etc. Sharing: With the sharing of ideas among swarm agents, such as the waggle dance of honeybees, the glowing capacity of ﬁreﬂies, etc., the operations in the colonies become more effective and easy. Acting globally: With global integration, there exists no geographi- cal boundaries, allowing swarm agents to operate freely in an environment and be more effective in collaborating with other agents for food search, trailing, and food collection from source to nest. 3.4.2 Characteristics of Collective Intelligence The behaviour and work of colonies of social insects integrate many characteristics of collective intelligence and are listed here (Wolpert & Tumer, 1999): 1. Flexibility: The environment changes dynamically, so individuals should adapt to changing environmental conditions via an 66 Anand Nayyar and Nhu Gia Nguyen ampliﬁcation by positive feedback so that the entire system adapts to new circumstances. 2. Complexity: The entire colony behaviour adapts to an ever-changing environment, which could be quite complex in nature, and also involves solving the problem of coordination among different swarm agents to operate effectively in the environment. 3. Reliability: The system can function in an efﬁcient manner even though some units fail and even without any central coordination utility to reassign duties in colonies. The following are some of the real-time examples involving distributed intelligent computational systems, which require a centralized communica- tion and can operate effectively using collective intelligence. Control systems for operating communication satellites (GPS satel- lites, weather forecasting satellites, or military satellites) for collecting and communicating scientiﬁc data. Control systems for effective routing of data in large communication networks (WAN or MAN). Parallel algorithms for solving complex optimization numerical pro- blems such as scientiﬁc calculations, mainframe computing, or paral- lel systems for effective operations. Trafﬁc control systems for large cities with an enormous number of vehicles operating at any point of day. Information grid control. Control of nuclear reactors or chemical plant for all sorts of logistics and control operations. Management of power electronics in large power grids based on wind mills, hydro power, etc. 3.4.3 Types of Collective Intelligence The research on collective intelligence revolves around the investigation for the design of intelligent infrastructures that enable agents in colonies to think and act intelligently and intriguingly as compared to individual agents. The following are the four different forms of collective intelligence which co-exist in natural animals and humans (Lévy, 1997): 1. Swarm 2. Original 3. Pyramidal 4. Holomidal Introduction to Swarm Intelligence 67 Swarm collective intelligence Swarm collective intelligence applies to a large number of individuals, from a few hundred to thousands to billions. Individuals don’t have a big difference from one another via design or by context. Their individual margin of actions remains limited and in most of the cases remains predictable. Swarm collective intelligence can show immense adaptive and learning capacities. Examples: various social insects (ants, bees, termites, wasps), schools of ﬁsh, ﬂocks of birds, and even trafﬁc jams. Original collective intelligence Original collective intelligence consists of small groups composed of spe- cialized individuals such as wolf swarm, dolphin swarm, cat swarm, monkey swarm, etc. Pyramidal collective intelligence Pyramidal collective intelligence comprises a hierarchy-based intelli- gence structure, which provides the best coordination and effectively utilizes the power of the masses. It is mostly used in human organiza- tions because of their civilization. In civilization, a human intelligence has deﬁned criteria, like: urban concentrations, work specialization, accounting and memorizing, large geographical area, and centralized power. Pyramidal collective intelligence has the following four dynamic princi- ples (Bastiaens, Baumöl, & Krämer, 2010): 1. Labor Division: Everyone in civilization has a predeﬁned role and can be interchangeable. 2. Authority: Determines the rules; assigns rights and prerogatives. 3. Limited Currency: Medium of exchange and a store of value. 4. Standards and Norms: Circulation and interoperability of knowledge within the community. Holomidal collective intelligence It is one kind of intelligence that is at a developing stage and succeeds pyramidal collective intelligence as it has become powerless to address the tomorrow’s high-stake complexity of intelligence. Holomidal col- lective intelligence is showing an enormous amount of growth in various forms of technical and scientiﬁc applications, and innovations in arts. 68 Anand Nayyar and Nhu Gia Nguyen 3.4.4 Difference between Social Intelligence and Collective Intelligence Collective Intelligence, as mentioned above, highlights the two main points: First, there exist some species of natural animals, whose collective intelligence is regarded as much more sophisticated and intelligent than human beings’. Second, some animals, such as dolphins and monkeys, share a sense of group behaviour, i.e., social intelligence. So, it is highly important to mention a clear distinction between two terms, “social intelligence” and “collective intelligence”. Social intelligence is regarded as an advanced form of intelligence, which makes an animal capable of performing complex behaviour patterns to analyze and respond to situations correctly with other members in the group. Social intelligence is regarded as a situation in which mammals behave in a way that is termed as “collective consciousness”. Collective intelligence is also regarded as an advanced intelligence, in which the group intelligence of individual swarm agents copes correctly with a social and physical as well as biological environment. Ants have a higher degree of collective intelligence as compared to social intelligence. Social intelligence has a genetic capability to respond to all sorts of signals from conspeciﬁcs. The low degree of social intelligence of ants allows interlopers to confuse the ants completely. Example: Beetle begging behaviour causes ants to regurgitate droplets of food for them. The parasites can even perform the best mimicry of ants, not only in terms of behaviour but also with pheromone interference, to take food to their nests. Low social intelligence can also be found in bee hives. Italian and Australian bees share almost the same signals and confuse each other. Although, social insects that rank very low in social intelligence rank on the top in collective intelligence. Collective intelligence is mostly based on the mutual understanding and self-organization behaviour of agents. 3.5 Concept of Self-Organization in Social Insects In recent years, the concept of self-organization (Bell & Cardé, 2013; Bonabeau, Theraulaz, Deneubourg, Aron, & Camazine, 1997) has been used to derive the emergence and maintenance of complex stable states from simple component systems. It was primarily introduced with a rele- vance to physics and chemistry to deﬁne how various microscopic processes give birth to macroscopic structures in out-of-equilibrium systems. The theory of “self-organization” can even be further enhanced to ethological systems like social insects and animals (ants, bees, bats, ﬁsh, etc.) to demonstrate how the collective behaviour, which is complex, can emerge from interactions among individuals that exhibit simple behaviours. Introduction to Swarm Intelligence 69 Self-organization (Uyehara, 2008) is regarded as a process in which complex patterns originate without any sort of directions internally or any sort of supervising source. The self-organization is observed in varied systems like phase-transitions, chemical reactions, body muscles, and schools of ﬁsh. Self-organizing systems, with reference to biology, are composed of group of individuals working collectively to create complex patters via positive and negative feedback interactions. Various social insects’ beha- viour is derived from self-organization, as the social insects don’t have a cognitive power to generate their observed complex structures and activ- ities. Examples: ant foraging, honey bee thermoregulation, ant corpse- aggregation, etc. Examples of self-organization in the real world: The example of sporting oarsmen in a rowing team working collectively by pulling up oars in perfect synchronization with each one another with proper adjustments and same frequency. The rhythmic contractions of muscle ﬁbers in the heart is the best example of self-organization. The concept of self-organization in physical systems differs from that in biological systems in two ways: Complexity of sub-units: In physical systems, the sub-units are inanimate objects. In biological systems, there is some greater inher- ent complexity as sub-units are living organisms like ants, bees, ﬁsh, etc. Rules governing interactions: In physical systems, patterns are cre- ated via interactions based on physical laws. Biological systems do have behaviours based on laws of physics, in addition to physiologi- cal and behavioural interactions among living components. The following are the four constituents of self-organization in social insects: Positive feedback (ampliﬁcation): Simple behavioural patterns that leads to a creation of structures. Examples: recruitment and reinforce- ment. In ants, a food source is determined randomly by ants search- ing in environment and then a trail is laid and is followed from a source to the nest; indicating the location of a food source by honey bees via the waggle dance. Negative feedback counterbalances positive feedback and stabilizes collective patterns like saturation, exhaustion, and competition. Examples: foragers, food source ﬁnish, food source crowding, etc. Self-organization is based on the ampliﬁcation of ﬂuctuations like random walks, errors, random task-switching, etc. Example: loss of foragers in an ant colony. All self-organization relies on multiple interactions. 70 Anand Nayyar and Nhu Gia Nguyen 3.6 Adaptability and Diversity in Swarm Intelligence Swarm intelligence is the collective behaviour of decentralized, self-orga- nized systems, natural or artiﬁcial (Bonabeau et al., 1999). The emergent collective intelligence of groups of simple agents is termed swarm intelli- gence. Individually, these agents are not intelligent but they have self- organization and division of labor in their nature. Collectively, these agents follow simple rules while interacting with others without any centralized control. Adaptation and diversity in swarm intelligence-based algorithms can be seen as a proper balance between intensiﬁcation and diversiﬁcation, con- trolling and ﬁne-tuning of parameters, and the identiﬁcation of new solu- tions and the precise aggregation of uncertainty. The success of a swarm intelligence-based algorithm depends on two contradictory process: exploration of search space and exploitation of best feasible solution. The ﬁrst process is called diversiﬁcation, and the second is known as intensiﬁcation, both are driving forces for swarm intelligence. Most of the population-based techniques are diversiﬁcation oriented, whereas single solution-based techniques are intensiﬁcation oriented. The local search strategies lead to better intensiﬁcation, and random search strategies lead to better diversiﬁcation. The main criterion that one needs to deal with while initializing a population-based swarm intelligence strategy is diversiﬁcation. A weakly diversiﬁed initial population leads to premature convergence. Initialization strategies with decreasing diversity capabilities are as follows (Talbi, 2009): parallel diversiﬁcation, sequential diversiﬁcation, the quasi-random approach, the pseudo-random approach, and the heuristic approach. Thus, it is essential to maintain a balance between intensiﬁcation and diversiﬁcation. These, swarm-based algorithms have some parameters that directly or indirectly control the diversity of a population. A ﬁne-tuning of these control parameters is highly required along with adaption to the environment. The crucial model of adaptation is a balance between intensiﬁcation and diversiﬁcation in swarm intelligence, and diversity is inherently associated with it. A problem-speciﬁc search process with strong exploitation leads to an intensive search and concentrated diversity that results in a rapid loss of diversity and subsequently premature convergence. While completely randomized process can enhance exploration and locate more diversiﬁed solutions. However a higher degree of diversity may mislead the search process and results in very slow convergence. That’s why it is very crucial to make this search process adaptive. Most of the swarm-intelligence-based algorithms use a real number solution vector. The population size in these algorithms may be static or capricious. A varying size of population can maximize performance of algorithm. The adaptation has the capability to adjust algorithm-dependent parameters as a requirement of environment. Introduction to Swarm Intelligence 71 Likewise, a change in the radius of the search space, according to the iteration number, can lead to better search efﬁciency. This type of para- meter tuning is known as a real parameter adaptation (Yang, 2015). Bansal et al. (2014) proposed a self-adaptive ABC with adaptation in the step size and limit parameter. In the same way, the diversity in swarm-intelligence-based algorithms also takes various forms. Most of the swarm-based algorithms update a solution using speciﬁc equations. These equations have some random components and steps. These random components control the size of steps, and the performance of an algorithm depends on the step size. If step size is too large, then there are chances to skip true solutions, and if the step size is very tiny, then it may lead to a slow convergence. Thus, it is very crucial to maintain a proper amount of randomness. In order to maintain a proper diversiﬁcation, Bansal et al. (2013) added a local search phase in ABC algorithm. Adaptation and diversity in swarm intelligence are also related to the selection solution, i.e., which solution is to be forwarded for the next iterations and which one will be abandoned. Population-based algorithms perform this task using a ﬁtness function. A highly ﬁtted solution will be selected and the worst-ﬁtted solution discarded during this selection process. In this case, a good adaptation policy is highly required can also maintain the diversity of solutions. A self-balanced particle swarm optimi- zation developed by Bhambu et al. (2017) allows one to maintain a proper balance between the diversiﬁcation and convergence abilities of the popu- lation. Xin-She Yang (2015) discussed adaptation and diversity, exploration and exploitation, and attraction and diffusion mechanisms in detail. It is not possible to study adaptation and diversity independently; they are interlinked with each other, and it is essential to retain an appropriate balancing between them. 3.7 Issues Concerning Swarm Intelligence Swarm intelligence has become an important subject these days for addressing many issues in the research of engineering problems. It has wide applications in wireless communications, robotics, surveillance, bio- medical applications, etc. As part of research it is very important to understand issues that arise while adopting the swarm intelligence prin- ciples and applying them to the subject considered. The modern engineering applications adapt the swarm intelligence for improving the overall reliability of the system performance. Swarm intelli- gence is the technology in which many members are associated in order to obtain the prime objective of overall standardization of the system (Banzi, Pozo, & Duarte, 2011). Obviously, when many members are associated to 72 Anand Nayyar and Nhu Gia Nguyen each other, there are chances for security issues related to the information. The intruder’s association with the swarm may cause serious issues in data communication between members and may corrupt the data (Dai, Liu, & Ying, 2011). It is very important to think about the security challenges that may arise in the areas like communications, robotics, and cloud-computing-based Internet of Things in particular. Swarm intelligence is implemented based on the data accumulated from many swarm members associated in the network. So, because the information must be carried from one member to others, we should consider security. One should consider using a special type of encryption and decryption codes for encoding and decoding data that is communicated over the channels between swarm members; other- wise, an intruder might change or control the data. In mobile sensor networks like MANET, a set of the devices or nodes is connected by a wireless network. The ﬂying robots, such as drones, are associated with sensor networks used for some security applications and use swarm intelligence for the association and effective decisions. The communication in the preceding applications is through a wireless medium. Here, swarm intelligent networks go beyond the capabilities of mobile sensor networks because the latter are not capable of duplicating a developing behaviour of swarm intelligence networks. The conﬁdentiality of the system members and their data distributed in the swarm is becoming an important issue. The protection of the data is a ﬁrst and foremost priority in the swam-intelligence-based applications. The next concern is to protect the integrity of the data. Data communicated among the members can be accessed only in authorized ways. Service availability is also an important issue for applications of swarm intelli- gence. Denial of service (DoS) is about losing the accessibility of service. It is very important that most of the security issues arise are same as we see in other systems. The resource constraints are more important in the case of swarm intelligence. The smaller the system that is considered, the tougher the security is for it. This is because of the resource constraints such as memory, communication bandwidth, power of computation, and energy. In the robotic swarm, if a certain attack on a particular robot happens, then the behaviour of an entire swarm may be affected. Suppose the robot is inﬂuenced and tampered with, then reintroduced into the swarm. An attacker may then be inﬂuencing the complete swarm. Control- ling an object is a very sensitive issue in swarm intelligence. Because there is no central control in the swarm intelligence concept, members of the swarm are solely dependent on others’ intelligence. The identity and authentication of the robot play a major role in the swarm intelligence. Different authentication schemes are in use such as group identity and individual identity. Intruder identiﬁcation in the swarm is very important. The intruder in the group can be identiﬁed easily. The abnormal behaviour of a member as Introduction to Swarm Intelligence 73 compared to other members’ behaviour shows the difference. Once the intruder is identiﬁed, it must be segregated from the system. Finally, a swarm member should have efﬁcient learning ability. 3.8 Future Swarm Intelligence in Robotics – Swarm Robotics Swarm robotics (Şahin, 2004; Brambilla et al., 2013; Gogna & Tayal, 2013) is regarded as a novel approach that is concerned with the coordination and cooperation of a large number of simple and powerful robots, which are autonomous, not even controlled centrally, capable of local communication and fully operational on the basis of the biological approach. The main characteristics which make up a swarm robotic system are: Autonomous approach. Operational in speciﬁc environment with ability to modify themse- leves as per changing environmental conditions. Sensing and communication capabilities in stored memory. No centralized controlling mechanism and global knowledge. Cooperation among other robotic systems to accomplish tasks in coordinated manner. In order to elaborate further, regarding deﬁnition of swarm robotics, we can split an entity as follows: Machine: Entity having mechanical operational behaviour. Automation: Entity having capability of informational behaviour, i.e., information transfer as well as processing. Robot: Mechanical automation, i.e., an entity having both mechanical and information behaviour. 3.8.1 Advantages of Swarm Robotics In order to understand the concept and advantages of swarm robotics in more deep manner, we compare advantages of swarm robotics with a single robot (Tan, & Zheng, 2013): 1. Accomplishing a Tedious Task: In order to accomplish a tedious task, single robot design and development can lead to a complicated structure and require high maintenance. A single robot can even face some problems with component failure and if, at any point of 74 Anand Nayyar and Nhu Gia Nguyen time, a single component fails, the entire robot can stand still and task is halted. As compared to single robot systems, swarm robotics can perform the same task with a high agility in less time with error- free operation and with less maintenance. 2. Parallel Task Execution: A single robot can do one single task at a time like a batch processing system in computer. As compared to this, swarm robotics have high population size in which many robots can work at single point of time accomplishing multiple tasks in a coordinated manner. 3. Scalability: Swarms have local interaction in which individuals can join or quit a task at any point of time without interrupting the whole swarm. The swarm can easily adapt with environmental change and re-allocate units from the task to perform external operations. 4. Stability: As compared to single robot system, swarm robotics are much stable and reliable, and their work is even not affected when a single swarm quits work. The swarm robotic system will keep on working even with few swarms, but having few swarms will impact the overall performance and cause task degradation. 5. Economical: When building an intelligent self-coordinating swarm robotic structure, the cost will be much lower with regard to design, manufacturing, and maintenance as compared to single robot. Also, swarm robots can be produced in a mass manner, whereas a single robot development is a high-precision task and takes much more time. 6. Energy Efﬁcient: As compared to single robot system, swarm robotics are smaller and highly simple in operation; therefore, the energy consumption cost is far less as compared to single robot taking into consideration the battery size. Swarm robots can operate for a large time, doing all sorts of complex tasks as compared to a single robot system, which requires battery recharging after a cer- tain period. Considering all the beneﬁts of swarm robotics, as mentioned above com- pared to a single robot system, swarm robotics can be applied to high-end applications such as military applications, disaster relief operations, mining, geological surveys, transportation, and even environmental mon- itoring control. 3.8.2 Difference between Swarm Robotics and Multi-Robot Systems The following Table 3.2 highlights the differences between swarm robotics and multi-robot systems:

Introduction To Swarm Intelligence PDF

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue