Research And Implementation Of Parallel Genetic Algorithm Based On Multi-Core Computers

Nowadays Genetic Algorithm is still a hot spot in the area of Evolutionary Computation, and resolving the Traveling Salesman Problem is an application using Genetic Algorithm. Traditional Genetic Algorithm is not applicable to large-scale traveling salesman problems anymore, so new algorithms should be raised or the better of the traditional ones should be advanced. Parallelism is a feature of Genetic Algorithm which is implicit, and the appearance of multi-core computers expounds the development space of Parallel Genetic Algorithm based on multi-core platforms.This thesis first compares several kinds of parallel genetic algorithms, and then recommends multithreading technology of multi-core computers to the Improved Genetic Algorithm to introduce the Multithreading Parallel Genetic Algorithm for large-scale traveling salesman problems. This new algorithm uses multithreads to control multi-populations’synchronous evolution. Populations transfer their optimum chromosomes after they all evolved into the migration generation. In this way, the diversity of populations can be amplified and the search efficiency can be increased both in over-all and partial occasions.This thesis uses Microsoft Visual Studio2010as the multi-core parallel programming environment. According to the Parallel Patterns Library of VS2010, the concept’Thread’is substituted by’Task’to implement the multithreading algorithm and the Traveling Salesman Problem-Solving System based on multi-core computers is finally accomplished.Ultimately, the algorithm proposed in this thesis is tested in three ways on a single multi-core computer:lateral comparison test, longitudinal comparison test and load balance performance test. The results demonstrate that this algorithm is effective for large-scale traveling salesman problems. It can figure out superior results better than most of the serial-running genetic algorithms especially when the sum of cities of the problem is about400to1000, and the relative error of accuracy according to TSPLIB is not more than3.14%. Meanwhile, it’s a load balance algorithm since it takes full advantage of each CPU of multi-core computers.