REMEDA: Random Embedding EDA for optimising functions with intrinsic dimension

Momodou Sanyang, Ata Kaban

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

4 Citations (Scopus)
263 Downloads (Pure)

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.
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
PublisherSpringer
Pages859-868
Number of pages10
ISBN (Electronic)978-3-319-45823-6
ISBN (Print)978-3-319-45822-9
DOIs
Publication statusPublished - 2016
Event14th International Conference on Parallel Problem Solving from Nature, PPSN 2016 - Edinburgh, United Kingdom
Duration: 17 Sept 201621 Sept 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

Fingerprint

Dive into the research topics of 'REMEDA: Random Embedding EDA for optimising functions with intrinsic dimension'. Together they form a unique fingerprint.

Cite this