Survey PaperA survey of swarm intelligence for dynamic optimization: Algorithms and applications
Introduction
Swarm intelligence (SI) is an important category of optimization methods. SI is the property of a system whereby the collective behaviours of agents that interact locally with their environment cause coherent functional global patterns to emerge. Different from evolutionary algorithms (EAs), SI algorithms are inspired from simple behaviours and self-organizing interaction among agents, such as ant colonies foraging, bird flocking, animal herding, bacterial growth, honey bees, fish schooling, and so on. The term SI was first used by Beni [1] in cellular robotic system where simple agents organize themselves through neighbourhood interactions and later on established in [2], [3], [4].
The mainstream SI algorithms are ant colony optimization (ACO) [5] and particle swarm optimization (PSO) [6]. Less popular SI algorithms include artificial bee colony (ABC) [7], bacterial foraging optimization (BFO) [8], firefly algorithm (FA) [9], [10], artificial fish swarm optimization (AFSO) [11] and many others. Originally, SI algorithms were designed for stationary optimization problems. However, many real-world optimization problems are subject to dynamic environments. Changes in a dynamic optimization problem (DOP) may occur in the objective function, constraints, problem instance, Pareto front or set (in the case of dynamic multi-objective optimization problems) that cause the optimum to change. Hence, DOPs are more challenging to address than stationary optimization problems since repeated optimization of the changing optimum is required [12].
The field of dynamic optimization is closely related with EAs, known as evolutionary dynamic optimization (EDO) [12]. However, it has been a growing interest to apply SI algorithms on different DOPs. EDO has received extensive attention with several surveys [12], [13], [14], [15] and books [16], [17], [18], [19], [20], whereas SI dynamic optimization (SIDO) has not received much attention, with exception of some very brief reviews of PSO in [14] and ACO in [15] included as subsections in the EDO surveys. The aim of this paper is to extend these reviews of ACO and PSO and provide a comprehensive survey of existing work done related to SIDO, which also includes the less popular and recent SI algorithms. The survey will mainly focus on classifying SI algorithms based on their applications and reviewing the strategies integrated with SI algorithms to tackle dynamic changes. The DOPs are mainly classified into problems with discrete and continuous spaces and their applications are further classified. A review of real-world problems addressed with SI and reviews of performance measurements and benchmark generators of SIDO are also given.
The rest of the paper is organized as follows. Section 2 briefly presents the concept of DOPs and describes the differences between discrete and continuous DOPs and their applications. Moreover, it describes the benchmark generators and performance measurements commonly used in SIDO. Section 3 briefly describes different SI algorithms. Section 4 reviews algorithms and applications of SIDO arranged by classes of problems, i.e., discrete, continuous, constrained, multi-objective, and classification problems. Section 5 reviews the real-world applications in which SI algorithms are used. Section 6 concludes this paper and summarizes future research issues and directions on SIDO.
Section snippets
Dynamic optimization problem (DOP)
A DOP can be intuitively defined as a sequence of static problem instances that need to be optimized [21]. The two main aspects of “dynamism” are defined by the frequency and magnitude of an environmental change. The former and latter parameters correspond to the speed and degree at which the environment of the problem changes, respectively. Other aspects include the predictability, detectability, and time-linkage of dynamic changes [22], [23]. The former two aspects correspond to whether a
Brief description
The area of metaheuristics in SI is chaotic because there are many "novel" metaheuristics that are basically repeating existing metaheuristics [87] or are not even inspired by nature or swarms, e.g., the fireworks algorithms inspired by the fireworks explosions [88]. Nevertheless, this paper focuses only on the SI metaheuristics applied to DOPs as listed in Table 1.
Generally speaking, all SI algorithms were developed specifically for different optimization problem domains as defined in Table 1.
Swarm intelligence for dynamic optimization
In this section, major SI strategies that tackle dynamic changes will be reviewed for various classes of problems divided as follows:
- •
SI in dynamic discrete optimization
- •
SI in dynamic continuous optimization
- •
SI in dynamic constrained optimization
- •
SI in dynamic multi-objective optimization
- •
SI in dynamic classification
Real-world applications of SI in dynamic environments
In this section real-world applications that appear in SIDO are reviewed and classified into discrete and continuous applications. The difference between “real-world applications” and the applications discussed in Table 2, Table 3 is rather arbitrary [210]. In this paper, the applications discussed in Table 2, Table 3 focus on well-known models that aim to model a real-world problem or setting (e.g., multi-objective or constraint handling). Such models may provide an indication whether such an
Conclusions and future work
This paper attempts to review the related work of SIDO found from several web-search engines. The most important applications of SIDO are classified into continuous or discrete problems. The strategies used to enhance SI algorithms to cope with dynamic changes are grouped and extensively discussed. In addition, SIDO real-world problems are reviewed in this paper.
The review of this paper was constructed as follows. The search was conducted from five recognized scientific databases, i.e.,
Acknowledgements
This work was supported by the Engineering and Physical Sciences Research Council (EPSRC) of U.K. under Grant EP/K001310/1, by the National Natural Science Foundation of China (NSFC) under Grants 61673331 and 61673355, by the Hubei Provincial Natural Science Foundation of China under Grant 2015CFA010, and by the 111 project under Grant B17040.
References (269)
- et al.
Evolutionary dynamic optimizationa survey of the state of the art
Swarm Evol. Comput.
(2012) - et al.
Ant colony optimization with immigrants schemes for the dynamic travelling salesman problem with traffic factors
Appl. Soft Comput.
(2013) - et al.
No-free-lunch theorems in the continuum
Theoret. Comput. Sci.
(2015) - et al.
Ant algorithms with immigrants schemes for the dynamic vehicle routing problem
Inf. Sci.
(2015) - et al.
Vehicle routing problem with uncertain demandsan advanced particle swarm algorithm
Comput. Ind. Eng.
(2012) - G. Beni, The concept of cellular robotic system, in: 1988 Proceedings of the IEEE International Symposium on...
- G. Beni, J. Wang, Swarm intelligence, in: Proceedings of the Seventh Annual Meeting of the Robotics Society of Japan,...
- G. Beni, S. Hackwood, Stationary waves in cyclic swarms, in: Proceedings of the 1992 IEEE International Symposium on...
- J. Branke, Memory enhanced evolutionary algorithms for changing optimization problems, in: Proceedings of the 1999 IEEE...
- A. Colorni, M. Dorigo, V. Maniezzo, Distributed optimization by ant colonies, in: F. Vaerla, P. Bourgine (Eds.),...
Biomimicry of bacterial foraging for distributed optimization and control
IEEE Control Syst. Mag.
Firefly algorithm
Nature-Inspired Metaheuristic Algorithms
An optimizing method based on autonomous animalsfish-swarm algorithm
Syst. Eng. Theory Pract.
Evolutionary optimization in uncertain environments—a survey
IEEE Trans. Evol. Comput.
Optimization in dynamic environmentsa survey on problems, methods and measures
Soft Comput.
Metaheuristics for dynamic combinatorial optimization problems
IMA J. Manag. Math.
Evolutionary Optimization in Dynamic Environments
Designing Evolutionary Algorithms for Dynamic Environments
Dynamic multiobjective optimization problemstest cases, approximations, and applications
IEEE Trans. Evol. Comput.
Continuous dynamic constrained optimization-the challenges
IEEE Trans. Evol. Comput.
No free lunch theorems for optimization
IEEE Trans. Evol. Comput.
Reinterpreting no free lunch
Evol. Comput.
Continuous lunches are free plus the design of optimal optimization algorithms
Algorithmica
Ant colony optimization with local search for the dynamic travelling salesman problems
IEEE Trans. Cybern.
Benchmark generator for dynamic optimization
WSEAS Trans. Syst.
A memetic ant colony optimization algorithm for the dynamic travelling salesman problem
Soft Comput.
A framework for finding robust optimal solutions over time
Memetic Comput.
A multiple ant colony system for a vehicle routing problem with time windows and uncertain travel times
J. Traffic Logist. Eng.
Cited by (449)
Revisiting ‘survival of the fittest’ principle in global stochastic optimisation: Incorporating anisotropic mutations
2024, Communications in Nonlinear Science and Numerical SimulationA fast density peak clustering based particle swarm optimizer for dynamic optimization
2024, Expert Systems with ApplicationsOptimizing LSTM with multi-strategy improved WOA for robust prediction of high-speed machine tests data
2024, Chaos, Solitons and FractalsAn enhanced node segmentation and distance estimation scheme with a reduced search space boundary and improved PSO for obstacle-aware wireless sensor network localization
2024, Journal of Network and Computer ApplicationsChaotic heterogeneous comprehensive learning PSO method for size and shape optimization of structures
2023, Engineering Applications of Artificial Intelligence