Improving Performance of Algorithm Selection Pipelines on Large Instance Sets via Dynamic Reallocation of Budget
提出一种算法选择管线，通过识别简单实例、中止停滞运行并智能再分配节省的预算，显著提升大规模实例集上的求解性能。
Special Issue PPSN 2024: Algorithm-selection (AS) methods are essential in order to obtain the best performance from a portfolio of solvers. When considering large sets of instances that either arrive in a stream or in a single batch, there is significant potential to save the function evaluation budget on some instances and reallocate it to others, thereby improving overall performance. We propose an AS pipeline which (1) identifies easy instances which are solved using the single best solver, avoiding the need to run a selector; (2) curtails runs on both easy and hard instances if they become stalled in the search space and/or are predicted to remain in a stalled state thereby saving budget; (3) reallocates budget saved from both previous steps to downstream instances, using an intelligent strategy to predict which instances will benefit most from extra function evaluations. Experiments using the BBOB dataset in two settings (batch and streaming) show that augmenting an AS pipeline with strategies to save and reallocate budget obtains significantly better results in both settings compared to a standard pipeline.