Various Island-based Parallel Genetic Algorithms for the 2-Page Drawing Problem

H. He, O. Sýkora, and A. Salagean (UK)


Island-based Parallel genetic algorithms, 2-page book crossing number, Cartesian topologies, Periodical syn chronization, Computation-to-Communication ratio, Population-to-Chromosome ratio.


Genetic algorithms have been applied to solve the 2-page drawing problem successfully, but they work with one global population, so the search time and space are limited. Parallelization provides an attrac tive prospect in improving the efficiency and solution quality of genetic algorithms. One of the most pop ular tools for parallel computing is Message Passing Interface (MPI). In this paper, we present four island models of Parallel Genetic Algorithms with MPI: is land models with linear, grid, random graph topolo gies, and island model with periodical synchronisation. We compare their efficiency and quality of solutions for the 2-page drawing problem on a variety of graphs.

Important Links:

Go Back