REMEDA: Random Embedding EDA for optimising functions with intrinsic dimension

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

Authors

Colleges, School and Institutes

External organisations

  • University of the Gambia

Abstract

It has been observed that in many real-world large scale problems only few variables have a major impact on the function value: While there are many inputs to the function, there are just few degrees of freedom. We refer to such functions as having a low intrinsic dimension. In this paper we devise an Estimation of Distribution Algorithm (EDA) for continuous optimisation that exploits intrinsic dimension without knowing the influential subspace of the input space, or its dimension, by employing the idea of random embedding. While the idea is applicable to any optimiser, EDA is known to be remarkably successful in low dimensional problems but prone to the curse of dimensionality in larger problems because its model building step requires large population sizes. Our method, Random Embedding in Estimation of Distribution Algorithm (REMEDA) remedies this weakness and is able to optimise very large dimensional problems as long as their intrinsic dimension is low.

Details

Original languageEnglish
Title of host publicationParallel Problem Solving from Nature – PPSN XIV
Subtitle of host publication14th International Conference, Edinburgh, UK, September 17-21, 2016, Proceedings
Publication statusPublished - 2016
Event14th International Conference on Parallel Problem Solving from Nature, PPSN 2016 - Edinburgh, United Kingdom
Duration: 17 Sep 201621 Sep 2016

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9921
ISSN (Print)0302-9743

Conference

Conference14th International Conference on Parallel Problem Solving from Nature, PPSN 2016
Country/TerritoryUnited Kingdom
CityEdinburgh
Period17/09/1621/09/16