1 package net.bmahe.genetics4j.gp.mutation;
2
3 import java.util.List;
4 import java.util.Objects;
5 import java.util.random.RandomGenerator;
6
7 import org.apache.commons.lang3.Validate;
8
9 import net.bmahe.genetics4j.core.Genotype;
10 import net.bmahe.genetics4j.core.chromosomes.Chromosome;
11 import net.bmahe.genetics4j.core.chromosomes.TreeChromosome;
12 import net.bmahe.genetics4j.core.chromosomes.TreeNode;
13 import net.bmahe.genetics4j.core.mutation.Mutator;
14 import net.bmahe.genetics4j.core.spec.AbstractEAConfiguration;
15 import net.bmahe.genetics4j.core.spec.chromosome.ChromosomeSpec;
16 import net.bmahe.genetics4j.gp.Operation;
17 import net.bmahe.genetics4j.gp.OperationFactory;
18 import net.bmahe.genetics4j.gp.program.Program;
19 import net.bmahe.genetics4j.gp.program.ProgramHelper;
20 import net.bmahe.genetics4j.gp.spec.chromosome.ProgramTreeChromosomeSpec;
21
22 public class ProgramRandomPruneMutator implements Mutator {
23
24 private final ProgramHelper programHelper;
25 private final RandomGenerator randomGenerator;
26 private final AbstractEAConfiguration eaConfiguration;
27 private final double populationMutationProbability;
28
29 public ProgramRandomPruneMutator(final ProgramHelper _programHelper,
30 final RandomGenerator _randomGenerator,
31 final AbstractEAConfiguration _eaConfiguration,
32 final double populationMutationProbability) {
33 Objects.requireNonNull(_programHelper);
34 Objects.requireNonNull(_randomGenerator);
35 Objects.requireNonNull(_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<?>> duplicateAndCut(final Program program, final TreeNode<Operation<?>> root,
45 final int cutPoint, final int nodeIndex) {
46 Objects.requireNonNull(root);
47 Validate.isTrue(cutPoint >= 0);
48
49 final Operation<?> rootData = root.getData();
50
51 if (nodeIndex == cutPoint) {
52 final OperationFactory randomTerminal = programHelper.pickRandomTerminal(program, rootData.returnedType());
53 final Operation<?> operation = randomTerminal.build(program.inputSpec());
54 return new TreeNode<Operation<?>>(operation);
55 } else {
56 final List<TreeNode<Operation<?>>> children = root.getChildren();
57
58 final TreeNode<Operation<?>> duplicateRoot = new TreeNode<Operation<?>>(rootData);
59
60 int currentIndex = nodeIndex + 1;
61 for (int i = 0; i < children.size(); i++) {
62 final TreeNode<Operation<?>> treeNode = children.get(i);
63 final int childSize = treeNode.getSize();
64
65 final TreeNode<Operation<?>> childCopy = duplicateAndCut(program, treeNode, cutPoint, currentIndex);
66 duplicateRoot.addChild(childCopy);
67 currentIndex += childSize;
68 }
69
70 return duplicateRoot;
71 }
72 }
73
74 @Override
75 public Genotype mutate(final long generation, final Genotype original) {
76 Validate.isTrue(generation >= 0);
77 Objects.requireNonNull(original);
78
79 if (randomGenerator.nextDouble() < populationMutationProbability == false) {
80 return original;
81 }
82
83 final Chromosome[] newChromosomes = new Chromosome[original.getSize()];
84 final Chromosome[] chromosomes = original.getChromosomes();
85 for (int chromosomeIndex = 0; chromosomeIndex < chromosomes.length; chromosomeIndex++) {
86 final ChromosomeSpec chromosomeSpec = eaConfiguration.getChromosomeSpec(chromosomeIndex);
87 final Chromosome chromosome = chromosomes[chromosomeIndex];
88
89 if (chromosomeSpec instanceof ProgramTreeChromosomeSpec == false) {
90 throw new IllegalArgumentException("This mutator does not support chromosome specs " + chromosomeSpec);
91 }
92
93 if (chromosome instanceof TreeChromosome<?> == false) {
94 throw new IllegalArgumentException(
95 "This mutator does not support chromosome of type " + chromosome.getClass().getSimpleName());
96 }
97
98 final ProgramTreeChromosomeSpec programTreeChromosomeSpec = (ProgramTreeChromosomeSpec) chromosomeSpec;
99
100 final TreeChromosome<Operation<?>> treeChromosome = (TreeChromosome<Operation<?>>) chromosome;
101 final int chromosomeSize = treeChromosome.getSize();
102
103 if (chromosomeSize > 2) {
104 final int cutPoint = randomGenerator.nextInt(chromosomeSize - 1) + 1;
105
106 final TreeNode<Operation<?>> root = treeChromosome.getRoot();
107 final TreeNode<Operation<?>> newRoot = duplicateAndCut(
108 programTreeChromosomeSpec.program(),
109 root,
110 cutPoint,
111 0);
112 final TreeChromosome<Operation<?>> newTreeChromosome = new TreeChromosome<>(newRoot);
113 newChromosomes[chromosomeIndex] = newTreeChromosome;
114 } else {
115 newChromosomes[chromosomeIndex] = chromosome;
116 }
117
118 }
119
120 return new Genotype(newChromosomes);
121 }
122 }