Frequency fitness assignment

Thomas WEISE, Mingxu WAN, Pu WANG, Ke TANG, Alexandre DEVERT, Xin YAO

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

21 Citations (Scopus)

Abstract

Metaheuristic optimization procedures such as evolutionary algorithms are usually driven by an objective function that rates the quality of a candidate solution. However, it is not clear in practice whether an objective function adequately rewards intermediate solutions on the path to the global optimum and it may exhibit deceptiveness, epistasis, neutrality, ruggedness, and a lack of causality. In this paper, we introduce the frequency fitness H, subject to minimization, which rates how often solutions with the same objective value have been discovered so far. The ideas behind this method are that good solutions are difficult to find and that if an algorithm gets stuck at a local optimum, the frequency of the objective values of the surrounding solutions will increase over time, which will eventually allow it to leave that region again. We substitute a frequency fitness assignment process (FFA) for the objective function into several different optimization algorithms. We conduct a comprehensive set of experiments: the synthesis of algorithms with genetic programming (GP), the solution of MAX-3SAT problems with genetic algorithms, classification with Memetic Genetic Programming, and numerical optimization with a (1+1) Evolution Strategy, to verify the utility of FFA. Given that they have no access to the original objective function at all, it is surprising that for some problems (e.g., the algorithm synthesis task) the FFA-based algorithm variants perform significantly better. However, this cannot be guaranteed for all tested problems. Thus, we also analyze scenarios where algorithms using FFA do not perform better or perform even worse than with the original objective functions. © 1997-2012 IEEE.
Original languageEnglish
Article number6476662
Pages (from-to)226-243
Number of pages18
JournalIEEE Transactions on Evolutionary Computation
Volume18
Issue number2
Early online date8 Mar 2013
DOIs
Publication statusPublished - Apr 2014
Externally publishedYes

Funding

This work was supported in part by the 973 Program of China under Grant 2011CB707006, the National Natural Science Foundation of China under Grants 61150110488, 61028009, and 61175065, the Special Financial Grant 201104329 from the China Post-Doctoral Science Foundation, the Chinese Academy of Sciences Fellowship for Young International Scientists under Grant 2011Y1GB01, the Natural Science Foundation of the Anhui Province under Grant 1108085J16, and the European Union 7th Framework Program under Grant 247619.

Keywords

  • Combinatorial optimization
  • diversity
  • fitness assignment
  • frequency
  • genetic programming (GP)
  • numerical optimization

Fingerprint

Dive into the research topics of 'Frequency fitness assignment'. Together they form a unique fingerprint.

Cite this