The Research Of Descending Encoding Genetic Algorithm And Its Application In TSP

TSP is used in an extensive practical background, which is the combinational optimization problem with important theoretical value, the obvious feature is the description is very simple, but difficult to get an optimal solution. It is high research value as TSP used in the application of engineering technology extensively.As the great time complexity of TSP, exact algorithms can only solve small-scale TSP, so approximation algorithm is used a lot to solve large-scale TSP, genetic algorithm is a common solution of approximation algorithm for TSP.Because the information is simple and intuitive when choose the character encoding for TSP, the genetic algorithm for characteristics encoding is a common solution nowadays. However as its own characteristics of character encoding, it is not the best effect as it makes illegal chromosome and also calculate with low efficiency. This research gives a new characteristics encoding of genetic algorithm for TSP, compared with other characteristics, it is proved that it doesn't produce illegal chromosomes when crossed, also the experimental results show that it can help you to find a optimal solution much faster, with these two advantages, this new coding method is proved that it is a more suitable solution for TSP.