Migration Policies for Island Genetic Models on Multicomputer Platform

The paper presents a comparative study of five migration policies for parallel genetic algorithm (PGA) solving the traveling salesman problem (TSP). The investigated migration policies utilize one way ("slow") and two way ("fast") circular periodic chromosomes migration and global ("immediate") periodic chromosomes migration. For each migration policy best or random chromosome migration is applied. The proposed parallel computational models for the dynamic migration policies are verified by MPI-based implementation run on a multicomputer platform. The performance evaluation is based on experimental estimation of solution quality and execution time speedup. The solution quality of the five migration policies was estimated over 50 runs of each migration policy. The influence of the parallel machine size over the efficiency of the parallel computation has been investigated by averaging the execution time of 10 runs on different number of processors.