Tournament evaluation in genetic algorithm

Question

Right now, every genetic C# library (A.Forge, Genetic Algorithm Framework, GeneticSharp) seems to only evaluates a single Chromosome, and then uses one of the various selection methods to create a new generation.

Since my problem involves two AIs to play against each other, it's a bit harder to evaluate their fitness alone. While the game is simple enough to create some superficial hurdles (the AI don't interact directly, but obstacles are sent to each others game) that would allow me to get some abstract fitness, but that wouldn't be the "real" deal.

The libraries also don't seem to offer another Interface I could implement such an evaluation method. Are there other frameworks that allow this or do I need to start from scratch?

Answer 1

Every genetic algorithm library should have some way for you to define a fitness function, which is really what you're looking for. AForge.NET exposes the IFitnessFunction interface. GeneticSharp exposes the IFitness interface. Yes, you will have to code the fitness function yourself -- that's the part that's unique to your problem area. You can make it as simple or complex as you want.

After each chromosome goes through the fitness function and is assigned a score, the system uses whatever selection criteria you like (tournament, roulette wheel, etc.) to pick which chromosomes go on to the next generation via crossover and/or mutation.

So rather than the process flowing like this:

1. Match up chromosomes in current generation
2. Each chromosome pair plays a round
3. The winners create the next generation

Genetic algorithms work like this:

1. Each chromosome plays a round and gets a score
2. The selection algorithm uses that score to pick the overall winners
3. The winners create the next generation

In essence, every chromosome is already competing with every other chromosome, just one step more abstract than you and I would play a game.

You could probably rig the fitness function to pull in a random other member of the current population as an opponent. Better would be to use the best chromosome from the previous generation as the opponent for the entire current generation.

Assign points to your chromosome for progressing further in the game and award points for generating obstacles for the opponent (if that is a distinct action separate from normal gameplay in your game). Return the chromosome's final score as the fitness function output.