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).add(node);
51
52 if (node.getChildren() != null && node.getChildren().isEmpty() == false) {
53 nodes.addAll(node.getChildren());
54 }
55 }
56
57 return returnedTypeIndex;
58 }
59
60 protected TreeNode<Operation<?>> copyAndReplace(final TreeNode<Operation<?>> root,
61 final TreeNode<Operation<?>> replaced, final TreeNode<Operation<?>> replacement) {
62 Validate.notNull(root);
63 Validate.notNull(replaced);
64 Validate.notNull(replacement);
65
66 if (root == replaced) {
67 return copyAndReplace(replacement, replaced, replacement);
68 }
69
70 final Operation<?> data = root.getData();
71 final List<TreeNode<Operation<?>>> children = root.getChildren();
72
73 final List<TreeNode<Operation<?>>> copiedChildren = children == null ? null
74 : children.stream().map(child -> copyAndReplace(child, replaced, replacement)).collect(Collectors.toList());
75
76 final TreeNode<Operation<?>> copy = new TreeNode<>(data);
77 if (children.isEmpty() == false) {
78 copy.addChildren(copiedChildren);
79 }
80
81 return copy;
82 }
83
84 @SuppressWarnings("rawtypes")
85 private final TreeNode<Operation<?>> mix(final TreeNode<Operation<?>> rootA, final TreeNode<Operation<?>> rootB,
86 final Set<Class> acceptableClasses, final Map<Class, List<TreeNode<Operation<?>>>> returnedTypeToNodeA,
87 final Map<Class, List<TreeNode<Operation<?>>>> returnedTypeToNodeB) {
88 Validate.notNull(rootA);
89 Validate.notNull(rootB);
90 Validate.notNull(acceptableClasses);
91 Validate.isTrue(acceptableClasses.isEmpty() == false);
92 Validate.notNull(returnedTypeToNodeA);
93 Validate.notNull(returnedTypeToNodeB);
94
95 final int targetClassIndex = randomGenerator.nextInt(acceptableClasses.size());
96 final Class targetClass = acceptableClasses.stream().skip(targetClassIndex).findFirst().get();
97
98 final List<TreeNode<Operation<?>>> candidateReplacedNodes = returnedTypeToNodeA.get(targetClass);
99 final TreeNode<Operation<?>> replacedNode = candidateReplacedNodes
100 .get(randomGenerator.nextInt(candidateReplacedNodes.size()));
101
102 final List<TreeNode<Operation<?>>> candidateReplacementNodes = returnedTypeToNodeB.get(targetClass);
103 final TreeNode<Operation<?>> replacementNode = candidateReplacementNodes
104 .get(randomGenerator.nextInt(candidateReplacementNodes.size()));
105
106 return copyAndReplace(rootA, replacedNode, replacementNode);
107 }
108
109 @SuppressWarnings({ "rawtypes", "unchecked" })
110 @Override
111 public List<Chromosome> combine(final AbstractEAConfiguration<T> eaConfiguration, final Chromosome chromosome1,
112 final T firstParentFitness, final Chromosome chromosome2, final T secondParentFitness) {
113 Validate.notNull(chromosome1);
114 Validate.notNull(chromosome2);
115
116 if (chromosome1 instanceof TreeChromosome<?> == false) {
117 throw new IllegalArgumentException(
118 "This mutator does not support chromosome of type " + chromosome1.getClass().getSimpleName());
119 }
120
121 if (chromosome2 instanceof TreeChromosome<?> == false) {
122 throw new IllegalArgumentException(
123 "This mutator does not support chromosome of type " + chromosome2.getClass().getSimpleName());
124 }
125
126 if (chromosome1 == chromosome2) {
127 return Collections.emptyList();
128 }
129
130 final TreeChromosome<Operation<?>> treeChromosome1 = (TreeChromosome<Operation<?>>) chromosome1;
131 final TreeNode<Operation<?>> root1 = treeChromosome1.getRoot();
132 final Map<Class, List<TreeNode<Operation<?>>>> returnedTypeToNode1 = returnedTypeToNode(root1);
133
134 final TreeChromosome<Operation<?>> treeChromosome2 = (TreeChromosome<Operation<?>>) chromosome2;
135 final TreeNode<Operation<?>> root2 = treeChromosome2.getRoot();
136 final Map<Class, List<TreeNode<Operation<?>>>> returnedTypeToNode2 = returnedTypeToNode(root2);
137
138 final Set<Class> acceptableClasses = new HashSet<>();
139 acceptableClasses.addAll(returnedTypeToNode1.keySet());
140 acceptableClasses.retainAll(returnedTypeToNode2.keySet());
141
142 final List<Chromosome> children = new ArrayList<>();
143
144 if (acceptableClasses.isEmpty() == false) {
145
146 final TreeNode<Operation<?>> child1 = mix(
147 root1,
148 root2,
149 acceptableClasses,
150 returnedTypeToNode1,
151 returnedTypeToNode2);
152 final TreeChromosome<Operation<?>> child1Chromosome = new TreeChromosome<Operation<?>>(child1);
153
154 final TreeNode<Operation<?>> child2 = mix(
155 root2,
156 root1,
157 acceptableClasses,
158 returnedTypeToNode2,
159 returnedTypeToNode1);
160 final TreeChromosome<Operation<?>> child2Chromosome = new TreeChromosome<Operation<?>>(child2);
161
162 children.add(child1Chromosome);
163 children.add(child2Chromosome);
164 }
165
166 return children;
167 }
168 }