GA written in Java

Question

I am attempting to write a Genetic Algorithm based on techniques I had picked up from the book "AI Techniques for Game Programmers" that uses a binary encoding and fitness proportionate selection (also known as roulette wheel selection) on the genes of the population that are randomly generated within the program in a two-dimensional array.

I recently came across a piece of pseudocode and have tried to implement it, but have come across some problems with the specifics of what I need to be doing. I've checked a number of books and some open-source code and am still struggling to progress. I understand that I have to get the sum of the total fitness of the population, pick a random number between the sum and zero, then if the number is greater than the parents to overwrite it, but I am struggling with the implementation of these ideas.

Any help in the implementation of these ideas would be very much appreciated as my Java is rusty.

Answer 1

I made an extensible implementation in java, in which operators and individual structure is well defined by interfaces that work together. Github repo here https://github.com/juanmf/ga

It has a standard implementation for each operator, and an example problem implementation with a particular Individual/Population structure and a Fitness meter. The example problem Implementation is to find the a good soccer team with players among 20 teams and a budget restriction.

To adapt it to your current problem you need to provide implementations of these interfaces:

juanmf.ga.structure.Gen;
juanmf.ga.structure.Individual;
juanmf.ga.structure.IndividualFactory; 
juanmf.ga.structure.Population;  // Has a basic implementation already
juanmf.ga.structure.PopulationFactory;

In pkg juanmf.grandt you have the example problem implementation classes, and how to publish them, as shown in the code snippet below.

To publish you implementations you just have to return the proper classes from this Spring beans:

/**
 * Make sure @ComponentScan("pkg") in juanmf.ga.App.java includes this class' pkg 
 * so that these beans get registered.
 */
@Configuration
public class Config {

    @Bean(name="individualFactory")
    public IndividualFactory getIndividualFactory() {
        return new Team.TeamFactory();
    }

    @Bean(name="populationFactory")
    public PopulationFactory getPopulationFactory() {
        return new Team.TeamPopulationFactory();
    }

    @Bean(name="fitnessMeter")
    public FitnessMeter getFitnessMeter() {
        return new TeamAptitudeMeter();
    }
} 

Crosser operator has two implementations for the same technique, one sequential and one concurrent which outperforms sequential by far.

Stop condition can be specified. If none is given, it has a default stop condition that stops after 100 generations with no improvements (here you must be careful with elitist, not to loose the best of each generation so as to trigger this stop condition effectively).

So if anyone is willing to give it a try, I'd be glad to help. Anyone is welcome to offer suggestions, and better yet operator implementations :D or any improving pull request.