Epsilon Lexicase Selection

Lexicase selection is a parent selection algorithm that is described here.

Epsilon lexicase selection is a refinement of lexicase selection developed by William La Cava (@williamlacava) for use on problems with floating-point error values.

Epsilon lexicase selection is identical to ordinary lexicase selection except for the way that filtering is done, which is described for ordinary lexicase selection in step 2a here, as:

In the recommended form of epsilon lexicase selection (see below for a discussion of alternatives), we keep not only the candidates with exactly the best performance of any individual currently in the set (on the given case), but also any other candidates with performance that differs from the best performance (on that case) by less than epsilon, where epsilon is the median absolute difference between errors on the case and the median error for the case, computed over the entire population, once per generation.

Different versions of epsilon lexicase selection: The 2016 GECCO paper that introduces epsilon lexicase selection, and other publications including the more comprehensive 2018 ECJ article (arXiv preprint, MIT Press, PubMed), describe multiple formulations of epsilon lexicase selection. These differ primarily in the way that epsilon is calculated and in the way that the “best” performance on a case is determined at each step of filtering. For example, either may be determined relative to the entire population, once per generation (“statically”), or relative to the current set of candidates during filtering (“dynamically”). Some also differ in the ways that errors are processed to produce epsilon (that is, using a formulation other than “the median absolute difference between errors on the case and the median error for the case”). For historical reasons, the terminology used for the multiple versions is not entirely consistent across publications, but the method described above has proven to be both among the simplest and among the most effective across many tests on many problems. We therefore recommend that this version be used in most cases, and that the name “epsilon lexicase selection,” when used without further qualification, be used to refer to this version. In the context of the terminology in the literature, this version might be more fully described as “semi-dynamic $\epsilon_{e\lambda}$ lexicase selection.”

2 Likes

I don’t have edit privileges: “What is epsilon?”

This is based on the phrase “epsilon-optimal” from Optimization Theory, Game Theory and Mathematical Programming. A solution is considered epsilon-optimal if it is within some small $\epsilon$ of the “true optimal” value.

1 Like

For those interested in different versions of epsilon lexicase selection, please see a preprint of our recent paper comparing different definitions of epsilon.

3 Likes

(Bumping topic because of significant updates.)