On-line Search History-assisted Restart Strategy for Covariance Matrix Adaptation Evolution Strategy

Yang LOU, Shiu Yin YUEN, Guanrong CHEN, Xin ZHANG

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

1 Citation (Scopus)

Abstract

Restart strategy helps the covariance matrix adaptation evolution strategy (CMA-ES) to increase the probability of finding the global optimum in optimization, while a single run CMA-ES is easy to be trapped in local optima. In this paper, the continuous non-revisiting genetic algorithm (cNrGA) is used to help CMA-ES to achieve multiple restarts from different sub-regions of the search space. The CMA-ES with on-line search history-assisted restart strategy (HR-CMA-ES) is proposed. The entire on-line search history of cNrGA is stored in a binary space partitioning (BSP) tree, which is effective for performing local search. The frequently sampled sub-region is reflected by a deep position in the BSP tree. When leaf nodes are located deeper than a threshold, the corresponding sub-region is considered a region of interest (ROI). In HR-CMA-ES, cNrGA is responsible for global exploration and suggesting ROI for CMA-ES to perform an exploitation within or around the ROI. CMA-ES restarts independently in each suggested ROI. The non-revisiting mechanism of cNrGA avoids to suggest the same ROI for a second time. Experimental results on the CEC 2013 and 2017 benchmark suites show that HR-CMA-ES performs better than both CMA-ES and cNrGA. A positive synergy is observed by the memetic cooperation of the two algorithms.

Original languageEnglish
Title of host publication2019 IEEE Congress on Evolutionary Computation, CEC 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages3142-3149
Number of pages8
ISBN (Electronic)9781728121536
ISBN (Print)9781728121543
DOIs
Publication statusPublished - Jun 2019
Externally publishedYes
Event2019 IEEE Congress on Evolutionary Computation - Wellington, New Zealand
Duration: 10 Jun 201913 Jun 2019

Conference

Conference2019 IEEE Congress on Evolutionary Computation
Abbreviated titleCEC 2019
Country/TerritoryNew Zealand
CityWellington
Period10/06/1913/06/19

Bibliographical note

Funding Information:
This research was supported in part by a grant from the Hong Kong Research Grants Council under GRF Grant CityU 125313 and GRF Grant 11200317, the National Natural Science Foundation of China (Project No. 61603275, 61601329), and the Tianjin Higher Education Creative Team Funds Program.

Publisher Copyright:
© 2019 IEEE.

Keywords

  • covariance matrix adaptation evolution strategy
  • memetic algorithm
  • non-revisiting genetic algorithm
  • on-line history

Fingerprint

Dive into the research topics of 'On-line Search History-assisted Restart Strategy for Covariance Matrix Adaptation Evolution Strategy'. Together they form a unique fingerprint.

Cite this