Stochastic Runtime Analysis of the Cross-Entropy Algorithm

This paper analyzes the stochastic runtime of the cross-entropy (CE) algorithm for the well-studied standard problems ONEMAX and LEADINGONES. We prove that the total number of solutions the algorithm needs to evaluate before reaching the optimal solution (i.e., its runtime) is bounded by a polynomia...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on evolutionary computation 2017-08, Vol.21 (4), p.616-628
Main Authors: Zijun Wu, Kolonko, Michael, Mohring, Rolf H.
Format: Article
Language:English
Subjects:
1-ANT algorithm
Algorithm design and analysis
Algorithms
analysis of randomized algorithms
Ant colony optimization
Complexity theory
cross-entropy (CE) algorithm
Entropy (Information theory)
Evolutionary computation
Functions (mathematics)
Iterative methods
Mathematical analysis
Mathematical model
Optimization
Probability theory
Randomness
Runtime
Sampling
stochastic complexity
Stochastic processes
stochastic runtime analysis of evolutionary algorithms (EAs)
Citations: Items that this one cites
Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper analyzes the stochastic runtime of the cross-entropy (CE) algorithm for the well-studied standard problems ONEMAX and LEADINGONES. We prove that the total number of solutions the algorithm needs to evaluate before reaching the optimal solution (i.e., its runtime) is bounded by a polynomial Q(n) in the problem size n with a probability growing exponentially to 1 with n if the parameters of the algorithm are adapted to n in a reasonable way. Our polynomial bound Q(n) for ONEMAX outperforms the well-known runtime bound of the 1-ANT algorithm, a particular ant colony optimization algorithm. Our adaptation of the parameters of the CE algorithm balances the number of iterations needed and the size of the samples drawn in each iteration, resulting in an increased efficiency. For the LEADINGONES problem, we improve the runtime of the algorithm by bounding the sampling probabilities away from 0 and 1. The resulting runtime outperforms the known stochastic runtime for a univariate marginal distribution algorithm, and is very close to the known expected runtime of variants of max-min ant systems. Bounding the sampling probabilities allows the CE algorithm to explore the search space even for test functions with a very rugged landscape as the LEADINGONES function.
ISSN:1089-778X
1941-0026
DOI:10.1109/TEVC.2017.2667713