Generation of Instances with Estimated Landscape Features for the Two Level p-Median Location Problem
摘要
The Two Level p-Median Location Problem is an NP-hard combinatorial problem. Algorithm Selection Methods have been extensively studied in the literature, to solve such problems. These studies have emphasized the importance of analyzing fitness landscape characteristics. In this paper we focus on ruggedness and neutrality features. First, we propose estimating both features using various machine learning models on reproducible instances. The tests show that models based on Random Forest and Gradient Boosting produce the best results overall with a coefficient of determination \(R^2\) exceeding 0.9 for both features. Then, we introduce a reverse model, FLEM-Rev based on an evolutionary algorithm to generate instances that match one or both of the targeted landscape features. FLEM-Rev either uses the RF predictors or GB predictors to predict features in the evaluation function. Two classes of scenarios are tested. The first class involves features whose values are close to those in the training set, and the second class involves features whose values fall within unexplored zones of the training-test space. The results show that our reverse model performs well in both cases when the features are considered separately.