Precision, local search and unimodal functions

ABSTRACT

We investigate the effects of precision on the efficiency of various local search algorithms on 1-D unimodal functions. We present a (1+1)-EA with adaptive step size which finds the optimum in O(log n) steps, where n is the number of points used. We then consider binary and Gray representations with single bit mutations. The standard binary method does not guarantee locating the optimum, whereas using Gray code does so in O((log n)²) steps. A (1+1)-EA with a fixed mutation probability distribution is then presented which also runs in O((log n)²). Moreover, a recent result shows that this is optimal (up to some constant scaling factor), in that there exist unimodal functions for which a lower bound of Ω((log n)²) holds regardless of the choice of mutation distribution. Finally, we show that it is not possible for a black box algorithms to efficiently optimise unimodal functions for two or more dimensions (in terms of the precision used).

REFERENCES

• 1: M. Dietzfelbinger, J. E. Rowe, I. Wegener, and P. Woelfel. Tight bounds for blind search on the integers. In Proc. 25th International Symposium on Theoretical Aspects of Computer Science, 2008.
• 2: Stefan Droste , Thomas Jansen , Ingo Wegener, On the Optimization of Unimodal Functions with the (1 + 1) Evolutionary Algorithm, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.13-22, September 27-30, 1998
• 3: D. Hidović and J. E. Rowe. Validating a model of colon colouration using an evolution strategy with adaptive approximations. In K. Deb, editor, GECCO 2004, LNCS 3102, pages 1005--1016. Springer-Verlag, 2004.
• 4: Jens Jägersküpper, Algorithmic analysis of a basic evolutionary algorithm for continuous optimization, Theoretical Computer Science, v.379 n.3, p.329-347, June, 2007 [doi>10.1016/j.tcs.2007.02.042]
• 5: J. Kiefer. Sequential minimal search for a maximum. Proc. Amer. Math. Soc., 4:502--506, 1953.
• 6: J. E. Rowe and D. Hidović. An evolution strategy using a continuous version of the gray-code neighbourhood distribution. In K. Deb, editor, GECCO 2004, LNCS 3102, pages 725--736. Springer-Verlag, 2004.
• 7: Jonathan Rowe , Darrell Whitley , Laura Barbulescu , Jean-Paul Watson, Properties of Gray and Binary Representations, Evolutionary Computation, v.12 n.1, p.47-76, March 2004 [doi>NO_DOI]
• 8: Ingo Wegener , R. Pruim, Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 9: L. D. Whitley. A free lunch proof for Gray versus binary encodings. In W. Banzhaf et al, editor, GECCO 1999, pages 726--733. Morgan Kaufmann, 1999.
• 10: L. D. Whitley and J. E. Rowe. Gray, binary and real valued encodings: Quad search and locality proofs. In A. H.Wright, M. D. Vose, K. De Jong, and L. Schmitt, editors, Foundations of Genetic Algorithms, Vol. 8. LNCS 3469, pages 21--36. Springer-Verlag, 2005.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

General Terms:
Theory

Keywords:
computational complexity, local search, precision, unimodal functions