Type: Process Essays
Sample donated: Archie Copeland
Last updated: September 21, 2019
Abstract The composite andoften synchronized behavior of swarms captivates not only biologists but alsocomputer scientists.
Ant colony and fish schooling are striking examples ofcoordinated behavior that emerges without essential control. Swarm Intelligenceis a field of computer science that designs and studies efficient computationalmethods for solving problems in a way that is inspired by the behavior of realswarms or insect colonies. These SI-based algorithms can have somegains over usual algorithms. In this paper, we carry out a study these SI-based algorithmsby studying their variants, performance, operators and applications. Finally,we provide some discussions and topics for further research.1. Introduction Naturalinspired algorithms have become a very promising alternative for solving veryhard optimization problems in science and engineering.
In the last decades, manynature inspired algorithms have been developed. The inspirations for developingsuch nature-inspired algorithms often come from biological, chemical andphysical processes in nature. In addition, some algorithms were developed bydrawing characteristics that based on sociology, history and even sports. Inthis line the Swarm intelligence is the discipline that deals with natural andartificial systems with the collections of many entities that coordinate usingdecentralized control and self-organization. In particular, the disciplineconcentrated on the collective manners that result from the local relations ofthe entities with each other and with their setting. In this sequence SwarmIntelligence plays a vital role in the optimization problem. Swarm intelligence (SI)is the collective behavior of decentralized, self-organized systems,natural or artificial.
The concept is employed in work on artificial intelligence. The expressionwas introduced by Gerardo Beni and Jing Wang in 1989, in thecontext of cellular robotic systems. SI systems consist typically of apopulation of simple agents or boids interactinglocally with one another and with their environment. The inspiration oftencomes from nature, especially biological systems. The agents follow very simplerules, and although there is no centralized control structure dictating how individualagents should behave, local, and to a certain degree random, interactionsbetween such agents lead to the emergence of”intelligent” global behavior, unknown to the individual agents.
Examples in natural systems of SI include ant colonies, bird flocking,animal herding, bacterial growth, fish schooling and microbialintelligence. The application of swarm principles to robots is called swarmrobotics, while ‘swarm intelligence’ refers to the more general setof algorithms. ‘Swarm prediction’ has been used in the context of forecastingproblems.2. Study on Swarm Intelligence BasedAlgorithms2.1.
Bacterial ForagingAlgorithm (BFA) The Bacterial Foraging Algorithm(BFA) was proposed by Passino in 2002. The working principle is the leasthealth bacteria ultimately die and the remaining bacteria i.e.
, healthiestbacteria will be divided into two identical ones and placed at the samelocation. Dispersion and elimination: For the purpose to avoid local optima,dispersion and elimination process is performed after a certain number ofreproduction steps. The variants are Bacterial Colony Optimization Algorithm,Bacterial Colony Chemo taxis Algorithm. The BFA mainly used in Circuit designoptimization, Communication optimization, Fuzzy system design optimization,Image processing, Inventory management, Manufacturing cell formation, Motorcontrol optimization, Nonlinear system identification. The variants referenceis Innovative Computational Intelligence: A Rough Guide to 134 CleverAlgorithms”, Bo Xing and Wen-Jing Gao, Springer.2.
2. BatAlgorithm The Bat Algorithm was proposed by Xin-She Yang inthe year 2010. This algorithm is based on the echolocation behaviour, the batscan notice the distance and distinguish between food and background barriers aswell, even in the darkness. Bats usually fly arbitrarily to search for prey.According to that, some numerical parameters connected with the bats’ foragingbehaviour are defined first, such as velocity (vi) at position (xi) with afixed frequency (fmin), varying wavelength (k) and loudness (Ao).
The loudnesscan vary from a large positive (Ao) when searching for prey to a minimumconstant value (Amin) when homing towards the prey. This algorithm variants areBat intelligence algorithm, Multi objective bat Algorithm by Yang (2011), FuzzyLogic Bat Algorithm by Khan et al.(2011), K-Means bat Algorithm by Komarasamy and Wahi (2012), Chaotic BatAlgorithm(2012), Binary bat Algorithm by Nakamura et al.
(2012), DifferentialOperator and Levy flights Bat Algorithm by Xie et al. (2013) and Improved BatAlgorithm by Jamil et al. (2013). BA is mainly used in Continuous OptimizationCombinatorial Optimization and Scheduling, Inverse Problems and ParameterEstimation, Classifications, Clustering and Data Mining, Image Processing,Fuzzy Logic and Other Applications. 2.3. Bee Inspired Algorithms The BeeInspired Algorithms is developed by Karaboga in2005.
This algorithm is working by Marriage Behaviour of Bees is anotherfamous behaviour of bees is the marriage (i.e., mating) behaviour. In theempire of honeybees, queens are dedicated in egg-laying. A colony may containone queen or more during its life cycle. Dancing andCommunication Behaviour of Bees i.e., scout bees, perform a series of movementsi.
e., dancing to swap information such as the place, quantity and quality offood sources and convince their nest mates to chase them. There are two typesof dances, i.e.
,round dance when food is very close and waggle dance. In addition, according to the speedof the dances, honeybees broadcast the distance information, i.e.
, if dance isfaster, then the food distance is smaller. Variants of this algorithms are Artificialbee colony (ABC) algorithm, Honeybees mating optimization (HBMO) algorithm,artificial beehive algorithm (ABHA), Bee colony optimization (BCO) algorithm,Bee colony inspired algorithm (BCiA), Bee swarm optimization (BSO) algorithm,Bee system (BS) algorithm, BeeHive algorithm, bees algorithm (BeA), Bees lifealgorithm (BLA), bumblebees algorithm, Honeybee social foraging (HBSF)algorithm, OptBees algorithm, Simulated bee colony (SBC) algorithm, Virtualbees algorithm (VBA), and wasp swarm optimization (WSO) algorithm. Thisalgorithm is mainly involved in Travelling Salesman Problem (TSP), Job ShopScheduling (JSS), MANET- Routing Protocol, Solving Sudoku Puzzles, NumericalOptimization, Engineering Optimization, Application to Generalized Assignment Problem,Advisory Systems and Numerical Assignment Problem and Developing OptimizationAlgorithm. 2.4. Biogeography-basedoptimization Algorithm (BBO) TheBiogeography-basedoptimization Algorithm was projected bySimon in 2008. This BBO is functioning by typically used to optimize multidimensional real-valuedfunctions, but it does not use the gradient of the function, whichmeans that it does not require the function to be differentiable asrequired by classic optimization methods.
BBO can therefore be used ondiscontinuous functions. It is optimizes a problem by maintaining a populationof candidate solutions, and creating new candidate solutions by combiningexisting ones according to a simple formula. The Variants references are HybridBBO with bacterial foraging algorithm, Antenna design optimization,Communication network optimization, Knapsack problem, Machining processoptimization and Motor design optimization.
The BBO algorithm is mainly used inTravelling salesman problem, Virtual simulationoptimization, Motor design optimization, Machining process optimization. 2.5. CatSwarm Optimization Algorithm The Cat SwarmOptimization Algorithm was developed by Chu and Tsaiin 2007.
This algorithm is based on Population of cats are created and randomlydistributed in the M-dimensional solution space, with each cat representing asolution. This population is divided into two subgroups. The cats in the firstsubgroup are resting and keeping an eye on their surroundings (i.e., seekingmode), while the cats in the second subgroup start moving around and chasingtheir preys (i.e., tracing mode).
The mixture of these two modes helps CSO tomove toward the global solution in the M-dimensional solution space. Since thecats spend too little time in the tracing mode, the number of the cats in thetracing subgroup should be small. This number is defined by using the mixtureratio (MR) which has a small value. After sorting the cats into these twomodes, new positions and fitness functions will be available, from which the catwith the best solution will be saved in the memory.
This CSO is mainly appliedin Adaptive plant modeling, C-clustering problem, Economic dispatchproblem, Graph colouring problem, IIR system identification, Image qualityproblem. The variants are Parallel algorithm, Multiobjective CSO Algorithm.2.6. Cuckoo Inspired Algorithms TheCuckoo Inspired Algorithm was developed by Yang andDeb in 2009. This algorithm is never builds its own nest and lays their eggs inthe nest of another host bird nest. Some host birds can engage directly withthe interfering cuckoo.
If the host bird identifies the eggs that are not theiregg then it will either throw that eggs away from its nest or simply rid itsnest and build a new nest. In a nest, each egg represents a solution and cuckooegg represents a new and good solution. The obtained solution is a new solutionbased on the existing one and the modification of some characteristics. In thesimplest form each nest has one egg of cuckoo in which each nest will havemultiple eggs represents a set of solutions.
These CI variants are HybridCS algorithm is used for shop scheduling problems. Improved CS for Global optimization is used toenhance the accuracy and convergence rate. Modified-CS is used forUnconstrained Optimization problems.
Based on Levenberg Marquardt (LM) is usedto Help in reducing errors and avoids local minima in an algorithm. Multiobjective CS is used in Job Scheduling Problems. A Novel Complex value is usedin reducing the local convergence and Enhance the information of nests.Discrete is used for solving traveling salesman problem. Neural based is usedfor Employee health and safety (HS) risk on employees at their workplaces. Thisalgorithm is applied in Web service composition, Travel-Salesman problem ,Engineeringoptimization, Scheduling, Groundwater expedition, Flood forecasting, Flow shopscheduling, Multilevel image thresholding, Speaker recognition, Ontologymatching , Surface roughness, Supplier selection, Face Recognition.2.
7. FireflyAlgorithm The Firefly Algorithm has founded byXin-She Yang in 2007. The FA is based on Fireflies are unisex so that one firefly will be attractedto other fireflies regardless of their sex. The attractiveness is proportionalto the brightness, and they both decrease as their distance increases.
Thus forany two flashing fireflies, the less bright one will move towards the brighterone. If there is no brighter one than a particular firefly, it will moverandomly. The brightness of a firefly is determined by the landscape of theobjective function. The variants are Classical firefly algorithms,Modified firefly algorithms, Hybrid firefly algorithms. The FA is mainly usedin engineering application Image Processing, Antenna Design, WirelessNetworking, Business, Robotics & Semantic Web, Industrial Optimization,Chemistry and Civil Engineering. 2.8. FishInspired Algorithms The Fish Inspired Algorithms aredeveloped by Li et al.
in 2002. This algorithm is based on Random behavior – ingeneral, fish looks at random for food and other companion; Searching behavior – when the fish discoversa region with more food, it will go directly and quickly to that region;Swarming behavior – when swimming, fish will swarm naturally in order to avoiddanger; Chasing behavior – when a fish in the swarm discovers food, the otherswill find the food dangling after it; Leaping behaviour – when fish stagnatesin a region, a leap is required to look for food in other regions. The variantsare Artificial fish school algorithm, Fish school search algorithm, Groupescaping algorithm, Shark search algorithm. This algorithm is used inArtificial neural network training, Control optimization, Fault diagnosis,Power system optimization, Robot control optimization, Vehicle routing problem.2.9.
Ant colony optimization algorithm The Antcolony optimization algorithm was proposed by Marco Dorigo in 1992. Antscommunicate to one another by laying down pheromones along their trails, sowhere ants go within and around their ant colony is a stigmergic system. In manyant species, ants walking from or to a food source, deposit on the ground asubstance called pheromone. Other ants are able to smell this pheromone, andits presence influences the choice of their path, that is, they tend to followstrong pheromone concentrations. The pheromone deposited on the ground forms apheromone trail, which allows the ants to find good sources of food that havebeen previously identified by other ants. Using random walks and pheromoneswithin a ground containing one nest and one food source, the ants will leavethe nest, find the food and come back to the nest.
This algorithm applied inTraveling salesman (TSP), Vehicle routing, Sequential ordering,Connection-oriented network routing, Connectionless network routing and Opticalnetwork routing. The variants of these algorithms are MAX-MIN Ant System andAnt Colony System (ACS), Ant System (AS) Ant System (AS). 2.10.
Particle Swarm Optimization(PSO) TheParticle Swarm Optimization (PSO) was developed by Russell Eberhart and JamesKennedy in 1995. This algorithm is based on working about particles’ data couldbe anything. In the flocking birds, the data would be the X, Y, Z coordinatesof each bird. The individual coordinates of each bird would try to move closerto the coordinates of the bird which is closer to the food’s coordinates(gBest).
If the data is a pattern or sequence, then individual pieces of thedata would be manipulated until the pattern matches the target pattern. Thevelocity value is calculated according to how far an individual’s data is fromthe target. The further it is, the larger the velocity value. In the bird’sexample, the individuals furthest from the food would make an effort to keep upwith the others by flying faster toward the gBest bird. If the data is a patternor sequence, the velocity would describe how different the pattern is from thetarget, and thus, how much it needs to be changed to match the target.
Each particle’s pBest value onlyindicates the closest the data has ever come to the target since the algorithmstarted. The gBest value only changes when any particle’s pBest value comescloser to the target than gBest. Through each iteration of this algorithm,gBest gradually moves closer and closer to the target until one of theparticles reaches the target. The variants are Discrete PSO, GuaranteedConvergence PSO (GCPSO), NeighborhoodGCPSO, Niche PSO Regrouping PSO,Neighborhood search strategies (NSPSO), Immunity-enhanced particle swarmoptimization IEPSO, PS Class algorithm,Quantum-Behaved PSO algorithm, Multi-objective optimization (MPSO) and HybridPSO. The applications of these algorithms are Job Scheduling on ComputationalGrids, Data Mining.
3.Performance MeasuresDespite the huge number of studies about variousmetaheuristic algorithms, it still lacks a good performance measure forcomparing different algorithms. In general, there are two major ways to compareany two algorithms. One way is to compare the accuracy of two algorithms tosolve the same problem for a fixed number of function evaluations.
In mostcase, the problem to be solved is usually a test function whose minimum valueis often zero by proper formulation. For example, if algorithm A obtains 0.001for, say, N = 1000 function evaluations, while algorithm B obtains 0.002 in arun, one tends to say A obtained a better value than B. However, care should betaken when making a statement. Due to the stochastic nature, multiple runsshould be carried out so that meaningful statistical measures can be obtained.
Suppose, we run each algorithm 100 times, and we can get a mean function valueand its standard deviation. Another way is to compare the numbers offunction evaluations required by two different algorithms for a given accuracy.Suppose, the accuracy ? = 10?3is fixed, if algorithm A requires about 1000 function evaluations, whilealgorithm B requires 1400 function evaluations, we may say A is better than B.Again, care should be taken when drawing such conclusions.
Multiple runs areneeded to ensure meaningful statistical measures. Suppose, we run eachalgorithm 100 times independently, we get a mean 1000 and a correspondingstandard deviation of 300. A third way is to compare the execution timesfor two algorithms. However, this approach is not recommended because it hasmany drawbacks. Firstly, one has to ensure each algorithm is implementedcorrectly and efficiently.
Even two algorithms are equally efficient, but theways of implementing the calculations can affect the execution time. Secondly,different computers may have different configurations, and one has to ensurethe computation is carried out on the same computer. Thirdly, even the samecomputer is used, the hidden processes (especially true for the Windowsoperating system) can consume a lot of computing power at different times, eventhe computer is virus free.
Finally, even all the above has ensured that theresults are good, such execution times are usually not repeatable by otherusers.A fourth way is to use normalize results forcomparison, and this approach is misleading and can produce wrong conclusions44. The idea is to choose an algorithm as the basis of comparison, andnormalize the results by others to produce a ratio. 4.Analysis of SwarmAlgorithms S.no Algorithm Name Advantages Disadvantages 1 Bacterial Foraging Algorithm (BFA) · Application of group foraging strategy of a swarm of E.
coli bacteria in multi-optimal function optimization is the key idea of the new algorithm. · This algorithm has less computational burden, global convergence, less computational time requirement and can handle more number of objective function. 2 Bat Algorithm · Computational results showed that BaA performs significantly better than other algorithms in terms of accuracy and efficiency. · Flexible and Easy to implement. · Solve a wide range of problems and highly non linear problems efficiently. · The loudness and pulse emission rates essentially provide a mechanism for auto control and auto zooming into the region. · It gives promising optimal solutions.
· Works well with complicated problems. · Very quickly at the early stage and then convergence rate slow down. · There is no mathematical analysis to link the parameters with convergence rates. · Accuracy may be limited if the number of function evaluations is not high. · Not clear what the best value are for most applications.
· It is highly needed that large scale application should be tested. 3 Bee Inspired Algorithms · The characteristics of this interesting insect also motivate researchers. · To develop several other bee inspired innovative CI algorithms. · The algorithm has strength in both local and global searchers · Implemented with several optimization problems.
· Random initialization, · The algorithm has several parameters, · Parameters need to be tuned, · Probabilistic approach in the local search. 4 Biogeography-based optimization Algorithm Able to offer better results in most cases. Example world aircraft engine health estimation problem · BBO is poor in exploiting the solutions · There is no provision for selecting the best members from each generation · A habitat doesn’t consider its resultant fitness while immigrating the features, as a result so many infeasible solutions are generated. 5 Cat Swarm Optimization Algorithm To achieve an appropriate balance between the exploitation of the search position gathered so far (i.e., seeking mode) and the exploration of untraced or relatively unexplored search space regions (i.e.
, tracing mode), a mixed ration (MR) is employed. Normally, due to the cats are resting most of the time, the value of MR is very small. 6 Cuckoo Inspired Algorithms · It satisfies the global convergence requirements · It supports local and global search capabilities · It uses Lévy flights as a global search strategy. Easy to fall into local boundary optimal value, the parasitic nests are generated randomly when exceeding the borders. 7 Firefly Algorithm · FA can deal with highly non- linear, multi-modal optimization problems naturally and efficiently. · The speed of convergence of FA is very high in probability of finding the global optimized answer.
· It has the flexibility of integration with other optimization techniques to form hybrid tools. · It does not require a good initial solution to start its iteration process. · The process will be slower and less convergence rate. While the intensification is about local search, the optimization will be converging quickly. · It will may lead to premature convergence and it will reduce the chance to find global optimum 8 Fish Inspired Algorithms · Very competitive in solving unstructured high dimensional spaces. · Global search ability · Tolerance of Parameter setting · Good Robustness · Higher time complexity · Lower convergence speed · Lack of balance between global and local search · Not use of experiences of group members for the next move.
9 Ant colony optimization algorithm · Can be used in dynamic applications · Positive Feedback leads to rapid discovery of good solutions · Distributed computation avoids premature convergence · Convergence is guaranteed, but time to convergence uncertain · Coding is not straightforward 10 Particle Swarm Optimization (PSO) · PSO is based on the intelligence. It can be applied into both scientific research and engineering use. · PSO have no overlapping and mutation calculation. The search can be carried out by the speed of the particle. During the development of several generations, only the most optimist particle can transmit information onto the other particles, and the speed of the researching is very fast.
· The calculation in PSO is very simple. Compared with the other developing calculations, it occupies the bigger optimization ability and it can be completed easily. · PSO adopts the real number code, and it is decided directly by the solution. The number of the dimension is equal to the constant of the solution.