3.2 Multi-objective Fitness

For multi-objective fitness, a fitness score is a list or vector (depending on selector) of values: one for each objective.

SEL provides two selection options for multi-objective optimization: Pareto selection and lexicase selection.

3.2.1 Pareto Selection

Function sel/cp/multi-objective:pareto-selector compares each candidate against a random comparison set, preferring candidates which dominate the comparison set. This will select for individuals along the Pareto front of the population.

Because dominance is a partial order, pareto-selector will often produce multiple winners, requiring a tie-breaker.

Pareto fitness scores are lists in which each list element can be a vector, a list, or a number. When an element in this list is a vector of numeric values, it can be subjected to lexicase selection. The fitness score lists must be the same length (that is, contain the same number of objectives) across the entire population.

3.2.2 Lexicase Selection

Function sel/cp/lexicase:lexicase-select-best performs lexicase selection: a form of multi-objective optimization which prioritizes objectives in a different order for each selection event.

Lexicase fitness scores are vectors of numeric values. The vectors must be the same length across the entire population.

3.2.3 API Support for Multi-Objective Fitness

• Set variable sel:*fitness-predicate* to specify how fitness values should be compared. Note that this applies across all objectives: it is not possible to maximize some objectives while minimizing others.
• Set variable sel:*tournament-selector* to specify the selector function to use for multi-objective optimization. There are currently two such functions:
  • sel/cp/multi-objective:pareto-selector
  • sel/cp/lexicase:lexicase-select-best
• Set variable sel:*tournament-tie-breaker* to specify how the tournament should break ties in the case where the selector produces multiple winners. A useful tie-breaker for multi-objective optimization is sel/cp/multi-objective:pick-least-crowded, which promotes diversity by selecting individuals that are farther from their neighbors in fitness space.

3.2.4 Example

The following code will enable multi-objective optimization with Pareto selection.

(defpackage :example
  (:use :gt/full
        :software-evolution-library
        :software-evolution-library/software/asm
        :software-evolution-library/components/multi-objective))
(in-package :example)

(setf *tournament-selector* #'pareto-selector)
;; Recommended value
(setf *pareto-comparison-set-size* (round (/ *max-population-size* 10)))
(setf *tournament-tie-breaker* #'pick-least-crowded)

(defun test (software)
  ;; Return a list containing scores for each objective.
  (list #| TODO: ... |#))