论文标题
使用质量多样性探索TSP实例的特征空间
Exploring the Feature Space of TSP Instances Using Quality Diversity
论文作者
论文摘要
生成不同属性的实例是算法选择方法的关键，这些方法可以区分给定组合优化问题的不同求解器的性能。近年来已经引入了使用进化计算技术的广泛方法。在本文中，我们通过提供基于质量多样性（QD）的新方法来为这一研究领域做出了贡献，该方法能够探索整个功能空间。 QD算法允许在给定特征空间中创建高质量的解决方案，通过将其分成框并提高每个框中的解决方案质量。我们使用QD方法来生成TSP实例，以可视化和分析区分各种TSP求解器的各种实例，并将其与$（μ+1）$ -EA生成的实例进行比较，以生成TSP实例生成。
Generating instances of different properties is key to algorithm selection methods that differentiate between the performance of different solvers for a given combinatorial optimization problem. A wide range of methods using evolutionary computation techniques has been introduced in recent years. With this paper, we contribute to this area of research by providing a new approach based on quality diversity (QD) that is able to explore the whole feature space. QD algorithms allow to create solutions of high quality within a given feature space by splitting it up into boxes and improving solution quality within each box. We use our QD approach for the generation of TSP instances to visualize and analyze the variety of instances differentiating various TSP solvers and compare it to instances generated by a $(μ+1)$-EA for TSP instance generation.
