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.tutorial.old.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 accoring 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 using a PermutationChromosome is presented below:
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 };
2. Redefining the crossover and mutator
Crossover
Redefining a crossover is quite simple. The first thing to do is to extend the Chromosome class.
059 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 gicen by the other. This
operation is performed by implementing the cross method.
080 protected void cross(Individual<IntegerChromosome> offsprings[]) {
081
082 IntegerChromosome chrom_child1 = offsprings[0].getChromosome();
083 IntegerChromosome chrom_child2 = offsprings[1].getChromosome();
084
085 if( chrom_parent1 == null ) {
086 chrom_parent1 = chrom_child1.clone();
087 chrom_parent2 = chrom_child2.clone();
088 } else {
089 chrom_parent1.setAs(chrom_child1);
090 chrom_parent2.setAs(chrom_child2);
091 }
092
093 final int size = chrom_child1.length();
094 if( chrom_child2.length() != size )
095 throw new AlgorithmException("Error: the two chromosomes are required to have the same length.");
096
097
098 //we choose a random city
099 int city = Random.getInstance().nextInt(0, size);
100
101 //i1, i2 are the positions of the city respectively in child1 and child2
102 int i1 = findPositionOf(city, chrom_child1);
103 int i2 = findPositionOf(city, chrom_child2);
104
105 int j1 = 0;
106 int j2 = 0;
107 for( int i = 0; i < size; ++i ) {
108 // get the city c1 in position i for parent1
109 int c1 = chrom_parent1.getValue(i);
110 // find the position of c1 in parent 2
111 int p2 = findPositionOf(c1, chrom_parent2);
112 // if the position is over the cross-point, it copies c1 in child2
113 if( p2 > i2 ) {
114 chrom_child2.setValue(i2 + (++j2), c1);
115 }
116
117 // similarly we process the other pair
118 int c2 = chrom_parent2.getValue(i);
119 int p1 = findPositionOf(c2, chrom_parent1);
120 if( p1 > i1 ) {
121 chrom_child1.setValue(i1 + (++j1), c2);
122 }
123 }
124 }
Mutator
Redefining the mutator is straightforward as well. First, we need to subclass the Mutator operator.
051 public class TSPScrambleMutator<T extends Chromosome> extends Mutator<T> {
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
085 public void randomize(Individual<T> c,int min, int max) {
086 IntegerChromosome chrom = (IntegerChromosome) c.getChromosome();
087 //we create a temporany array
088 int len = max-min+1;
089 int[] base = new int[len];
090 //we fill it with the elements within [min,max]
091 for(int i=0;i<len;i++)
092 base[i]= chrom.getValue(min+i);
093
094 //a randomizes process starts
095 int i=0;
096 //the loop ends when the temporany array is empty
097 while(len!=0){
098 //we choose a random position pos in the array and copy the element at pos in the chromosome
099 int pos = Random.getInstance().nextInt(0,len);
100 chrom.setValue(min+i,base[pos]);
101 //we removes the choosed element from the temporany array
102 for(int j=pos;j<(len-1);j++){
103 base[j]=base[j+1];
104 }
105 //we updates len and i
106 len--;i++;
107 }
108 }
