The characteristic of the function determines the complexity of the function. The reported results in this section do not necessarily reflect the performance of the utilized methods under all circumstances. The overall performance of such methods can be influenced by the utilized parameterizations and other experimental conditions. However, benchmark functions can be the indicators of how well the optimization algorithms perform under several degrees of complexities. In this section, the results of all selected algorithms tested on thirty benchmark functions are presented and discussed.
The average result of the runs Mean , standard deviation SD and time taken in seconds to complete each run are reported in Tables 3 , 4 and 5. If the mean value is less than 1. In this experiment, only basic versions of SI techniques are considered and no modifications are applied. Algorithm codes are adapted from several sources and are modified to be compatible with our experimental setup [ — ]. The first two benchmark functions in Table 3 and Table 4 e. In Sphere, the result which is closest to the theoretical optimal value is acquired by DE with 5.
In the Sumsquare function, none of the algorithms achieved the best minimization performance but PSO has become the best algorithm with 3. The third best is DE where it managed to achieve 7. PSO and GA achieve better minimization performance compared with the other approaches when applied to the Coville functions with zero being the optimal value. DE is the best performing method on the Dixon-Price function with the mean value of 1. All algorithms managed to achieve the theoretical optimal value with the Matyas function except for GSO where the mean value obtained is 2.
DE managed to outperform other approaches by achieving 3. DE and ACO are the best performing approaches on Rosenbrock and Schwefel functions respectively with the mean value of 3. In Trid6 function the theoretical value of , PSO manage to achieved this theoretical value and outperform the other algorithms.
The second best algorithm is DE with the mean value of Considering the reported results in Table 3 , DE is the best performing since it managed to be selected as the best approach with eight out of twelve functions closely followed by PSO, being selected as the best approach in seven out of twelve function. The third best approach for unimodal functions are GA and ACO where both of them have been selected as the best approach for three out of twelve functions.
From all these considered methods, GSO is the poorest performing method due to not being able to become the best performing method in any of the functions. This is closely followed by CSA being selected as the best performing method in only one function. However, from literature investigation, ABC and CSA perform quite well when the number of evolutions were higher [ , ].
They even managed to outperform other algorithms in several benchmark functions. Further discussion is available in the S1 File. Tables 5 to 8 are focusing on multimodal functions with the first six functions Bohachecvsky1, Booth, Branin, Michalewicz5, Rastrigin and Shubert being separable. The forth function is Michalewicz5 with theoretical value of DE achieved the closest average per value to the theoretical value with In Rastrigin with 0 theoretical value, GA managed to outperform other algorithms with the mean value of 5.
The rest of the functions considered in these tables are multimodal and inseparable. Considering these functions, DE, became the best performing approach achieving the best performance in 11 out of 12 functions. In Egg-Holder, GA managed to record a mean value of PSO and GA shared the second best performing approaches where they become the best algorithm in eight out of twelve function. Within the Griewank and Perm functions, DE has become the best performing approach with a mean value of 1. PSO and DE once again have become the best methods when applied to Schaffer2 function where they managed to obtain an optimal value of 0.
The results presented in Tables 3 to 8 can also be investigated based on the characteristics of the fitness functions utilized in the study. Considering the results presented in Table 9 , DE seems to be the best overall performing approach, outperforming other methods in 24 out of 30 functions followed by PSO with the best performance in 19 out of The third best is GA with 14 out 30 best performance and closely followed by ACO with 13 out of 30 best performance. Focusing on the breakdown results it is noticeable that DE has been the best performing method in all categories.
However, in terms of time consumed to complete the benchmark test, ABC is the best with an average for all 30 functions is 0. Even DE is the best overall performance in term of mean value but it is the second slowest algorithm after GSO. In the first step, the Lilliefors test is used to examine the parametric nature of the results.
Subsequently, the Anova and Kruskal-Wallis tests are utilized in order to assess the statistical significance of any findings: the Anova test is used if the data is parametric and the Kruskal-Wallis test is utilized if the data is non-parametric. Given the superiority of DE and PSO compared with other approaches considered in this study, further assessment is performed on these two approaches in experiments 2 and 3.
In experiment 2 the overall performances of four well-known variations of DE algorithm are assessed against the basic DE. The rationale behind this is to investigate the potential of these modified versions of DE and the possibility of achieving better overall performance. This issue is assessed using a subset of benchmark functions considered in experiment 1 and the experimental results are taken from literature.
In this comparison, four modified DE-based algorithms have been selected and their performance on a sub-selection of benchmark functions utilized in experiment 1 are evaluated. In order to facilitate better understanding of the results with respect to what is reported in experiment 1, the reported results in experiment 1 for original DE and the best performing algorithm are also included.
The parameter settings of each of the algorithms can be found in [ — ]. The results are reported in Table As mentioned before, Sphere is a unimodal and separable function while Rosenbrock is a unimodal and inseparable function. SADE also performed better than all other variations of DE on the Rosenbrock function achieving the theoretical optimum while also outperforming the best performing algorithm on this function in experiment 1 DE.
The Rastrigin and Michalewicz5 functions share the same characteristics by being multimodal and separable. The overall results presented in Table 10 indicated SADE as the best performing variation of DE among those considered in this experiment. Similar to experiment 2, four well-known variations of PSO have been evaluated against the basic PSO and the best performing algorithm found in experiment 1.
Table 11 depicts the performance achieved by these selected variations of PSO based on their outcome on the Sphere, Rosenbrock, Schwefel, Rastrigin, Michalewicz5 and Griewank functions. The results reported in Table 7 indicate that SPSO is the best performing algorithm among the considered variations of PSO since it is selected as the best PSO variation in 3 out of 6 benchmark functions in addition to being able to outperform the best performing approach in experiment 1 in 3 of the benchmark functions Sphere, Rosenbrock and Griewank. CLPSO is the third best performance where it managed to outperform other competitors in Rastrigin function.
This study was concerned with overall performance of various Swarm Intelligence SI based approaches and aimed to provide a comparison among the well-known SI-based approaches. These benchmark functions cover a range of characteristics including unimodal, multimodal, separable, and inseparable. The results indicated the superiority of DE with the ability to outperform or perform equally to the best algorithm in 24 out of 30 functions.
DE performed very well on multimodal functions, being selected as the best performing approach in 11 out of 12 such functions. This performance repeater in unimodal and inseparable functions in which DE outperformed others in 8 out of 12 and 18 out of 22 functions respectively. PSO is the second best approach that outperformed or performed equally to the best algorithm in 18 out of 30 functions and follows by GA with 14 out of Two extra experiments are offered to capture the performance of four well-known modified versions of PSO and DE on a sub set of 6 benchmark functions.
Table A. Parameter setting utilized by literature studies for each algorithm. Table B. Benchmark Functions Selected for Comparison.
- Other Titles by Aboul Ella Hassanien.
- Financial Accounting.
- Swarm Intelligence: Principles, Advances, and Applications?
Table C. Table D. Table E. Table F. Table G. Table H. Table I. Table J. Table K. Table L. Table M. Table N. Analyzed the data: AA. Browse Subject Areas? Click through the PLOS taxonomy to find articles in your field. This is an open access article distributed under the terms of the Creative Commons Attribution License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited Data Availability: All relevant data are within the paper and its Supporting Information files.
Introduction Swarm Intelligence SI has attracted interest from many researchers in various fields. Swarm Intelligence Algorithms This section introduces several SI-based algorithms, highlighting their notable variants, their merits and demerits, and their applications. Genetic Algorithm The Genetic Algorithm GA introduced by John Holland in [ 2 , 3 ], is a search optimization algorithm based on the mechanics of the natural selection process.
Download: PPT. Fig 1. Flow Chart of Genetic Algorithm with all steps involved from beginning until termination conditions met [ 6 ]. Fig 4. Particle Swarm Optimization movement towards global optima over iteration numbers [ 33 ]. Differential Evolution The Differential Evolution DE algorithm is a population-based algorithm that can be considered to be similar to GA since it employs similar operators; crossover, mutation, and selection. Fig 5. Illustration of Crossover Process of DE with vector dimension j of 7. The general process of ABC method and the details of each step are as follows [ 76 — 78 ]: Step 1.
The probability value, p i , is measured using the following equation: 14 Step 4. Step 5. The best fitness value and the position associated to that value are memorized. Fig 6. Levy flights provide a random walk and the random steps are drawn from a Levy Distribution equation for large steps as follows: 20 The equation has infinite variance with an infinite mean. Other Evolutionary Algorithms There are so many other evolutionary algorithms available but not discussed in the previous sections because the purpose of the previous section were to only introduce and discuss the well-known and commonly used SI-based approaches.
Benchmark Functions Experiment There are many optimization techniques claiming superiority over other approaches. Experimental Settings In evolutionary methods, experimental settings are very important and can influence the outcome of the experiments. Experiment 1: Performance Evaluation on Benchmark Functions with strict conditions. Benchmark Functions Every benchmark function has its own properties whether it is unimodal, multimodal, separable or non-separable.
Comparisons and Discussion The reported results in this section do not necessarily reflect the performance of the utilized methods under all circumstances. Table 3. Table 4. Table 5. Tables 3 and 4. Table 6. Table 7. Table 8. Overall performance. Table 9. Analysis of significance inter-relation analysis. Performance Evaluation on Benchmark Functions between Several Variants of DE In this comparison, four modified DE-based algorithms have been selected and their performance on a sub-selection of benchmark functions utilized in experiment 1 are evaluated.
Table Conclusions This study was concerned with overall performance of various Swarm Intelligence SI based approaches and aimed to provide a comparison among the well-known SI-based approaches. Supporting Information. S1 File. Supporting text and tables. References 1. Journal of Artificial Societies and Social Simulation. View Article Google Scholar 2. Goldberg D. Addison Wesley. Holland J, Genetic Algorithms. Scientific American Journal. View Article Google Scholar 4. Grefenstette JJ.
Bhattacharjya RK. Introduction to Genetic Algorithms. IIT Guwahati. Accessed 14 November Devooght R. Multi-objective genetic algorithm. Available: epb-physique. Accessed 01 January Uzel O, Koc E. Basic of Genetic Programming. Graduation Project I. Accessed 03 January View Article Google Scholar 8. Using Genetic Algorithms to solve scheduling problems on flexible manufacturing systems FMS : a literature survey, classification and analysis. Flexible Services and Manufacturing Journal. View Article Google Scholar 9.
An improved genetic algorithm with local search for order acceptance and scheduling problems. A heuristics based multi-robot task allocation. Path planning of robotic fish based on genetic algorithm and modified dynamic programming. International Conference on Advanced Mechatronic Systems.
A genetic algorithm-based Boolean delay model of intracellular signal transduction in inflammation. BMC Bioinformatics. Foschini L, Tortonesi M. Adaptive and business-driven service placement in federated Cloud computing environments. International Symposium on Integrated Network Management. Modelling and controlling of engineering ship based on genetic algorithm. Optimization of part type selection and loading problem with alternative production plans in flexible manufacturing system using hybrid genetic algorithms—part 1: Modelling and representation. Optimization of part type selection and loading problem with alternative production plans in flexible manufacturing system using hybrid genetic algorithms—part 2: Genetic operators and results.
Genetic algorithm solution of the TSP avoiding special crossover and mutation. View Article Google Scholar A formal analysis of the role of multi-point crossover in genetic algorithms. Annals of Mathematics and Artificial Intelligence.
Distributed Artificial Intelligence (Part II): A Primer On MAS, ABM And Swarm Intelligence
Adaptive GA: An essential ingredient in high-level synthesis. Improving the Performance of Genetic Algorithm by reducing the population size. Dorigo M. Optimization, learning and natural algorithms. Thesis, Politecnico di Milano, Milan. Ant Colony Optimization. Basic Ant Colony Optimization.
Accessed 28 December Selvi V, Umarani R. International Journal of Computer Applications. Valdez F, Chaparro I. International Journal of Production Research. Yagmahan B, Yenisey MM. A multi-objective ant colony system algorithm for flow shop scheduling problem. Expert Systems with Applications. Kumar SB, Myilsamy G. Multi-target tracking in mobility sensor networks using Ant Colony Optimization.
International Conference on Computing Sciences. Improved ant colony optimization algorithm and its application for path planning of mobile robot in 3-D space. International Conference on Advanced Computer Control. Expert Systems with Application. Dorigo M, Gambardella LM. Ant colony system: a cooperative learning approach to the traveling salesman problem. Future Generation Computer System. Kennedy J, Eberhart R.
Particle swarm optimization. Shi Y, Eberhart R. A modified particle swarm optimizer. International Journal of Computer Science. A novel and effective particle swarm optimization like algorithm with extrapolation technique. Applied Soft Computing.
- I Forgive You, Daddy.
- A Comprehensive Review of Swarm Optimization Algorithms?
- Brotherhood of the Tomb;
- A Hybrid Swarm Intelligence Algorithm for Intrusion Detection Using Significant Features;
Fractional particle swarm optimization in multidimensional search space. Particle swarm optimization based on intermediate disturbance strategy algorithm and its application in multi-threshold image segmentation. Information Science. A Review of Particle Swarm Optimization. Part I: Background and Development. Springer Science. Particle Swarm Optimization an Overview. Swarm Intell. Bai Q. Analysis of Particle Swarm Optimization Algorithm. Computer and Information Science. Investigations on the impacts of uncertain wind power dispersion on power system stability and enhancement through PSO technique.
Jun Z, Kanyu Z. Mohan S, Mahesh TR. Particle Swarm Optimization based Contrast Limited enhancement for mammogram images. International Conference on Intelligent Systems and Control. Gorai A, Ghosh A. Hue-preserving colour image enhancement using particle swarm optimization. Recent Advances in Intelligent Computational Systems. Na L, Yuanxiang L. Chang Y, Yu G. Cloud Computing Information Security. Cooperative area extension of PSO: Transfer learning vs. Bratton D, Kennedy J. Defining a Standard for Particle Swarm Optimization. Clerc M, Kennedy J.
Eberhart RC, Shi Y. Comparing inertia weights and constriction factors in particle swarm optimization. Proceedings of the Congress on Evolutionary Computation. Brazilian Symposium on Neural Networks. Storn R, Price K. Journal of Global Optimization. International Conference on Machine Learning and Computing. Differential evolution applications in electromagnetics. Interactive differential evolution for image enhancement application in smart phone. Training multilayer perceptron using differential evolution algorithm for signature recognition application.
Signal Processing and Communications Applications Conference. International Symposium on Computer, Consumer and Control. Proceedings of Genetic Evolutions Computation Conference. Das S, Suganthan PN. Differential evolution: A survey of the state-of-the-art. Price KV. An Introduction to Differential Evolution. New Ideas in Optimization.
About This Item
Karaboga D. An idea based on honeybee swarm for numerica optimization. Initialization of velocities may require extra inputs. Another simpler variant is the accelerated particle swarm optimization APSO ,  which also does not need to use velocity and can speed up the convergence in many applications. A simple demo code of APSO is available. PSO has also been applied to multi-objective problems ,    in which the objective function comparison takes pareto dominance into account when moving the PSO particles and non-dominated solutions are stored so as to approximate the pareto front.
As the PSO equations given above work on real numbers, a commonly used method to solve discrete problems is to map the discrete search space to a continuous domain, to apply a classical PSO, and then to demap the result. Such a mapping can be very simple for example by just using rounded values or more sophisticated. However, it can be noted that the equations of movement make use of operators that perform four actions:. But all these mathematical objects can be defined in a completely different way, in order to cope with binary problems or more generally discrete ones , or even combinatorial ones.
From Wikipedia, the free encyclopedia. Iterative simulation method. Swarm Intelligence. Morgan Kaufmann. Technical Report CSM Journal of Artificial Evolution and Applications. Evolutionary Computation. Mathematical Problems in Engineering. Applied Soft Computing. Proceedings of the Congress on Evolutionary Computation. Proceedings of the Particle Swarm Optimization Workshop. Archived from the original PDF on Information Processing Letters. BMC Bioinformatics. S; Cazzaniga, P. Swarm and Evolutionary Computation. S; Pasi, G. Technical Report HL Population structure and particle swarm performance.
Evolutionary Computation, Proceedings of the Congress on. Universidade do Minho. CEC IEEE, Communication Diversity in Particle Swarm Optimizers. International Conference on Swarm Intelligence. Lecture Notes in Computer Science. A parsimonious SVM model selection criterion for classification of real-world data sets via an adaptive population-based algorithm. Neural Computing and Applications, Particle Swarm Optimization. A Complementary Cyber Swarm Algorithm. Honolulu, HI. Swarm Intelligence Conference. Fundamenta Informaticae. DEPSO: hybrid particle swarm with differential evolution operator.
Fluctuations meanwhile are useful for randomness. Multiple interactions occur when the swarms share information among themselves within their searching area. The second property of SI is division of labour which is defined as the simultaneous execution of various simple and feasible tasks by individuals. This division allows the swarm to tackle complex problems that require individuals to work together [ 1 ].
This paper outline starts with brief discussion on seven SI-based algorithms and is followed by general discussion on others available algorithms. After that, an experiment is conducted to measure the performance of the considered algorithms on thirty benchmark functions. The results are discussed comprehensively after that with statistical analysis in the following section.
From there, the two best performing algorithms are selected to investigate their variants performance against the best performing algorithm in five benchmark functions. The conclusion section is presented at the end of this paper. This section introduces several SI-based algorithms, highlighting their notable variants, their merits and demerits, and their applications. The Genetic Algorithm GA introduced by John Holland in [ 2 , 3 ], is a search optimization algorithm based on the mechanics of the natural selection process.
In GA, a new population is formed using specific genetic operators such as crossover, reproduction, and mutation [ 4 — 7 ]. Population can be represented in a set of strings referred to as chromosomes. In each generation, a new chromosome a member of the population is created using information originated from the fittest chromosomes of the previous population [ 4 — 6 ]. GA generates an initial population of feasible solutions and recombines them in a way to guide their search toward more promising areas of the search space. Each of these feasible solutions is encoded as a chromosome, also referred to as genotype, and each of these chromosomes will get a measure of fitness through a fitness function evaluation or objective function.
The value of fitness function of a chromosome determines its capability to endure and produce offspring. The high fitness value indicates the better solution for maximization and the low fitness value shows the better solution for minimization problems. A basic GA has five main components: a random number generator, a fitness evaluation unit, a reproduction process, a crossover process, and a mutation operation.
Reproduction selects the fittest candidates of the population, while crossover is the procedure of combining the fittest chromosomes and passing superior genes to the next generation, and mutation alters some of the genes in a chromosome [ 4 — 7 ]. Fig 1 shows the general flow chart of GA and the main components that contribute to the overall algorithm.
The operation of the GA starts with determining an initial population whether randomly or by the use of some heuristics. The fitness function is used to evaluate the members of the population and then they are ranked based on the performances. Once all the members of the population have been evaluated, the lower rank chromosomes are omitted and the remaining populations are used for reproduction. This is one of the most common approaches used for GA. Another possible selection scheme is to use pseudo-random selection, allowing lower rank chromosomes to have a chance to be selected for reproduction.
The crossover step randomly selects two members of the remaining population the fittest chromosomes and exchanges and mates them. The final step of GA is mutation. In this step, the mutation operator randomly mutates on a gene of a chromosome. Mutation is a crucial step in GA since it ensures that every region of the problem space can be reached.
Elitism is used to prevent the best solution of the population from being destroyed during crossover and mutation operation. Elitism guarantees the fitness of new generation will be at least as good as current generation. The evaluation and generation of the new populations continue until the maximum number of generations is reached or the optimum solution is found. GA is advantageous in terms of requiring limited parameter settings and initialising itself from possible solutions rather than a single solution.
One of the main drawbacks of GA is the lack of fast convergence towards the optimal values since the crossover and mutation process are random [ 6 , 7 ]. The applications of GA are wide ranging from scheduling [ 8 , 9 ], machine learning [ 10 ], robotics [ 11 , 12 ], signal processing [ 13 ], business [ 14 ], mathematics [ 15 ], manufacturing [ 16 , 17 ], routing [ 18 ], and many more.
Since the introduction of GA, many researchers have conducted studies to improve the performance of the GA. They have introduced several alternative approaches for crossover and mutation to enhance the quality of solutions. In crossover, instead of selecting one crossover point, De Jong et al. The difference between them is N-point crossover is choosing several breaking points randomly, while in segmented crossover, only two breaking points are utilized.
Mutation is one of the most important operators in GA in order to direct the chromosomes towards the better solution. Therefore, several studies have given different methods for mutation. By default, each gene in a chromosome is assigned with probability, p m , and mutated depending on that probability. This mutation is known as uniform mutation. The other approaches for mutation are bitwise inversion where the whole gene in a chromosome is mutated using a random mutation [ 19 ]. Adaptive genetic algorithms have been introduced in order to allow the use of precise parameters in setting the population size, the crossing over probability, and the mutation probability.
All of these parameters are dynamic and changing over the iterations. For instance, if the population is not improving, the mutation rate is increasing and whenever the population is improving, the mutation rate starts decreasing [ 21 ]. Raja and Bhaskaran [ 22 ] have suggested a new approach of GA initialization that improve the overall performance of GA. In this approach, they utilized initialization twice where the first initialization is uses to identify the promising area.
After the first initialization, all chromosome are ranked and the best chromosomes are selected.
Swarm Intelligence - Aboul Ella Hassanien, Eid Emary - Bok () | Bokus
After that, GA is initialize again within the area where the best chromosomes have been identified. It is inspired by the foraging behaviour of real ants. This algorithm consists of four main components ant, pheromone, daemon action, and decentralized control that contribute to the overall system. Ants are imaginary agents that are used in order to mimic the exploration and exploitation of the search space.
In real life pheromone is a chemical material spread by ants over the path they travel and its intensity changes over time due to evaporation. In ACO the ants drop pheromones when traveling in the search space and the quantities of these pheromones indicate the intensity of the trail. The ants choose the direction based on path marked by the high intensity of the trail.
The intensity of the trail can be considered as a global memory of the system. Daemon actions is used to gather global information which cannot be done by a single ant and uses the information to determine whether it is necessary to add extra pheromone in order to help the convergence. The decentralized control is used in order to make the algorithm robust and flexible within a dynamic environment. The importance of having a decentralized system in ACO is due to resulting flexibility in the face of ant lost or ant failure offered by such a system.
These basic components contribute to a cooperative interaction that leads to the emergence of shortest paths [ 23 , 24 ]. Fig 2. The left figure illustrates the initial environment when the algorithm starts, where an agent ant starts moving randomly from the nest towards the source and returns back. The middle figure illustrates several iterations of execution when ants discover multiple possible paths between nest and source. The shortest path is chosen, and ants use this path frequently which contributes to high intensity of pheromone trail as shown in the sub-figure 3 in Fig 2.
N , S , a , and b represent nest, food source, on-going path, and returning path respectively. The steps involved to find the best solution starts with choosing the next node from the current position in the search space using following equation: 1 p i , j is the probability of going from node i to node j. J k are the nodes that the ant is allowed to travel to from node i.
Each ant also has a taboo list which is used to prevent any ants from visiting the same node twice. N and S denote Nest and Source with a is ongoing direction and b is returning direction. Sub Figure 2. Figure 2. Pheromones, as stated before, are one of the crucial components in ACO as they leave trails which increase the probability of the next ant choosing the same path.
In order to deposit a pheromone, the following equation is used: 2. Q is a constant, L is the cost of the ant's tour, i. The value represents the pheromone rate between node i and node j that the ant visited in iteration t. The pheromone deposition value for a path that is not selected is zero.
Another important component is the pheromone evaporation rate. This component determines the exploration and exploitation behaviour of the ant. High and low evaporation rates result in exploration and exploitation behaviours respectively. Too high exploration rates result in ants getting lost, while too low values result in an inability to acquire the optimal path [ 23 , 24 ].
The pheromone decay factor is utilized using following equation: 3 m is the number of ants in the system and p is the pheromone evaporation rate or decay factor. ACO has several advantages over other evolutionary approaches including offering positive feedback resulting in rapid solution finding, and having distributed computation which avoids premature convergence. These are in addition to taking advantage of the existing collective interaction of a population of agents [ 26 , 27 ]. However, ACO has drawbacks such as slower convergence compared with other heuristic-based methods and lack a centralized processor to guide it towards good solutions.
Although the convergence is guaranteed, the time for convergence is uncertain. Another important demerit of ACO is its poor performance within problems with large search spaces [ 26 , 27 ]. ACO has been applied in various optimization problems such as traveling salesman problem TSP [ 28 ], quadratic assignment problem [ 29 ], vehicle routing [ 30 ], network model problem [ 31 , 32 ], image processing [ 33 ], path planning for mobile robot [ 34 ], path optimization for UAV System [ 35 ], project management [ 36 ] and so on.
A number of ACO variants have been created with the aim to improve overall performance. GA is initialize again. ACS uses centralise global update approach for pheromone update and only concentrate the search within a neighbourhood of the best solution found so far in order to increase efficiency for convergence time. The state transition rule is different from ACO where ACS has a stated probability q 0 to decide which behaviour is used by the ant. If the value of q is less than that, then exploitation behaviour is used and vice versa. For local search procedures, a local optimization heuristic based on an edge exchange strategy such as 2-opt, 3-opt or Lin-Kernighan is applied to each solution generated by an ant to get its local minima.
This combination of new pheromone management, new state transition, and local search procedures has produced a variant of ACO for TSP problems [ 37 ]. First, at the beginning, the pheromone trails are set to the maximum value which escalate the exploration behaviour of the ants. Third, only one ant is allowed to add pheromone which help exploiting the best solutions found during the execution of the algorithm.
The pheromone may be added by using either an iteration-best approach or a global-best approach. In the iteration-best approach, only the ant with best solution adds the pheromone for each iteration while in the global-best approach, the ant with the best solution can add the pheromone without considering other ants in the same iteration [ 38 ]. It uses a simple mechanism that mimics swarm behaviour in birds flocking and fish schooling to guide the particles to search for global optimal solutions.
Del Valle and his co-authors [ 40 ] described PSO with three simple behaviours of separation, alignment, and cohesion as shown in Fig 3 respectively. Separation is the behaviour of avoiding the crowded local flockmates while alignment is the behaviour of moving towards the average direction of local flockmates. Cohesion is the behaviour of moving towards the average position of local flockmates. The formulas of PSO algorithm are as follows [ 39 , 41 ]: 4 5 where and are particle velocity and particle position respectively.
PSO proved to be an efficient optimization algorithm by searching an entire high-dimensional problem space. It is a robust stochastic optimization technique based on the movement and intelligence of swarms. It applies the concept of social interaction to problem solving and does not use the gradient of the problem being optimized, so it does not require the optimization problem to be differential, as is required by classic optimization methods [ 42 ].
The optimization of irregular problems that are noisy and change over time can be determined using PSO [ 43 — 45 ]. The parameters of PSO consist of number of particles, position of agent in the solution space, velocity and neighbourhood of agents communication of topology. Figure 3. The PSO algorithm begins by initializing the population first. The second step is calculating the fitness values of each particle, followed by updating individual and global bests, and later, the velocity and the position of the particles get updated.
The second to fourth steps get repeated until the termination condition is satisfied [ 40 , 46 — 48 ]. Fig 4 illustrates the PSO algorithm output over iterations. In the first iteration, all particles spread out in order to find the best solution exploration. Each particle is evaluated. The best solutions are found with respect to neighbourhood topology and the personal and global best particles for each member of the swarm are updated.
The convergence would be achieved through attracting all particles towards the particle with the best solution. The PSO algorithm has many merits. It is simple to implement, has only a few parameters to be set, it is effective in global search, it is insensitive to scaling of design variables, and it is easily parallelized for concurrent processing [ 48 — 50 ]. PSO has tendency to result in a fast and premature convergence in mid optimum points, in addition to having slow convergence in a refined search area having weak local search ability [ 48 — 50 ].
PSO is used in networking [ 51 ], power systems [ 52 ], signal processing [ 53 ], control system [ 54 ], machine learning [ 55 ], image processing [ 56 — 58 ], and many more. There are several approaches that can be used to improve PSO in general. The size of the population is one of the important factors. Higher population size can increase the chance of faster and precise convergence. A second approach is to achieve a balance between exploration and exploitation. In the beginning of iteration, high exploration would give a high chance to find a solution which is close to global optima.
Meanwhile towards the end of iteration, high exploitation would give a chance for particle to find the most accurate solution within the promising area. A sub-swarm approach is another way that can be used to increase the basic PSO performance which is quite commonly used nowadays. Allocating different tasks or objectives to each sub-swarm can also increase the efficiency of PSO in the multi-objective problems [ 59 ].
Another approach to improve the PSO performance is to set the contributing components of the velocity equation dynamic velocity adjustment. Such an approach can direct particles in different directions resulting in faster convergence towards a global optimum [ 60 ]. The two most notable variants in PSO are the introduction of inertia weight and constriction factors. Inertia weight w is introduced by Shi and Eberhart three years after PSO was first introduced to regulate the influence of previous velocity which also controls the exploration and the exploitation behaviours of particle [ 61 ].
If the w value is high then the step size is big, resulting in the occurrence of exploration behaviour. If the w value is low then the step size is small and the exploitation behaviour occurs. This element has been accepted as new standard form of velocity equation for basic PSO as illustrated in Eq 6 : 6. The introduction of inertia weight has improved overall performance of PSO in terms of the speed of convergence and the quality of solutions.
Bratton and Kennedy suggested to use an inertia weight value higher than 1. Clerc and Kennedy later introduced the constriction factor named as K in order to increase the chance of convergence and avoid particles from leaving the search space [ 63 ]. Both variants have improved the overall performance of the PSO algorithm.
Eberhart and Shi have compared these two variants and come to the conclusion that the constricted PSO perform better than the improved basic PSO [ 64 ]. There are several elements in PSO such as swarm communication topology, and the number of particles which can determine the quality of the solution. Figueirdo and Ludermir have evaluated five types of communication topologies of global, local, von neuman, wheel and four clusters. They concluded that global topology shows promising results compared to other topologies [ 65 ].
Bratton and Kennedy investigated the effect of number of particles in finding the solutions. Their study showed that there is no absolute number of population size that can be applied for all optimization problems [ 62 ]. The Differential Evolution DE algorithm is a population-based algorithm that can be considered to be similar to GA since it employs similar operators; crossover, mutation, and selection.
The main difference between DE and GA is in constructing better solutions, where DE relies on mutation operation while GA relies on crossover operation. This algorithm was introduced by Storn and Price in [ 66 ]. Since this algorithm relies on mutation operation, it utilizes the mutation as a search mechanism and takes advantage of the selection operation in order to direct the search towards the potential regions in the search space.
The target vector is the vector that contains the solution for the search space; the mutant vector is the mutation of the target vector; and the trail vector is the resultant vector after the crossover operation between target vector and mutant vector. The basic steps of the DE algorithm as stated before, are similar to GA with only slight differences [ 67 , 68 ].
DE starts with steps such as population initialization followed by evaluation to determine the fittest members of the population. Later, new parameter vectors get generated by adding the weighted difference of the two population vectors with the third vector. This step is referred to as mutation. Within the crossover, the vector is mixed and the algorithm takes a final step of selection. In order to see the differences between DE and GA, a more detailed discussion on the three main operators in DE is required. In the mutation step each of N parameter vectors goes through mutation.
Mutation is the operation of expanding the search space and a mutant vector is generated by: 8 where F is the scaling factor with a value in the range of [0,1] with solution vectors x r 1, x r 2, and x r 3 being chosen randomly and satisfying following criteria: 9 where i is the index of the current solution. Fig 5 illustrates a two-dimensional vector which plays a part in generating the mutant vector. Target vector is current solution with mutant vector is another possible solution. Trail vector is new solution after crossover process between target vector and mutant vector [ 43 ].
Crossover operation is introduced to increase the diversity of the disconcerted parameter vectors. The parent vector is mixed with a mutated vector and a trial vector is produced by: 10 where CR is a crossover constant and R j is a random real number between [0,1] with j denoting the j th component of the resultant array. In DE, all solutions in the population have the same probability of being selected as parents without considering their fitness value. This is the main difference in the operations of DE and GA. Simply put, the child trail vector produced is only evaluated after mutation and crossover operations.
After that, the performance of this child vector is compared to its parent and the better vector is retained in the population. The exploitation behaviour occurs when the difference between two solution vectors in Eq 6 are small, while the exploration behaviour occurs when the difference between those two are large.
DE is advantageous in terms of enhancing the capacity of local search and keeping the multiplicity of the population while it suffers from slow convergence and being unstable [ 68 ]. DE is employed in various applications such as electrical engineering [ 69 ], image processing [ 70 ], machine learning [ 71 ], and economy [ 72 ]. In general, DE performance can be improved by increasing the population size. It can also balance between exploration and exploitation behaviour where the scaling factor which determines the step size is high at the beginning and decreases towards the end of an iteration.
Another step that can be used is the introduction of elitism which can avoid the best solution from being destroyed when the next generation is created. There are many variants of DE available since its introduction by Storn and Price. Mezura-Montes et al. The differences between them are in terms of individuals selected for mutation, the numbers of pairs of solutions selected and the type of recombination [ 74 ].
Meanwhile, current-to-best and current-to-rand are arithmetic recombination proposed by Price [ 75 ] to eliminate the binomial and exponential crossover operator with the rotation invariant. It was proposed by Dervis Karaboga in [ 76 ]; in , the performance of ABC was analysed [ 77 ] and it was concluded that ABC performs quite well compared with several other approaches. This algorithm is inspired by the intelligent behaviour of real honey bees in finding food sources, known as nectar, and the sharing of information about that food source among other bees in the nest.
In this approach, the artificial agents are defined and categorized into three types, the employed bee, the onlooker bee, and the scout bee. The employed bees focus on a food source and retain the locality of that food source in their memories. The number of employed bees is equal to the number of food sources since each employed bee is associated with one and only one food source. The onlooker bee receives the information of the food source from the employed bee in the hive.
After that, one of the food sources is selected to gather the nectar. The scout bee is in charge of finding new food sources and the new nectar. The general process of ABC method and the details of each step are as follows [ 76 — 78 ]:. Step 1. Each vector holds n variables, which is optimized, to minimize the objective function. The following equation is used for initialization phase: 11 where l i and u i respectively are the lower and upper bound parameters of x i.
Step 2. Employed Bees Phase: In this phase, the search for a new food source, , increases in order to have more nectar around the neighbourhood of the food source,. Once a neighbouring food source is found, its profitability or fitness is evaluated. Once the new food source, v i , is produced its profitability is measured and a greedy selection is applied between and.
The fitness value of the solution, fit i , is determined using following equation: 13 where is the objective function value of solution. Step 3. Onlooker Bees Phase: Onlooker bees that are waiting in the hive choose their food sources depending on probability values measured using the fitness value and the information shared by employed bees. The probability value, p i , is measured using the following equation: Step 4. Scout Bees Phase: The scout bees are those unemployed bees that choose their food sources randomly.
Employed bees whose fitness values cannot be improved through predetermined number of iterations, called as limit or abandonment criteria , become the scout bees and all their food sources get abandoned. Step 6. Termination Checking Phase: If the termination condition is met, the programme terminates, otherwise the programme returns to Step 2 and repeats until the termination condition is met.
Advantages of ABC include being easy to implement, robust, and highly flexible. It is considered as highly flexible since only requires two control parameters of maximum cycle number and colony size. Therefore, adding and removing bee can be done without need to reinitialize the algorithm. It can be used in many optimization problems without any modification, and it requires fewer control parameters compared with other search techniques [ 77 — 80 ]. The disadvantages of ABC include the requirement of new fitness tests for the new parameters to improve performance, being quite slow when used in serial processing, and the need for a high amount of objective function evaluations [ 81 ].
ABC has been implemented in various fields including engineering design problems [ 82 , 83 ], networking [ 84 ], business [ 85 ], electronics [ 86 ], scheduling [ 86 ] and image processing [ 86 ]. Although ABC algorithm was only been introduced less than ten years ago there are already quite number of variants of ABC available. The main aim for all these variants is to upsurge the population diversity and avoid premature convergence. Bao and Zeng have tested these modified ABCs with the standard ABC and the results showed that these three selection strategies perform better search compared with the standard ABC [ 88 ].
GSO employs physical entities agents called glowworms. A condition of glowworm m , at time t has three main parameters of a position in the search space x m t , a luciferin level l m t and a neighbourhood range r m t. These three parameters change over time [ 89 — 91 ]. Initially the glowworms are distributed randomly in the workspace, instead of finite regions being randomly placed in the search area as demonstrated in ACO.
Later, other parameters are initialized using predefined constants. Yet, similar to other methods, three phases are repeated until the termination condition is satisfied. These phases are luciferin level update, glowworm movement, and neighbourhood range update [ 89 ]. The position in the search space is updated using following equation: 16 where s is the step size, and.
If the difference between x n and x m is large then exploration behaviour takes place and if this difference is small then exploitation behaviour occurs. Later, each glowworm tries to find its neighbours. In GSO, a glowworm m is the neighbour of glowworm n only if the distance between them is shorter than the neighbourhood range r m t , and on condition where glowworm n is brighter than glowworm m.
However, if a glowworm has multiple choices of neighbours, one neighbour is selected using the following probability equation. The solution with the highest probability is selected and then the glowworm moves one step closer in direction of the chosen neighbour with a constant step size s. In the final phase, the neighbourhood range r m t is updated to limit the range of communication in a group of glowworms. In a , i , j and k represent the agents of glowworm. The same applies with i and k where sensor range and local-decision range are represented by and and and respectively. It is applied in the circumstances where agent i is in the sensor range of agent j and k.
Since the agents have different local-decision domains only agent j uses the information from agent i. Agents are ranked based on their luciferin values resulting in agent a being ranked 1 since it has the highest luciferin value. GSO is effective within applications with limited sensor range and is capable of detecting multiple sources and is applicable to numerical optimization tasks [ 89 — 91 ].
However, it also has low accuracy and slow convergence rate [ 92 , 93 ]. GSO has been applied to routing [ 94 ], swarm robotics [ 95 ], image processing [ 96 ], and localization [ 97 , 98 ] problems. In Figure 6. It shows if agent within local-decision of other agent, the agent with lower luciferin values move towards agent with higher luciferin values. GSO can be improved in general by considering the following modifications. Once the best solution has been determined, all agents can move towards the agent with the best solution. This step can increase the efficiency in exploitation, since higher number of agents to be within the best solution range.
This step might reduce the time taken for GSO since less calculation required to determine the probability and direction of its movement. For example, He et al. He et al.
Related Swarm Intelligence: Principles, Advances, and Applications
Copyright 2019 - All Right Reserved