Non-revisiting stochastic search revisited: Results, perspectives, and future directions

Yang LOU*, Shiu Yin YUEN, Guanrong CHEN

*Corresponding author for this work

Research output: Journal PublicationsJournal Article (refereed)peer-review

2 Citations (Scopus)

Abstract

The non-revisiting genetic algorithm (NrGA) uses the entire search history with parameter-less adaptive mutation to significantly enhance search performance. In the past decade, a family of non-revisiting stochastic search (NrSS) methods has been developed. Using the entire (or partial) search history to assist evolutionary computation can achieve not only the goal of duplicated solution prevention, but also other utilizations such as adaptive parameter-less local search and fitness landscape estimation. In this survey, the focus is on the memory-assisted stochastic search techniques that store the search history in a binary space partitioning (BSP) tree. First, the basic NrGA is reviewed. Then, the development of the family of NrSS is reviewed from three aspects: 1) the basic NrSS algorithms, 2) conceptual extension of non-revisit and usage of the search history as novel operators and estimators, and 3) application of NrSS to different problem types, such as multi-objective problems, dynamic problems, and multi-modal problems. A comprehensive classification of search history-assisted algorithms suggests that the cumulative historical search information can be developed in a more functional manner; for example, a BSP tree can be simultaneously used for revisit prevention, fitness landscape estimation, and adaptive operation. Both the application on real-world problems and the theoretical analysis of NrSS are reviewed. Possible future work suggestions include a deeper understanding of the non-revisiting scheme in theory, a more comprehensive functional usage of search history, and a closer cooperation with data-driven techniques.

Original languageEnglish
Article number100828
JournalSwarm and Evolutionary Computation
Volume61
Early online date29 Dec 2020
DOIs
Publication statusPublished - Mar 2021
Externally publishedYes

Bibliographical note

Funding Information:
This work was supported by the National Natural Science Foundation of China (No. 62002249 ) and the Hong Kong Research Grants Council through GRF under Grant CityU 11206320.

Publisher Copyright:
© 2020 Elsevier B.V.

Keywords

  • Binary space partitioning tree
  • Evolutionary computation
  • Genetic algorithm
  • Non-revisiting scheme
  • Optimization

Fingerprint

Dive into the research topics of 'Non-revisiting stochastic search revisited: Results, perspectives, and future directions'. Together they form a unique fingerprint.

Cite this