Analysis on the collaboration between global search and local search in memetic computation

Jih Yiing Lin*, Ying-Ping Chen

*Corresponding author for this work

Research output: Contribution to journalArticle

33 Scopus citations

Abstract

The synergy between exploration and exploitation has been a prominent issue in optimization. The rise of memetic algorithms, a category of optimization techniques which feature the explicit exploration-exploitation coordination, much accentuates this issue. While memetic algorithms have achieved remarkable success in a wide range of real-world applications, the key to successful exploration-exploitation synergies still remains obscure as conclusions drawn from empirical results or theoretical derivations are usually quite algorithm specific and/or problem dependent. This paper aims to provide a theoretical model that can depict the collaboration between global search and local search in memetic computation on a broad class of objective functions. In the proposed model, the interaction between global search and local search creates a set of local search zones, in which the global optimal points reside, within the search space. Based on such a concept, the quasi-basin class (QBC) which categorizes problems according to the distribution of their local search zones is adopted. The subthreshold seeker, taken as a representative archetype of memetic algorithms, is analyzed on various QBCs to develop a general model for memetic algorithms. As the proposed model not only well describes the expected time for a simple memetic algorithm to find the optimal point on different QBCs but also consists with the observations made in previous studies in the literature, the proposed model may reveal important insights to the design of memetic algorithms in general.

Original languageEnglish
Article number6031912
Pages (from-to)608-623
Number of pages16
JournalIEEE Transactions on Evolutionary Computation
Volume15
Issue number5
DOIs
StatePublished - 1 Oct 2011

Keywords

  • Global search
  • local search
  • memetic algorithms
  • quasi-basin class
  • subthreshold seeker

Fingerprint Dive into the research topics of 'Analysis on the collaboration between global search and local search in memetic computation'. Together they form a unique fingerprint.

  • Cite this