domingo, fevereiro 02, 2014

Compact Genetic Algorithm Solve The OneMax Problem Using Arduino

This article presents how to solve the OneMax Problem, using a Compact Genetics Algorithms (CGA) executed on Arduino.

The Compact Genetic Algorithms are a evolutionary computing method, that use a probabilist distribution to solve a problem when the solutions are unknown.

More details in Goldberg.

To permit this, some parameters of CGA need to be configured, like the population size, and the maximum number of epochs.

To test that method, the OneMax problem is used to proof the concept.


The demonstration problem is a maximizing binary optimization problem called OneMax that seeks a binary string of unity (all '1' bits).

The objective function only provides an indication of the number of correct bits in a candidate string, not the positions of the correct bits. The algorithm is an implementation of Compact Genetic Algorithm that uses integer values to represent 1 and 0 bits in a binary string representation.

The individual represented here in the chromosome has 32 bits of length.
So the solution is represented by a individual with fitness value equal to 32, denoting the sum of all bits that contain the value 1.

More details in Clever.

To generate the random values used to initialize each chromosome, a LFSR Generator was used.


So that way, was implemented a C code to Arduino based on python code provided by previous link, that can solve the OneMax Problem.

The source code was divided in two pieces, the MyTypes.h file has the chromosome data structure, while the cga.ino file has the CGA source code to solve the OneMax.

The intefarce to control the algorithm is simple, using the serial port:

  • To disable debug mode, just send 'd' char through the serial port. The debug mode print the best individual in each epoch.
  • To run the code, just send 'r' char and wait the result.

The source code can be download HERE !

Bellow you can see a output from code executed.

Welcome do ACGA a Arduino Compact Genetic Algorithm.
Press 'r' to solve OneMax Problem.

Press 'd' to disable Debug Mode.
Running, please wait...

Iteration 0, BitString: 11110111010111101011011011111111 , Best Fitness: 25.00
Iteration 1, BitString: 11110111010111101011011011111111 , Best Fitness: 25.00
Iteration 2, BitString: 11110111010111101011011011111111 , Best Fitness: 25.00
Iteration 3, BitString: 11111111111101111011101011111111 , Best Fitness: 28.00
Iteration 4, BitString: 11111111111101111011101011111111 , Best Fitness: 28.00
Iteration 5, BitString: 11111111111101111011101011111111 , Best Fitness: 28.00
Iteration 6, BitString: 11111111111101111011101011111111 , Best Fitness: 28.00
Iteration 7, BitString: 11111111111111111111111001111101 , Best Fitness: 29.00
Iteration 8, BitString: 11111111111111111111111001111101 , Best Fitness: 29.00
Iteration 9, BitString: 11111111111111111111111001111101 , Best Fitness: 29.00
Iteration 10, BitString: 11111111111111111111111001111101 , Best Fitness: 29.00
Iteration 11, BitString: 11111111111111111111111001111101 , Best Fitness: 29.00
Iteration 12, BitString: 11111111111111111111111001111101 , Best Fitness: 29.00
Iteration 13, BitString: 11111111111111111111111001111101 , Best Fitness: 29.00
Iteration 14, BitString: 11111111111111111111111001111101 , Best Fitness: 29.00
Iteration 15, BitString: 11111111111111111111111001111101 , Best Fitness: 29.00
Iteration 16, BitString: 11111111111111111111111001111101 , Best Fitness: 29.00
Iteration 17, BitString: 11111111111111111111111001111101 , Best Fitness: 29.00
Iteration 18, BitString: 11111111111111111111111001111101 , Best Fitness: 29.00
Iteration 19, BitString: 11111111111111111111111001111101 , Best Fitness: 29.00
Iteration 20, BitString: 11011111111101111111111111111111 , Best Fitness: 30.00
Iteration 21, BitString: 11111111111111111111111111111111 , Best Fitness: 32.00
Done!
Best Solution = BitString: 11111111111111111111111111111111 , Best Fitness: 32.00

Enjoy !