Research And Improvement On Genetic Algorithm For Solving TSP

Genetic algorithm(GA) is an adaptive, global and stochastic optimization search approach which simulates the genetic and evolutionary processes of biologic life in the natural environment accrording to biologic life evolutionary and nature selection mechanism. In recent years, GA has functioned so well with robustness and interoperability, hidden parallelity and adaptability in the settlement of all kinds of optimization problems that it becomes an increasingly widespread application of smart optimizaton algorithms. TSP(Traveling Salesman Problem) is a classical nondeterministic polynomial complete problem in the field of combinatorial optimization, and it is the concentrated generality and simplified form of many complicated problem emerging from all kinds of field. Solving it fleetly and effectively has not only great theoretical function, but also important pragmatic value.This paper chooses GA to solve TSP problem according to the characteristic and research status nowadays of TSP problem. the paper introduces the elements and basic implement technology of GA, and expatiates the specialty of GA and the impact factors of GA performance expressly.the paper puts up some idiographic improvement to standard GA. Firstly, a greedy selection strategy is introduced insteading of random method to generate initial population; then a greedy crossover operator is designed according to the characteristics of individual encoding mechanism for TSP problem combined with greedy algorithm, so as to be effective to retain the good genes in father individual and to generate new indivedual with greater probability; As to the mutation operation, a combination of the two mutation operator is used to enhance the diversity of the population; In addition, an adaptive strategy is proposed to control the GA parameters. The modified GA was tested on various instances in TSPLIB, the experiment results demonstrate the algorithm is valid and effective.On the basis of the improved GA above, the paper proposes a parallel genetic algorithm(PGA) to solve TSP problem based on MPI in cluster of workstation combined with the ideas of master-slave parallel programming. The population are distributed to slave processes according to the city ID number, and the fine individual are exchanged regularly between master and slave processes. The algorithm is implemented by using VC++ and MPICH. The analysis and comparison of multi-group experiment data show that the algorithm has enhanced not only in solving speed but also in solving precision.