The TriBA Parallel Genetic Algorithm Based On Improved Migration Operator And TSP Application

TSP(Traveling Salesman Problem) is a problem of combination optimization withsimple definition but difficult to be solved, which attracts many researchers in various fieldsincluding mathematics, physics, biology and artificial intelligence. It has become a standardproblem to test a new algorithm of combination optimization. Theoretically speaking, theenumeration not only can solve TSP, but also can get the best answer. But to all computersnowadays, it’s hardly to obtain its best answer in such huge researching space by usingcommon enumeration. Therefore, all kinds of algorithms to solve TSP emerged because ofdemand. At present, there are more evolutionary algorithm have been applied to the TSPproblem, such as simulated annealing algorithm, artificial fish school algorithm, neuralnetwork algorithm, genetic algorithm.In this paper, the main topic is genetic algorithm solving the TSP problem. Through theanalysis of advantages and disadvantages of the parallel genetic algorithm and concludes thatgenetic algorithm and parallel genetic algorithm is an effective algorithm for the TSP problemwith constraint. Aiming at the defect of parallel algorithm model, we put forward a new kindof TriBA(triplet based architecture) topology parallel algorithm model based on the evaluationvalue migration. Based on the TriBA parallel algorithm model, the now algorithm model isimproved from three aspects:Change the topology. Using the new mode of population’s allocation, the TriBA structuremodel can solve the problem of load imbalance in master-salve model. According to thenumber of population, the TriBA structure is scalable and it can make sure the number ofsub-population, solve the hardware resources.Change the model of data migration. The mode of data migration in TriBA structureincluding single mode, center mode, parallel mode, nested mode, which changing traditionalmigrate mode of master-slave model. It helps the best individual spread to everysub-population of TriBA structure.Propose a new migration operator based on the evaluate value. Based on the evaluatevalue, the degree of convergence in sub-population can be reflected. The migration beginswhen the degree of convergence meets set evaluate value. Using the improving migration, the asynchronous migration is achieved and it enhances the efficiency of parallel geneticalgorithm and has a good speed up.Use the TriBA-structure parallel algorithm based on the evaluation value migration tosolving the TSP problem with2020cities through the fitness calculating, crossover,mutation and migration. The TriBA model finds the best individual in TSP problem. Throughthe analysis of the experiment data, we can conclude that, the new algorithm model hasadvantage than the traditional parallel algorithm in evolutionary efficiency and has higherspeed up for same problem.