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