Genetic Algorithm

Optimizing bit strings through genetics and natural selections

Implementation of a genetic algorithm written in pure C that optimizes arbitrary bit strings of sizes 8. Given a random starting population of octane bit strings a fitness function which evaluates the number of set bits is applied to determine the fitness value of each bit string (individual). Two candidates are then chosen through fitness proportionate selection (roulette wheel selection) and single point crossover is performed to produce offsprings from those two candidates. This process is repeated until the children generation matches that of the parent generation. In addition, each offspring will have a 1 / bit string length chance to be selected for mutation where a random bit will be toggled. The simulation is ran until the maximum generation is reached or a solution based on the fitness function has been found i.e. if the bit strings are of length of 16 then the solution is 16.

Installation

Linux & OS X:

git clone https://github.com/AGontcharov/Genetic-Algorithm.git
cd Genetic-Algorithm/
make

Windows:

Not yet available

Running

The Genetric Algorithm accepts a number of arguments that must be supplied to it and are listed in the following order:

Argument	Description
arg1	Number of generations
arg2	Population size
arg3	Bit string length
arg4 (optional)	Randon number generator seed

Alternatively, arg1, arg2 and arg3 can be changed inside the Makefile whereas arg4 can be defined during rule runtime. By default these variables have the following values:

• Number of Generations = 1000
• Population Size = 100
• Bit string length = 16
• Seed = undefined

Linux & OS X:

#Run via Makefile:
make run

#Run with seed:
make run SEED=1738

#Run in debug mode:
make debug

#Run seperately:
./runMe [arg1] [arg2] [arg3] [seed]

Usage Example

Meta

Alexander Gontcharov – [email protected]

https://github.com/AGontcharov/