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