Survey Paper
A survey of swarm intelligence for dynamic optimization: Algorithms and applications

https://doi.org/10.1016/j.swevo.2016.12.005Get rights and content

Highlights

  • Existing dynamic optimisation surveys focus entirely on evolutionary algorithms and little on swarm intelligence algorithms. This survey provides a comprehensive survey dedicated to swarm intelligence algorithms to fill in the gap in the dynamic optimisation domain.

  • In addition to the mainstream ant colony optimisation and particle swarm optimisation algorithms; recent swarm intelligence applications to dynamic optimisation problems (DOPs) are included.

  • Provides several classifications related to both the algorithmic components and the application problem.

Abstract

Swarm intelligence (SI) algorithms, including ant colony optimization, particle swarm optimization, bee-inspired algorithms, bacterial foraging optimization, firefly algorithms, fish swarm optimization and many more, have been proven to be good methods to address difficult optimization problems under stationary environments. Most SI algorithms have been developed to address stationary optimization problems and hence, they can converge on the (near-) optimum solution efficiently. However, many real-world problems have a dynamic environment that changes over time. For such dynamic optimization problems (DOPs), it is difficult for a conventional SI algorithm to track the changing optimum once the algorithm has converged on a solution. In the last two decades, there has been a growing interest of addressing DOPs using SI algorithms due to their adaptation capabilities. This paper presents a broad review on SI dynamic optimization (SIDO) focused on several classes of problems, such as discrete, continuous, constrained, multi-objective and classification problems, and real-world applications. In addition, this paper focuses on the enhancement strategies integrated in SI algorithms to address dynamic changes, the performance measurements and benchmark generators used in SIDO. Finally, some considerations about future directions in the subject are given.

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

Since the first two classes have been extensively researched, they are further classified by application (see Table 2, Table 3) and by the type of strategy: (a) increasing diversity

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)

  • J. Kennedy, R. Eberhart, Particle swarm optimization, in: Proceedings of the IEEE International Conference on Neural...
  • D. Karaboga, An idea based on honey bee swarm for numerical optimization, Technical Report TR06, Erciyes University,...
  • K. Passino

    Biomimicry of bacterial foraging for distributed optimization and control

    IEEE Control Syst. Mag.

    (2002)
  • X.-S. Yang

    Firefly algorithm

    Nature-Inspired Metaheuristic Algorithms

    (2008)
  • X.-S. Yang, Firefly algorithms for multimodal optimization, in: O. Watanabe, T. Zeugmann (Eds.), Stochastic Algorithms:...
  • L. Li et al.

    An optimizing method based on autonomous animalsfish-swarm algorithm

    Syst. Eng. Theory Pract.

    (2002)
  • Y. Jin et al.

    Evolutionary optimization in uncertain environments—a survey

    IEEE Trans. Evol. Comput.

    (2005)
  • C. Cruz et al.

    Optimization in dynamic environmentsa survey on problems, methods and measures

    Soft Comput.

    (2011)
  • S. Yang et al.

    Metaheuristics for dynamic combinatorial optimization problems

    IMA J. Manag. Math.

    (2013)
  • E. Alba, A. Nakib, P. Siarry (Eds.), Metaheuristics for Dynamic Optimization, Studies in Computational Intelligence,...
  • J. Branke

    Evolutionary Optimization in Dynamic Environments

    (2001)
  • S. Yang, Y.-S. Ong, Y. Jin (Eds.), Evolutionary computation in dynamic and uncertain environments, Studies in...
  • S. Yang, X. Yao (Eds.), Evolutionary Computation for Dynamic Optimization Problems, Studies in Computational...
  • R. Morrison

    Designing Evolutionary Algorithms for Dynamic Environments

    (2004)
  • P. Bosman, Learning, anticipation and time-deception in evolutionary online dynamic optimization, in: Proceedings of...
  • T. Nguyen, X. Yao, Dynamic time-linkage problems revisited, in: M. Giacobini, A. Brabazon, S. Cagnoni, G. Di Caro, A....
  • M. Helbig, A. Engelbrecht, Dynamic multi-objective optimization using PSO, in: E. Alba, A. Nakib, P. Siarry (Eds.),...
  • M. Farina et al.

    Dynamic multiobjective optimization problemstest cases, approximations, and applications

    IEEE Trans. Evol. Comput.

    (2004)
  • T. Nguyen et al.

    Continuous dynamic constrained optimization-the challenges

    IEEE Trans. Evol. Comput.

    (2012)
  • D. Wolpert et al.

    No free lunch theorems for optimization

    IEEE Trans. Evol. Comput.

    (1997)
  • J.E. Rowe et al.

    Reinterpreting no free lunch

    Evol. Comput.

    (2009)
  • A. Auger, O. Teytaud, Continuous Lunches are Free!, in: Proceedings of the 9th Annual Conference on Genetic and...
  • A. Auger et al.

    Continuous lunches are free plus the design of optimal optimization algorithms

    Algorithmica

    (2010)
  • W. Rand, R. Riolo, Measurements for understanding the behavior of the genetic algorithm in dynamic environments: a case...
  • R. Morrison, Performance measurement in dynamic environments, in: Proceedings of the 2003 Genetic and Evolutionary...
  • M. Mavrovouniotis et al.

    Ant colony optimization with local search for the dynamic travelling salesman problems

    IEEE Trans. Cybern.

    (2016)
  • M. Mavrovouniotis, S. Yang, X. Yao, Multi-colony ant algorithms for the dynamic travelling salesman problem, in: 2014...
  • M. Mavrovouniotis, S. Yang, Ant colony optimization with memory-based immigrants for the dynamic vehicle routing...
  • A. Younes et al.

    Benchmark generator for dynamic optimization

    WSEAS Trans. Syst.

    (2004)
  • M. Mavrovouniotis, F.M. Müller, S. Yang, An ant colony optimization based memetic algorithm for the dynamic travelling...
  • C. Li, S. Yang, T. Nguyen, E. Yu, X. Yao, Y. Jin, H.-G. Beyer, P. Suganthan, Benchmark generator for CEC’2009...
  • K. Weicker, Performance measures for dynamic environments, in: J. Merelo-Guervós, P. Adamidis, H.-G. Beyer, H.-P....
  • R. Salomon, P. Eggenberger, Adaptation on the evolutionary time scale: A working hypothesis and basic experiments, in:...
  • K. Weicker, N. Weicker, On evolution strategy optimization in dynamic environments, in: Proceedings of the 1999 IEEE...
  • M. Mavrovouniotis et al.

    A memetic ant colony optimization algorithm for the dynamic travelling salesman problem

    Soft Comput.

    (2011)
  • X. Yu, Y. Jin, K. Tang, X. Yao, Robust optimization over time - a new perspective on dynamic optimization problems, in:...
  • Y. Jin et al.

    A framework for finding robust optimal solutions over time

    Memetic Comput.

    (2013)
  • N. Toklu, R. Montemanni, L. Gambardella, An ant colony system for the capacitated vehicle routing problem with...
  • N. Toklu et al.

    A multiple ant colony system for a vehicle routing problem with time windows and uncertain travel times

    J. Traffic Logist. Eng.

    (2014)
  • M. Mavrovouniotis, S. Yang, An immigrants scheme based on environmental information for ant colony optimization for the...
  • Cited by (449)

    View all citing articles on Scopus
    View full text