1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.math.genetics;
18
19 import static org.junit.Assert.assertTrue;
20
21 import java.util.ArrayList;
22 import java.util.List;
23
24 import org.junit.Test;
25
26
27
28
29
30
31
32 public class GeneticAlgorithmTestPermutations {
33
34
35 private static final int DIMENSION = 20;
36 private static final int POPULATION_SIZE = 80;
37 private static final int NUM_GENERATIONS = 200;
38 private static final double ELITISM_RATE = 0.2;
39 private static final double CROSSOVER_RATE = 1;
40 private static final double MUTATION_RATE = 0.08;
41 private static final int TOURNAMENT_ARITY = 2;
42
43
44 private static List<Integer> sequence = new ArrayList<Integer>();
45 static {
46 for (int i=0; i<DIMENSION; i++) {
47 sequence.add(i);
48 }
49 }
50
51 @Test
52 public void test() {
53
54
55
56 GeneticAlgorithm ga = new GeneticAlgorithm(
57 new OnePointCrossover<Integer>(),
58 CROSSOVER_RATE,
59 new RandomKeyMutation(),
60 MUTATION_RATE,
61 new TournamentSelection(TOURNAMENT_ARITY)
62 );
63
64
65 Population initial = randomPopulation();
66
67 StoppingCondition stopCond = new FixedGenerationCount(NUM_GENERATIONS);
68
69
70 Chromosome bestInitial = initial.getFittestChromosome();
71
72
73 Population finalPopulation = ga.evolve(initial, stopCond);
74
75
76 Chromosome bestFinal = finalPopulation.getFittestChromosome();
77
78
79
80
81 assertTrue(bestFinal.compareTo(bestInitial) > 0);
82
83
84
85 }
86
87
88
89
90
91 private static ElitisticListPopulation randomPopulation() {
92 List<Chromosome> popList = new ArrayList<Chromosome>();
93 for (int i=0; i<POPULATION_SIZE; i++) {
94 Chromosome randChrom = new MinPermutations(RandomKey.randomPermutation(DIMENSION));
95 popList.add(randChrom);
96 }
97 return new ElitisticListPopulation(popList, popList.size(), ELITISM_RATE);
98 }
99
100
101
102
103
104
105 private static class MinPermutations extends RandomKey<Integer> {
106
107 public MinPermutations(List<Double> representation) {
108 super(representation);
109 }
110
111 public double fitness() {
112 int res = 0;
113 List<Integer> decoded = decode(sequence);
114 for (int i=0; i<decoded.size(); i++) {
115 int value = (Integer) decoded.get(i);
116 if (value != i) {
117
118 res += Math.abs(value - i);
119 }
120 }
121
122
123 return -res;
124 }
125
126 @Override
127 public AbstractListChromosome<Double> newFixedLengthChromosome(List<Double> representation) {
128 return new MinPermutations(representation);
129 }
130 }
131 }