Application Of Mixed Genetic Algorithm On MTSP

mTSP(multiple traveling salesman problem) is a kind of problem encountered usually in practical application such as the mission planning of multi-robots, the schedule of bus routing and so on. However, mTSP is a famous NP-hardness problem (nondeterministic polynomial time hardness problem) from a theoretical point and has not yet had a valid exact solution. Consequently, it becomes a considerable way to study a variety of approximate solutions to mTSP. Genetic algorithm, as a kind of approximate algorithm, is a robust search algorithm for optimization of complicated system and provide it with a general solution framework. The author proposes a new intelligent mixed genetic algorithm with self-adaptability by deep study for mTSP, which provides solution to mTSP with a new idea and method. the new intelligent mixed genetic algorithm has two major character as follow1. The effective use of known heuristic information from problem to guide the direction where genetic algorithm would search. Among the use of heuristic information, the most effective is the prediction of the extent of adjacency between two nodes by theα-nearness of the edge between two nodes, instead of the weight of the edge between two nodes. which largely improves the reliability of adjacency between two nodes and the performance of the algorithm.2. the proposition of idea of hierarchical evaluation during the process of computation of genetic algorithm. Guided by the idea, the process of search of genetic algorithm is determined not only by the fit value from the chromosome, but also by the evaluation value from upper level. the fit value from the chromosome is responsible for the control of search of solution to problem in micro-level, and the evaluation value from upper level does in macro-level. By the double mechanism from both micro-level and macro-level, the better service for search of optimized solution to problem can be available.