Co-operation in the Parallel Memetic Algorithm

Evolutionary algorithms (EAs) have been attracting research attention for last decades. They were shown to be very efficient in solving various complex optimization problems in most fields of science and engineering. In EAs, the population of solutions evolves in time to explore the search space. Parallel EAs became an important stream of development due to a wide availability of parallel computer architectures. Thus, designing parallel algorithms utilizing hundreds of CPU cores efficiently is critical nowadays. In this paper, we investigate the impact of selecting a co-operation scheme for the parallel memetic algorithm (PMA-VRPTW) to solve the NP-hard vehicle routing problem with time windows. In the island-model PMA-VRPTW, which is a hybrid of a genetic algorithm applied to explore the search space, and some refinement methods to exploit solutions already found, a number of populations are evolved in parallel. Processes then co-operate and exchange solutions according to the co-operation scheme (migration policy, interval, and topology). Extensive experimental study (which comprised more than 1,584,000 CPU hours on an SMP cluster) performed on 1000-customer Gehring and Homberger’s (GH) benchmark tests gave a detailed insight into the PMA-VRPTW performance and search capabilities. We report 19 (32 % of all 1000-customer GH tests) new world’s best solutions obtained using the best co-operation schemes. Finally, we give clear and consistent guidelines on how to select a proper co-operation scheme in PMA-VRPTW based on the test characteristics.