Solving dynamic optimisation problems by combining evolutionary algorithms with KD-tree

Article English OPEN
Nguyen, TT ; Jenkinson, I ; Yang, Z

In this paper we propose a novel evolutionary algorithm that is able to adaptively separate the explored and unexplored areas to facilitate detecting changes and tracking the moving optima. The algorithm divides the search space into multiple regions, each covers one basin of attraction in the search space and tracks the corresponding moving optimum. A simple mechanism was used to estimate the basin of attraction for each found optimum, and a special data structure named KD-Tree was used to memorise the searched areas to speed up the search process. Experimental results show that the algorithm is competitive, especially against those that consider change detection an important task in dynamic optimisation. Compared to existing multi-population algorithms, the new algorithm also offers less computational complexity in term of identifying the appropriate sub-population/region for each individual.
  • References (27)
    27 references, page 1 of 3

    [1] T. T. Nguyen, “Continuous Dynamic Optimisation Using Evolutionary Algorithms,” Ph.D. dissertation, School of Computer Science, University of Birmingham, January 2011,

    [2] T. T. Nguyen, S. Yang, and J. Branke, “Evolutionary dynamic optimization: A survey of the state of the art,” Swarm and Evolutionary Computation, vol. 6, pp. 1 - 24, 2012.

    [3] S. Yang and C. Li, “A clustering particle swarm optimizer for locating and tracking multiple optima in dynamic environments,” IEEE Trans. Evolutionary Computation, vol. 14, no. 6, pp. 959-974, 2010.

    [4] R. Lung and D. Dumitrescu, “Evolutionary swarm cooperative optimization in dynamic environments,” Natural Computing, vol. 9, no. 1, pp. 83-94, 2010.

    [5] V. Noroozi, A. Hashemi, and M. Meybodi, “Cellularde: A cellular based differential evolution for dynamic optimization problems,” in Adaptive and Natural Computing Algorithms. Springer, 2011, pp. 340-349.

    [6] R. Mendes and A. Mohais, “Dynde: a differential evolution for dynamic optimization problems,” in Congress on Evolutionary Computation. IEEE, 2005, pp. 2808-2815.

    [7] W. Du and B. Li, “Multi-strategy ensemble particle swarm optimization for dynamic optimization,” Information Sciences, vol. 178, no. 15, pp. 3096 - 3109, 2008.

    [8] T. T. Nguyen and X. Yao, “Continuous dynamic constrained optimisation - the challenges,” IEEE Transactions on Evolutionary Computation, vol. 16, no. 6, pp. 769-786, 2012.

    [9] H. Richter, “Detecting change in dynamic fitness landscapes,” in Congress on Evolutionary Computation, 2009, pp. 1613-1620.

    [10] J. J. Grefenstette, “Genetic algorithms for changing environments,” in Parallel Problem Solving from Nature 2, 1992, pp. 137-144.

  • Metrics
    views in OpenAIRE
    views in local repository
    downloads in local repository

    The information is available from the following content providers:

    From Number Of Views Number Of Downloads
    LJMU Research Online - IRUS-UK 0 51
Share - Bookmark