1 package net.bmahe.genetics4j.samples;
2
3 import java.io.IOException;
4 import java.util.Arrays;
5 import java.util.List;
6 import java.util.Random;
7
8 import org.apache.logging.log4j.LogManager;
9 import org.apache.logging.log4j.Logger;
10
11 import net.bmahe.genetics4j.core.EASystem;
12 import net.bmahe.genetics4j.core.EASystemFactory;
13 import net.bmahe.genetics4j.core.Fitness;
14 import net.bmahe.genetics4j.core.Genotype;
15 import net.bmahe.genetics4j.core.chromosomes.Chromosome;
16 import net.bmahe.genetics4j.core.chromosomes.IntChromosome;
17 import net.bmahe.genetics4j.core.evolutionlisteners.EvolutionListeners;
18 import net.bmahe.genetics4j.core.spec.EAConfiguration;
19 import net.bmahe.genetics4j.core.spec.EAConfiguration.Builder;
20 import net.bmahe.genetics4j.core.spec.EAExecutionContext;
21 import net.bmahe.genetics4j.core.spec.EAExecutionContexts;
22 import net.bmahe.genetics4j.core.spec.EvolutionResult;
23 import net.bmahe.genetics4j.core.spec.Optimization;
24 import net.bmahe.genetics4j.core.spec.chromosome.IntChromosomeSpec;
25 import net.bmahe.genetics4j.core.spec.combination.EdgeRecombinationCrossover;
26 import net.bmahe.genetics4j.core.spec.combination.MultiCombinations;
27 import net.bmahe.genetics4j.core.spec.combination.OrderCrossover;
28 import net.bmahe.genetics4j.core.spec.mutation.MultiMutations;
29 import net.bmahe.genetics4j.core.spec.mutation.SwapMutation;
30 import net.bmahe.genetics4j.core.spec.selection.MultiSelections;
31 import net.bmahe.genetics4j.core.spec.selection.RouletteWheel;
32 import net.bmahe.genetics4j.core.spec.selection.Tournament;
33 import net.bmahe.genetics4j.core.termination.Terminations;
34
35 public class TSVExample {
36
37 public static final Logger logger = LogManager.getLogger(TSVExample.class);
38
39 public static double distance(final Position pos1, final Position pos2) {
40 final double xs = (pos2.x - pos1.x) * (pos2.x - pos1.x);
41 final double ys = (pos2.y - pos1.y) * (pos2.y - pos1.y);
42
43 return Math.sqrt(xs + ys);
44 }
45
46 public static void main(String[] args) {
47 logger.trace("Input data: {}", Arrays.deepToString(args));
48
49 final TSPLIBParser tsplibParser = new TSPLIBParser();
50 TSPLIBProblem tsplibProblem = null;
51 try {
52 tsplibProblem = tsplibParser.parse(args[0]);
53 } catch (IOException e) {
54 logger.error("Could not parse {}", args[0], e);
55 System.exit(-1);
56 }
57
58 final Random random = new Random();
59
60 final List<Position> cities = tsplibProblem.cities;
61 final int numCities = cities.size();
62
63
64 final Builder<Double> eaConfigurationBuilder = new EAConfiguration.Builder<Double>();
65 eaConfigurationBuilder.chromosomeSpecs(IntChromosomeSpec.of(numCities, 0, numCities))
66 .parentSelectionPolicy(
67 MultiSelections.of(RouletteWheel.build(), Tournament.of(5)))
68 .combinationPolicy(MultiCombinations.of(OrderCrossover.build(), EdgeRecombinationCrossover.build()))
69 .mutationPolicies(MultiMutations.of(SwapMutation.of(0.05, (int) (numCities*0.20), false)))
70 .optimization(Optimization.MINIMIZE)
71 .fitness(Fitness.forChromosome(0, (IntChromosome intChromosome) -> {
72
73 final Position firstCity = cities.get(intChromosome.getAllele(0));
74 final Position lastCity = cities.get(intChromosome.getAllele(intChromosome.getNumAlleles() - 1));
75 double cost = distance(lastCity, firstCity);
76
77
78 for (int i = 0; i < intChromosome.getNumAlleles() - 1; i++) {
79 final Position city1 = cities.get(intChromosome.getAllele(i));
80 final Position city2 = cities.get(intChromosome.getAllele(i + 1));
81
82 cost += distance(city1, city2);
83 }
84
85 return cost;
86 }))
87 .termination(Terminations.ofStableFitness(100))
88 .genotypeGenerator(() -> {
89 final int[] values = random.ints(0, numCities).distinct().limit(numCities).toArray();
90
91 final Chromosome chromosome = new IntChromosome(numCities, 0, numCities, values);
92 return new Genotype(chromosome);
93 });
94
95 final EAConfiguration<Double> eaConfiguration = eaConfigurationBuilder.build();
96
97 final EAExecutionContext<Double> eaExecutionContext = EAExecutionContexts.<Double>forScalarFitness()
98 .populationSize(500)
99 .addEvolutionListeners(EvolutionListeners.ofLogTopN(logger,
100 5,
101 genotype -> genotype.toString()
102 .substring(0, 200)))
103 .build();
104
105 final EASystem<Double> eaSystem = EASystemFactory.from(eaConfiguration, eaExecutionContext);
106
107 final EvolutionResult<Double> evolutionResult = eaSystem.evolve();
108 System.out.println("Best genotype: " + evolutionResult.bestGenotype());
109 }
110 }