Genetic Algorithm

Implement the basic genetic algorithm. This project is suitable for students that are comfortable with more research oriented tasks. Genetic algorithms are a very useful meta-heuristic optimization technique because they make no assumptions about the underlying problem. This makes them very versatile. Students choosing this project should propose a problem they would like to optimize and discuss it with the assistant. If the proposed problem is not suitable, the assistant will provide one.\ The algorithm should include the basic steps of evolution:

1: procedure GA
2: pop ← Initialize population of individuals.
3: for iter := 1 to maxIter do
4:      Selection(pop)
5:      Corssover(pop)
6:      Mutation(pop)
7: end for
8: end procedure

Implementation guidelines

1. Running the program:

   • The program can be ran in different modes (sequential, parallel and distributed) by specifying a parameter.

   • User can specify the size of the optimization problem

   • The program measures run-time needed to complete.

2. Implementation details

   • The fitness function must be computed in parallel.

   • The implementation must adapt automatically to the hardware it is being ran on (Physical CPU's, Cores, Memory, etc..);

Testing

Testing is specific to the problem at hand. In general, the tests should measure the time it takes for the implementation to converge to an optimum(probably local optimum). The test should be formulated so that it captures the advantage of using parallel or distributed implementations.