Abstract
We present new variants of Estimation of Distribution Algorithms (EDA) for large scale continuous optimisation, that extend and enhance a recently proposed random projection (RP) ensemble based approach. The main novelty here
is to depart from the theory of RPs that required (sub-)Gaussian random matrices for norm-preservation, and instead for the purposes of high dimensional search we propose to employ random matrices with independent and identically distributed entries drawn from a t-distribution. We analytically show that the implicitly resulting high dimensional covariance of the search distribution is enlarged as a result. Moreover, the extent of this enlargement is controlled by a single parameter, the degree of freedom. For this reason, in the context of optimisation, such heavy tailed random matrices turn out to be preferable over the previously employed (sub-)Gaussians. Based on this observation, we then propose novel covariance adaptation schemes that are able to adapt the degree of freedom parameter during the search, and give rise to a exible approach to balance exploration versus exploitation. We perform a thorough experimental study on high dimensional benchmark functions, and provide statistical analyses that demonstrate state-of-the-art performance of our approach when compared with previously existing alternatives in problems with 1000 search variables.
is to depart from the theory of RPs that required (sub-)Gaussian random matrices for norm-preservation, and instead for the purposes of high dimensional search we propose to employ random matrices with independent and identically distributed entries drawn from a t-distribution. We analytically show that the implicitly resulting high dimensional covariance of the search distribution is enlarged as a result. Moreover, the extent of this enlargement is controlled by a single parameter, the degree of freedom. For this reason, in the context of optimisation, such heavy tailed random matrices turn out to be preferable over the previously employed (sub-)Gaussians. Based on this observation, we then propose novel covariance adaptation schemes that are able to adapt the degree of freedom parameter during the search, and give rise to a exible approach to balance exploration versus exploitation. We perform a thorough experimental study on high dimensional benchmark functions, and provide statistical analyses that demonstrate state-of-the-art performance of our approach when compared with previously existing alternatives in problems with 1000 search variables.
Original language | English |
---|---|
Pages (from-to) | 1241-1257 |
Number of pages | 21 |
Journal | Journal of Computer Science and Technology |
Volume | 34 |
Issue number | 6 |
Publication status | Published - 16 Nov 2019 |
Keywords
- covariance adaptation
- estimation of distribution algorithm
- random projection ensemble
- t-distribution