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

• Published in: Applied mathematics and computation 2013-12, Vol.225, p.843-859
• Main Authors: Easter Selvan, S., Subathra, M.S.P., Hepzibah Christinal, A., Amato, Umberto
• Format: Article
• Language: English
• Subjects: Algorithms; Convergence; Cross-entropy optimization; Landscapes; Long-tailed distributions; Mathematical analysis; Mathematical models; Nonconvex fitness function; Optimization; Preserves; Simulated annealing
• ISSN: 0096-3003; 1873-5649
• DOI: 10.1016/j.amc.2013.10.011

•Influence of long-tailed distributions in the cross-entropy optimizer, on generating candidate solutions is analyzed.•A theoretical reasoning for the superior performance of Laplace samples has been provided.•A rigorous empirical study has been conducted to verify our conjecture.•In exploration and exploitation, Laplace samples strike a balance between the Gaussian and Cauchy/logistic samples.•The findings can be extended to other heuristic/evolutionary algorithms meant for rare event problem solving. 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 long-tailed 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.