Adaptive Parallel Genetic Algorithms

Genetic algorithms are a widely used technique for search and optimization problems and belong to the group of evolutionary algorithms. One of its recent applications has been in image clustering. Serial implementations of the algorithm, customized for image clustering, suffer from slow execution. Also, a genetic algorithm, if run for small number of generations, gets stuck in the local minima, and therefore requires larger number of generations to achieve optimal results. These two factors motivated the parallel implementation of the algorithm. The concurrency in the application was identified and we partitioned it such that the I/O and computation was done in parallel. Both the “Master-Worker” paradigm and the “All-Worker” paradigm were implemented in C and MPI. Distribution of the computation intensive task amongst multiple processors resulted in a linear speedup and a vastly reduced execution time. While the “Master-Worker” model is better suited for the grid environment, the “All-Worker” model performs better on dedicated clusters. We modified the “Master-Worker” implementation further to run successfully and intelligently in Grid Environment where resources are heterogeneous, distributed across disparate locations, and can appear and disappear dynamically. This eventually turned out to be a scheduling problem that can be solved using operation research techniques.