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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Generation of Instances with Estimated Landscape Features for the Two Level p-Median Location Problem

  • Sarah Degaugue,
  • Olivier Gérard,
  • Justin Scouarnec,
  • Corinne Lucet,
  • Sara Tari,
  • Laure Brisoux Devendeville

摘要

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.