Coarse-grain parallel genetic algorithms: categorization and new approach

This paper describes a number of different coarse-grain GA´s, including various migration strategies and connectivity schemes to address the premature convergence problem. These approaches are evaluated on a graph partitioning problem. Our experiments showed, first, that the sequential GA´s used are not as effective as parallel GA´s for this graph partition problem. Second, for coarse-grain GA´s, the results indicate that using a large number of nodes and exchanging individuals asynchronously among them is very effective. Third, GA´s that exchange solutions based on population similarity instead of a fixed connection topology get better results without any degradation in speed. Finally, we propose a new coarse-grained GA architecture, the Injection Island GA (iiGA). The preliminary results of iiGA´s show them to be a promising new approach to coarse-grain GA´s