Improvement Of Genetic Algorithm For TSP And Its Parallelization Study

The genetic algorithm is a kind of searching method which simulates the natural evolution. It is simple and easy to implement, especially it doesn't need the special field knowledge, so it has been used in every broad fields. Now the genetic algorithm has got a lot of fruits and more scholars begin to pay attention to it.The genetic algorithm is still a new developing technology. Despite its success in so many domains, its theoretical fundament is relatively weak. There are still lots of problems to be studied and improved.This paper has done some work in the research and application of the genetic algorithm. First, The introduction on GA's theory and its applications on combination optimization are given. An improved hybrid genetic algorithm is then presented for TSP problem. In this algorithm, the unfitness function is chosen as a merit at the beginning of iterative and a new cross operation is designed.In addition, we use a hybrid mutation operation, and make immune operation on individual after mutation operation. The simulation numerical results show that this algorithm is efficient. At last, to overcome GA's large computation consumption, a master/slave parallel hybrid genetic algorithm is implemented based on the GA's parallel characteristic. The experiment results demonstrate that the method is valid and efficitive.