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<>(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 return Stream.concat(functions.stream(), terminals.stream())
83 .filter(opFactory -> returnedType.isAssignableFrom(opFactory.returnedType()))
84 .filter(opFactory -> {
85
86 if (opFactory.acceptedTypes().length != acceptedTypes.size()) {
87 return false;
88 }
89
90 for (int i = 0; i < acceptedTypes.size(); i++) {
91
92 if (acceptedTypes.get(i).isAssignableFrom(opFactory.acceptedTypes()[i]) == false) {
93 return false;
94 }
95 }
96
97 return true;
98 })
99 .collect(Collectors.toList());
100 }
101
102 protected TreeNode<Operation<?>> duplicateAndReplaceNode(final Program program, final TreeNode<Operation<?>> root,
103 final int cutPoint, final int nodeIndex) {
104 Objects.requireNonNull(root);
105 Validate.isTrue(cutPoint >= 0);
106
107 final Operation<?> rootData = root.getData();
108
109 if (nodeIndex == cutPoint) {
110
111 final List<OperationFactory> candidates = findReplacementCandidates(program, root);
112
113 if (candidates.isEmpty() == false) {
114
115 final OperationFactory chosenOperationFactory = candidates.get(randomGenerator.nextInt(candidates.size()));
116 final Operation operation = chosenOperationFactory.build(program.inputSpec());
117
118 final TreeNode<Operation<?>> replacedNode = new TreeNode<>(operation);
119 int currentIndex = nodeIndex + 1;
120 for (final TreeNode<Operation<?>> child : root.getChildren()) {
121 final int childSize = child.getSize();
122
123 final TreeNode<Operation<?>> childCopy = duplicateAndReplaceNode(program, child, cutPoint, currentIndex);
124 replacedNode.addChild(childCopy);
125 currentIndex += childSize;
126
127 }
128
129 return replacedNode;
130 } else {
131 return duplicateNode(program, root, cutPoint, nodeIndex);
132 }
133 } else {
134 return duplicateNode(program, root, cutPoint, nodeIndex);
135 }
136 }
137
138 @Override
139 public Genotype mutate(final long generation, final Genotype original) {
140 Validate.isTrue(generation >= 0);
141 Objects.requireNonNull(original);
142
143 if ((randomGenerator.nextDouble() < populationMutationProbability) == false) {
144 return original;
145 }
146
147 final Chromosome[] newChromosomes = new Chromosome[original.getSize()];
148 final Chromosome[] chromosomes = original.getChromosomes();
149 for (int chromosomeIndex = 0; chromosomeIndex < chromosomes.length; chromosomeIndex++) {
150 final ChromosomeSpec chromosomeSpec = eaConfiguration.getChromosomeSpec(chromosomeIndex);
151 final Chromosome chromosome = chromosomes[chromosomeIndex];
152
153 if ((chromosomeSpec instanceof ProgramTreeChromosomeSpec) == false) {
154 throw new IllegalArgumentException("This mutator does not support chromosome specs " + chromosomeSpec);
155 }
156
157 if ((chromosome instanceof TreeChromosome<?>) == false) {
158 throw new IllegalArgumentException(
159 "This mutator does not support chromosome of type " + chromosome.getClass().getSimpleName());
160 }
161
162 final ProgramTreeChromosomeSpec programTreeChromosomeSpec = (ProgramTreeChromosomeSpec) chromosomeSpec;
163
164 final TreeChromosome<Operation<?>> treeChromosome = (TreeChromosome<Operation<?>>) chromosome;
165 final int chromosomeSize = treeChromosome.getSize();
166
167 if (chromosomeSize > 2) {
168 final int cutPoint = randomGenerator.nextInt(chromosomeSize - 1) + 1;
169
170 final TreeNode<Operation<?>> root = treeChromosome.getRoot();
171 final TreeNode<Operation<?>> newRoot = duplicateAndReplaceNode(
172 programTreeChromosomeSpec.program(),
173 root,
174 cutPoint,
175 0);
176
177 final TreeChromosome<Operation<?>> newTreeChromosome = new TreeChromosome<>(newRoot);
178 newChromosomes[chromosomeIndex] = newTreeChromosome;
179 } else {
180 newChromosomes[chromosomeIndex] = chromosome;
181 }
182
183 }
184
185 return new Genotype(newChromosomes);
186 }
187 }