Genetic algorithms. From theory to practice

Good day. Recently decided to engage in self-education. It was decided to start with genetic algorithms.

One of the remarkable properties of GA is that the Selection, Crossing and Mutation procedures do not have an idea about Individuals in Generations - for them it is only 0 and 1. The only function that knows what these same 0 and 1 are This is a Fitness Function.

So I decided that it would be nice to write a framework class for any GA. About this will be this article. It is assumed that you are already familiar with the basics of genetic algorithms.
')
For those interested, I ask under the cat.


The code will be written in Java.

Despite the fact that we are writing a framework, we need to test it. For this, I took the classic NP-complete task - the traveling salesman problem.

A little bit about the architecture of the application:

For the representation of the Genome (Individual) we will use long []. For some reason I found this option better than boolean [].

We also need an interface:

public interface FitnessFunction { int getArity(); //-    long run(long[] genom); //    . } 

The class we are developing is:

 public class GeneticEngine{ public GeneticEngine(FitnessFunction fitnessFunction) {...} // public long[] run() {...} //  private void generateFirstGeneration() {...} //   private void selection(){...} //  private void crossing() {...} //  private void mutation() {...} //  } 

Since we are writing a “universal” class, it is necessary that it supports different variants of crossing and selection, so 2 enumerations (Enum) were added:

 public enum SelectionType { TOURNEY, ROULETTE_WHEEL } public enum CrossingType { ONE_POINT_RECOMBINATION, TWO_POINT_RECOMBINATION, ELEMENTWISE_RECOMBINATION, ONE_ELEMENT_EXCHANGE } 

... and some private fields:

 private int genomLength; //    private long generationCount; //-  private int individualCount; //- (,)   private SelectionType selectionType; //  private CrossingType crossingType; //  private boolean useMutation; //  private double mutationPercent; //    

For them, there are setters and getters.

And now about everything in order ...

The generation of the first generation.

It's very simple: randomly generate longs, compose genomes from longs and put them into an array. I will not give the code.

Selection.

I found 2 types of selection:

• Roulette
• Tournament

The selection procedure creates a new array of genomes.

 private void selection(){ switch (selectionType) { case ROULETTE_WHEEL:{ float[] wheel = new float[this.individualCount]; wheel[0] = //   1-  for (int i=1;i<this.individualCount;i++){ wheel[i] = wheel[i-1] + //   i-  } float all = wheel[this.individualCount-1]; for (int i=0;i<this.individualCount;i++){ float index = Math.abs(this.random.nextFloat())*all; int l = 0; int r = individualCount-1; int c = 0; while (l < r){ c = (l+r) >> 1; if (index <= while[c]){ r = c; }else{ l = c + 1; } } this.genomListOffsprings[i] = this.genomListParents[l].clone(); } break; } case TOURNEY:{ for (int i=0;i<this.individualCount;i++){ int index1 = random.nextInt(individualCount); int index2 = random.nextInt(individualCount); long fr1 = //   index1  long fr2 = //   index2  this.genomListOffsprings[i] = fr1 > fr2 ? this.genomListParents[index1].clone() : this.genomListParents[index2].clone(); } break; } } 

A few comments "from myself":

• During the tests, it turned out that fitness function was performed most of the time (about 90% of the time).
• By applying caching of the results of the FinessFunction on each generation, it was possible to increase the performance of the entire algorithm by 3-4 times.
• Due to the previous two points, Roulette turned out to be several times worse algorithm than the Tournament.

Crossbreeding

Crossing happens:

• Single point recombination.
• Double recombination.
• Elemental crossing.
• One genome exchange.

A few comments "from myself":

• During the tests, it turned out that Elemental crossing works best. While the remaining 3 algorithms have the same “utility”.
• (obvious) The exchange of one genome works for O (1), the rest of the algorithms work for O (L), where l is the length of the genome.
• In spite of the previous point, ALL 4 algorithms work for approximately the same time (exactly time). More precisely: 90% of the time of work of the whole GA is taken by the FitnessFunction, on its background O (1) and O (L) for crossing are equivalent.
• By virtue of the previous three points, I consider (I think) the best crossbreeding algorithm.

* For the function of crossing and mutation, I used binary operations. Therefore, we had to declare a few static variables.

 public static final int OCTET_LENGTH = 64; // -    public static final int MASK_FOR_MOD = OCTET_LENGTH - 1; //  "x%64"   "x & MASK_FOR_MOD" public static final int SHIFT_FOR_DIVISION; //  "x/64" - "x >> SHIFT_FOR_DIVISION" 

Function for crossing two genomes:
(The code is only for Elemental Crossing)

 private void cross(long[] genom1, long[] genom2) { switch (crossingType) { ... case ELEMENTWISE_RECOMBINATION:{ for (int outerOffset = 0; outerOffset < this.sizeOfArray; outerOffset++) { long mask = this.random.nextLong(); //   ,    (1- , 0-) long swapMask = (genom1[outerOffset] ^ genom2[outerOffset]) & mask; genom1[outerOffset] ^= swapMask; genom2[outerOffset] ^= swapMask; } break; } } 

Explanations:
To exchange the numbers a and b between you:
swapMask = a xor b;
a = a xor swapMask;
b = b xor swapMask;

And if we impose (and) mask on swapMask, then a and b will change only those bits that are == 1 in the mask number.

swapMask = (a xor b) and mask;
a = a xor swapMask;
b = b xor swapMask;

Mutation.

 private void mutation() { for (long[] genom : this.genomListOffsprings) { if (random.nextDouble() <= mutationPercent) { mutate(genom); } } } private void mutate(long[] genom) { int index = this.random.nextInt(this.genomLength); int outerOffset = index >> SHIFT_FOR_DIVISION; int innerOffset = (index & MASK_FOR_MOD); long mask = 1L << innerOffset; genom[outerOffset] ^= mask; } 

To invert a bit you need:
bit = bit xor 1;
Therefore, in order to invert any bit in the number, you need to shift the unit to the desired position.

"Body".

And the main function that links all the previous ones:

 public long[] run() { generateFirstGeneration(); while (currentGeneration < generationCount) { selection(); this.crossing(); if (useMutation) { mutation(); } currentGeneration++; } return . } 

Application.

Using it all is quite simple:
First you need to describe the class Fitness.
So what is next…

 MyFitnessFunction ff = new MyFitnessFunction(); GeneticEngine ge = new GeneticEngine(ff); ge.setIndividualCount(1000); // -    ge.setGenerationCount(10000); // -  ge.setSelectionType(SelectionType.TOURNEY); //  ge.setCrossingType(CrossingType.ELEMENTWISE_RECOMBINATION); //  ge.setUseMutation(true); //    ge.setMutationPercent(0.02d); //    long[] better = ge.run(); // 

Let's return to the traveling salesman problem.

Since the distance between the cities was filled with the random.nextInt (256) random access. Then I dare to assume that the average distance between 2 cities = 128. => The average length of the route for all cities = 128 * 256 = 32768. (! I can be wrong).

With

 IndividualCount = 100; GenerationCount = 10000; SelectionType = SelectionType; CrossingType = ELEMENTWISE_RECOMBINATION; UseMutation = true; MutationPercent = 0.02d; 

GA finds the path = 10000-12000 for 6-7 seconds. Which is 3 times better than average.

With

 IndividualCount = 1000; GenerationCount = 10000; 

5500-7000 per minute.

With

 IndividualCount = 10000; GenerationCount = 100000; 

The code works about 15 hours. and finds the route = 3500-4000.

Where to grow further.

• I hope, knowledgeable people will tell you how to better implement the Roulette.
• It is possible to make a GA stop not only by the number of generations, but after reaching some value of the Fitness Function, or when the difference in the average values ​​of the Fitness Function of the generations has become small.
• You can store an individual with the best Fitness Function for all generations. Or not for all generations, but only from those individuals for whom the FitnessFunction was calculated - it will not be expensive.

Link to github. I would be glad if someone come in handy.

UPD: The code is written in Java, but I tried to write it without using java.util, and in such a way that it looked like C.
What caused this aspect:

• There will be no overhead in data storage.
• The code becomes easily portable in C / C ++ / php / any C-like language.
• It does not hurt speed (maybe even a little increase).
• The code will not be harder to read.

(in the comments the code was confused with S-shny, therefore I consider this task completed)

UPD2: LeoCcoder found an error in Roulette (in binary search). Fixed.