How effective is Cauchy-EDA in high dimensions?

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Authors

Colleges, School and Institutes

External organisations

  • University of Waikato, New Zealand

Abstract

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.

Details

Original languageEnglish
Title of host publicationProceedings of the IEEE Congress on Evolutionary Computation 2016
Publication statusE-pub ahead of print - 21 Nov 2016
EventIEEE Congress on Evolutionary Computation 2016 - Vancouver, Canada
Duration: 25 Jul 201629 Jul 2016

Conference

ConferenceIEEE Congress on Evolutionary Computation 2016
CountryCanada
Period25/07/1629/07/16