TY - GEN
T1 - Cost-vs-accuracy of sampling in multi-objective combinatorial exploratory landscape analysis
AU - Cosson, Raphaël
AU - Derbel, Bilel
AU - Liefooghe, Arnaud
AU - Verel, Sébastien
AU - Aguirre, Hernan
AU - Zhang, Qingfu
AU - Tanaka, Kiyoshi
N1 - Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).
PY - 2022/7
Y1 - 2022/7
N2 - The design of effective features enabling the development of automated landscape-aware techniques requires to address a number of inter-dependent issues. In this paper, we are interested in contrasting the amount of budget devoted to the computation of features with respect to: (i) the effectiveness of the features in grasping the characteristics of the landscape, and (ii) the gain in accuracy when solving an unknown problem instance by means of a feature-informed automated algorithm selection approach. We consider multi-objective combinatorial landscapes where, to the best of our knowledge, no in depth investigations have been conducted so far. We study simple cost-adjustable sampling strategies for extracting different state-of-the-art features. Based on extensive experiments, we report a comprehensive analysis on the impact of sampling on landscape feature values, and the subsequent automated algorithm selection task. In particular, we identify different global trends of feature values leading to non-trivial cost-vs-accuracy trade-off(s). Besides, we provide evidence that the sampling strategy can improve the prediction accuracy of automated algorithm selection. Interestingly, this holds independently of whether the sampling cost is taken into account or not in the overall solving budget.
AB - The design of effective features enabling the development of automated landscape-aware techniques requires to address a number of inter-dependent issues. In this paper, we are interested in contrasting the amount of budget devoted to the computation of features with respect to: (i) the effectiveness of the features in grasping the characteristics of the landscape, and (ii) the gain in accuracy when solving an unknown problem instance by means of a feature-informed automated algorithm selection approach. We consider multi-objective combinatorial landscapes where, to the best of our knowledge, no in depth investigations have been conducted so far. We study simple cost-adjustable sampling strategies for extracting different state-of-the-art features. Based on extensive experiments, we report a comprehensive analysis on the impact of sampling on landscape feature values, and the subsequent automated algorithm selection task. In particular, we identify different global trends of feature values leading to non-trivial cost-vs-accuracy trade-off(s). Besides, we provide evidence that the sampling strategy can improve the prediction accuracy of automated algorithm selection. Interestingly, this holds independently of whether the sampling cost is taken into account or not in the overall solving budget.
KW - automated algorithm selection
KW - landscape analysis
KW - Multi-objective optimization
KW - NK-landscapes
UR - http://www.scopus.com/inward/record.url?scp=85135211707&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85135211707&origin=recordpage
U2 - 10.1145/3512290.3528731
DO - 10.1145/3512290.3528731
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 978-1-4503-9237-2
T3 - GECCO - Proceedings of the Genetic and Evolutionary Computation Conference
SP - 493
EP - 501
BT - GECCO' 22
A2 - Fieldsend, Jonathan E.
PB - Association for Computing Machinery
T2 - 2022 Genetic and Evolutionary Computation Conference, GECCO 2022
Y2 - 9 July 2022 through 13 July 2022
ER -