1 package net.bmahe.genetics4j.core.combination.erx;
2
3 import java.util.HashMap;
4 import java.util.HashSet;
5 import java.util.List;
6 import java.util.Map;
7 import java.util.Map.Entry;
8 import java.util.Objects;
9 import java.util.Optional;
10 import java.util.Set;
11 import java.util.random.RandomGenerator;
12
13 import org.apache.commons.lang3.Validate;
14
15 import net.bmahe.genetics4j.core.chromosomes.Chromosome;
16 import net.bmahe.genetics4j.core.chromosomes.IntChromosome;
17 import net.bmahe.genetics4j.core.combination.ChromosomeCombinator;
18 import net.bmahe.genetics4j.core.spec.AbstractEAConfiguration;
19
20 public class IntEdgeRecombinationCrossover<T extends Comparable<T>> implements ChromosomeCombinator<T> {
21
22 private final RandomGenerator randomGenerator;
23
24 public IntEdgeRecombinationCrossover(final RandomGenerator _randomGenerator) {
25 Objects.requireNonNull(_randomGenerator);
26
27 this.randomGenerator = _randomGenerator;
28 }
29
30 protected void addEdges(final Map<Integer, Set<Integer>> edgeMap, final int[] chromosomeValues) {
31 Objects.requireNonNull(edgeMap);
32 Objects.requireNonNull(chromosomeValues);
33
34 for (int i = 0; i < chromosomeValues.length; i++) {
35 final int j = chromosomeValues[i];
36
37
38 if (i > 0) {
39 final int cityBefore = chromosomeValues[i - 1];
40 final Set<Integer> cities = edgeMap.computeIfAbsent(cityBefore, k -> new HashSet<Integer>());
41 cities.add(j);
42 }
43
44
45 if (i < chromosomeValues.length - 1) {
46 final int cityAfter = chromosomeValues[i + 1];
47 final Set<Integer> cities = edgeMap.computeIfAbsent(cityAfter, k -> new HashSet<Integer>());
48 cities.add(j);
49 }
50 }
51
52 final Set<Integer> lastCities = edgeMap
53 .computeIfAbsent(chromosomeValues[chromosomeValues.length - 1], k -> new HashSet<Integer>());
54 lastCities.add(chromosomeValues[0]);
55
56 final Set<Integer> firstCities = edgeMap.computeIfAbsent(chromosomeValues[0], k -> new HashSet<Integer>());
57 firstCities.add(chromosomeValues[chromosomeValues.length - 1]);
58 }
59
60 protected Optional<Integer> cityWithSmallestEdgeList(final Map<Integer, Set<Integer>> edgeMap) {
61 Objects.requireNonNull(edgeMap);
62
63 int citySmallestEdgeList = -1;
64 int smallestEdgeListSize = Integer.MAX_VALUE;
65
66 for (final Entry<Integer, Set<Integer>> entry : edgeMap.entrySet()) {
67 final Integer city = entry.getKey();
68 final Set<Integer> edgeList = entry.getValue();
69
70 if (edgeList.size() < smallestEdgeListSize) {
71 citySmallestEdgeList = city;
72 smallestEdgeListSize = edgeList.size();
73 }
74 }
75
76 return citySmallestEdgeList > -1 ? Optional.of(citySmallestEdgeList) : Optional.empty();
77 }
78
79 protected Optional<Integer> cityWithSmallestEdgeList(final Map<Integer, Set<Integer>> edgeMap,
80 final Set<Integer> candidates) {
81 Objects.requireNonNull(edgeMap);
82
83 int citySmallestEdgeList = -1;
84 int smallestEdgeListSize = Integer.MAX_VALUE;
85
86 for (final Integer candidate : candidates) {
87 if (edgeMap.containsKey(candidate)) {
88 final Set<Integer> edgeList = edgeMap.get(candidate);
89
90 if (edgeList.size() < smallestEdgeListSize) {
91 citySmallestEdgeList = candidate;
92 smallestEdgeListSize = edgeList.size();
93 }
94 }
95 }
96
97 return citySmallestEdgeList > -1 ? Optional.of(citySmallestEdgeList) : Optional.empty();
98 }
99
100 @Override
101 public List<Chromosome> combine(final AbstractEAConfiguration<T> eaConfiguration, final Chromosome chromosome1,
102 final T firstParentFitness, final Chromosome chromosome2, final T secondParentFitness) {
103 Objects.requireNonNull(chromosome1);
104 Objects.requireNonNull(chromosome2);
105 Validate.isInstanceOf(IntChromosome.class, chromosome1);
106 Validate.isInstanceOf(IntChromosome.class, chromosome2);
107
108 final IntChromosome intChromosome1 = (IntChromosome) chromosome1;
109 Validate.isTrue(intChromosome1.getNumAlleles() > 2);
110 final int[] chromosome1Values = intChromosome1.getValues();
111
112 final IntChromosome intChromosome2 = (IntChromosome) chromosome2;
113 final int[] chromosome2Values = intChromosome2.getValues();
114
115 Validate.isTrue(intChromosome2.getNumAlleles() > 2);
116 Validate.isTrue(intChromosome1.getNumAlleles() == intChromosome2.getNumAlleles());
117
118 final Map<Integer, Set<Integer>> edgeMap = new HashMap<>();
119 addEdges(edgeMap, chromosome1Values);
120 addEdges(edgeMap, chromosome2Values);
121
122 int[] chromosome = new int[chromosome1.getNumAlleles()];
123 int currentCity = randomGenerator.nextInt(chromosome1Values.length);
124 int currentIndex = 0;
125 final Set<Integer> citiesVisited = new HashSet<>();
126 while (edgeMap.size() > 0) {
127
128 chromosome[currentIndex] = currentCity;
129 final Set<Integer> nextCities = edgeMap.get(currentCity);
130 edgeMap.remove(currentCity);
131 citiesVisited.add(currentCity);
132 currentIndex++;
133
134 final Optional<Integer> cityWithSmallestEdgeList = cityWithSmallestEdgeList(edgeMap, nextCities);
135
136 if (cityWithSmallestEdgeList.isPresent()) {
137 currentCity = cityWithSmallestEdgeList.get();
138 } else {
139 final Set<Integer> citiesSet = edgeMap.keySet();
140 if (citiesSet.size() == 1) {
141 currentCity = citiesSet.iterator().next();
142 } else if (citiesSet.isEmpty() == false) {
143 currentCity = citiesSet.stream().skip(randomGenerator.nextInt(citiesSet.size() - 1)).findFirst().get();
144 }
145 }
146 }
147
148 if (currentIndex < chromosome1.getNumAlleles()) {
149 final Set<Integer> remainingValues = new HashSet<>();
150 for (int i : chromosome1Values) {
151 remainingValues.add(i);
152 }
153 for (int i : chromosome2Values) {
154 remainingValues.add(i);
155 }
156 remainingValues.removeAll(citiesVisited);
157 for (Integer remainingCity : remainingValues) {
158 chromosome[currentIndex++] = remainingCity;
159
160 }
161 }
162
163 return List.of(
164 new IntChromosome(chromosome1.getNumAlleles(),
165 intChromosome1.getMinValue(),
166 intChromosome1.getMaxValue(),
167 chromosome));
168 }
169 }