Full Implementation of an Estimation of Distribution Algorithm on a GPU

Simon Marcus Poulding; Jan Peter Staunton; Nathan John Burles

Full Implementation of an Estimation of Distribution Algorithm on a GPU

Simon Marcus Poulding, Jan Peter Staunton, Nathan John Burles

Computer Science

Research output: Contribution to conference › Paper

Abstract

We submit an implementation of an Estimation of Distribution Algorithm – specifically a variant of the Bayesian Optimisation Algorithm (BOA) – using GPGPU. Every aspect of the algorithm is executed on the device, and it makes effective of use multiple GPU devices in a single machine. As for other EDAs, our implementation is generic in that it may be applied to any problem for which solutions may be represented as binary strings. For the purpose of this paper, we apply it to a particular problem known to be difficult for metaheuristic algorithms due to high interdependency between variables: finding the lowest energy state of an Ising Spin Glass. We show that our GPU implementation demonstrates a speedup in excess of 80x compared with an equivalent CPU implementation. To our knowledge, this is the first EDA to be implemented fully on the GPU.

Original language	English
Publication status	Published - 2011
Event	GECCO 2011, GPUs for Genetic and Evolutionary Computation Competition - Dublin, Ireland Duration: 12 Jul 2011 → 16 Jul 2011

Conference

Conference	GECCO 2011, GPUs for Genetic and Evolutionary Computation Competition
Country/Territory	Ireland
City	Dublin
Period	12/07/11 → 16/07/11

Bibliographical note

Competition winning entry

Access to Document

edaIsingSpinGlassSubmitted manuscript, 130 KB

Cite this

@conference{3d7f00dad4234f7bb7ec803d17980be0,

title = "Full Implementation of an Estimation of Distribution Algorithm on a GPU",

abstract = "We submit an implementation of an Estimation of Distribution Algorithm – specifically a variant of the Bayesian Optimisation Algorithm (BOA) – using GPGPU. Every aspect of the algorithm is executed on the device, and it makes effective of use multiple GPU devices in a single machine. As for other EDAs, our implementation is generic in that it may be applied to any problem for which solutions may be represented as binary strings. For the purpose of this paper, we apply it to a particular problem known to be difficult for metaheuristic algorithms due to high interdependency between variables: finding the lowest energy state of an Ising Spin Glass. We show that our GPU implementation demonstrates a speedup in excess of 80x compared with an equivalent CPU implementation. To our knowledge, this is the first EDA to be implemented fully on the GPU.",

author = "Poulding, {Simon Marcus} and Staunton, {Jan Peter} and Burles, {Nathan John}",

note = "Competition winning entry; GECCO 2011, GPUs for Genetic and Evolutionary Computation Competition ; Conference date: 12-07-2011 Through 16-07-2011",

year = "2011",

language = "English",

}

TY - CONF

T1 - Full Implementation of an Estimation of Distribution Algorithm on a GPU

AU - Poulding, Simon Marcus

AU - Staunton, Jan Peter

AU - Burles, Nathan John

N1 - Competition winning entry

PY - 2011

Y1 - 2011

N2 - We submit an implementation of an Estimation of Distribution Algorithm – specifically a variant of the Bayesian Optimisation Algorithm (BOA) – using GPGPU. Every aspect of the algorithm is executed on the device, and it makes effective of use multiple GPU devices in a single machine. As for other EDAs, our implementation is generic in that it may be applied to any problem for which solutions may be represented as binary strings. For the purpose of this paper, we apply it to a particular problem known to be difficult for metaheuristic algorithms due to high interdependency between variables: finding the lowest energy state of an Ising Spin Glass. We show that our GPU implementation demonstrates a speedup in excess of 80x compared with an equivalent CPU implementation. To our knowledge, this is the first EDA to be implemented fully on the GPU.

AB - We submit an implementation of an Estimation of Distribution Algorithm – specifically a variant of the Bayesian Optimisation Algorithm (BOA) – using GPGPU. Every aspect of the algorithm is executed on the device, and it makes effective of use multiple GPU devices in a single machine. As for other EDAs, our implementation is generic in that it may be applied to any problem for which solutions may be represented as binary strings. For the purpose of this paper, we apply it to a particular problem known to be difficult for metaheuristic algorithms due to high interdependency between variables: finding the lowest energy state of an Ising Spin Glass. We show that our GPU implementation demonstrates a speedup in excess of 80x compared with an equivalent CPU implementation. To our knowledge, this is the first EDA to be implemented fully on the GPU.

M3 - Paper

T2 - GECCO 2011, GPUs for Genetic and Evolutionary Computation Competition

Y2 - 12 July 2011 through 16 July 2011

ER -