1 package net.bmahe.genetics4j.gp.mutation;
2
3 import java.util.List;
4 import java.util.Objects;
5 import java.util.Set;
6 import java.util.random.RandomGenerator;
7 import java.util.stream.Collectors;
8 import java.util.stream.Stream;
9
10 import org.apache.commons.lang3.Validate;
11
12 import net.bmahe.genetics4j.core.Genotype;
13 import net.bmahe.genetics4j.core.chromosomes.Chromosome;
14 import net.bmahe.genetics4j.core.chromosomes.TreeChromosome;
15 import net.bmahe.genetics4j.core.chromosomes.TreeNode;
16 import net.bmahe.genetics4j.core.mutation.Mutator;
17 import net.bmahe.genetics4j.core.spec.AbstractEAConfiguration;
18 import net.bmahe.genetics4j.core.spec.chromosome.ChromosomeSpec;
19 import net.bmahe.genetics4j.gp.Operation;
20 import net.bmahe.genetics4j.gp.OperationFactory;
21 import net.bmahe.genetics4j.gp.program.Program;
22 import net.bmahe.genetics4j.gp.program.ProgramHelper;
23 import net.bmahe.genetics4j.gp.spec.chromosome.ProgramTreeChromosomeSpec;
24
25 public class NodeReplacementMutator implements Mutator {
26
27 private final ProgramHelper programHelper;
28 private final RandomGenerator randomGenerator;
29 private final AbstractEAConfiguration eaConfiguration;
30 private final double populationMutationProbability;
31
32 public NodeReplacementMutator(final ProgramHelper _programHelper,
33 final RandomGenerator _randomGenerator,
34 final AbstractEAConfiguration _eaConfiguration,
35 final double populationMutationProbability) {
36 Objects.requireNonNull(_programHelper);
37 Objects.requireNonNull(_randomGenerator);
38 Objects.requireNonNull(_eaConfiguration);
39 Validate.inclusiveBetween(0.0, 1.0, populationMutationProbability);
40
41 this.programHelper = _programHelper;
42 this.randomGenerator = _randomGenerator;
43 this.eaConfiguration = _eaConfiguration;
44 this.populationMutationProbability = populationMutationProbability;
45 }
46
47 protected TreeNode<Operation<?>> duplicateNode(final Program program, final TreeNode<Operation<?>> root,
48 final int cutPoint, final int nodeIndex) {
49 Objects.requireNonNull(root);
50 Validate.isTrue(cutPoint >= 0);
51
52 final Operation<?> rootData = root.getData();
53 final List<TreeNode<Operation<?>>> children = root.getChildren();
54
55 final TreeNode<Operation<?>> duplicateRoot = new TreeNode<Operation<?>>(rootData);
56
57 int currentIndex = nodeIndex + 1;
58 for (int i = 0; i < children.size(); i++) {
59 final TreeNode<Operation<?>> treeNode = children.get(i);
60 final int childSize = treeNode.getSize();
61
62 final TreeNode<Operation<?>> childCopy = duplicateAndReplaceNode(program, treeNode, cutPoint, currentIndex);
63 duplicateRoot.addChild(childCopy);
64 currentIndex += childSize;
65 }
66
67 return duplicateRoot;
68 }
69
70 protected List<OperationFactory> findReplacementCandidates(final Program program,
71 final TreeNode<Operation<?>> root) {
72 Objects.requireNonNull(root);
73
74 final Operation<?> rootData = root.getData();
75
76 final Class returnedType = rootData.returnedType();
77 final List<Class> acceptedTypes = rootData.acceptedTypes();
78
79 final Set<OperationFactory> functions = program.functions();
80 final Set<OperationFactory> terminals = program.terminal();
81
82 final List<OperationFactory> candidates = Stream.concat(functions.stream(), terminals.stream())
83 .filter(opFactory -> {
84 final boolean b = returnedType.isAssignableFrom(opFactory.returnedType());
85 return b;
86 })
87 .filter(opFactory -> {
88
89 if (opFactory.acceptedTypes().length != acceptedTypes.size()) {
90 return false;
91 }
92
93 for (int i = 0; i < acceptedTypes.size(); i++) {
94
95 if (acceptedTypes.get(i).isAssignableFrom(opFactory.acceptedTypes()[i]) == false) {
96 return false;
97 }
98 }
99
100 return true;
101 })
102 .collect(Collectors.toList());
103
104 return candidates;
105 }
106
107 protected TreeNode<Operation<?>> duplicateAndReplaceNode(final Program program, final TreeNode<Operation<?>> root,
108 final int cutPoint, final int nodeIndex) {
109 Objects.requireNonNull(root);
110 Validate.isTrue(cutPoint >= 0);
111
112 final Operation<?> rootData = root.getData();
113
114 if (nodeIndex == cutPoint) {
115
116 final List<OperationFactory> candidates = findReplacementCandidates(program, root);
117
118 if (candidates.size() > 0) {
119
120 final OperationFactory chosenOperationFactory = candidates.get(randomGenerator.nextInt(candidates.size()));
121 final Operation operation = chosenOperationFactory.build(program.inputSpec());
122
123 final TreeNode<Operation<?>> replacedNode = new TreeNode<Operation<?>>(operation);
124 int currentIndex = nodeIndex + 1;
125 for (final TreeNode<Operation<?>> child : root.getChildren()) {
126 final int childSize = child.getSize();
127
128 final TreeNode<Operation<?>> childCopy = duplicateAndReplaceNode(program, child, cutPoint, currentIndex);
129 replacedNode.addChild(childCopy);
130 currentIndex += childSize;
131
132 }
133
134 return replacedNode;
135 } else {
136 return duplicateNode(program, root, cutPoint, nodeIndex);
137 }
138 } else {
139 return duplicateNode(program, root, cutPoint, nodeIndex);
140 }
141 }
142
143 @Override
144 public Genotype mutate(final long generation, final Genotype original) {
145 Validate.isTrue(generation >= 0);
146 Objects.requireNonNull(original);
147
148 if (randomGenerator.nextDouble() < populationMutationProbability == false) {
149 return original;
150 }
151
152 final Chromosome[] newChromosomes = new Chromosome[original.getSize()];
153 final Chromosome[] chromosomes = original.getChromosomes();
154 for (int chromosomeIndex = 0; chromosomeIndex < chromosomes.length; chromosomeIndex++) {
155 final ChromosomeSpec chromosomeSpec = eaConfiguration.getChromosomeSpec(chromosomeIndex);
156 final Chromosome chromosome = chromosomes[chromosomeIndex];
157
158 if (chromosomeSpec instanceof ProgramTreeChromosomeSpec == false) {
159 throw new IllegalArgumentException("This mutator does not support chromosome specs " + chromosomeSpec);
160 }
161
162 if (chromosome instanceof TreeChromosome<?> == false) {
163 throw new IllegalArgumentException(
164 "This mutator does not support chromosome of type " + chromosome.getClass().getSimpleName());
165 }
166
167 final ProgramTreeChromosomeSpec programTreeChromosomeSpec = (ProgramTreeChromosomeSpec) chromosomeSpec;
168
169 final TreeChromosome<Operation<?>> treeChromosome = (TreeChromosome<Operation<?>>) chromosome;
170 final int chromosomeSize = treeChromosome.getSize();
171
172 if (chromosomeSize > 2) {
173 final int cutPoint = randomGenerator.nextInt(chromosomeSize - 1) + 1;
174
175 final TreeNode<Operation<?>> root = treeChromosome.getRoot();
176 final TreeNode<Operation<?>> newRoot = duplicateAndReplaceNode(
177 programTreeChromosomeSpec.program(),
178 root,
179 cutPoint,
180 0);
181
182 final TreeChromosome<Operation<?>> newTreeChromosome = new TreeChromosome<>(newRoot);
183 newChromosomes[chromosomeIndex] = newTreeChromosome;
184 } else {
185 newChromosomes[chromosomeIndex] = chromosome;
186 }
187
188 }
189
190 return new Genotype(newChromosomes);
191 }
192 }