The chaotic behaviour of search algorithms

DOI10.1007/BF00998150MaRDI QIDQ1314871zbMATH OpenOpenAlexWikidataFDO

Authors Henry P. Wynn, A. Zhigljavsky

Publication date 14 September 1994

Published in Acta Applicandae Mathematicae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00998150

zbMATH Keywords

almost sure asymptotic rates of convergenceasymptotic ratesbacktracking bifurcation algorithmchaosdynamic processergodic theoryFibonacciGolden Sectionsecond-order line searchsymmetric functions

Mathematics Subject Classification ID

Strange attractors, chaotic dynamics of systems with hyperbolic behavior (37D45) Numerical methods in optimal control (49M99) Management decision making, including multiple objectives (90B50) Mathematical programming (90C99)

Review text

Certain search algorithms produce a sequence of decreasing regions converging to a point \(x\). After renormalizing to a standard region at each iteration, the renormalized location of \(x\) may obey a dynamic process. In this case, simple ergodic theory might be used to compute asymptotic rates. The family of ``second-order line search algorithms for local minimization which includes the Golden Section (GS) method has this property. The paper exhibits several alternatives to GS which have better almost sure asymptotic rates of convergence for symmetric functions despite the fact that GS is asymptotically minimax. The discussion in the last section includes weakening of the symmetry condition and announces a backtracking bifurcation algorithm with optimum asymptotic rate.

Recommendations

• scientific article; zbMATH DE number 912590
• Pattern search algorithm using chaos and its application
• Chaotic harmony search algorithms
• A search technique for global optimization in a chaotic environment
• Chaotic behavior in evolution strategies
• Chaotic behavior in evolution strategies
• A new optimization algorithm based on chaos
• scientific article; zbMATH DE number 2125306

Cites work

• scientific article; zbMATH DE number 49471 (Why is no real title available?)
• scientific article; zbMATH DE number 1222554 (Why is no real title available?)
• scientific article; zbMATH DE number 822890 (Why is no real title available?)
• scientific article; zbMATH DE number 912590 (Why is no real title available?)
• scientific article; zbMATH DE number 912596 (Why is no real title available?)
• scientific article; zbMATH DE number 3894124 (Why is no real title available?)
• Optimum Sequential Search and Approximation Methods Under Minimum Regularity Assumptions
• Sequential Minimax Search for a Maximum

Cited in

(12)

• Lognormal law for a renormalization chain arising in search theory and the modelling of descent algorithms
• Finite sample behaviour of an ergodically fast line-search algorithm
• The theory of search from a statistical viewpoint. (With discussion)
• Achieving the ergodically optimal convergence rate for a one-dimensional minimization problem
• A generalized golden-section algorithm for line search
• scientific article; zbMATH DE number 1346777 (Why is no real title available?)
• Stochastic Analysis of Convergence via Dynamic Representation for a Class of Line-search Algorithms
• scientific article; zbMATH DE number 1857673 (Why is no real title available?)
• scientific article; zbMATH DE number 822890 (Why is no real title available?)
• scientific article; zbMATH DE number 862330 (Why is no real title available?)
• scientific article; zbMATH DE number 912590 (Why is no real title available?)
• scientific article; zbMATH DE number 920731 (Why is no real title available?)

This page was built for publication: The chaotic behaviour of search algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1314871)