Dynamic Tsp Genetic Algorithm

Traveling salesman problem (TSP) is a classical combinatorial optimization problem. In the traditional TSP, the city's size and the distance between cities are fixed, but in practice, the scale of the problem is changed constantly and dynamically, that is the dynamic TSP problem. In order to provide the right decision, the algorithm must return a satisfactory solution in short time based on real-time information. In addition, real-time information collection and development of network technology provides the possibility for solving DTSP problem. Researching on these issues, not only provides a theoretical reference for all types of dynamic combinatorial optimization problems, but also is most widely used in practice.As a self-adapted global optimization search algorithm, Genetic algorithm is simple, easy to use, and intelligent; it also has good robustness and concurrency. It has been successfully applied to solve combinatorial optimization problems. In this thesis, we use genetic algorithm to solve DTSP, its chief work and creative ideas are listed as follow.1)On the basis of the analysis of the problems of the TSP, a mathematical model is builded. According to the deduction and extraction from many related references, this thesis gives the dynamic TSP, presents three models of the problem from different aspects of dynamic performance, and then proposes a unified model of dynamic TSP problem that can adapt to any situations.2)For the static TSP, this thesis presents a diploid encoding scheme, sets neighbor relations and accesses to sequence in one, makes the individual evaluation of varieties of performance. The method increases population diversity with speeding up the convergence rate of population, so that Genetic algorithm has practical value;3)The paper presents the "2-8" population control strategy, it controls population with a small number individuals, and controls the whole population; The paper presents a competitive strategy and judge individual operators, these operators increase the convergence rate of population , and enhance the calculation speed with maintaining the diversity of the population of double effect.4)This paper proposes a two-stage reverse mapping genetic algorithm. The algorithm includes two stages. In the first phase, algorithm uses inversion method and the individual cross-competition strategy, it can get optimal solutions of sub-string or even the optimal solution. In the second phase of mapping algorithm, the mapping of the populations of individual turn to construct the optimal solution, Experiments show that the genetic algorithm method has improved a lot.5)Papers designs the embedded genetic algorithm for the dynamic TSP problem , the algorithm includes two cycles, one is used to adapt to changes in the environment primarily, the other is embedded in the current environment of genetic algorithm process. One can discrete dynamic TSP problem into a static problem according to acceptable condition, and the other is a two-stage reverse mapping genetic algorithm. Experiments show that the algorithm has a good effect in the dynamic TSP.In the conclusion section, the chief work and the creative ideas are summarized, the defects in the research are analyzed and we look forward the research orientation in the future.