1 package net.bmahe.genetics4j.gp.combination;
2
3 import java.util.ArrayDeque;
4 import java.util.ArrayList;
5 import java.util.Collections;
6 import java.util.Deque;
7 import java.util.HashMap;
8 import java.util.HashSet;
9 import java.util.List;
10 import java.util.Map;
11 import java.util.Set;
12 import java.util.random.RandomGenerator;
13 import java.util.stream.Collectors;
14
15 import org.apache.commons.lang3.Validate;
16
17 import net.bmahe.genetics4j.core.chromosomes.Chromosome;
18 import net.bmahe.genetics4j.core.chromosomes.TreeChromosome;
19 import net.bmahe.genetics4j.core.chromosomes.TreeNode;
20 import net.bmahe.genetics4j.core.combination.ChromosomeCombinator;
21 import net.bmahe.genetics4j.core.spec.AbstractEAConfiguration;
22 import net.bmahe.genetics4j.gp.Operation;
23
24 final class ProgramChromosomeCombinator<T extends Comparable<T>> implements ChromosomeCombinator<T> {
25
26 private final RandomGenerator randomGenerator;
27
28 public ProgramChromosomeCombinator(final RandomGenerator _randomGenerator) {
29 Validate.notNull(_randomGenerator);
30
31 this.randomGenerator = _randomGenerator;
32 }
33
34 @SuppressWarnings("rawtypes")
35 protected Map<Class, List<TreeNode<Operation<?>>>> returnedTypeToNode(final TreeNode<Operation<?>> root) {
36 Validate.notNull(root);
37
38 final Map<Class, List<TreeNode<Operation<?>>>> returnedTypeIndex = new HashMap<>();
39
40 final Deque<TreeNode<Operation<?>>> nodes = new ArrayDeque<>();
41 nodes.add(root);
42
43 while (nodes.isEmpty() == false) {
44 final TreeNode<Operation<?>> node = nodes.remove();
45
46 final Operation<?> operation = node.getData();
47 final Class returnedType = operation.returnedType();
48
49 returnedTypeIndex.computeIfAbsent(returnedType, k -> new ArrayList<>());
50 returnedTypeIndex.get(returnedType)
51 .add(node);
52
53 if (node.getChildren() != null && node.getChildren()
54 .isEmpty() == false) {
55 nodes.addAll(node.getChildren());
56 }
57 }
58
59 return returnedTypeIndex;
60 }
61
62 protected TreeNode<Operation<?>> copyAndReplace(final TreeNode<Operation<?>> root,
63 final TreeNode<Operation<?>> replaced, final TreeNode<Operation<?>> replacement) {
64 Validate.notNull(root);
65 Validate.notNull(replaced);
66 Validate.notNull(replacement);
67
68 if (root == replaced) {
69 return copyAndReplace(replacement, replaced, replacement);
70 }
71
72 final Operation<?> data = root.getData();
73 final List<TreeNode<Operation<?>>> children = root.getChildren();
74
75 final List<TreeNode<Operation<?>>> copiedChildren = children == null ? null
76 : children.stream()
77 .map(child -> copyAndReplace(child, replaced, replacement))
78 .collect(Collectors.toList());
79
80 final TreeNode<Operation<?>> copy = new TreeNode<>(data);
81 if (children.isEmpty() == false) {
82 copy.addChildren(copiedChildren);
83 }
84
85 return copy;
86 }
87
88 @SuppressWarnings("rawtypes")
89 private final TreeNode<Operation<?>> mix(final TreeNode<Operation<?>> rootA, final TreeNode<Operation<?>> rootB,
90 final Set<Class> acceptableClasses, final Map<Class, List<TreeNode<Operation<?>>>> returnedTypeToNodeA,
91 final Map<Class, List<TreeNode<Operation<?>>>> returnedTypeToNodeB) {
92 Validate.notNull(rootA);
93 Validate.notNull(rootB);
94 Validate.notNull(acceptableClasses);
95 Validate.isTrue(acceptableClasses.isEmpty() == false);
96 Validate.notNull(returnedTypeToNodeA);
97 Validate.notNull(returnedTypeToNodeB);
98
99 final int targetClassIndex = randomGenerator.nextInt(acceptableClasses.size());
100 final Class targetClass = acceptableClasses.stream()
101 .skip(targetClassIndex)
102 .findFirst()
103 .get();
104
105 final List<TreeNode<Operation<?>>> candidateReplacedNodes = returnedTypeToNodeA.get(targetClass);
106 final TreeNode<Operation<?>> replacedNode = candidateReplacedNodes
107 .get(randomGenerator.nextInt(candidateReplacedNodes.size()));
108
109 final List<TreeNode<Operation<?>>> candidateReplacementNodes = returnedTypeToNodeB.get(targetClass);
110 final TreeNode<Operation<?>> replacementNode = candidateReplacementNodes
111 .get(randomGenerator.nextInt(candidateReplacementNodes.size()));
112
113 return copyAndReplace(rootA, replacedNode, replacementNode);
114 }
115
116 @SuppressWarnings({ "rawtypes", "unchecked" })
117 @Override
118 public List<Chromosome> combine(final AbstractEAConfiguration<T> eaConfiguration, final Chromosome chromosome1,
119 final T firstParentFitness, final Chromosome chromosome2, final T secondParentFitness) {
120 Validate.notNull(chromosome1);
121 Validate.notNull(chromosome2);
122
123 if (chromosome1 instanceof TreeChromosome<?> == false) {
124 throw new IllegalArgumentException("This mutator does not support chromosome of type " + chromosome1.getClass()
125 .getSimpleName());
126 }
127
128 if (chromosome2 instanceof TreeChromosome<?> == false) {
129 throw new IllegalArgumentException("This mutator does not support chromosome of type " + chromosome2.getClass()
130 .getSimpleName());
131 }
132
133 if (chromosome1 == chromosome2) {
134 return Collections.emptyList();
135 }
136
137 final TreeChromosome<Operation<?>> treeChromosome1 = (TreeChromosome<Operation<?>>) chromosome1;
138 final TreeNode<Operation<?>> root1 = treeChromosome1.getRoot();
139 final Map<Class, List<TreeNode<Operation<?>>>> returnedTypeToNode1 = returnedTypeToNode(root1);
140
141 final TreeChromosome<Operation<?>> treeChromosome2 = (TreeChromosome<Operation<?>>) chromosome2;
142 final TreeNode<Operation<?>> root2 = treeChromosome2.getRoot();
143 final Map<Class, List<TreeNode<Operation<?>>>> returnedTypeToNode2 = returnedTypeToNode(root2);
144
145 final Set<Class> acceptableClasses = new HashSet<>();
146 acceptableClasses.addAll(returnedTypeToNode1.keySet());
147 acceptableClasses.retainAll(returnedTypeToNode2.keySet());
148
149 final List<Chromosome> children = new ArrayList<>();
150
151 if (acceptableClasses.isEmpty() == false) {
152
153 final TreeNode<Operation<?>> child1 = mix(root1,
154 root2,
155 acceptableClasses,
156 returnedTypeToNode1,
157 returnedTypeToNode2);
158 final TreeChromosome<Operation<?>> child1Chromosome = new TreeChromosome<Operation<?>>(child1);
159
160 final TreeNode<Operation<?>> child2 = mix(root2,
161 root1,
162 acceptableClasses,
163 returnedTypeToNode2,
164 returnedTypeToNode1);
165 final TreeChromosome<Operation<?>> child2Chromosome = new TreeChromosome<Operation<?>>(child2);
166
167 children.add(child1Chromosome);
168 children.add(child2Chromosome);
169 }
170
171 return children;
172 }
173 }