In some circumstances the search space is sparse within a larger space. This is the case of the Travel Salesman Problem, aimed at finding a minimal routing among a set of points, given the distances between them.
A natural way for representing a solution is by a permutation of elements, providing the order by which the minimal routing visits the points. Therefore, a chromosome is generally made of integer indeces, each referring to a particular point (city). Traditional crossover and mutation operators do not assure to produce valid solutions , i.e. permutations, as some cities could be replicated or missing. There is a need for redefining these operations. In this tutorial we show two ways to accomplish this task.
- Using or creating a specific chromosome class
- Redefining the crossover and mutator
Package:
jenes.tutorials.problem3
Files:
TravelSalesmanProblem.java
TSPScrambleMutator.java
TSPGA.java
TSPCityCenteredCrossover.java.
1. Using or creating a specific chromosome class
In Jenes, genetic operators rely on the primitives made available by the
Chromosome interface, such as cross, randomize, swap and shift. Therefore, it is possible too define a specific Chromosome subclass with a set of primitives avoiding transformations that lead to unfeasible solutions.
In Jenes the
PermutationChromosome is able to process permutations according to the following stategy:
- Crossover: alleles in one chromosome are re-arranged according to the order they are considered by the other chromosome
- Mutation: one allele is exchanged with another randomly chosen
The code code used to set-up the algorithm and the fitness function are showed below:
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);
2. Redefining the crossover and mutator
Crossover
Redefining a crossover is quite simple. The first thing to do is to extend the Chromosome class.
057 public class TSPCityCenteredCrossover extends Crossover<IntegerChromosome>{
The City Centered Crossover, chooses one city and re-sort the following cities in one chromosome according to the order given by the other. This operation is performed by implementing the cross method.
078 protected void cross(Individual<IntegerChromosome> offsprings[]) {
079
080 IntegerChromosome chrom_child1 = offsprings[0].getChromosome();
081 IntegerChromosome chrom_child2 = offsprings[1].getChromosome();
082
083 if( chrom_parent1 == null ) {
084 chrom_parent1 = chrom_child1.clone();
085 chrom_parent2 = chrom_child2.clone();
086 } else {
087 chrom_parent1.setAs(chrom_child1);
088 chrom_parent2.setAs(chrom_child2);
089 }
090
091 final int size = chrom_child1.length();
092 if( chrom_child2.length() != size )
093 throw new AlgorithmException("Error: the two chromosomes are required to have the same length.");
094
095
096 //we choose a random city
097 int city = Random.getInstance().nextInt(0, size);
098
099 //i1, i2 are the positions of the city respectively in child1 and child2
100 int i1 = findPositionOf(city, chrom_child1);
101 int i2 = findPositionOf(city, chrom_child2);
102
103 int j1 = 0;
104 int j2 = 0;
105 for( int i = 0; i < size; ++i ) {
106 // get the city c1 in position i for parent1
107 int c1 = chrom_parent1.getValue(i);
108 // find the position of c1 in parent 2
109 int p2 = findPositionOf(c1, chrom_parent2);
110 // if the position is over the cross-point, it copies c1 in child2
111 if( p2 > i2 ) {
112 chrom_child2.setValue(i2 + (++j2), c1);
113 }
114
115 // similarly we process the other pair
116 int c2 = chrom_parent2.getValue(i);
117 int p1 = findPositionOf(c2, chrom_parent1);
118 if( p1 > i1 ) {
119 chrom_child1.setValue(i1 + (++j1), c2);
120 }
121 }
122 }
Mutator
Redefining the mutator is straightforward as well. First, we need to subclass the Mutator operator.
047 public class TSPScrambleMutator extends Mutator<IntegerChromosome> {
The Scramble mutator is based on the following strategy: two indeces
i1 and
i2 are randomly choosen and the order of the elements within the range
[i1, i2] changes randomly.
This algorithm is implemented by the randomize method
081 public void randomize(IntegerChromosome chrom, int min, int max) {
082
083 //we create a temporany array
084 int len = max-min+1;
085 int[] base = new int[len];
086
087 //we fill it with the elements within [min,max]
088 for(int i=0;i<len;i++)
089 base[i]= chrom.getValue(min+i);
090
091 //the loop ends when the temporany array is empty
092 for( int i = 0; len > 0; --len, ++i) {
093 //we choose a random position pos in the array and copy the element at pos in the chromosome
094 int pos = Random.getInstance().nextInt(0,len);
095 chrom.setValue(min+i,base[pos]);
096 //we removes the chosen element from the temporany array
097 for(int j=pos;j<(len-1);j++){
098 base[j]=base[j+1];
099 }
100 }
101 }
