10.1016/j.cor.2024.106747">
 

Applying Instance Space Analysis for Metaheuristic Selection to the 0-1 Multidemand Multidimensional Knapsack Problem

Document Type

Article

Publication Date

10-2024

Abstract

The empirical testing of metaheuristic solution methods for optimization applications should consider the effect of the underlying structure of the optimization problem test instances employed. This paper presents a methodology for analyzing the performance of metaheuristics applied to the 0–1 multidemand multidimensional knapsack problem (MDMKP) specifically considering problem structure. This research leverages instance space analysis (ISA) to graphically depict both the multidimensional problem structure and metaheuristic performance. A new instance generation method augments the existing set of test instances; in doing so, it introduces correlation structure into the problem and helps ensure MDMKP instance feasibility. Testing compares four metaheuristics from the literature and trains an interpretable machine learning model to select a metaheuristic for a given instance based on that problem’s meta-features. The results show that the correlation structure meta-features are significant factors affecting metaheuristic performance and that a decision tree model can provide interpretable insights into the algorithm selection problem. This work demonstrates the usefulness of ISA for rigorous empirical testing to enhance understanding the performance of metaheuristics applied to the MDMKP.

Comments

This is a subscription-access article, available to readers with a subscription to Computers and Operations Research, using the DOI link below.

Current AFIT students, faculty, and staff may access the full article by clicking here.

The authors provided a link to supplemental data for this research at http://dx.doi.org/10.17632/jcjvdgp5xg.1

Source Publication

Computers and Operations Research

This document is currently not available here.

Share

COinS