Search

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. [ABSTRACT FROM PUBLISHER]

The discrete cross-entropy optimization algorithm iteratively samples solutions according to a probability density on the solution space. The density is adapted to the good solutions observed in the present sample before producing the next sample. The adaptation is controlled by a so-called smoothing parameter. We generalize this model by introducing a flexible concept of feasibility and desirability into the sampling process. In this way, our model covers several other optimization procedures, in particular the ant-based algorithms. The focus of this paper is on some theoretical properties of these algorithms. We examine the first hitting time \( \tau \) of an optimal solution and give conditions on the smoothing parameter for \( \tau \) to be finite with probability one. For a simple test case we show that runtime can be polynomially bounded in the problem size with a probability converging to 1. We then investigate the convergence of the underlying density and of the sampling process. We show, in particular, that a constant smoothing parameter, as it is often used, makes the sample process converge in finite time, freezing the optimization at a single solution that need not be optimal. Moreover, we define a smoothing sequence that makes the density converge without freezing the sample process and that still guarantees the reachability of optimal solutions in finite time. This settles an open question from the literature. [ABSTRACT FROM AUTHOR]