Parallelisation of genetic algorithms for the 2-page crossing number problem

Genetic algorithms have been applied to solve the 2-page crossing number problem successfully, but since they work with one global population, the search time and space are limited. Parallelisation provides an attractive prospect to improve the efficiency and solution quality of genetic algorithms. This paper investigates the complexity of parallel genetic algorithms (PGAs) based on two evaluation measures: Computation-time to Communication-time and Population-size to Chromosomesize. Moreover, the paper unifies the framework of PGA models with the function PGA (subpopulation size; cluster size, migration period; topology), and explores the performance of PGAs for the 2-page crossing number problem.