Methods for crossover in genetic algorithms

Question

When reading about the crossover part of genetic algorithms, books and papers usually refer to methods of simply swapping out bits in the data of two selected candidates which are to reproduce.

I have yet to see actual code of an implemented genetic algorithm for actual industry applications, but I find it hard to imagine that it's enough to operate on simple data types.

I always imagined that the various stages of genetic algorithms would be performed on complex objects involving complex mathematical operations, as opposed to just swapping out some bits in single integers.

Even Wikipedia just lists these kinds of operations for crossover.

Am I missing something important or are these kinds of crossover methods really the only thing used?

Answer 1

There are several things used... although the need for parallelity and several generations (and sometimes a big population) leads to using techniques that perform well...

Another point to keep in mind is that "swapping out some bits" when modeled correctly resembles a simple and rather accurate version of what happens naturally (recombination of genes, mutations)...

For a very simple and nicely written walkthrough see http://www.electricmonk.nl/log/2011/09/28/evolutionary-algorithm-evolving-hello-world/

For some more info see

• http://www.codeproject.com/KB/recipes/btl_ga.aspx
• http://www.codeproject.com/KB/recipes/genetics_dot_net.aspx
• http://www.codeproject.com/KB/recipes/GeneticandAntAlgorithms.aspx
• http://www.c-sharpcorner.com/UploadFile/mgold/GeneticAlgorithm12032005044205AM/GeneticAlgorithm.aspx

Answer 2

I always imagined that the various stages of genetic algorithms would be performed on complex objects involving complex mathematical operations, as opposed to just swapping out some bits in single integers.

You probably think complex mathematical operations are used because you think the Genetic Algorithm has to modify a complex object. That's usually not how a Genetic Algorithm works.

So what does happen? Well, usually, the programmer (or scientist) will identify various parameters in a configuration, and then map those parameters to integers/floats. This does limit the directions in which the algorithm can explore, but that's the only realistic method of getting any results.

Let's look at evolving an antenna. You could perform complex simulation with an genetic algorithm rearranging copper molecules, but that would be very complex and take forever. Instead, you'd identify antenna "parameters". Most antenna's are built up out of certain lengths of wire, bent at certain places in order to maximize their coverage area. So you could identify a couple of parameters: number of starting wires, section lengths, angle of the bends. All those are easily represented as integer numbers, and are therefor easy for the Genetic Algorithm to manipulate. The resulting manipulations can be fed into an "Antenna simulator", to see how well it receives signals.

In short, when you say:

I find it hard to imagine that it's enough to operate on simple data types.

you must realize that simple data types can be mapped to much more intricate structures. The Genetic Algorithm doesn't have to know anything about these intricate structures. All it needs to know is how it can manipulate the parameters that build up the intricate structures. That is, after all, the way DNA works.

Answer 3

In Genetic algorithms usually bitswapping of some variety is used.

As you have said:

I always imagined that the various stages of genetic algorithms would be performed on complex objects involving complex mathematical operations

What i think you are looking for is Genetic Programming, where the chromosome describes a program, in this case you would be able to do more with the operators when applying crossover.

Also make sure you have understood the difference between your fitness function in genetic algorithms, and the operators within a chromosome in genetic programming.

Answer 4

Different applications require different encondigs. The goal certainly is to find the most effective encoding and often enough the simple encodings are the better suited. So for example a Job Shop Scheduling Problem might be represented as list of permutations which represent the execution order of the jobs on the different machines (so called job sequence matrix). It can however also be represented as a list of priority rules that construct the schedule. A traveling salesman problem or quadratic assignment problem is typically represented by a single permutation that denotes a tour in one case or an assignment in another case. Optimizing the parameters of a simulation model or finding the root of a complex mathematical function is typically represented by a vector of real values.

For all those, still simple types crossover and mutation operators exist. For the permutation these are e.g. OX, ERX, CX, PMX, UBX, OBX, and many more. If you can combine a number of simple representations to represent a solution of your complex problem you might reuse these operations and apply them to each component individually.

The important thing about crossover to work effectively is that a few properties should be fulfilled:

• The crossover should conserve those parts that are similar in both
• For those parts that are not similar, the crossover should not introduce an element that is not already part of one of the parents
• The crossover of two solutions should, if possible, produce a feasible solution

You want to avoid so called unwanted mutations in your crossovers. In that light you also want to avoid having to repair a large part of your chromosomes after crossover, since that is also introducing unwanted mutations.

If you want to experiment with different operators and problems, we have a nice GUI-driven software: HeuristicLab.

Answer 5

Simple Bit swapping is usually the way to go. The key thing to note is the encoding that is used in each candidate solution. Solutions should be encoded such that there is minimal or no error introduced into the new offspring. Any error would require that the algorithm to provide a fix which will lead to increased processing time.

As an example I have developed a university timetable generator in C# that uses a integer encoding to represent the timeslots available in each day. This representation allows very efficient single point or multi-point crossover operator which uses the LINQ intersect function to combine parents.

Typical multipoint crossover with hill-climbing

 public List<TimeTable> CrossOver(List<TimeTable> parents) // Multipoint crossover
    {                                   
        var baby1 = new TimeTable {Schedule = new List<string>(), Fitness = 0};
        var baby2 = new TimeTable {Schedule = new List<string>(), Fitness = 0};

        for (var gen = 0; gen < parents[0].Schedule.Count; gen++)
        {               
            if (rnd.NextDouble() < (double) CrossOverProb)
            {                      
                baby2.Schedule.Add(parents[0].Schedule[gen]);
                baby1.Schedule.Add(parents[1].Schedule[gen]);                                                          
            }
            else
            {
                baby1.Schedule.Add(parents[0].Schedule[gen]);
                baby2.Schedule.Add(parents[1].Schedule[gen]);
            }
        }

        CalculateFitness(ref baby1);
        CalculateFitness(ref baby2);  

        // allow hill-climbing
        parents.Add(baby1);
        parents.Add(baby2);

        return parents.OrderByDescending(i => i.Fitness).Take(2).ToList();            
    }