1 package net.bmahe.genetics4j.gp.selection;
2
3 import java.util.ArrayList;
4 import java.util.Comparator;
5 import java.util.List;
6 import java.util.Objects;
7 import java.util.random.RandomGenerator;
8 import java.util.stream.IntStream;
9
10 import org.apache.commons.lang3.Validate;
11 import org.apache.logging.log4j.LogManager;
12 import org.apache.logging.log4j.Logger;
13
14 import net.bmahe.genetics4j.core.Genotype;
15 import net.bmahe.genetics4j.core.Individual;
16 import net.bmahe.genetics4j.core.Population;
17 import net.bmahe.genetics4j.core.selection.Selector;
18 import net.bmahe.genetics4j.core.spec.AbstractEAConfiguration;
19 import net.bmahe.genetics4j.core.spec.selection.SelectionPolicy;
20 import net.bmahe.genetics4j.core.spec.selection.Tournament;
21 import net.bmahe.genetics4j.core.util.IndividualUtils;
22 import net.bmahe.genetics4j.gp.spec.selection.DoubleTournament;
23
24 public class DoubleTournamentSelector<T extends Comparable<T>> implements Selector<T> {
25 final static public Logger logger = LogManager.getLogger(DoubleTournamentSelector.class);
26
27 private final SelectionPolicy selectionPolicy;
28 private final RandomGenerator randomGenerator;
29
30 public DoubleTournamentSelector(final SelectionPolicy _selectionPolicy, final RandomGenerator _randomGenerator) {
31 Objects.requireNonNull(_selectionPolicy);
32 Validate.isInstanceOf(DoubleTournament.class, _selectionPolicy);
33 Objects.requireNonNull(_randomGenerator);
34
35 this.selectionPolicy = _selectionPolicy;
36 this.randomGenerator = _randomGenerator;
37 }
38
39 protected Individual<T> randomIndividual(final List<Genotype> population, final List<T> fitnessScore) {
40 Objects.requireNonNull(population);
41 Objects.requireNonNull(fitnessScore);
42 Validate.isTrue(fitnessScore.size() > 0);
43 Validate.isTrue(population.size() == fitnessScore.size());
44
45 final int candidateIndex = randomGenerator.nextInt(fitnessScore.size());
46 return Individual.of(population.get(candidateIndex), fitnessScore.get(candidateIndex));
47
48 }
49
50 protected Individual<T> selectForFitness(final AbstractEAConfiguration<T> eaConfiguration,
51 final Comparator<Individual<T>> fitnessComparator, final int numCandidates, final List<Genotype> population,
52 final List<T> fitnessScore) {
53 Objects.requireNonNull(population);
54 Objects.requireNonNull(fitnessScore);
55 Validate.isTrue(fitnessScore.isEmpty() == false);
56
57 return IntStream.range(0, numCandidates)
58 .boxed()
59 .map(i -> randomIndividual(population, fitnessScore))
60 .max((a, b) -> fitnessComparator.compare(a, b))
61 .get();
62
63 }
64
65 protected Individual<T> parsimonyPick(final Comparator<Individual<T>> parsimonyComparator,
66 final double parsimonyTournamentSize, final Individual<T> first, final Individual<T> second) {
67 Objects.requireNonNull(parsimonyComparator);
68 Validate.inclusiveBetween(0.0, 2.0, parsimonyTournamentSize);
69 Objects.requireNonNull(first);
70 Objects.requireNonNull(second);
71
72 final int parsimonyCompared = parsimonyComparator.compare(first, second);
73
74 Individual<T> selected = first;
75 if (randomGenerator.nextDouble() < parsimonyTournamentSize / 2.0) {
76 if (parsimonyCompared > 0) {
77 selected = second;
78 }
79 } else {
80 if (parsimonyCompared < 0) {
81 selected = second;
82 }
83 }
84
85 return selected;
86 }
87
88 @Override
89 public Population<T> select(final AbstractEAConfiguration<T> eaConfiguration, final long generation,
90 final int numIndividuals, final List<Genotype> population, final List<T> fitnessScore) {
91 Objects.requireNonNull(eaConfiguration);
92 Objects.requireNonNull(population);
93 Objects.requireNonNull(fitnessScore);
94 Validate.isTrue(generation >= 0);
95 Validate.isTrue(numIndividuals > 0);
96 Validate.isTrue(population.size() == fitnessScore.size());
97
98 @SuppressWarnings("unchecked")
99 final DoubleTournament<T> doubleTournament = (DoubleTournament<T>) selectionPolicy;
100 final boolean doFitnessFirst = doubleTournament.doFitnessFirst();
101 final Tournament<T> fitnessTournament = doubleTournament.fitnessTournament();
102 final Comparator<Individual<T>> parsimonyComparator = doubleTournament.parsimonyComparator();
103 final double parsimonyTournamentSize = doubleTournament.parsimonyTournamentSize();
104
105 Validate.isTrue((doFitnessFirst && parsimonyTournamentSize <= 2.0 && parsimonyTournamentSize >= 0.0)
106 || doFitnessFirst == false);
107
108 final Comparator<Individual<T>> fitnessComparator = IndividualUtils.fitnessBasedComparator(eaConfiguration);
109
110 logger.debug("Selecting {} individuals", numIndividuals);
111
112 final Population<T> selectedIndividuals = new Population<>();
113
114 while (selectedIndividuals.size() < numIndividuals) {
115
116 if (doFitnessFirst) {
117 final Individual<T> first = selectForFitness(eaConfiguration,
118 fitnessComparator,
119 fitnessTournament.numCandidates(),
120 population,
121 fitnessScore);
122 final Individual<T> second = selectForFitness(eaConfiguration,
123 fitnessComparator,
124 fitnessTournament.numCandidates(),
125 population,
126 fitnessScore);
127
128 final Individual<T> selected = parsimonyPick(parsimonyComparator, parsimonyTournamentSize, first, second);
129
130 selectedIndividuals.add(selected.genotype(), selected.fitness());
131 } else {
132
133 final int numberCandidatesFitness = fitnessTournament.numCandidates();
134 final List<Individual<T>> candidatesFitness = new ArrayList<>(numberCandidatesFitness);
135
136 for (int i = 0; i < numberCandidatesFitness; i++) {
137 final Individual<T> first = randomIndividual(population, fitnessScore);
138 final Individual<T> second = randomIndividual(population, fitnessScore);
139
140 final Individual<T> selected = parsimonyPick(parsimonyComparator,
141 parsimonyTournamentSize,
142 first,
143 second);
144
145 candidatesFitness.add(selected);
146 }
147
148 final Individual<T> selected = candidatesFitness.stream()
149 .max((a, b) -> fitnessComparator.compare(a, b))
150 .get();
151
152 selectedIndividuals.add(selected.genotype(), selected.fitness());
153 }
154
155 }
156
157 return selectedIndividuals;
158 }
159 }