Challenge 3: Tiny GA

Deadline Friday 1st of June

The aim of this competition is to produce the tiniest possible implementation of a genetic algorithm.

Requirements

The implementation must have the following features:

  1. The system can be either generational or steady state. In the latter case a “generation” is to be interpreted as POPSIZE (see below) crossover/reproduction events.
  2. Fitness proportionate selection should be implemented.
  3. The representation is binary strings of fixed length.
  4. Uniform crossover must be implemented.
  5. Reproduction (a.k.a. cloning) must be implemented.
  6. Point mutation must be implemented. This must be applied to all strings generated either by crossover or reproduction.
  7. The fitness function must be One-max (a.k.a. counting ones), but should not be hard coded (i.e., it should easily be possible to modify the code to change fitness function).
  8. Initialization should be based on generation of random strings uniformly distributed in the search space.
  9. The following parameters must be implemented (but can be fixed at compile time if necessary) and printed when each run starts:
    • LEN // the length bit strings
    • POPSIZE // the size of the population
    • GENERATIONS // the maximum number of generations allowed for a run
    • CROSSOVER_PROB // the probability of crossing over (the reproduction probability is 1 – CROSSOVER_PROB)
    • PMUT // the mutation probability per bit
  10. At each generation the following statistics/data should be calculated and printed:
    • Generation number
    • Average fitness of the individuals in the population.
    • The fitness of the best individual in the population.
    • The string representing the best individual in the population.
  11. The random number generator will need to be seeded. It must be possible to do this from command line. If the command line parameter is absent, the system must use the current time to seed the random number generator.
  12. If the fitness of the best individual in the population reaches the maximum fitness (LEN, in the case of the one-max fitness function) the program should stop printing a message indicating success.
  13. If the problem has not been solved after the maximum number of generations, the program should stop printing a message indicating failure.

Winning criteria

  • Clarity of implementation and accompanying documentation.
  • Readability and formatting of the code.
  • Number of lines of code.
  • Source file size.
  • Memory footprint when running.
  • Degree to which the requirements indicated above have been met.
  • Obviously some form of readme will be required.
  • Languages Java, C, C++, Ruby, Python etc etc
  • Obviously any non standard, specialist library must be included

WINNER GETS A LOVELY CHOCOLATE BISCUIT CAKE

————————————-UPDATE————————————-

The Winner is in although to be fair all entries were good

Erik was Functional but a smidge on the portly side in size and length and some features were not implemented

James went for Python and put up a good fight beating Erik

But Eoin is the winner with his 2 entries of kinda readable code :P He does some funny things to get the code down in size, but excellent readme and comments and size in length and file size wins it

Cake is on the way to the winner in the next few days. (Plus some for the other entrants)

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>