1 package net.bmahe.genetics4j.samples.neat;
2
3 import java.io.BufferedWriter;
4 import java.io.File;
5 import java.io.FileWriter;
6 import java.io.IOException;
7 import java.nio.charset.StandardCharsets;
8 import java.util.Comparator;
9 import java.util.List;
10 import java.util.Map;
11 import java.util.Optional;
12 import java.util.Set;
13 import java.util.stream.IntStream;
14
15 import org.apache.commons.cli.CommandLine;
16 import org.apache.commons.cli.CommandLineParser;
17 import org.apache.commons.cli.DefaultParser;
18 import org.apache.commons.cli.Options;
19 import org.apache.commons.cli.ParseException;
20 import org.apache.commons.io.FileUtils;
21 import org.apache.logging.log4j.LogManager;
22 import org.apache.logging.log4j.Logger;
23
24 import net.bmahe.genetics4j.core.EASystem;
25 import net.bmahe.genetics4j.core.EASystemFactory;
26 import net.bmahe.genetics4j.core.Fitness;
27 import net.bmahe.genetics4j.core.evolutionlisteners.EvolutionListener;
28 import net.bmahe.genetics4j.core.evolutionlisteners.EvolutionListeners;
29 import net.bmahe.genetics4j.core.spec.EAConfiguration;
30 import net.bmahe.genetics4j.core.spec.EAConfiguration.Builder;
31 import net.bmahe.genetics4j.core.spec.EvolutionResult;
32 import net.bmahe.genetics4j.core.spec.Optimization;
33 import net.bmahe.genetics4j.core.spec.mutation.CreepMutation;
34 import net.bmahe.genetics4j.core.spec.mutation.MultiMutations;
35 import net.bmahe.genetics4j.core.spec.mutation.MutationPolicy;
36 import net.bmahe.genetics4j.core.spec.mutation.RandomMutation;
37 import net.bmahe.genetics4j.core.spec.selection.SelectionPolicy;
38 import net.bmahe.genetics4j.core.spec.selection.Tournament;
39 import net.bmahe.genetics4j.core.spec.statistics.distributions.NormalDistribution;
40 import net.bmahe.genetics4j.core.termination.Terminations;
41 import net.bmahe.genetics4j.extras.evolutionlisteners.CSVEvolutionListener;
42 import net.bmahe.genetics4j.extras.evolutionlisteners.ColumnExtractor;
43 import net.bmahe.genetics4j.neat.Activations;
44 import net.bmahe.genetics4j.neat.Connection;
45 import net.bmahe.genetics4j.neat.FeedForwardNetwork;
46 import net.bmahe.genetics4j.neat.NeatEAExecutionContexts;
47 import net.bmahe.genetics4j.neat.NeatUtils;
48 import net.bmahe.genetics4j.neat.chromosomes.NeatChromosome;
49 import net.bmahe.genetics4j.neat.spec.NeatChromosomeSpec;
50 import net.bmahe.genetics4j.neat.spec.combination.NeatCombination;
51 import net.bmahe.genetics4j.neat.spec.mutation.AddConnection;
52 import net.bmahe.genetics4j.neat.spec.mutation.AddNode;
53 import net.bmahe.genetics4j.neat.spec.mutation.DeleteConnection;
54 import net.bmahe.genetics4j.neat.spec.mutation.DeleteNode;
55 import net.bmahe.genetics4j.neat.spec.mutation.NeatConnectionWeight;
56 import net.bmahe.genetics4j.neat.spec.mutation.SwitchStateMutation;
57 import net.bmahe.genetics4j.neat.spec.selection.NeatSelection;
58 import net.bmahe.genetics4j.neat.util.GraphvizFormatter;
59 import net.bmahe.genetics4j.samples.CLIUtils;
60
61 public class Main {
62 public static final Logger logger = LogManager.getLogger(Main.class);
63
64 public static final String PARAM_FILENAME_BEST_NETWORK = "s";
65 public static final String LONG_PARAM_FILENAME_BEST_NETWORK = "save";
66
67 public static final String PARAM_DEST_CSV = "d";
68 public static final String LONG_PARAM_DEST_CSV = "csv-dest";
69
70 public static final String PARAM_POPULATION_SIZE = "p";
71 public static final String LONG_PARAM_POPULATION_SIZE = "population-size";
72
73 public static final String DEFAULT_DEST_CSV = "neat-xor.csv";
74
75 public static final int DEFAULT_POPULATION_SIZE = 500;
76
77 public static Fitness<Float> fitnessNEAT(final boolean print) {
78 return genotype -> {
79 final NeatChromosome neatChromosome = genotype.getChromosome(0, NeatChromosome.class);
80
81 if (print) {
82 logger.info("Evaluating chromosome: {}", neatChromosome);
83 }
84
85 final Set<Integer> inputNodeIndices = Set.copyOf(neatChromosome.getInputNodeIds());
86 final Set<Integer> outputNodeIndices = Set.copyOf(neatChromosome.getOutputNodeIds());
87 final List<Connection> connections = neatChromosome.getConnections();
88
89 if (connections.isEmpty()) {
90 return 0f;
91 }
92
93 float errorDistance = 0;
94
95
96 final var feedForwardNetwork = new FeedForwardNetwork(inputNodeIndices,
97 outputNodeIndices,
98 connections,
99 Activations.tanhFloat);
100
101
102
103 final int outputNodeIndex = outputNodeIndices.iterator().next();
104 for (final boolean a : Set.of(false, true)) {
105 final float aValue = a ? 1 : 0;
106 for (final boolean b : Set.of(false, true)) {
107 final float bValue = b ? 1 : 0;
108 final float expectedOutput = a ^ b ? 1 : 0;
109
110
111 final var inputValues = Map.of(0, aValue, 1, bValue, 2, 1.0f);
112 final Map<Integer, Float> computedOutputValues = feedForwardNetwork.compute(inputValues);
113
114 final float computedOutput = computedOutputValues.get(outputNodeIndex);
115
116 if (print) {
117 logger.info(
118 "a: {}, b: {} ===> {} ({}) / {}",
119 aValue,
120 bValue,
121 computedOutput,
122 outputNodeIndex,
123 expectedOutput);
124 }
125
126 errorDistance += Math.sqrt((expectedOutput - computedOutput) * (expectedOutput - computedOutput));
127 }
128 }
129
130 return 4 - errorDistance;
131
132 };
133 }
134
135 public static void executeNEATXor(final Optional<String> bestNetworkFilename, final int populationSize,
136 final String csvFilename) throws IOException {
137
138
139 final SelectionPolicy neatSelection = NeatSelection.builder()
140 .minSpeciesSize(1)
141 .perSpeciesKeepRatio(.20f)
142 .speciesSelection(Tournament.of(3))
143 .speciesPredicate(
144 (i1, i2) -> NeatUtils.compatibilityDistance(i1.genotype(), i2.genotype(), 0, 2, 2, 1f) < 4.5)
145 .build();
146
147
148
149 final List<MutationPolicy> neatMutations = List.of(
150 MultiMutations.of(
151 CreepMutation.of(0.85f, NormalDistribution.of(0.0, 0.333)),
152 RandomMutation.of(0.85f),
153 NeatConnectionWeight.builder().populationMutationProbability(0.85f).build()),
154 MultiMutations.of(
155 SwitchStateMutation.of(0.01f),
156 AddNode.of(0.20f),
157 DeleteNode.of(0.20f),
158 AddConnection.of(0.5f),
159 DeleteConnection.of(0.5f)));
160
161
162
163 final Builder<Float> eaConfigurationBuilder = new EAConfiguration.Builder<>();
164 eaConfigurationBuilder.chromosomeSpecs(NeatChromosomeSpec.of(3, 1, -5, 5))
165 .parentSelectionPolicy(neatSelection)
166 .combinationPolicy(NeatCombination.build())
167 .mutationPolicies(neatMutations)
168 .fitness(fitnessNEAT(false))
169 .optimization(Optimization.MAXIMIZE)
170 .termination(
171 Terminations.<Float>or(Terminations.ofStableFitness(300), Terminations.ofFitnessAtLeast(3.95f)));
172
173
174 final EAConfiguration<Float> eaConfiguration = eaConfigurationBuilder.build();
175
176 final List<EvolutionListener<Float>> evolutionListeners = List.of(
177 EvolutionListeners.<Float>ofLogTopN(logger, 3, Comparator.naturalOrder()),
178 CSVEvolutionListener.<Float, Void>of(
179 csvFilename,
180 List.of(
181 ColumnExtractor.of("generation", evolutionStep -> evolutionStep.generation()),
182 ColumnExtractor.of("individual_index", evolutionStep -> evolutionStep.individualIndex()),
183 ColumnExtractor.of("fitness", evolutionStep -> evolutionStep.fitness()),
184 ColumnExtractor.of(
185 "individual_num_connections",
186 evolutionStep -> evolutionStep.individual()
187 .getChromosome(0, NeatChromosome.class)
188 .getConnections()
189 .size()),
190 ColumnExtractor.of(
191 "individual_num_connections_enabled",
192 evolutionStep -> evolutionStep.individual()
193 .getChromosome(0, NeatChromosome.class)
194 .getConnections()
195 .stream()
196 .filter(Connection::isEnabled)
197 .count()),
198 ColumnExtractor.of(
199 "individual_num_connections_disabled",
200 evolutionStep -> evolutionStep.individual()
201 .getChromosome(0, NeatChromosome.class)
202 .getConnections()
203 .stream()
204 .filter(connection -> connection.isEnabled() == false)
205 .count()),
206 ColumnExtractor.of(
207 "individual_num_nodes",
208 evolutionStep -> evolutionStep.individual()
209 .getChromosome(0, NeatChromosome.class)
210 .getConnections()
211 .stream()
212 .flatMapToInt(
213 connection -> IntStream
214 .of(connection.fromNodeIndex(), connection.toNodeIndex()))
215 .distinct()
216 .count()))));
217
218
219 final var eaExecutionContextBuilder = NeatEAExecutionContexts.<Float>standard();
220 eaExecutionContextBuilder.populationSize(populationSize).evolutionListeners(evolutionListeners);
221
222 final var eaExecutionContext = eaExecutionContextBuilder.build();
223
224
225
226 final EASystem<Float> eaSystem = EASystemFactory.from(eaConfiguration, eaExecutionContext);
227 final EvolutionResult<Float> evolutionResult = eaSystem.evolve();
228 logger.info("Best genotype: {}", evolutionResult.bestGenotype());
229 logger.info("\twith fitness: {}", evolutionResult.bestFitness());
230 logger.info("\tat generation: {}", evolutionResult.generation());
231
232
233 final var bestOfTheBest = evolutionResult.bestGenotype();
234 logger.info("Best of the best: {}", bestOfTheBest);
235
236
237
238
239 final var bestFitnessRaw = fitnessNEAT(true).compute(bestOfTheBest);
240 logger.info("\tand raw fitness: {} / {}", bestFitnessRaw, evolutionResult.bestFitness());
241
242 final var bestOfTheBestChromosome = bestOfTheBest.getChromosome(0, NeatChromosome.class);
243 final List<List<Integer>> layersNodes = NeatUtils.partitionLayersNodes(
244 Set.copyOf(bestOfTheBestChromosome.getInputNodeIds()),
245 Set.copyOf(bestOfTheBestChromosome.getOutputNodeIds()),
246 bestOfTheBestChromosome.getConnections());
247
248 logger.info("\tLayers: {}", layersNodes);
249
250 final GraphvizFormatter graphvizFormatter = new GraphvizFormatter();
251 final String bestNetworkStr = graphvizFormatter
252 .format(bestOfTheBestChromosome, Map.of(0, "A", 1, "B", 2, "bias=1", 3, "A xor B"));
253 logger.info("{}", bestNetworkStr);
254
255 if (bestNetworkFilename.isPresent()) {
256 FileUtils.forceMkdirParent(new File(bestNetworkFilename.get()));
257
258 try (var fileWriter = new FileWriter(bestNetworkFilename.get(), StandardCharsets.UTF_8);
259 var bufferedWriter = new BufferedWriter(fileWriter)) {
260 bufferedWriter.write(bestNetworkStr);
261 }
262 }
263
264 if (evolutionResult.bestFitness() <= 3.80f) {
265 throw new IllegalStateException("Evolution unsuccesful. Fitness too low");
266 }
267 }
268
269 public static void main(final String[] args) throws IOException {
270 logger.info("Starting");
271
272
273
274
275 logger.info("Parsing command line arguments");
276 final CommandLineParser parser = new DefaultParser();
277
278 final Options options = new Options();
279 options.addOption("h", "help", false, "print help");
280 options.addOption(PARAM_FILENAME_BEST_NETWORK, LONG_PARAM_FILENAME_BEST_NETWORK, true, "save the best network");
281 options.addOption(PARAM_DEST_CSV, LONG_PARAM_DEST_CSV, true, "destination csv file");
282 options.addOption(PARAM_POPULATION_SIZE, LONG_PARAM_POPULATION_SIZE, true, "Population size");
283
284 final Optional<String> bestNetworkFilename;
285 String csvFilename = DEFAULT_DEST_CSV;
286 int populationSize = DEFAULT_POPULATION_SIZE;
287 try {
288 final CommandLine line = parser.parse(options, args);
289 if (line.hasOption("h")) {
290 CLIUtils.cliHelpAndExit(logger, Main.class, options, null);
291 }
292
293 if (line.hasOption("s")) {
294 bestNetworkFilename = Optional.of(line.getOptionValue("s"));
295 } else {
296 bestNetworkFilename = Optional.empty();
297 }
298
299 if (line.hasOption(PARAM_DEST_CSV)) {
300 csvFilename = line.getOptionValue(PARAM_DEST_CSV);
301 }
302
303 if (line.hasOption(PARAM_POPULATION_SIZE)) {
304 populationSize = Integer.parseInt(line.getOptionValue(PARAM_POPULATION_SIZE));
305 }
306
307 } catch (ParseException exp) {
308 CLIUtils.cliHelpAndExit(logger, Main.class, options, "Unexpected exception:" + exp.getMessage());
309
310
311 throw new RuntimeException();
312
313 }
314
315 logger.info("Population size: {}", populationSize);
316
317 logger.info("CSV output located at {}", csvFilename);
318 FileUtils.forceMkdirParent(new File(csvFilename));
319
320 executeNEATXor(bestNetworkFilename, populationSize, csvFilename);
321
322 logger.info("The End.");
323 }
324 }