Parallelization of an Evolutionary Algorithm on a Platform with Multi-core Processors

This paper proposes methods of parallel evolutionary algorithms using multi-thread programming on a platform with multi-core processors. For this study, we revise the previously proposed edge histogram sampling algorithm (EHBSA) which we call the enhanced EHBSA (eEHBSA). The parallelization models are designed using eEHBSA to increase the execution speed of the algorithm. We propose two types of parallel models; a synchronous multi-thread model (SMTM), and an asynchronous multi-thread model (AMTM). Experiments are performed using TSP. The results showed that both parallel methods increased the speed of the computation times nearly proportional to the number of cores for all test problems. The AMTM produced especially good run time results for small TSP instances without local search. A consideration on parallel evolutionary algorithms with many-core GPUs was also given for future work.