How effective is Cauchy-EDA in high dimensions?
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
Colleges, School and Institutes
- University of Waikato, New Zealand
We consider the problem of high dimensional blackbox optimisation via Estimation of Distribution Algorithms (EDA) and the use of heavy-tailed search distributions in this setting. Some authors have suggested that employing a heavy tailed search distribution, such as a Cauchy, may make EDA better explore a high dimensional search space. However, other authors have found Cauchy search distributions are less effective than Gaussian search distributions in high dimensional problems. In this paper, we set out to resolve this controversy. To achieve this we run extensive experiments on a battery of high-dimensional test functions, and develop some theory which shows that small search steps are always more likely to move the search distribution towards the global optimum than large ones and, in particular, large search steps in high-dimensional spaces do badly in this respect with high probability. We hypothesise that, since exploration by large steps is mostly counterproductive in high dimensions, and since the fraction of good directions decays exponentially fast with increasing dimension, instead one should focus mainly on finding the right direction in which to move the search distribution. We propose a minor change to standard Gaussian EDA which implicitly achieves this aim, and our experiments on a sequence of test functions confirm the good performance of our new approach.
|Title of host publication||Proceedings of the IEEE Congress on Evolutionary Computation 2016|
|Publication status||E-pub ahead of print - 21 Nov 2016|
|Event||IEEE Congress on Evolutionary Computation 2016 - Vancouver, Canada|
Duration: 25 Jul 2016 → 29 Jul 2016
|Conference||IEEE Congress on Evolutionary Computation 2016|
|Period||25/07/16 → 29/07/16|