Landscape analyses and global search of knapsack problems

Abstract

Presents statistical analyses of the search-space landscape of knapsack problems in due consideration of stochastic optimization. It is known from existing works that travelling salesman problems have a rugged landscape. We deal with 1000 knapsack problems where the values and the weights of the objects are arranged randomly. By introducing proper estimate values and topology, it is revealed that the landscape of these knapsack problems is a rugged landscape similar to that of the travelling salesman problems. It is assumed that the rugged landscape is a combination of a global valley-like structure and a local noise-like structure. We propose a new algorithm to estimate the optimum point by introducing the least mean square method to fit the global structure at some points selected randomly in the search space. The method does not contradict "no free lunch" theorems because of the availing features of the landscape. It is forecast that not only knapsack problems but also many practical problems have a structure which is characterized with the same measure. These results are useful in order to compose more effective optimization methods without a trial-and-error process.