Tutorials‎ > ‎

Tutorial 3: Redefining genetic operations

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.
  1. Using or creating a specific chromosome class
  2. 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         ifchrom_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         ifchrom_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         forint 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             ifp2 > 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             ifp1 > 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         forint 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     }