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