# Feature-Based Diversity Optimization for Problem Instance Classification

arXiv: https://arxiv.org/abs/1510.08568 · HTML: https://mlsanity.com/paper/1510.08568/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Oct 2015.

## Built on by (most cited first, 3 of 3)

- [Rigorous Runtime Analysis of Diversity Optimization with GSEMO on OneMinMax](https://mlsanity.com/paper/2307.07248/) (2023)
- [Runtime Analysis of Evolutionary Diversity Optimization on the Multi-objective (LeadingOnes, TrailingZeros) Problem](https://mlsanity.com/paper/2404.11496/) (2024)
- [Evolving Hard Maximum Cut Instances for Quantum Approximate Optimization Algorithms](https://mlsanity.com/paper/2502.12012/) (2025)

## Abstract (arXiv)

Understanding the behaviour of heuristic search methods is a challenge. This even holds for simple local search methods such as 2-OPT for the Traveling Salesperson problem. In this paper, we present a general framework that is able to construct a diverse set of instances that are hard or easy for a given search heuristic. Such a diverse set is obtained by using an evolutionary algorithm for constructing hard or easy instances that are diverse with respect to different features of the underlying problem. Examining the constructed instance sets, we show that many combinations of two or three features give a good classification of the TSP instances in terms of whether they are hard to be solved by 2-OPT.