Non-revisiting Genetic Algorithm with Constant Memory

Yang LOU, Shiu Yin YUEN

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

1 Citation (Scopus)

Abstract

The continuous Non-revisiting Genetic Algorithm (cNrGA) uses the entire search history and parameter-less adaptive mutation to significantly enhance search performance. Experimental results show that it has better performance than Covariance Matrix Adaptation Evolution Strategy (CMA-ES), a state of the art evolutionary algorithm. Storing the search history is natural and costs little when fitness evaluations are expensive. However, if the number of evaluations required is substantial, some memory management is desirable. In this paper, we propose two pruning mechanisms to keep the memory used constant. They are Random pruning and Least Recently Used pruning. The idea is to prune a node when a memory threshold is reached and a new node is required to be inserted, thus keeping the overall memory used constant. Experimental results show that both strategies can maintain the performance of cNrGA, up to the limit when 90% of the nodes are not recorded. This suggests that cNrGA can be extended to use in situations when the number of fitness evaluations are much larger than before with no significant effect on statistical performance, which widens the applicability of cNrGA to include more practical problems that require larger number of fitness evaluations before converging to the global optimum.

Original languageEnglish
Title of host publication2015 IEEE International Conference on Systems, Man, and Cybernetics
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1714-1719
Number of pages6
ISBN (Electronic)9781479986965
DOIs
Publication statusPublished - 2015
Externally publishedYes
EventIEEE International Conference on Systems, Man, and Cybernetics, SMC 2015 - Kowloon Tong, Hong Kong
Duration: 9 Oct 201512 Oct 2015

Conference

ConferenceIEEE International Conference on Systems, Man, and Cybernetics, SMC 2015
Country/TerritoryHong Kong
CityKowloon Tong
Period9/10/1512/10/15

Bibliographical note

Publisher Copyright:
© 2015 IEEE.

Keywords

  • binary space partition tree
  • least recently used pruning
  • Non-revisiting genetic algorithms
  • random pruning

Fingerprint

Dive into the research topics of 'Non-revisiting Genetic Algorithm with Constant Memory'. Together they form a unique fingerprint.

Cite this