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