Massively parallel differential evolution—pattern search optimization with graphics hardware acceleration: an investigation on bound constrained optimization problems

This paper presents a novel parallel Differential Evolution (DE) algorithm with local search for solving function optimization problems, utilizing graphics hardware acceleration. As a population-based meta-heuristic, DE was originally designed for continuous function optimization. Graphics Processing Units (GPU) computing is an emerging desktop parallel computing technology that is becoming popular with its wide availability in many personal computers. In this paper, the classical DE was adapted in the data-parallel CPU-GPU heterogeneous computing platform featuring Single Instruction-Multiple Thread (SIMT) execution. The global optimal search of the DE was enhanced by the classical local Pattern Search (PS) method. The hybrid DE–PS method was implemented in the GPU environment and compared to a similar implementation in the common computing environment with a Central Processing Unit (CPU). Computational results indicate that the GPU-accelerated SIMT-DE-PS method is orders of magnitude faster than the corresponding CPU implementation. The main contribution of this paper is the parallelization analysis and performance analysis of the hybrid DE–PS with GPU acceleration. The research results demonstrate a promising direction for high speed optimization with desktop parallel computing on a personal computer.

\({x_t^g }\) :

A solution vector with index t at generation g

\({v_t^g }\) :

Mutant vector for a vector with index t at DE generation g

\({u_t^g }\) :

Trial vector for a vector with index t at DE generation g

F :

Mutant constant in DE

\({f(x_t^g )}\) :

Solution cost for a vector with index t at DE generation g

c(x _t ):

Bound constraints for a vector with index t, x _min ≤ x _t ≤ x _max

\({e_j^+ ,e_j^- }\) :

The positive and negative unit directional vector in PS

Δ^k :

Step size in PS

Δ⁰ :

Initial step size in PS

Δ_min :

Minimal step size in PS

i :

Index of problem dimensions, i = 0, 1, ..., n − 1, where n is the problem dimension

t :

Index of vectors, t = 0, 1, ..., T − 1, where T is the number of vectors (threads)

r1, r2, r3, r4:

Indices of randomly selected vectors

j :

Index of the unit coordinate axes in PS, j = 0, 1, ..., n − 1

g :

Current DE generation, g = 0, 1, ..., G − 1, where G is the number of generations

k :

Current PS iteration, k = 0, 1, ..., K − 1, where K is the number of iterations

Authors and Affiliations

1. Department of Industrial Engineering, Lamar University, P.O. Box 10032, Beaumont, TX, 77710, USA

   Weihang Zhu

Corresponding author

Correspondence to Weihang Zhu.

Reprints and permissions