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 import org.apache.logging.log4j.LogManager;
8 import org.apache.logging.log4j.Logger;
9
10 import net.bmahe.genetics4j.core.Genotype;
11 import net.bmahe.genetics4j.core.chromosomes.Chromosome;
12 import net.bmahe.genetics4j.core.chromosomes.TreeChromosome;
13 import net.bmahe.genetics4j.core.chromosomes.TreeNode;
14 import net.bmahe.genetics4j.core.mutation.Mutator;
15 import net.bmahe.genetics4j.core.spec.AbstractEAConfiguration;
16 import net.bmahe.genetics4j.core.spec.chromosome.ChromosomeSpec;
17 import net.bmahe.genetics4j.gp.Operation;
18 import net.bmahe.genetics4j.gp.program.Program;
19 import net.bmahe.genetics4j.gp.program.ProgramGenerator;
20 import net.bmahe.genetics4j.gp.spec.chromosome.ProgramTreeChromosomeSpec;
21
22 public class ProgramRandomMutateMutator implements Mutator {
23 final static public Logger logger = LogManager.getLogger(ProgramRandomMutateMutator.class);
24
25 private final ProgramGenerator programGenerator;
26 private final RandomGenerator randomGenerator;
27 private final AbstractEAConfiguration eaConfiguration;
28 private final double populationMutationProbability;
29
30 public ProgramRandomMutateMutator(final ProgramGenerator _programGenerator, final RandomGenerator _randomGenerator,
31 final AbstractEAConfiguration _eaConfiguration, final double _populationMutationProbability) {
32 Validate.notNull(_programGenerator);
33 Validate.notNull(_randomGenerator);
34 Validate.notNull(_eaConfiguration);
35 Validate.inclusiveBetween(0.0, 1.0, _populationMutationProbability);
36
37 this.programGenerator = _programGenerator;
38 this.randomGenerator = _randomGenerator;
39 this.eaConfiguration = _eaConfiguration;
40 this.populationMutationProbability = _populationMutationProbability;
41 }
42
43 protected TreeNode<Operation<?>> duplicateAndMutate(final Program program, final TreeNode<Operation<?>> root,
44 final int cutPoint, final int nodeIndex, final int currentDepth) {
45 Validate.notNull(program);
46 Validate.notNull(root);
47 Validate.isTrue(cutPoint >= 0);
48
49 final Operation<?> rootData = root.getData();
50
51 if (nodeIndex == cutPoint) {
52 final int depth = Math.max(1, program.maxDepth() - currentDepth);
53 final int maxSubtreeDepth = depth > 1 ? randomGenerator.nextInt(depth - 1) + 1 : depth;
54 return programGenerator.generate(program, maxSubtreeDepth, rootData.returnedType());
55 }
56
57 final List<TreeNode<Operation<?>>> children = root.getChildren();
58
59 final TreeNode<Operation<?>> duplicateRoot = new TreeNode<Operation<?>>(rootData);
60
61 int currentIndex = nodeIndex + 1;
62 for (int i = 0; i < children.size(); i++) {
63 final TreeNode<Operation<?>> treeNode = children.get(i);
64 final int childSize = treeNode.getSize();
65
66 final TreeNode<Operation<?>> childCopy = duplicateAndMutate(program,
67 treeNode,
68 cutPoint,
69 currentIndex,
70 currentDepth + 1);
71 duplicateRoot.addChild(childCopy);
72 currentIndex += childSize;
73 }
74
75 return duplicateRoot;
76 }
77
78 @Override
79 public Genotype mutate(final Genotype originalGenotype) {
80 Validate.notNull(originalGenotype);
81
82 if (randomGenerator.nextDouble() >= populationMutationProbability) {
83 return originalGenotype;
84 }
85
86 logger.trace("Mutating genotype {}", originalGenotype);
87
88 final Chromosome[] newChromosomes = new Chromosome[originalGenotype.getSize()];
89 final Chromosome[] chromosomes = originalGenotype.getChromosomes();
90 for (int chromosomeIndex = 0; chromosomeIndex < chromosomes.length; chromosomeIndex++) {
91 final ChromosomeSpec chromosomeSpec = eaConfiguration.getChromosomeSpec(chromosomeIndex);
92 final Chromosome chromosome = chromosomes[chromosomeIndex];
93
94 if (chromosomeSpec instanceof ProgramTreeChromosomeSpec == false) {
95 throw new IllegalArgumentException("This mutator does not support chromosome specs " + chromosomeSpec);
96 }
97
98 if (chromosome instanceof TreeChromosome<?> == false) {
99 throw new IllegalArgumentException(
100 "This mutator does not support chromosome of type " + chromosome.getClass().getSimpleName());
101 }
102
103 final ProgramTreeChromosomeSpec programTreeChromosomeSpec = (ProgramTreeChromosomeSpec) chromosomeSpec;
104
105 final TreeChromosome<Operation<?>> treeChromosome = (TreeChromosome<Operation<?>>) chromosome;
106 final int chromosomeSize = treeChromosome.getSize();
107
108 if (chromosomeSize > 2) {
109 final int cutPoint = randomGenerator.nextInt(chromosomeSize - 1);
110
111 final TreeNode<Operation<?>> root = treeChromosome.getRoot();
112 final TreeNode<Operation<?>> newRoot = duplicateAndMutate(programTreeChromosomeSpec
113 .program(), root, cutPoint, 0, 0);
114 final TreeChromosome<Operation<?>> newTreeChromosome = new TreeChromosome<>(newRoot);
115 newChromosomes[chromosomeIndex] = newTreeChromosome;
116 } else {
117 final TreeNode<Operation<Object>> newRoot = programGenerator.generate(programTreeChromosomeSpec.program(),
118 programTreeChromosomeSpec.program().maxDepth());
119 final TreeChromosome<Operation<Object>> newTreeChromosome = new TreeChromosome<>(newRoot);
120
121 newChromosomes[chromosomeIndex] = newTreeChromosome;
122 }
123
124 logger.trace("\tChromosome {} - {}", chromosomeIndex, newChromosomes[chromosomeIndex]);
125 }
126
127 return new Genotype(newChromosomes);
128 }
129 }