Lexicase selection (and a few other additions to Clojush)
Wednesday, June 13th, 2012Lexicase selection (and a few other additions) have been made recently to Clojush. See https://github.com/lspector/Clojush and the commit logs for details.
Lexicase selection is a parent selection algorithm that is described in a paper that will be presented at the Understanding Problems workshop at GECCO-2012 (“Assessment of Problem Modality by Differential Performance of Lexicase Selection in Genetic Programming: A Preliminary Report“), the gist of which is that each time we need a parent for use in a genetic operator we:
1. Initialize:
(a) Set candidates to be the entire population.
(b) Set cases to be a list of all of the fitness cases in random order.
2. Loop:
(a) Set candidates to be the subset of the current candidates that have exactly the best fitness of any individual currently in candidates for the first case in cases.
(b) If candidates or cases contains just a single element then return the first individual in candidates.
(c) Otherwise remove the first case from cases and go to Loop.
More specifically this is “global pool, uniform random sequence, elitist lexicase parent selection.” It can be slow if run with large populations, but I believe that it can sometimes be quite useful, particularly for “modal” problems (= problems “that require qualitatively different actions for different inputs”).
