Zorizko instantzia uniformeak sortzen al dira optimizazio konbinatorioan?

Josu Ceberio, Borja Calvo, Alexander Mendiburu, José A. LozanoEKAIA 2018 · DOI

Abstract

Konputazio ebolutiboan, algoritmoek optimizazio-problemen gainean duten errendimendua ebaluatzeko, ohikoa izaten da problema horien hainbat instantzia erabiltzea. Batzuetan, problema errealen instantziak eskuragarri daude, eta beraz, esperimentaziorako instantzien multzoa hortik osatzen da. Tamalez, orokorrean, ez da hori gertatzen: instantziak eskuratzeko zailtasunak direla tarteko, ikerlariek instantzia artifizialak sortu behar izaten dituzte. Lan honetan, instantzia artifizialak uniformeki zoriz sortzearen inguruko aspektu batzuk izango ditugu aztergai. Zehazki, bibliografian horrenbestetan onetsi den ideia bati erreparatuko diogu: Instantzien parametroen espazioan zein helburu-funtzioen espazioan uniformeki zoriz lagintzea baliokideak dira. Exekutatu ditugun esperimentuen arabera, baliokidetasuna kasu batzuetan ez dela betetzen frogatuko dugu, eta beraz, sortzen diren instantziek espero diren ezaugarriak ez dituztela erakutsiko dugu.

Introduction

In the field of combinatorial optimization, evaluating the performance of evolutionary algorithms requires robust test-beds. When real-world data is unavailable, researchers typically generate synthetic instances by sampling problem parameters—such as costs, distances, or processing times—uniformly at random. The prevailing assumption is that uniform parameter sampling yields an unbiased, representative sample of the problem space.

This paper challenges that assumption. The authors demonstrate that for "ranking-based" algorithms—those that rely on the relative order of solutions rather than absolute values—uniform parameter sampling leads to significant structural bias, over-representing easy instances while ignoring complex ones.

Methods and Problem Instances

The study focuses on three classic combinatorial problems: the Linear Ordering Problem (LOP), the Quadratic Assignment Problem (QAP), and the Permutation Flowshop Scheduling Problem (PFSP). For these problems, an instance is defined by a set of parameters, often represented as a matrix.

A typical 5x5 weight matrix used to define an instance of the Linear Ordering Problem (LOP).

The researchers generated 100,000 random instances for each problem at a small scale ($n=3$). This small size allowed for an exhaustive analysis of the "ranking space"—the set of all possible permutations of solutions ordered by quality. By mapping each parameter-defined instance to its corresponding ranking, the authors could measure how frequently each unique ranking appeared.

The Myth of Uniformity

The core finding is a "volume mismatch" between parameter space and ranking space. A specific ranking is defined by a system of linear inequalities between parameters. In the parameter space, some rankings occupy large volumes while others occupy negligible slivers. Consequently, uniform sampling of parameters is mathematically guaranteed to over-represent certain problem structures.

For example, in the LOP, out of 720 theoretically possible rankings, only 48 actually appeared across 100,000 samples due to inherent problem symmetries.

Key Results: Frequency and Difficulty

The distribution of rankings was found to be highly non-uniform across all tested problems. In the LOP, the authors categorized rankings into four groups based on their frequency of occurrence: XL (Extra Large), L (Large), M (Medium), and S (Small).

Frequency distribution of unique rankings for LOP instances. The sharp peaks represent "XL" rankings that appear much more frequently than others.

Crucially, there is a strong correlation between an instance's frequency and its difficulty. The most common rankings (XL and L) were often trivial, typically containing only a single local optimum (the global one). In contrast, the rarest rankings (S-type) were the most complex, featuring multiple local optima. This suggests that standard random benchmarks are biased toward "easy" instances, potentially leading to over-optimistic evaluations of algorithm performance.

Conclusion

The standard practice of uniform parameter sampling does not produce a uniform distribution of problem instances for ranking-based algorithms. This bias favors simpler search landscapes and ignores more challenging ones. Future benchmarking efforts should aim for "ranking-uniform" generation procedures to ensure that algorithms are tested against a truly representative and diverse set of challenges.

Reference: Ceberio, J., Calvo, B., Mendiburu, A., & Lozano, J. A. (2018). Zorizko instantzia uniformeak sortzen al dira optimizazio konbinatorioan? EKAIA, 34, 261-277.

Summary updated

Abstract

Konputazio ebolutiboan, algoritmoek optimizazio-problemen gainean duten errendimendua ebaluatzeko, ohikoa izaten da problema horien hainbat instantzia erabiltzea. Batzuetan, problema errealen instantziak eskuragarri daude, eta beraz, esperimentaziorako instantzien multzoa hortik osatzen da. Tamalez, orokorrean, ez da hori gertatzen: instantziak eskuratzeko zailtasunak direla tarteko, ikerlariek instantzia artifizialak sortu behar izaten dituzte. Lan honetan, instantzia artifizialak uniformeki zoriz sortzearen inguruko aspektu batzuk izango ditugu aztergai. Zehazki, bibliografian horrenbestetan onetsi den ideia bati erreparatuko diogu: Instantzien parametroen espazioan zein helburu-funtzioen espazioan uniformeki zoriz lagintzea baliokideak dira. Exekutatu ditugun esperimentuen arabera, baliokidetasuna kasu batzuetan ez dela betetzen frogatuko dugu, eta beraz, sortzen diren instantziek espero diren ezaugarriak ez dituztela erakutsiko dugu.
BibTeX
@inproceedings{ceberio2018zorizko,
  author = {Josu Ceberio and Borja Calvo and Alexander Mendiburu and José A. Lozano},
  title = {{Zorizko instantzia uniformeak sortzen al dira optimizazio konbinatorioan?}},
  booktitle = {EKAIA},
  year = {2018},
  doi = {10.1387/ekaia.18877},
}
Figure