On the benefits of Laplace samples in solving a rare event problem using cross-entropy method

The convergence quality of the cross-entropy (CE) optimizer relies critically on the mechanism meant for randomly generating data samples, in agreement with the inference drawn in the earlier works--the fast simulated annealing (FSA) and fast evolutionary programming (FEP). Since tracing a near-global-optimum embedded on a nonconvex search space can be viewed as a rare event problem, a CE algorithm constructed using a longtailed distribution is intuitively attractive for effectively exploring the optimization landscape. Based on this supposition, a set of CE algorithms employing the Cauchy, logistic and Laplace distributions are experimentally validated in a wide range of optimization functions, which are shifted, rotated, expanded and/or composed, characterized by convex, unimodal, discontinuous, noisy and multimodal fitness landscapes. The Laplace distribution has been demonstrated to be more suitable for the CE optimization, since the samples drawn have jump-lengths long enough to elude local optima and short enough to preserve sufficient candidates in the global optimum neighborhood. Besides, a theoretical analysis has been carried out to understand the following: (i) benefits offered by the long-tailed distributions towards evasion of local optima; (ii) link between the variation in scale parameter estimate and the probability of producing candidate solutions arbitrarily close to the global optimum.