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(
106 (doFitnessFirst && parsimonyTournamentSize <= 2.0 && parsimonyTournamentSize >= 0.0)
107 || doFitnessFirst == false);
108
109 final Comparator<Individual<T>> fitnessComparator = IndividualUtils.fitnessBasedComparator(eaConfiguration);
110
111 logger.debug("Selecting {} individuals", numIndividuals);
112
113 final Population<T> selectedIndividuals = new Population<>();
114
115 while (selectedIndividuals.size() < numIndividuals) {
116
117 if (doFitnessFirst) {
118 final Individual<T> first = selectForFitness(
119 eaConfiguration,
120 fitnessComparator,
121 fitnessTournament.numCandidates(),
122 population,
123 fitnessScore);
124 final Individual<T> second = selectForFitness(
125 eaConfiguration,
126 fitnessComparator,
127 fitnessTournament.numCandidates(),
128 population,
129 fitnessScore);
130
131 final Individual<T> selected = parsimonyPick(parsimonyComparator, parsimonyTournamentSize, first, second);
132
133 selectedIndividuals.add(selected.genotype(), selected.fitness());
134 } else {
135
136 final int numberCandidatesFitness = fitnessTournament.numCandidates();
137 final List<Individual<T>> candidatesFitness = new ArrayList<>(numberCandidatesFitness);
138
139 for (int i = 0; i < numberCandidatesFitness; i++) {
140 final Individual<T> first = randomIndividual(population, fitnessScore);
141 final Individual<T> second = randomIndividual(population, fitnessScore);
142
143 final Individual<T> selected = parsimonyPick(
144 parsimonyComparator,
145 parsimonyTournamentSize,
146 first,
147 second);
148
149 candidatesFitness.add(selected);
150 }
151
152 final Individual<T> selected = candidatesFitness.stream()
153 .max((a, b) -> fitnessComparator.compare(a, b))
154 .get();
155
156 selectedIndividuals.add(selected.genotype(), selected.fitness());
157 }
158
159 }
160
161 return selectedIndividuals;
162 }
163 }