1 package net.bmahe.genetics4j.gp.spec.selection;
2
3 import java.util.Comparator;
4
5 import org.apache.commons.lang3.Validate;
6 import org.immutables.value.Value;
7
8 import net.bmahe.genetics4j.core.Individual;
9 import net.bmahe.genetics4j.core.spec.selection.SelectionPolicy;
10 import net.bmahe.genetics4j.core.spec.selection.Tournament;
11
12 /**
13 * Double tournament selection strategy that combines fitness-based and parsimony-based selection to control bloat in
14 * genetic programming and other evolutionary algorithms.
15 *
16 * <p>Double tournament selection operates in two modes:
17 * <ul>
18 * <li><b>Fitness First Mode</b> (default): Performs two independent fitness tournaments, then applies parsimony
19 * selection between the winners to select the less complex individual</li>
20 * <li><b>Parsimony First Mode</b>: For each tournament candidate, performs parsimony selection on random pairs first,
21 * then selects the fittest among the parsimony winners</li>
22 * </ul>
23 *
24 * <p>The parsimony tournament uses a probabilistic approach where the parsimony tournament size parameter controls the
25 * selection pressure toward less complex individuals:
26 * <ul>
27 * <li>Size 0.0: Always selects randomly (no parsimony pressure)</li>
28 * <li>Size 1.0: Balanced selection between complexity preferences</li>
29 * <li>Size 2.0: Always selects the less complex individual</li>
30 * </ul>
31 *
32 * <p>This selection method is particularly effective in genetic programming where it helps prevent code bloat while
33 * maintaining competitive fitness levels.
34 *
35 * @param <T> the fitness type, must be Comparable
36 *
37 * @see DoubleTournamentSelector
38 * @see Tournament
39 */
40 @Value.Immutable
41 public abstract class DoubleTournament<T extends Comparable<T>> implements SelectionPolicy {
42
43 /**
44 * The fitness tournament configuration used for selecting individuals based on fitness. This tournament determines
45 * how many candidates compete in each fitness-based selection round.
46 *
47 * @return the tournament configuration for fitness-based selection
48 */
49 @Value.Parameter
50 public abstract Tournament<T> fitnessTournament();
51
52 /**
53 * Comparator used to evaluate parsimony (complexity) between individuals. Typically compares individuals based on
54 * size, depth, or other complexity metrics. The comparator should return:
55 * <ul>
56 * <li>Negative value if first individual is less complex than second</li>
57 * <li>Zero if both individuals have equal complexity</li>
58 * <li>Positive value if first individual is more complex than second</li>
59 * </ul>
60 *
61 * @return the comparator for evaluating individual complexity
62 */
63 @Value.Parameter
64 public abstract Comparator<Individual<T>> parsimonyComparator();
65
66 /**
67 * Controls the selection pressure toward less complex individuals in parsimony tournaments. Must be between 0.0 and
68 * 2.0 inclusive.
69 * <ul>
70 * <li>0.0: No parsimony pressure, selection is random</li>
71 * <li>1.0: Balanced parsimony pressure</li>
72 * <li>2.0: Maximum parsimony pressure, always selects less complex individual</li>
73 * </ul>
74 *
75 * @return the parsimony tournament size parameter
76 */
77 @Value.Parameter
78 public abstract double parsimonyTournamentSize();
79
80 /**
81 * Determines the order of selection operations.
82 * <ul>
83 * <li>{@code true} (default): Fitness first mode - perform fitness tournaments first, then apply parsimony selection
84 * between winners</li>
85 * <li>{@code false}: Parsimony first mode - apply parsimony selection to random pairs first, then perform fitness
86 * tournament among parsimony winners</li>
87 * </ul>
88 *
89 * @return true for fitness-first mode, false for parsimony-first mode
90 */
91 @Value.Default
92 public boolean doFitnessFirst() {
93 return true;
94 }
95
96 /**
97 * Validates that the parsimony tournament size is within the allowed range [0.0, 2.0].
98 *
99 * @throws IllegalArgumentException if parsimony tournament size is outside valid range
100 */
101 @Value.Check
102 public void check() {
103 Validate.inclusiveBetween(0.0d, 2.0d, parsimonyTournamentSize());
104 }
105
106 /**
107 * Creates a new DoubleTournament selection policy with fitness-first mode enabled.
108 *
109 * @param <U> the fitness type, must be Comparable
110 * @param fitnessTournament the tournament configuration for fitness-based selection
111 * @param parsimonyComparator comparator for evaluating individual complexity
112 * @param parsimonyTournamentSize selection pressure parameter, must be between 0.0 and 2.0
113 * @return a new DoubleTournament instance with the specified parameters
114 * @throws IllegalArgumentException if parsimony tournament size is outside valid range
115 */
116 public static <U extends Comparable<U>> DoubleTournament<U> of(final Tournament<U> fitnessTournament,
117 final Comparator<Individual<U>> parsimonyComparator, final double parsimonyTournamentSize) {
118 return ImmutableDoubleTournament.of(fitnessTournament, parsimonyComparator, parsimonyTournamentSize);
119 }
120 }