This paper empirically studies basic properties of the fitness landscape of random instances of number partitioning problem, with a focus on how these properties change with the phase transition. The properties include number of local and global optima, number of plateaus, basin size and its correlation with fitness. The only two properties that were found to change when the problem crosses the phase transition are the number of global optima and the number of plateaus, the rest of the properties remained oblivious to the phase transition. This paper, also, studies the effect of different distributions of the weights and different neighbourhood operators on the problem landscape.
Phase Transition and Landscape Properties of the Number Partitioning Problem
Publication Online URL
Evolutionary Computation in Combinatorial Optimisation