001 /*
002 * JENES
003 * A time and memory efficient Java library for genetic algorithms and more
004 * Copyright (C) 2011 Intelligentia srl
005 *
006 * This program is free software: you can redistribute it and/or modify
007 * it under the terms of the GNU General Public License as published by
008 * the Free Software Foundation, either version 3 of the License, or
009 * (at your option) any later version.
010 *
011 * This program is distributed in the hope that it will be useful,
012 * but WITHOUT ANY WARRANTY; without even the implied warranty of
013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
014 * GNU General Public License for more details.
015 *
016 * You should have received a copy of the GNU General Public License
017 * along with this program. If not, see <http://www.gnu.org/licenses/>.
018 */
019 package jenes.tutorials.problem3;
020
021 import jenes.Fitness;
022 import jenes.GeneticAlgorithm;
023 import jenes.utils.Random;
024 import jenes.algorithms.SimpleGA;
025 import jenes.chromosome.IntegerChromosome;
026 import jenes.chromosome.PermutationChromosome;
027 import jenes.population.Individual;
028 import jenes.population.Population;
029 import jenes.population.Population.Statistics.Group;
030 import jenes.stage.AbstractStage;
031 import jenes.stage.operator.common.TournamentSelector;
032 import jenes.tutorials.utils.Utils;
033
034
035 /**
036 * Tutorial showing how to implement problem specific operators.
037 * The problem faced in this example is the well known Tavel Salesman Problem (TSP)
038 *
039 * This class specifies the problem.
040 *
041 * @author Luigi Troiano
042 *
043 * @version 1.0
044 * @since 1.0
045 */
046 public class TravelSalesmanProblem {
047
048 public static final int POPULATION_SIZE = 1000;
049 private static int GENERATION_LIMIT = 2000;
050 public static final int MAX_DISTANCE = 10;
051
052 private TSPGA algorithm;
053 private int cities;
054 private double[][] map;
055
056 public static void main(String[] args) {
057
058 Utils.printHeader();
059 System.out.println();
060
061 System.out.println("TUTORIAL 3:");
062 System.out.println("The Travel Salesman Problem, a classics.");
063 System.out.println();
064
065 Random.getInstance().setStandardSeed();
066
067 System.out.println("Case 1: 10 cities in circle");
068 double[][] m1 = simpleMap(10);
069 TravelSalesmanProblem tsp1 = new TravelSalesmanProblem(m1);
070 tsp1.solve();
071
072 System.out.println("Case 2: 30 cities in circle");
073 double[][] m2 = simpleMap(30);
074 TravelSalesmanProblem tsp2 = new TravelSalesmanProblem(m2);
075 tsp2.solve();
076
077 System.out.println("Case 3: 30 cities at random");
078 double[][] m3 = randomMap(30);
079 TravelSalesmanProblem tsp3 = new TravelSalesmanProblem(m3);
080 tsp3.solve();
081
082 System.out.println("Case 4: An application of PermutationChromosome");
083 tsp2.solvePC();
084 }
085
086 public TravelSalesmanProblem(double[][] matrix) {
087
088 cities = matrix[0].length;
089 map = matrix;
090
091 IntegerChromosome chrom = new IntegerChromosome(cities,0,cities-1);
092 for( int i = 0; i < cities; ++i ) {
093 chrom.setValue(i, i < cities - 1 ? i+1 : 0);
094 }
095 Individual<IntegerChromosome> sample = new Individual<IntegerChromosome>(chrom);
096 Population<IntegerChromosome> pop = new Population<IntegerChromosome>(sample, POPULATION_SIZE);
097
098 algorithm = new TSPGA(matrix, pop, GENERATION_LIMIT);
099 algorithm.setRandomization(true);
100
101 AbstractStage<IntegerChromosome> selection = new TournamentSelector<IntegerChromosome>(1);
102 AbstractStage<IntegerChromosome> crossover = new TSPCityCenteredCrossover(0.8);
103 AbstractStage<IntegerChromosome> mutation = new TSPScrambleMutator(0.02);
104
105 algorithm.addStage(selection);
106 algorithm.addStage(crossover);
107 algorithm.addStage(mutation);
108
109 algorithm.setElitism(10);
110 }
111
112 public void solve() {
113 algorithm.evolve();
114
115 Population.Statistics stats = algorithm.getCurrentPopulation().getStatistics();
116 GeneticAlgorithm.Statistics algostats = algorithm.getStatistics();
117
118 Group legals = stats.getGroup(Population.LEGALS);
119
120 System.out.println(legals.get(0));
121 System.out.format("found in %d ms and %d generations.\n", algostats.getExecutionTime(), algostats.getGenerations() );
122 System.out.println();
123 }
124
125 public void solvePC() {
126
127 Individual<PermutationChromosome> sample = new Individual<PermutationChromosome>(new PermutationChromosome(cities));
128 Population<PermutationChromosome> pop = new Population<PermutationChromosome>(sample, POPULATION_SIZE);
129
130 Fitness<PermutationChromosome> fitness = new Fitness<PermutationChromosome>(false) {
131
132 @Override
133 public void evaluate(Individual<PermutationChromosome> individual) {
134 PermutationChromosome chrom = individual.getChromosome();
135 double count = 0;
136 int size = chrom.length();
137 for(int i=0;i<size-1;i++){
138 int val1 = chrom.getElementAt(i);
139 int val2 = chrom.getElementAt(i+1);
140 count += TravelSalesmanProblem.this.map[val1][val2];
141 }
142 count += TravelSalesmanProblem.this.map[size-1][0];
143 individual.setScore(count);
144 }
145
146 };
147
148 SimpleGA<PermutationChromosome> sga = new SimpleGA<PermutationChromosome>(fitness, pop, GENERATION_LIMIT);
149
150 sga.setElitism(10);
151 sga.setMutationProbability(0.02);
152 sga.evolve();
153
154 Population.Statistics stats = sga.getCurrentPopulation().getStatistics();
155 GeneticAlgorithm.Statistics algostats = sga.getStatistics();
156
157 Group legals = stats.getGroup(Population.LEGALS);
158
159 System.out.println(legals.get(0));
160 System.out.format("found in %d ms and %d generations.\n", algostats.getExecutionTime(), algostats.getGenerations() );
161 System.out.println();
162 }
163
164 public static double[][] simpleMap( int cities ) {
165 double[][] matrix = new double[cities][cities];
166
167 matrix[0][0] = 0;
168 for( int i = 1; i <= cities/2; ++i) {
169 matrix[0][i] = i;
170 matrix[0][cities-i] = i;
171 }
172
173 for( int i = 1; i < cities; ++i ) {
174 for( int j = 0; j < cities; ++j ) {
175 matrix[i][(i+j)%cities] = matrix[0][j];
176 }
177 }
178 return matrix;
179 }
180
181 public static double[][] randomMap( int cities ) {
182 double[][] matrix = new double[cities][cities];
183 for( int i = 0; i < cities; ++i ) {
184 for( int j = 0; j < cities; ++j ) {
185 matrix[i][j] = i!=j ? Random.getInstance().nextDouble(MAX_DISTANCE) : 0;
186 }
187 }
188 return matrix;
189 }
190
191 }
|
|
|
