Marrero Alejandro, Segredo Eduardo, León Coromoto, Hart Emma
Departamento de Ingeniería Informática y de Sistemas, Universidad de La Laguna, San Cristóbal de La Laguna, Spain
School of Computing, Engineering and the Built Environment, Edinburgh Napier University, Edinburgh, United Kingdom
Evol Comput. 2025 Mar 15;33(1):55-90. doi: 10.1162/evco_a_00350.
Gathering sufficient instance data to either train algorithm-selection models or understand algorithm footprints within an instance space can be challenging. We propose an approach to generating synthetic instances that are tailored to perform well with respect to a target algorithm belonging to a predefined portfolio but are also diverse with respect to their features. Our approach uses a novelty search algorithm with a linearly weighted fitness function that balances novelty and performance to generate a large set of diverse and discriminatory instances in a single run of the algorithm. We consider two definitions of novelty: (1) with respect to discriminatory performance within a portfolio of solvers; (2) with respect to the features of the evolved instances. We evaluate the proposed method with respect to its ability to generate diverse and discriminatory instances in two domains (knapsack and bin-packing), comparing to another well-known quality diversity method, Multi-dimensional Archive of Phenotypic Elites (MAP-Elites) and an evolutionary algorithm that only evolves for discriminatory behaviour. The results demonstrate that the novelty search method outperforms its competitors in terms of coverage of the space and its ability to generate instances that are diverse regarding the relative size of the "performance gap" between the target solver and the remaining solvers in the portfolio. Moreover, for the Knapsack domain, we also show that we are able to generate novel instances in regions of an instance space not covered by existing benchmarks using a portfolio of state-of-the-art solvers. Finally, we demonstrate that the method is robust to different portfolios of solvers (stochastic approaches, deterministic heuristics, and state-of-the-art methods), thereby providing further evidence of its generality.
收集足够的实例数据来训练算法选择模型或理解实例空间中的算法足迹可能具有挑战性。我们提出了一种生成合成实例的方法，这些实例针对属于预定义组合的目标算法表现良好，但在特征方面也具有多样性。我们的方法使用一种带有线性加权适应度函数的新奇搜索算法，该函数平衡新奇性和性能，以便在算法的单次运行中生成大量多样且有区分性的实例。我们考虑两种新奇性的定义：(1) 相对于求解器组合中的区分性能；(2) 相对于进化实例的特征。我们在背包和装箱这两个领域评估所提出方法生成多样且有区分性实例的能力，将其与另一种著名的质量多样性方法——多维表型精英存档 (MAP-Elites) 以及仅为区分行为而进化的进化算法进行比较。结果表明，新奇搜索方法在空间覆盖范围以及生成关于目标求解器与组合中其余求解器之间“性能差距”相对大小具有多样性的实例的能力方面优于其竞争对手。此外，对于背包领域，我们还表明，使用一组最先进的求解器，我们能够在现有基准未覆盖的实例空间区域生成新颖的实例。最后，我们证明该方法对不同的求解器组合（随机方法、确定性启发式方法和最先进方法）具有鲁棒性，从而进一步证明了其通用性。
