The aim of this competition is to produce the tiniest possible implementation of a genetic algorithm.
The implementation must have the following features:
Submission of Entries:
- 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.
- Fitness proportionate selection should be implemented.
- The representation is binary strings of fixed length.
- Uniform crossover must be implemented.
- Reproduction (a.k.a. cloning) must be implemented.
- Point mutation must be implemented. This must be applied to all strings generated either by crossover or reproduction.
- 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).
- Initialization should be based on generation of random strings uniformly distributed in the search space.
- 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
- 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.
- 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.
- 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.
- If the problem has not been solved after the maximum number of generations, the program should stop printing a message indicating failure.
Submit the source code and a short document (in PDF format, ACM style, max 3 pages) explaining how the code works, how to execute it, how to change the parameters, etc.
Winning criteria include
- Clarity of implementation and accompanying documentation.
- Readability and formatting of the code.
- Number of lines of code.
- Source file size.
- Size of compiled version of program (if any) under gcc or Java.
- Memory footprint when running.
- Degree to which the requirements indicated above have been met.
Entries submitted for this competition will be judged by a panel of international experts (to be announced).