Parallel Cuckoo Search Algorithm on OpenMP for Traveling Salesman Problem

Algorithmic parallelism arises naturally for population-based evolutionary algorithms. In this paper, a subpopulation-based parallel Cuckoo Search (CS) algorithm on OpenMP (Open Multi-Processing) for Traveling Salesman Problem (TSP) is proposed. The obligate brood parasitism behavior and mapping of the CS to TSP are explored to design the parallelization approach on OpenMP's fork-join model. The proposed parallel algorithm has been tested with symmetric instances from TSPLIB. Results show the subpopulation-based CS via random walk achieved superlinear speedup up to 42x and 1054% efficiency on OpenMP running 4 cores processor with superior percentage deviation against TSPLIB optimal solutions on small cities ranging from 51 to 101 cities, and only started to deviate significantly with 4461 cities. OpenMP subpopulation-based CS speedup also recorded at least 17x and up to 36x higher than related works in parallel CS. Overall results demonstrate that multi-threaded parallelism is very effective to achieve speedup for population-based evolutionary algorithms by dividing the main population into subpopulations to increase diversity on solution exploration.