Research And Application Of Genetic Algorithm In Traveling Salesman Problem And Optimization Of Network

The evolutionary of nature is a cycle process. In this process,the biotic population continuously develop and improve themselves, It is obviously that the evolutionary process is alike an optimization process. we can directly learn it in compute science. People simulate the biological evolution and inheritance system, then they give a new optimization algorithm--GA (genetic algorithm). Because of the common adaptation and the robustness, GA is extensively used in many aspects of engineering. For example in the route planning of robot and the design of road. So the research of the GA is meaningful.Because the TSP problem (Traveling Salesman Problem) is often used to test the performance of algorithm and it has some degree likeness of many network route optimization questions, the application of GA in TSP can give some guides to solve the net route optimization question.With the use of SPC exchange,NO.7 signal network has become a supporting network of telephone network, so the planning of NO.7 network become more important than past. In this problem, The division of A/B plane is a NPC problem for a traditional algorithm, it have some degree likeness with other figure division questions, but it also have some unique characteristics.The major work of this paper can be summarized as follows:1. This paper establishes the model of TSP problem. Based on the traditional genetic algorithm and greedy genetic algorithm, the method of solving TSP problem based on two algorithms are introduced. Then, this paper get the simulation figures of two examples of TSPLIB.2. In order to overcome the difficulty of slow convergence of GA, This paper give a new mutation operator to solve this problem. The operator purposefully enlarge the searching space and make the best value of population converge to the best value of function. The simulation shows the improve algorithm can make the algorithm performance become better.3. To compare the performances of three algorithms, it points out the difference of three alogirithms in searching the best value respect and explains the cause of the change of the algorithm performance.4.This paper establishes A/B devision model, devised the traditional genetic algorithm and improving algorithm to simulate the problem. It also compare the performance difference of two algorithms. Lastly,the paper also simulated the relation of cost time and net-scale.