Solving XOR using Genetic Algorithms

Yesterday I posted about genetic algorithms. Now it's time to put a GA to use and solve a very simple problem: in this case, generating boolean logic gates until one of them behaves exactly like a logic XOR gate.

Boolean logic gates take one or more boolean values as input (in our case, value A and B) and return a single boolean response value. Their behavior can be expressed by a so called truth table: in XOR's case, the gate will return True if the two input values are different, while it will return False if both are true or both are false.

Encoding the chromosome

The first step in using a genetic algorithm is to define the "chromosome" encoding (the gene sequence) of the candidate solutions that will be generated. To encode the behavior of a boolean gate, we could for instance define the following simple class:

class XorChromosome : NGene.IChromosome<XorChromosome> {
    public bool FalseFalse;
    public bool FalseTrue;
    public bool TrueFalse;
    public bool TrueTrue;

    //IChromosome<T> implementation
}

Ignore the NGene.IChromosome<T> interface for now. The four boolean values define how the logical gate with that particular chromosome will react to the possible combinations of input values. For instance, having False and False as input will return the "FalseFalse" boolean as output. Therefore, the correct encoding of a XOR gate would have both "FalseTrue" and "TrueFalse" set to true, while "FalseFalse" and "TrueTrue" would be set to false instead.

The fitness function

Since we know how the "perfect" XOR gate does look like, we can write an equally simple fitness function that will compute "how good" each chromosome is:

class XorEvaluator : IFitnessEvaluator<XorChromosome> {

    #region IFitnessEvaluator<XorChromosome> Members

    public double Evaluate(XorChromosome individual) {
        double points = 0.0;

        if (individual.FalseFalse == false)
            points += 1.0;
        if (individual.FalseTrue == true)
            points += 1.0;
        if (individual.TrueFalse == true)
            points += 1.0;
        if (individual.TrueTrue == false)
            points += 1.0;

        return points;
    }

    #endregion

}

This XorEvaluator assigns a point for each correct value. Correct XOR gates will obtain a total score of 4 when their fitness is evaluated. Gates that are incomplete and return wrong values will have a lower fitness value.

Crossover and mutation

The core of the algorithm is very simple. In my case I wrote a small library, NGene, that I will publish on the site in the following weeks. The only missing parts are the methods to crossover two chromosome and to apply mutation to one's genome.

In NGene those methods are part of the IChromosome interface. Their implementation for a XOR chromosome is very simple:

class XorChromosome : NGene.IChromosome<XorChromosome> {

    bool GenRndBool(Random random) {
        return (random.NextDouble() < 0.5);
    }

    #region IChromosome<XorChromosome> Members

    public XorChromosome CreateRandom(Random random) {
        XorChromosome ret = new XorChromosome();
        ret.FalseFalse = GenRndBool(random);
        ret.FalseTrue = GenRndBool(random);
        ret.TrueFalse = GenRndBool(random);
        ret.TrueTrue = GenRndBool(random);

        return ret;
    }

    public XorChromosome Crossover(XorChromosome otherParent, double crossPoint) {
        XorChromosome ret = new XorChromosome(this);

        if (crossPoint < 0.25)
            ret.FalseFalse = otherParent.FalseFalse;
        if (crossPoint < 0.5)
            ret.FalseTrue = otherParent.FalseTrue;
        if (crossPoint < 0.75)
            ret.TrueFalse = otherParent.TrueFalse;
        if (crossPoint >= 0.75)
            ret.TrueTrue = otherParent.TrueTrue;

        return ret;
    }

    public void Mutate(Random random) {
        int index = random.Next(1, 4);

        switch (index) {
            case 1:
                FalseFalse = GenRndBool(random); break;
            case 2:
                FalseTrue = GenRndBool(random); break;
            case 3:
                TrueFalse = GenRndBool(random); break;
            case 4:
                TrueTrue = GenRndBool(random); break;
            default:
                throw new ArgumentOutOfRangeException();
        }
    }

    #endregion

}

Run the genetic algorithm

Now that the test is ready, let's run the algorithm on a small population and see how the resulting XOR gates change from generation to generation.

The first test will take a random population of 20 chromosomes (that is, a group of 20 candidate logic gates) and let it evolve for 40 generations. The fitness levels over all generations are the following:

As you can see the minimum fitness (the "score" of the worst individual in the population) starts very low at 0.0 (the initial population included a completely wrong logical gate) but then starts to get better. Since the XOR model is so simple, even at the beginning we have some individuals in the population that are pretty close to the correct solution. In fact, already at generation 3 or 4 there is at least one chromosome that features the behavior of a correct XOR gate.

Anyway, the average fitness climbs more or less steadily from the first to the 40th generation. Some sudden drops in fitness level are noticable: for instance at generation 11 or around generation 27-28. This is expected, since the whole algorithm is based on chance and mutation can corrupt an otherwise correct candidate, but in overall the trend is positive.

Ok, let's do a second test. This time we use a larger population of 30 individuals, let it evolve for 30 generations and artificially limit the initial population to a fitness of 1 or lower. This should let us test how the algorithm behaves even with unfavorable initial conditions.

Interestingly, even if the population starts out pretty badly, already at generation 4 a chromosome with the desired behavior has been breeded. The average fitness converges to the value 3.0 in approximately 10 generations. Even running tests on very large populations and on very large timespans (300 generations or more) yields the same results: the genetic algorithm quickly finds the correct solution and the average fitness value converges towards 3.0-3.5.

Above you can see the output of the program, returning the correct XOR gate.

So?

Now, arguably, this test isn't very significative since the XOR domain is exceedingly simple. But the mechanisms used by the genetic algorithm work and can be applied to much more complex problems, where an "optimal" solution is either not known or cannot be identified a priori.

The next step will be an application of a genetic algorithm to a videogame.