001 /*
002 * JENES
003 * A time asnd 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.old.problem3;
020
021 import jenes.GeneticAlgorithm;
022 import jenes.utils.Random;
023 import jenes.algorithms.SimpleGA;
024 import jenes.chromosome.IntegerChromosome;
025 import jenes.chromosome.PermutationChromosome;
026 import jenes.population.Individual;
027 import jenes.population.Population;
028 import jenes.stage.AbstractStage;
029 import jenes.stage.operator.common.TournamentSelector;
030 import jenes.tutorials.utils.Utils;
031
032
033 /**
034 * Tutorial showing how to implement problem specific operators.
035 * The problem faced in this example is the well known Tavel Salesman Problem (TSP)
036 *
037 * This class specifies the problem.
038 *
039 * @author Luigi Troiano
040 * @author Pierpaolo Lombardi
041 *
042 * @version 1.0
043 * @since 1.0
044 */
045 public class TravelSalesmanProblem {
046
047 public static final int POPULATION_SIZE = 1000;
048 private static int GENERATION_LIMIT = 2000;
049 public static final int MAX_DISTANCE = 10;
050
051 private TSPGA algorithm;
052 private int cities;
053 private double[][] map;
054
055 public static void main(String[] args) {
056
057 Utils.printHeader();
058 System.out.println();
059
060 System.out.println("TUTORIAL 3:");
061 System.out.println("The Travel Salesman Problem, a classics.");
062 System.out.println();
063
064 Random.getInstance().setStandardSeed();
065
066 System.out.println("Case 1: 10 cities in circle");
067 double[][] m1 = simpleMap(10);
068 TravelSalesmanProblem tsp1 = new TravelSalesmanProblem(m1);
069 tsp1.solve();
070
071 System.out.println("Case 2: 30 cities in circle");
072 double[][] m2 = simpleMap(30);
073 TravelSalesmanProblem tsp2 = new TravelSalesmanProblem(m2);
074 tsp2.solve();
075
076 System.out.println("Case 3: 30 cities at random");
077 double[][] m3 = randomMap(30);
078 TravelSalesmanProblem tsp3 = new TravelSalesmanProblem(m3);
079 tsp3.solve();
080
081 System.out.println("Case 4: An application of PermutationChromosome");
082 tsp2.solvePC();
083 }
084
085 public TravelSalesmanProblem(double[][] matrix) {
086
087 cities = matrix[0].length;
088 map = matrix;
089
090 IntegerChromosome chrom = new IntegerChromosome(cities,0,cities-1);
091 for( int i = 0; i < cities; ++i ) {
092 chrom.setValue(i, i < cities - 1 ? i+1 : 0);
093 }
094 Individual<IntegerChromosome> sample = new Individual<IntegerChromosome>(chrom);
095 Population<IntegerChromosome> pop = new Population<IntegerChromosome>(sample, POPULATION_SIZE);
096
097 algorithm = new TSPGA(matrix, pop, GENERATION_LIMIT);
098 algorithm.setRandomization(true);
099
100 AbstractStage<IntegerChromosome> selection = new TournamentSelector<IntegerChromosome>(1);
101 AbstractStage<IntegerChromosome> crossover = new TSPCityCenteredCrossover(0.8);
102 AbstractStage<IntegerChromosome> mutation = new TSPScrambleMutator(0.02);
103
104 algorithm.addStage(selection);
105 algorithm.addStage(crossover);
106 algorithm.addStage(mutation);
107
108 algorithm.setBiggerIsBetter(false);
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 System.out.println(stats.getLegalHighestIndividual().getChromosome() );
119 System.out.println(stats.getLegalHighestIndividual());
120 System.out.format("found in %d ms and %d generations.\n", algostats.getExecutionTime(), algostats.getGenerations() );
121 System.out.println();
122 }
123
124 public void solvePC() {
125
126 Individual<PermutationChromosome> sample = new Individual<PermutationChromosome>(new PermutationChromosome(cities));
127 Population<PermutationChromosome> pop = new Population<PermutationChromosome>(sample, POPULATION_SIZE);
128
129 SimpleGA<PermutationChromosome> sga = new SimpleGA<PermutationChromosome>(pop, GENERATION_LIMIT) {
130 @Override
131 public void evaluateIndividual(Individual<PermutationChromosome> individual) {
132 PermutationChromosome chrom = individual.getChromosome();
133 double count = 0;
134 int size = chrom.length();
135 for(int i=0;i<size-1;i++){
136 int val1 = chrom.getElementAt(i);
137 int val2 = chrom.getElementAt(i+1);
138 count += TravelSalesmanProblem.this.map[val1][val2];
139 }
140 count += TravelSalesmanProblem.this.map[size-1][0];
141 individual.setScore(count);
142 }
143
144 };
145
146 sga.setElitism(10);
147 sga.setMutationProbability(0.02);
148 sga.setBiggerIsBetter(false);
149 sga.evolve();
150
151 Population.Statistics stats = sga.getCurrentPopulation().getStatistics();
152 GeneticAlgorithm.Statistics algostats = sga.getStatistics();
153
154 System.out.println(stats.getLegalHighestIndividual().getChromosome() );
155 System.out.println(stats.getLegalHighestIndividual());
156 System.out.format("found in %d ms and %d generations.\n", algostats.getExecutionTime(), algostats.getGenerations() );
157 System.out.println();
158 }
159
160 public static double[][] simpleMap( int cities ) {
161 double[][] matrix = new double[cities][cities];
162
163 matrix[0][0] = 0;
164 for( int i = 1; i <= cities/2; ++i) {
165 matrix[0][i] = i;
166 matrix[0][cities-i] = i;
167 }
168
169 for( int i = 1; i < cities; ++i ) {
170 for( int j = 0; j < cities; ++j ) {
171 matrix[i][(i+j)%cities] = matrix[0][j];
172 }
173 }
174 return matrix;
175 }
176
177 public static double[][] randomMap( int cities ) {
178 double[][] matrix = new double[cities][cities];
179 for( int i = 0; i < cities; ++i ) {
180 for( int j = 0; j < cities; ++j ) {
181 matrix[i][j] = i!=j ? Random.getInstance().nextDouble(MAX_DISTANCE) : 0;
182 }
183 }
184 return matrix;
185 }
186
187 }
|
|
|
