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