Landscape analyses of search-space in travelling salesman problems

This paper shows statistical analyses of the search-space landscape of travelling salesman problems in due consideration of stochastic optimization. It is known from existing works that travelling salesman problems have landscape called "a rugged landscape" and "big valley structure". This work reveals more detailed structure of the landscape. We deal with the 1000 travelling salesman problems of 6 to 9 cities where the cities are arranged randomly and a travelling salesman problem of 100 cities. It is assumed that the rugged landscape is a combination of the global valleylike structure and the local noiselike structure. Each of them is characterized by the statistical properties of the search-space landscape, that is, the global valleylike structure has linearity with the distance (in this case, the bond distance) from the optimum, and the variance of the local noiselike structure increase monotonously with the distance from the optimum. On the other side correlation of the tours with the costs close upon the optimum cost is low. For this reason to combine the genetic search with the local search is supported. Even if the number of cities and the definition of the intercity cost value are changed, the structure of the landscape has the same feature. Although the number of the cities of the examined travelling salesman problems is not large, obtained results seem to be universal. It is forecasted that not only travelling salesman problems but also many practical problems have the structure which is characterized with the same measure. These results are useful to compose more effective optimization methods without trial and error.