A gradient oriented recombination scheme for evolution strategies

ABSTRACT

This paper proposes a novel recombination scheme for evolutionary algorithms, which can guide the new population generation towards the maximum increase of the objective function. Given the current sample points and their function evaluations, the Shepard's interpolation method is used to approximate the underlying objective function in that local region. We then compute the gradient of the estimated function which in consequence leads to an iterative process, called the mean shift, for searching the local function optimum. In each mean shift step, we calculate the weighted mean of sample points in the kernel window, followed by shifting the location of the kernel to the computed mean. Such iterative process eventually converges to the point at which the estimated objective function has zero gradient. We use the converged point as the output of our recombination operator. Experimental results show that such gradient based recombination scheme can improve the efficiency of optimization search in evolutionary algorithms.

REFERENCES

• 1: D. V. Arnold. An analysis of evolutionary gradient search. IEEE Congress on Evolutionary Computation, 1: 47--54, June 2004.
• 2: D. V. Arnold and D. MacDonald. Weighted multirecombination evolution strategies on the parabolic ridge. IEEE Congress on Evolutionary Computation, pages 104--111, 2006.
• 3: T. Bäck. Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms. Oxford University Press, Oxford, UK, 1996.
• 4: H. G. Beyer. The theory of evolution strategies. Springer-Verlag New York, Inc., New York, NY, USA, 2001.
• 5: Yizong Cheng, Mean Shift, Mode Seeking, and Clustering, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.8, p.790-799, August 1995 [doi>10.1109/34.400568]
• 6: Dorin Comaniciu , Peter Meer, Mean Shift: A Robust Approach Toward Feature Space Analysis, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.5, p.603-619, May 2002 [doi>10.1109/34.1000236]
• 7: L. M. Freeman. Industrial Applications of Genetic Algorithms. CRC Press, Inc., Boca Raton, FL, USA, 1998.
• 8: Nikolaus Hansen , Andreas Ostermeier, Completely Derandomized Self-Adaptation in Evolution Strategies, Evolutionary Computation, v.9 n.2, p.159-195, June 2001 [doi>10.1162/106365601750190398]
• 9: Anooshiravan Saboori , Guofei Jiang , Haifeng Chen, Autotuning Configurations in Distributed Systems for Performance Improvements Using Evolutionary Strategies, Proceedings of the 2008 The 28th International Conference on Distributed Computing Systems, p.769-776, June 17-20, 2008 [doi>10.1109/ICDCS.2008.11]
• 10: R. Salomon. Evolutionary algorithms and gradient search: similarities and differences. IEEE Trans. Evolutionary Computation, 2(2): 45--55, 1998.
• 11: Donald Shepard, A two-dimensional interpolation function for irregularly-spaced data, Proceedings of the 1968 23rd ACM national conference, p.517-524, August 27-29, 1968 [doi>10.1145/800186.810616]
• 12: M. P. Wand and M. C. Jones. Kernel Smoothing. Chapman & Hall, 1995.
• 13: D. Whitley. An overview of evolutionary algorithms: practical issues and common pitfalls. Information and Software Technology, 43(14): 817--831, 2001.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms, Performance

Keywords:
evolutionary computation, gradient estimation, mean shift, recombination