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