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, final RandomGenerator _randomGenerator,
33 final AbstractEAConfiguration _eaConfiguration, final double populationMutationProbability) {
34 Objects.requireNonNull(_programHelper);
35 Objects.requireNonNull(_randomGenerator);
36 Objects.requireNonNull(_eaConfiguration);
37 Validate.inclusiveBetween(0.0, 1.0, populationMutationProbability);
38
39 this.programHelper = _programHelper;
40 this.randomGenerator = _randomGenerator;
41 this.eaConfiguration = _eaConfiguration;
42 this.populationMutationProbability = populationMutationProbability;
43 }
44
45 protected TreeNode<Operation<?>> duplicateNode(final Program program, final TreeNode<Operation<?>> root,
46 final int cutPoint, final int nodeIndex) {
47 Objects.requireNonNull(root);
48 Validate.isTrue(cutPoint >= 0);
49
50 final Operation<?> rootData = root.getData();
51 final List<TreeNode<Operation<?>>> children = root.getChildren();
52
53 final TreeNode<Operation<?>> duplicateRoot = new TreeNode<Operation<?>>(rootData);
54
55 int currentIndex = nodeIndex + 1;
56 for (int i = 0; i < children.size(); i++) {
57 final TreeNode<Operation<?>> treeNode = children.get(i);
58 final int childSize = treeNode.getSize();
59
60 final TreeNode<Operation<?>> childCopy = duplicateAndReplaceNode(program, treeNode, cutPoint, currentIndex);
61 duplicateRoot.addChild(childCopy);
62 currentIndex += childSize;
63 }
64
65 return duplicateRoot;
66 }
67
68 protected List<OperationFactory> findReplacementCandidates(final Program program,
69 final TreeNode<Operation<?>> root) {
70 Objects.requireNonNull(root);
71
72 final Operation<?> rootData = root.getData();
73
74 final Class returnedType = rootData.returnedType();
75 final List<Class> acceptedTypes = rootData.acceptedTypes();
76
77 final Set<OperationFactory> functions = program.functions();
78 final Set<OperationFactory> terminals = program.terminal();
79
80 final List<OperationFactory> candidates = Stream.concat(functions.stream(), terminals.stream())
81 .filter(opFactory -> {
82 final boolean b = returnedType.isAssignableFrom(opFactory.returnedType());
83 return b;
84 })
85 .filter(opFactory -> {
86
87 if (opFactory.acceptedTypes().length != acceptedTypes.size()) {
88 return false;
89 }
90
91 for (int i = 0; i < acceptedTypes.size(); i++) {
92
93 if (acceptedTypes.get(i)
94 .isAssignableFrom(opFactory.acceptedTypes()[i]) == false) {
95 return false;
96 }
97 }
98
99 return true;
100 })
101 .collect(Collectors.toList());
102
103 return candidates;
104 }
105
106 protected TreeNode<Operation<?>> duplicateAndReplaceNode(final Program program, final TreeNode<Operation<?>> root,
107 final int cutPoint, final int nodeIndex) {
108 Objects.requireNonNull(root);
109 Validate.isTrue(cutPoint >= 0);
110
111 final Operation<?> rootData = root.getData();
112
113 if (nodeIndex == cutPoint) {
114
115 final List<OperationFactory> candidates = findReplacementCandidates(program, root);
116
117 if (candidates.size() > 0) {
118
119 final OperationFactory chosenOperationFactory = candidates.get(randomGenerator.nextInt(candidates.size()));
120 final Operation operation = chosenOperationFactory.build(program.inputSpec());
121
122 final TreeNode<Operation<?>> replacedNode = new TreeNode<Operation<?>>(operation);
123 int currentIndex = nodeIndex + 1;
124 for (final TreeNode<Operation<?>> child : root.getChildren()) {
125 final int childSize = child.getSize();
126
127 final TreeNode<Operation<?>> childCopy = duplicateAndReplaceNode(program, child, cutPoint, currentIndex);
128 replacedNode.addChild(childCopy);
129 currentIndex += childSize;
130
131 }
132
133 return replacedNode;
134 } else {
135 return duplicateNode(program, root, cutPoint, nodeIndex);
136 }
137 } else {
138 return duplicateNode(program, root, cutPoint, nodeIndex);
139 }
140 }
141
142 @Override
143 public Genotype mutate(final long generation, final Genotype original) {
144 Validate.isTrue(generation >= 0);
145 Objects.requireNonNull(original);
146
147 if (randomGenerator.nextDouble() < populationMutationProbability == false) {
148 return original;
149 }
150
151 final Chromosome[] newChromosomes = new Chromosome[original.getSize()];
152 final Chromosome[] chromosomes = original.getChromosomes();
153 for (int chromosomeIndex = 0; chromosomeIndex < chromosomes.length; chromosomeIndex++) {
154 final ChromosomeSpec chromosomeSpec = eaConfiguration.getChromosomeSpec(chromosomeIndex);
155 final Chromosome chromosome = chromosomes[chromosomeIndex];
156
157 if (chromosomeSpec instanceof ProgramTreeChromosomeSpec == false) {
158 throw new IllegalArgumentException("This mutator does not support chromosome specs " + chromosomeSpec);
159 }
160
161 if (chromosome instanceof TreeChromosome<?> == false) {
162 throw new IllegalArgumentException(
163 "This mutator does not support chromosome of type " + chromosome.getClass()
164 .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(programTreeChromosomeSpec.program(),
177 root,
178 cutPoint,
179 0);
180
181 final TreeChromosome<Operation<?>> newTreeChromosome = new TreeChromosome<>(newRoot);
182 newChromosomes[chromosomeIndex] = newTreeChromosome;
183 } else {
184 newChromosomes[chromosomeIndex] = chromosome;
185 }
186
187 }
188
189 return new Genotype(newChromosomes);
190 }
191 }