Swarm Intelligence: An Overview

Swarm Intelligence: An Overview

Pranjali Rathee

Dept. of IT,

Indira Gandhi Delhi Technical University for Women New Delhi, India

Abstract Swarm Intelligence is a sub-discipline of Artificial Intelligence. The term Swarm Intelligence was introduced by Gerardo Beni and Jing Wang in the year 1989 [1]. It deals with both natural and artificial systems which are composed of multiple individuals or agents. These systems display the properties of self-organisation and de-centralized control. The term evolved with various experiments conducted on populations of natural organisms like the ants, termites, fishes, birds and many more. Swarm Intelligence can be used to solve many real world problems including maximisation and minimisation problems. This paper focusses on swarm intelligence techniques inspired by natural organisms.

KeywordsSwarm Intelligence; Meta-heuristic; Optimization

1. INTRODUCTION

   Swarm Intelligence systems deal with multiple agents communicating with each other in an artificial environment. The different agents communicate with each other and also with the environment. The agents can be homogeneous or heterogeneous. The homogeneous agents share various logical and behavioral properties. The heterogeneous agents differ in these properties. When a system is composed of heterogeneous agents; its functionality can be termed as similar to the common master slave systems. The heterogeneous systems do not fulfill the property of de-centralized control. In the case of homogeneous agents the property of de-centralized control also holds well with self-organization.

   With the aid of local interaction between the agents, the entire system shows an intelligent behavior. This intelligent behavior is a combination of the individual decisions taken by the agents under varied constraints.

   As an example we can consider the situation where a restaurant wants to fulfill the demands of various customers for delivery of their orders. There is a time limit for delivering the orders which if not fulfilled will incur loses to the restaurant. In this situation the constraints present are: the number of orders from customers, number of delivery agents, number of delivery vehicles available, the number of orders a single delivery agent can fulfill and also the real time traffic conditions on the road. All the above given constraints need to be managed well to increase the profits of the restaurant. We can visualize the above problem as shown in Figure 1. For solving the above problem we need to find the shortest and fastest route to a customers place. Software agents can be used for fulfilling this purpose. Before using the software agents we need to collect the map of the whole area where the delivery process will take place. After doing so we can make the different software agents traverse the entire map using random decision making. In the first such traversal the various agents will find a set of

   routes covering the locality. In the present scenario the software agents take care of two constraints while measuring the routes. The first constraint is the maximum number of customers an agent can service and the second constraint would be the maximum time limit for servicing the customers.

   Fig. 1: Order Fulfilment

   As a number of software agents are simultaneously constructing solutions for the problem, the agents will come up with different solutions to the problem. After each such iteration, the solutions of various agents are measured for their quality. The best solution is chosen and is given a higher weight. The next iteration continues with the previous weighted solutions. This process goes on till the optimum solution is obtained.

   The above example explains the use of multiple agents in reducing the complexity of the problem and finding a solution by combining the solutions obtained by different agents.

2. DIFFERENT SWARM INTELLIGENCE TECHNIQUES

   There are various different swarm intelligence techniques. All these techniques are influenced by some biological population and its interaction mechanism. These techniques are also called as Meta-heuristics [2]. Meta-heuristics are strategies used to find an optimal i.e. the best solution to a problem with

   limited information and limited time. Meta-heuristics are problem independent. The various Swarm Intelligence Techniques are:-

   1. Ant Colony Optimization

      This algorithm is based on the inside interactions of an ant colony when the ants are foraging (looking for food). Ant Colony Optimization (ACO) is a probability based approach. It was developed by Prof. Marco Dorigo in his Ph.D. thesis in 1992 [3]. This algorithm requires a graph before computation of the optimal solution. The algorithm has many variants like the elitist ant system, max-min ant system, rank based ant system and recursive ACO. The algorithm offers an inherent parallelism. It is efficient for routing problems and can be used in real time situations. The optimal solution while using this algorithm is guaranteed.

   2. Particle Swarm Optimization

      Particle Swarm Optimization (PSO) is based on the behavior of a flock of birds or a fish school. It was developed by Dr. Eberhart and Dr. Kennedy in 1995 [4]. In PSO an optimized solution to a problem is found by improving the quality of an initial solution. The initial solution is called the candidate solution. In PSO each candidate solution is termed as a particle. The particles traverse the search space according to an equation which is based on the position and velocity of the particle. The particle traversal also depends on the best positions on the search space. PSO can search for the optimal like solution in very large search spaces. Guarantee of finding the optimal solution is not there. This algorithm has been successfully applied in various fields like optimization problems, artificial neural networks and fuzzy controllers. Example of application of PSO:-

      Let us suppose that a group of students are searching for a way out of a dense forest. There is only one exit from the forest. The students dont know where the exit is but the relative distance to the exit is known. Each student in the problem space can be termed as a particle. As such each particle is assigned a position and velocity. The velocity of each particle is dependent on the relative position to the exit point. All the particles in the problem space follow the particle with the largest velocity and the least relative distance.

   3. Artificial Bee Colony Algorithm

      It imitates the foraging behavior of bees. It is also called the ABC algorithm. It was proposed by Dervis Karaboga in 2005 [5]. The honey bee colony has three different types of bees with different functions. The three types of bees are employed bee, onlooker bee and scout bee. An assumption is made that the number of employed bees is same as the number of food sources i.e. the solutions. The employed bee without a food source is termed as the scout. In the initial phase every employed bee is associated with a food source and the employed bee measures the quality of the food source. After determining the quality of the source the employed bee performs a waggle dance in its hive [5]. The waggle dance gives information to the onlooker bees on the quality, distance and direction of the food source. After this waggle dance the onlooker bees exploit the location with highest quality of food sources. The scout bees search for new food sources. The ABC algorithm has been used in the areas of structural

      optimization, brain image classification and face pose estimation

   4. Firefly Algorithm

      It is inspired by the flashing behavior of the fireflies. The fireflies use flash to attract other fireflies. Fireflies are insects that live in the tropical environment. They produce yellow, green and pale red lights. This algorithm was developed by Xin-She Yang in 2008 [6]. The light intensity of each firefly is proportional to the quality of the solution. Each firefly moves towards brighter ones. The firefly algorithm is used in image processing, antenna design, structural design, scheduling and dynamic problems.

   5. Cuckoo Search

      This algorithm was inspired by a special type of parasitism of the cuckoo birds. It was developed by Xin-she Yang and Suash Deb in 2009 [7]. The female cuckoo bird lays her eggs in another birds nest. If the host bird discovers that the eggs are not hers then two possibilities are there. Either the host bird will throw away cuckoos eggs or it will build its nest in another location. A probability is associated with the host bird to discover alien eggs. Each egg in the nest either of the host bird or the cuckoo represents a unique solution. As such the above search procedure can be used to find an optimal solution to a problem. Cuckoo search is used in spring design, welded beam design, wireless sensor networks, software testing and neural networks.

   6. Bat Algorithm

      This algorithm was developed by Xin-She Yang in 2010 [8]. This algorithm imitates the echolocation behavior of micro- bats. Echolocation also known as BIO-SONAR is the biological SONAR (sound navigation and ranging) used by animals. Animals emit calls to the environment and receive the echoes of the calls. The echoes of the calls are used are used to identify the various objects and find out there location. Micro-bats are those species of bats that use echolocation. The algorithm uses virtual bats to find solutions to various problems. Each virtual bat will fly randomly with certain velocity. Each bat is also associated with three parameters that change constantly- frequency, loudness and pulse emission rate. The virtual bats use the echolocation mechanism to sense the distance from a solution. This algorithm has been used in engineering design, classification of gene expressions and energy modelling.

   7. Grey Wolf Optimizer

      This algorithm imitates the leadership and hunting behavior of grey wolves. It was developed by S. Mirjalili, S.M. Mirjalili and A. Lewis in 2014 [9]. Four types of grey wolves are used in this algorithm. They are alpha, beta, delta and omega. Grey wolf is a member of the Canidae family. They live in a group of 5-12. The male and female leader of the group is called alpha. The alphas decisions on the hunting, sleeping time etc. are dictated to the other group members. The beta wolves help the alpha wolves in making decisions. The omega wolf is the servant. Elders, scouts and care takers wolves are called deltas. The grey wolves follow three main steps for hunting:-

      • Tracking, chasing and approaching the prey

        Table 1: Comparison of Techniques

        Swarm Intelligence Technique	Year	Developer	Based on	Usage	Convergence to optimal solution	Homogeneous / Heterogeneous
        Ant Colony Optimization	1992	Prof. Marco Dorigo	Foraging behavior of Ant Colony	Routing Problems, Real Time situations, Scheduling, Assignment, Image Processing	Yes	Homogeneous
        Particle Swarm Optimization	1995	Dr. Eberhart and Dr. Kennedy	Flock of Birds or a Fish School	Optimization problems, Function optimization, Artificial neural networks, fuzzy controllers	No	Homogeneous
        Artificial Bee Colony Algorithm	2005	Dervis Karaboga	Foraging Behavior of Bees	Structural Optimization, Brain Image classification, Face Pose estimation	Yes	Heterogeneous
        Firefly Algorithm	2008	Xin-She Yang	Flashing behavior of the Fireflies	Image processing, antenna design, structural design, scheduling, dynamic problems	Yes	Homogeneous
        Cuckoo Search	2009	Xin-She Yang and Suash Deb	Parasitism of the Cuckoo birds	Spring design, welded beam design, wireless sensor networks, software testing, neural networks	Yes	Homogeneous
        Bat Algorithm	2010	Xin-She Yang	Echolocation behavior of Micro-bats	Engineering design, classification of gene expressions, energy modelling	Yes	Homogeneous
        Grey wolf optimizer	2014	S. Mirjalili, S.M. Mirjalili and A. Lewis	Leadership and Hunting behavior of Grey wolves	Optical engineering, tension/compression spring, welded beam, pressure vessel designs	Yes	Heterogeneous

        Harassing the prey until it stops moving (Circling around the prey)

      • Attacking the prey

   This algorithm has great use in the field of optical engineering. The behavior of grey wolves is mimicked to solve optimization problems. The best solution is termed as alpha and the subsequent solutions are named as beta and delta.

3. COMPARISON OF VARIOUS APPROACHES

   All the above given swarm intelligence techniques have two things in common: – all of them use a collective approach and all of them use a combination of individual solutions to find the best solution. As such we can compare the various approaches on factors like year of development, the biological population that inspired the approach and the applications of the techniques. The table given above gives a comparison of all the given techniques.

4. CONCLUSION

This paper focused on the different Swarm Intelligence techniques. All swarm intelligence techniques that mimic the collective behavior of biological organisms are used widely to solve a variety of problems. They can be used in disciplines of optical engineering, mechanical engineering, image processing, artificial intelligence and software testing.

REFERENCES

1. M. Mahant, B. Choudhary, A. Kesharwani, and K.S. Rathore, A Profound Survey on Swarm Intelligence, Int. Journal of Adv. Computer Research, Vol. 2, Num. 1, Iss. 3, pp. 31-36, March 2012.

2. K. Sorensen, Metaheuristics the Metaphor Exposed, University of Antwerp, Prinsstraat 13, 2000 Antwerp, Belgium, September 2012.

3. M. Gendreau, and J.Y. Potvin, Handbook of Metaheuristics, 2nd edition, Chap. 8, International series in Operations Research and Mangement Science, Springer, 2010.

4. M.M. Raghuwanshi, and L. Malik, A brief review on Particle Swarm Optimization:Limitations and Future directions, Int. Journal of Computer Science Engineering, Vol. 2, No. 5, pp. 196-200, September 2013.

5. D. Kumar, and B. Kumar, Optimization of benchmark functions using artificial bee colony(ABC) algorithm, IOSR Journal of Engineering, Vol. 3, Iss. 10, pp. 9-14, October 2013.

6. X.S. Yang, and X. He, Firefly Algorithm: recent advances and applications, Int. Journal of Swarm Intelligence, Vol. 1, No. 1, pp. 36-50, August 2013.

7. X.S. Yang, and S. Deb, Cuckoo Search via Levy Flights, Proc. Of World Congress on Nature and biologically inspired computing, IEEE Publications, USA, pp. 210-214, March 2010.

8. X.S. Yang, A new metaheuristic Bat-inspired algorithm Nature inspired cooperative strategies for Optimization, Studies in computayional intelligence, Springer Berlin, 284, Springer, pp. 65-74, April 2010.

9. S. Mirjalili, S.M. Mirjalili, and A. Lewis, Grey Wolf Optimizer, Advances in Software Engineering, Elsevier Science Ltd., Vol. 69, pp. 46-61, March 2014.