Research On Traveling Salesman Problem Based On Genetic Ant Colony Algorithm

Traveling salesman problem is a classic NP(non-deterministic polynomial) hard problem, and it is a common problem in daily life,such as logistics, tourism, meter reading and so on. Because the time complexity of traveling salesman problem grows rapidly, it is difficult to find the best answer within an acceptable time for accurate algorithms.Therefore heuristic algorithms are usually adopted to solve the traveling salesman problem, and genetic algorithm is one of them.Genetic algorithm is a kind of bionic algorithm. Genetic algorithm s the problem that need to be solved as population, and evaluates the fitness of individuals in the population. Individuals with low fitness are eliminated according artificial direction and individuals with high fitness are retained for gene recombination and mutation. An approximate optimal solution of the problem will be obtained after iterations. Genetic algorithm has been widely used. However, genetic algorithm has some disadvantages such as strong dependence on the initial population, premature, and control difficultly of convergence speed. So original algorithm need to be improved.In order to overcome the defects of genetic algorithm, the genetic ant colony algorithm was proposed. Genetic ant colony algorithm combined the genetic algorithm and ant colony optimization, and thepheromones in ant colony were introduced into genetic algorithm. In the initialization process, genetic ant colony algorithm compared the genes of initial population and eliminated the individuals with high repetition rate. By this way, the distribution of initial population would be homogeneous. Genetic ant colony algorithm included two phases: global search phase and fast convergence phase. The response of ants population to pheromones was different in different phases. In global search phase, genetic ant colony algorithm searched the global space adequately and the ants population was resistant to pheromones. The path that had not been accessed would be selected with a higher probability. In fast convergence phase, ants population were interested in pheromones, they would quickly gather on the paths that had higher pheromone concentration.The water charge system is used as practical application scenario to prove the performance of genetic ant colony algorithm. There is a path optimization problem while meter reader reads the meter, the essence of the problem is traveling salesman problem. Meter reader reads the meter monthly in his responsible area. Genetic ant colony algorithm is used to optimize the meter reading path. By comparing and analyzing the performance of genetic ant colony algorithm, we can prove that this algorithm can improve the efficiency of meter reading work and save the time required for meter reading. Thus we can adjust the number of meter readers, and save manpower and financial resources.