jenes.tutorials.problem3.TravelSalesmanProblem.java

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         forint i = 0; i < cities; ++i ) {
094             chrom.setValue(i, i < cities - ? i+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         forint i = 1; i <= cities/2; ++i) {
167             matrix[0][i] = i;
168             matrix[0][cities-i] = i;
169         }
170         
171         forint i = 1; i < cities; ++i ) {
172             forint 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         forint i = 0; i < cities; ++i ) {
182             forint 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 }
Comments