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, final RandomGenerator _randomGenerator,
30 final AbstractEAConfiguration _eaConfiguration, final double populationMutationProbability) {
31 Objects.requireNonNull(_programHelper);
32 Objects.requireNonNull(_randomGenerator);
33 Objects.requireNonNull(_eaConfiguration);
34 Validate.inclusiveBetween(0.0, 1.0, populationMutationProbability);
35
36 this.programHelper = _programHelper;
37 this.randomGenerator = _randomGenerator;
38 this.eaConfiguration = _eaConfiguration;
39 this.populationMutationProbability = populationMutationProbability;
40 }
41
42 protected TreeNode<Operation<?>> duplicateAndCut(final Program program, final TreeNode<Operation<?>> root,
43 final int cutPoint, final int nodeIndex) {
44 Objects.requireNonNull(root);
45 Validate.isTrue(cutPoint >= 0);
46
47 final Operation<?> rootData = root.getData();
48
49 if (nodeIndex == cutPoint) {
50 final OperationFactory randomTerminal = programHelper.pickRandomTerminal(program, rootData.returnedType());
51 final Operation<?> operation = randomTerminal.build(program.inputSpec());
52 return new TreeNode<Operation<?>>(operation);
53 } else {
54 final List<TreeNode<Operation<?>>> children = root.getChildren();
55
56 final TreeNode<Operation<?>> duplicateRoot = new TreeNode<Operation<?>>(rootData);
57
58 int currentIndex = nodeIndex + 1;
59 for (int i = 0; i < children.size(); i++) {
60 final TreeNode<Operation<?>> treeNode = children.get(i);
61 final int childSize = treeNode.getSize();
62
63 final TreeNode<Operation<?>> childCopy = duplicateAndCut(program, treeNode, cutPoint, currentIndex);
64 duplicateRoot.addChild(childCopy);
65 currentIndex += childSize;
66 }
67
68 return duplicateRoot;
69 }
70 }
71
72 @Override
73 public Genotype mutate(final long generation, final Genotype original) {
74 Validate.isTrue(generation >= 0);
75 Objects.requireNonNull(original);
76
77 if (randomGenerator.nextDouble() < populationMutationProbability == false) {
78 return original;
79 }
80
81 final Chromosome[] newChromosomes = new Chromosome[original.getSize()];
82 final Chromosome[] chromosomes = original.getChromosomes();
83 for (int chromosomeIndex = 0; chromosomeIndex < chromosomes.length; chromosomeIndex++) {
84 final ChromosomeSpec chromosomeSpec = eaConfiguration.getChromosomeSpec(chromosomeIndex);
85 final Chromosome chromosome = chromosomes[chromosomeIndex];
86
87 if (chromosomeSpec instanceof ProgramTreeChromosomeSpec == false) {
88 throw new IllegalArgumentException("This mutator does not support chromosome specs " + chromosomeSpec);
89 }
90
91 if (chromosome instanceof TreeChromosome<?> == false) {
92 throw new IllegalArgumentException(
93 "This mutator does not support chromosome of type " + chromosome.getClass()
94 .getSimpleName());
95 }
96
97 final ProgramTreeChromosomeSpec programTreeChromosomeSpec = (ProgramTreeChromosomeSpec) chromosomeSpec;
98
99 final TreeChromosome<Operation<?>> treeChromosome = (TreeChromosome<Operation<?>>) chromosome;
100 final int chromosomeSize = treeChromosome.getSize();
101
102 if (chromosomeSize > 2) {
103 final int cutPoint = randomGenerator.nextInt(chromosomeSize - 1) + 1;
104
105 final TreeNode<Operation<?>> root = treeChromosome.getRoot();
106 final TreeNode<Operation<?>> newRoot = duplicateAndCut(programTreeChromosomeSpec.program(),
107 root,
108 cutPoint,
109 0);
110 final TreeChromosome<Operation<?>> newTreeChromosome = new TreeChromosome<>(newRoot);
111 newChromosomes[chromosomeIndex] = newTreeChromosome;
112 } else {
113 newChromosomes[chromosomeIndex] = chromosome;
114 }
115
116 }
117
118 return new Genotype(newChromosomes);
119 }
120 }