Fitness landscape analysis of a class of np-hard problems

[摘要] A number of fitness landscape properties of randomly generated instances of a class of NP-hard combinatorial optimisation problems are empirically studied in this research. We believe that the studied properties give insight into the structure of the problem landscape and can be representative of the problem difficulty, in particular with respect to local search algorithms. The properties include: types of search position, number of local and global optima and plateaux, quality of optima and plateaux, basin size and its correlation with fitness, time to local optima, cost of finding the global solution, and the quality of optima obtained with a fixed budget search. Our work focuses on studying how these properties vary with different values of problem parameters. We also compare these properties across different landscapes that were induced by different neighbourhood operators or different penalty functions of the following problems: the number partitioning problem, the binary knapsack problem, and the quadratic binary knapsack problem. Unlike existing studies of these problems, we study instances generated at random from various distributions. We found a general trend where in all the three problems, some of their landscape features were found to vary between the different distributions. We captured this variation by a single, easy to calculate, parameter and we showed that it has a potentially useful application in guiding the choice of the neighbourhood operator of local search heuristics.

[发布机构] University:University of Birmingham;Department:School of Computer Science

[关键词] T Technology;TK Electrical engineering. Electronics Nuclear engineering