001 /*
002 * CISELab, Computational and Intelligent Systems Engineering Laboratory
003 * Department of Engineering
004 * University of Sannio, 82100 Benevento (ITALY)
005 * web-site: www.ciselab.org
006 *
007 * JENES, A Java Library for Genetic Algorithms
008 * Copyright (C) 2009, Luigi Troiano
009 *
010 * This library is free software; you can redistribute it and/or
011 * modify it under the terms of the GNU Lesser General Public
012 * License as published by the Free Software Foundation; either
013 * version 2.1 of the License, or (at your option) any later version.
014 *
015 * This library is distributed in the hope that it will be useful,
016 * but WITHOUT ANY WARRANTY; without even the implied warranty of
017 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
018 * Lesser General Public License for more details.
019 *
020 * You should have received a copy of the GNU Lesser General Public
021 * License along with this library; if not, write to the Free Software
022 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
023 02110-1301 USA
024 *
025 * COPYRIGHT DISCLAIMER
026 * CISELab, hereby disclaims all copyright interest in the
027 * library `JENES' (A Java Library for Genetic Algorithms)
028 * written by Luigi Troiano et al.
029 *
030 * Luigi Troiano, 1 January 2009
031 * CISELab Coordinator
032 */
033 package jenes.tutorials.problem3;
034
035 import jenes.GeneticAlgorithm;
036 import jenes.Random;
037 import jenes.algorithms.SimpleGA;
038 import jenes.chromosome.IntegerChromosome;
039 import jenes.chromosome.PermutationChromosome;
040 import jenes.population.Individual;
041 import jenes.population.Population;
042 import jenes.stage.AbstractStage;
043 import jenes.stage.operator.common.TournamentSelector;
044 import jenes.tutorials.utils.Utils;
045
046
047 public class TravelSalesmanProblem {
048
049 public static final int POPULATION_SIZE = 1000;
050 private static int GENERATION_LIMIT = 2000;
051 public static final int MAX_DISTANCE = 10;
052
053 private TSPGA algorithm;
054 private int cities;
055 private double[][] map;
056
057 public static void main(String[] args) {
058
059 Utils.printHeader();
060 System.out.println();
061
062 System.out.println("TUTORIAL 3:");
063 System.out.println("The Travel Salesman Problem, a classics.");
064 System.out.println();
065
066 Random.getInstance().setStandardSeed();
067
068 System.out.println("Case 1: 10 cities in circle");
069 double[][] m1 = simpleMap(10);
070 TravelSalesmanProblem tsp1 = new TravelSalesmanProblem(m1);
071 tsp1.solve();
072
073 System.out.println("Case 2: 30 cities in circle");
074 double[][] m2 = simpleMap(30);
075 TravelSalesmanProblem tsp2 = new TravelSalesmanProblem(m2);
076 tsp2.solve();
077
078 System.out.println("Case 3: 30 cities at random");
079 double[][] m3 = randomMap(30);
080 TravelSalesmanProblem tsp3 = new TravelSalesmanProblem(m3);
081 tsp3.solve();
082
083 System.out.println("Case 4: An application of PermutationChromosome");
084 tsp2.solvePC();
085 }
086
087 public TravelSalesmanProblem(double[][] matrix) {
088
089 cities = matrix[0].length;
090 map = matrix;
091
092 IntegerChromosome chrom = new IntegerChromosome(cities,0,cities-1);
093 for( int i = 0; i < cities; ++i ) {
094 chrom.setValue(i, i < cities - 1 ? i+1 : 0);
095 }
096 Individual<IntegerChromosome> sample = new Individual<IntegerChromosome>(chrom);
097 Population<IntegerChromosome> pop = new Population<IntegerChromosome>(sample, POPULATION_SIZE);
098
099 algorithm = new TSPGA(matrix, pop, GENERATION_LIMIT);
100 algorithm.setRandomization(true);
101
102 AbstractStage<IntegerChromosome> selection = new TournamentSelector<IntegerChromosome>(1);
103 AbstractStage<IntegerChromosome> crossover = new TSPCityCenteredCrossover(0.8);
104 AbstractStage<IntegerChromosome> mutation = new TSPScrambleMutator<IntegerChromosome>(0.2);
105
106 algorithm.addStage(selection);
107 algorithm.addStage(crossover);
108 algorithm.addStage(mutation);
109
110 algorithm.setBiggerIsBetter(false);
111 algorithm.setElitism(10);
112 }
113
114 public void solve() {
115 algorithm.evolve();
116
117 Population.Statistics stats = algorithm.getCurrentPopulation().getStatistics();
118 GeneticAlgorithm.Statistics algostats = algorithm.getStatistics();
119
120 System.out.println(stats.getLegalHighestIndividual().getChromosome() );
121 System.out.println(stats.getLegalHighestIndividual());
122 System.out.format("found in %d ms and %d generations.\n", algostats.getExecutionTime(), algostats.getGenerations() );
123 System.out.println();
124 }
125
126 public void solvePC() {
127
128 Individual<PermutationChromosome> sample = new Individual<PermutationChromosome>(new PermutationChromosome(cities));
129 Population<PermutationChromosome> pop = new Population<PermutationChromosome>(sample, POPULATION_SIZE);
130
131 SimpleGA<PermutationChromosome> sga = new SimpleGA<PermutationChromosome>(pop, GENERATION_LIMIT) {
132 @Override
133 protected void evaluateIndividual(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 sga.setElitism(10);
149 sga.setMutationProbability(0.02);
150 sga.setBiggerIsBetter(false);
151 sga.evolve();
152
153 Population.Statistics stats = sga.getCurrentPopulation().getStatistics();
154 GeneticAlgorithm.Statistics algostats = sga.getStatistics();
155
156 System.out.println(stats.getLegalHighestIndividual().getChromosome() );
157 System.out.println(stats.getLegalHighestIndividual());
158 System.out.format("found in %d ms and %d generations.\n", algostats.getExecutionTime(), algostats.getGenerations() );
159 System.out.println();
160 }
161
162 public static double[][] simpleMap( int cities ) {
163 double[][] matrix = new double[cities][cities];
164
165 matrix[0][0] = 0;
166 for( int i = 1; i <= cities/2; ++i) {
167 matrix[0][i] = i;
168 matrix[0][cities-i] = i;
169 }
170
171 for( int i = 1; i < cities; ++i ) {
172 for( int j = 0; j < cities; ++j ) {
173 matrix[i][(i+j)%cities] = matrix[0][j];
174 }
175 }
176 return matrix;
177 }
178
179 public static double[][] randomMap( int cities ) {
180 double[][] matrix = new double[cities][cities];
181 for( int i = 0; i < cities; ++i ) {
182 for( int j = 0; j < cities; ++j ) {
183 matrix[i][j] = i!=j ? Random.getInstance().nextDouble(MAX_DISTANCE) : 0;
184 }
185 }
186 return matrix;
187 }
188
189 }
|
|
|
