# Frequency Fitness Assignment: Optimization without Bias for Good Solutions can be Efficient

arXiv: https://arxiv.org/abs/2112.00229 · HTML: https://mlsanity.com/paper/2112.00229/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 69 references that are in the map.
- First posted on arXiv 1 Dec 2021.

## Builds on (most cited first, 14 of 14)

- [Quality and Diversity Optimization: A Unifying Modular Framework](https://mlsanity.com/paper/1708.09251/) (2017)
- [Benchmarking Discrete Optimization Heuristics with IOHprofiler](https://mlsanity.com/paper/1912.09237/) (2019)
- [Quality Diversity Through Surprise](https://mlsanity.com/paper/1807.02397/) (2018)
- [Fixed-Target Runtime Analysis](https://mlsanity.com/paper/2004.09613/) (2020)
- [Runtime Analysis of the (1+(λ,λ)) Genetic Algorithm on Random Satisfiable 3-CNF Formulas](https://mlsanity.com/paper/1704.04366/) (2017)
- [Evolutionary Algorithms and Submodular Functions: Benefits of Heavy-Tailed Mutations](https://mlsanity.com/paper/1805.10902/) (2018)
- [Optimal Parameter Choices Through Self-Adjustment: Applying the 1/5-th Rule in Discrete Settings](https://mlsanity.com/paper/1504.03212/) (2015)
- [Precise Runtime Analysis for Plateau Functions](https://mlsanity.com/paper/1806.01331/) (2018)
- [The Query Complexity of a Permutation-Based Variant of Mastermind](https://mlsanity.com/paper/1812.08480/) (2018)
- [How Crossover Speeds Up Building-Block Assembly in Genetic Algorithms](https://mlsanity.com/paper/1403.6600/) (2014)
- [Unbiased Black-Box Complexities of Jump Functions](https://mlsanity.com/paper/1403.7806/) (2014)
- [On Steady-State Evolutionary Algorithms and Selective Pressure: Why Inverse Rank-Based Allocation of Reproductive Trials is Best](https://mlsanity.com/paper/2103.10394/) (2021)
- [Towards a More Practice-Aware Runtime Analysis of Evolutionary Algorithms](https://mlsanity.com/paper/1812.00493/) (2018)
- [Frequency Fitness Assignment: Making Optimization Algorithms Invariant under Bijective Transformations of the Objective Function Value](https://mlsanity.com/paper/2001.01416/) (2020)

## Abstract (arXiv)

A fitness assignment process transforms the features (such as the objective value) of a candidate solution to a scalar fitness, which then is the basis for selection. Under Frequency Fitness Assignment (FFA), the fitness corresponding to an objective value is its encounter frequency in selection steps and is subject to minimization. FFA creates algorithms that are not biased towards better solutions and are invariant under all injective transformations of the objective function value. We investigate the impact of FFA on the performance of two theory-inspired, state-of-the-art EAs, the Greedy (2+1) GA and the Self-Adjusting (1+(lambda,lambda)) GA. FFA improves their performance significantly on some problems that are hard for them. In our experiments, one FFA-based algorithm exhibited mean runtimes that appear to be polynomial on the theory-based benchmark problems in our study, including traps, jumps, and plateaus. We propose two hybrid approaches that use both direct and FFA-based optimization and find that they perform well. All FFA-based algorithms also perform better on satisfiability problems than any of the pure algorithm variants.