Theoretical and Empirical Analysis of Lehmer Codes to Search Permutation Spaces with Evolutionary Algorithms
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908671626182656 |
|---|---|
| author | Ma, Yuxuan Santucci, Valentino Witt, Carsten |
| author_facet | Ma, Yuxuan Santucci, Valentino Witt, Carsten |
| contents | A suitable choice of the representation of candidate solutions is crucial for the efficiency of evolutionary algorithms and related metaheuristics. We focus on problems in permutation spaces, which are at the core of numerous practical applications of such algorithms, e.g. in scheduling and transportation. Inversion vectors (also called Lehmer codes) are an alternative representation of the permutation space $S_n$ compared to the classical encoding as a vector of $n$ unique entries. In particular, they do not require any constraint handling. Using rigorous mathematical runtime analyses, we compare the efficiency of inversion vector encodings to the classical representation and give theory-guided advice on their choice. Moreover, we link the effect of local changes in the inversion code space to classical measures on permutations like the number of inversions. Finally, through experimental studies on linear ordering and quadratic assignment problems, we demonstrate the practical efficiency of inversion vector encodings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_19089 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Theoretical and Empirical Analysis of Lehmer Codes to Search Permutation Spaces with Evolutionary Algorithms Ma, Yuxuan Santucci, Valentino Witt, Carsten Neural and Evolutionary Computing A suitable choice of the representation of candidate solutions is crucial for the efficiency of evolutionary algorithms and related metaheuristics. We focus on problems in permutation spaces, which are at the core of numerous practical applications of such algorithms, e.g. in scheduling and transportation. Inversion vectors (also called Lehmer codes) are an alternative representation of the permutation space $S_n$ compared to the classical encoding as a vector of $n$ unique entries. In particular, they do not require any constraint handling. Using rigorous mathematical runtime analyses, we compare the efficiency of inversion vector encodings to the classical representation and give theory-guided advice on their choice. Moreover, we link the effect of local changes in the inversion code space to classical measures on permutations like the number of inversions. Finally, through experimental studies on linear ordering and quadratic assignment problems, we demonstrate the practical efficiency of inversion vector encodings. |
| title | Theoretical and Empirical Analysis of Lehmer Codes to Search Permutation Spaces with Evolutionary Algorithms |
| topic | Neural and Evolutionary Computing |
| url | https://arxiv.org/abs/2511.19089 |