On the application of parallel genetic algorithms in X-ray crystallography

This paper discusses the design and implementations of a parallel genetic algorithm (PGA) for function optimization. The proposed PGA employs a coarse-grained approach in which a physical processor (a CPU) maintains several semi-isolated subpopulations (in the nodes), each of which operates an independent genetic plan. With this design, the entire population can preserve diversity by allowing each subpopulation to evolve relatively independently. Two types of network topologies are considered, a ring and a fully connected graph, together with several novel genetic operators. Implementations of the PGA were performed on a network of Sun₄ workstations, a network of SGI Indigos, and a Thinking Machine Corporation CM-5. The proposed PGA has been successfully utilized in solving an important problem in X-ray crystallography which can be formulated in terms of a function to be minimized. This function is used as the fitness function for our PGA. Results indicate that the PGA is suitable for solving problem instances of small sizes. However, the cost-effectiveness relationship with other approaches is unclear.