1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.math4.legacy.genetics;
18
19
20 import java.util.ArrayList;
21 import java.util.List;
22
23 import org.apache.commons.math4.core.jdkmath.JdkMath;
24 import org.junit.Assert;
25 import org.junit.Test;
26
27 /**
28 * This is also an example of usage.
29 *
30 * This algorithm does "stochastic sorting" of a sequence 0,...,N.
31 *
32 */
33 public class GeneticAlgorithmTestPermutations {
34
35 // parameters for the GA
36 private static final int DIMENSION = 20;
37 private static final int POPULATION_SIZE = 80;
38 private static final int NUM_GENERATIONS = 200;
39 private static final double ELITISM_RATE = 0.2;
40 private static final double CROSSOVER_RATE = 1;
41 private static final double MUTATION_RATE = 0.08;
42 private static final int TOURNAMENT_ARITY = 2;
43
44 // numbers from 0 to N-1
45 private static final List<Integer> sequence = new ArrayList<>();
46 static {
47 for (int i=0; i<DIMENSION; i++) {
48 sequence.add(i);
49 }
50 }
51
52 @Test
53 public void test() {
54 // to test a stochastic algorithm is hard, so this will rather be an usage example
55
56 // initialize a new genetic algorithm
57 GeneticAlgorithm ga = new GeneticAlgorithm(
58 new OnePointCrossover<>(),
59 CROSSOVER_RATE,
60 new RandomKeyMutation(),
61 MUTATION_RATE,
62 new TournamentSelection(TOURNAMENT_ARITY)
63 );
64
65 // initial population
66 Population initial = randomPopulation();
67 // stopping conditions
68 StoppingCondition stopCond = new FixedGenerationCount(NUM_GENERATIONS);
69
70 // best initial chromosome
71 Chromosome bestInitial = initial.getFittestChromosome();
72
73 // run the algorithm
74 Population finalPopulation = ga.evolve(initial, stopCond);
75
76 // best chromosome from the final population
77 Chromosome bestFinal = finalPopulation.getFittestChromosome();
78
79 // the only thing we can test is whether the final solution is not worse than the initial one
80 // however, for some implementations of GA, this need not be true :)
81
82 Assert.assertTrue(bestFinal.compareTo(bestInitial) > 0);
83
84 //System.out.println(bestInitial);
85 //System.out.println(bestFinal);
86 }
87
88
89 /**
90 * Initializes a random population
91 */
92 private static ElitisticListPopulation randomPopulation() {
93 List<Chromosome> popList = new ArrayList<>();
94 for (int i=0; i<POPULATION_SIZE; i++) {
95 Chromosome randChrom = new MinPermutations(RandomKey.randomPermutation(DIMENSION));
96 popList.add(randChrom);
97 }
98 return new ElitisticListPopulation(popList, popList.size(), ELITISM_RATE);
99 }
100
101 /**
102 * Chromosomes representing a permutation of (0,1,2,...,DIMENSION-1).
103 *
104 * The goal is to sort the sequence.
105 */
106 private static final class MinPermutations extends RandomKey<Integer> {
107
108 MinPermutations(List<Double> representation) {
109 super(representation);
110 }
111
112 @Override
113 public double fitness() {
114 int res = 0;
115 List<Integer> decoded = decode(sequence);
116 for (int i=0; i<decoded.size(); i++) {
117 int value = decoded.get(i);
118 if (value != i) {
119 // bad position found
120 res += JdkMath.abs(value - i);
121 }
122 }
123 // the most fitted chromosome is the one with minimal error
124 // therefore we must return negative value
125 return -res;
126 }
127
128 @Override
129 public AbstractListChromosome<Double> newFixedLengthChromosome(List<Double> chromosomeRepresentation) {
130 return new MinPermutations(chromosomeRepresentation);
131 }
132 }
133 }