Theoretical and Empirical Analysis of Lehmer Codes to Search Permutation Spaces with Evolutionary Algorithms

AI summary

Overview

Research area: Theory of evolutionary computation (cs.NE) — rigorous runtime analysis of evolutionary algorithms (EAs) plus an empirical study — applied to permutation spaces.

Technical level: Advanced. The paper is built on drift theory, multiplicative and variable drift, and coupon collector processes with non-uniform selection probabilities, and states its results as exact and asymptotic runtime bounds.

Scope: The paper compares Lehmer code (inversion vector) encodings against the classical vector-of-unique-entries encoding of permutations for simple EAs, theoretically on purpose-built benchmark functions and empirically on linear ordering (LOP) and quadratic assignment (QAP) instances.

What This Paper Is About

Permutation problems such as scheduling, routing and assignment are hard because their search space grows factorially, and the standard encoding of a solution as a vector of unique items forces algorithms to respect a mutual-exclusivity constraint through specialized neighborhoods and operators. Lehmer codes, also called inversion vectors, encode a permutation as a vector of integers in which each entry counts how many smaller items appear after that position; they need no constraint handling, are in one-to-one correspondence with permutations, and require no sophisticated algorithm to use. The goal of this paper is to determine, through rigorous runtime analysis and experiments, when this alternative representation makes evolutionary search faster or slower than the classical one.

Key Contributions

1. New benchmark functions in Lehmer code space. The authors define $\mathcal{L}$-OneMax, $\mathcal{L}$-LeadingZeros and FacVal over $L_n$, and pair them with the corresponding classical-space functions INV, PLeadingOnes, NVal and LexVal, showing the pairs are equivalent under the bijection $L: S_n \rightarrow L_n$.
2. Runtime bounds for simple Lehmer-EAs. They analyze RLS and $(1+1)$-EA on the Lehmer code space with two step operators (uniform and $\pm 1$) and two position-selection probability vectors (uniform and proportional), deriving tight or non-asymptotic bounds for each combination.
3. An improvement to an existing analysis. They improve the runtime analysis of Doerr and Pohl (2012) for the related multi-valued search space $[r+1]^n$ by a factor of almost $\Theta(n^2)$, proving Theorem 10: the expected optimization time of $(1+1)$-EA on NVal is $\Theta(n^2 \log n)$, where the previously available bounds were $\mathcal{O}(n^4 \log \log n)$ from above and $\Omega(n^2 \log n)$ from below.
4. Structural links between $L_n$ and $S_n$. They prove that an adjacent swap in permutation space affects two entries of the Lehmer code, swapping them and changing one of them by $\pm 1$ (Lemma 2), and that the sum of Lehmer code entries equals the number of inversions.

Main Findings

• Lehmer codes match or beat the classical representation on most benchmarks. Across the theoretical benchmarks, the Lehmer-EAs achieve expected runtimes of $\mathcal{O}(n^2 \log n)$ or $\mathcal{O}(n^2)$, on par with classical-representation algorithms or better by a factor of $\Theta(\log n)$.
• RLS with uniform mutation strength on $\mathcal{L}$-OneMax or FacVal (Theorem 1). With the uniform probability vector, the expected optimization time is bounded above by $(n-1)^2 \ln n + (n-1)^2$ and below by $(n-1)^2 \ln n - o(n^2 \log n)$.
• Exact bound for $\mathcal{L}$-LeadingZeros under RLS with uniform mutation (Theorem 2). The expected optimization time is exactly $n^3/2 - 2n^2 + nH_n + 3n/2 - H_n$.
• Proportional position probabilities give no asymptotic speed-up (Theorems 3 and 4). For RLS with uniform step and the proportional probability vector, the expected time on $\mathcal{L}$-OneMax or FacVal is $n(n-1)(\ln(n)+\Theta(1))/2$, and on $\mathcal{L}$-LeadingZeros it is $n^3/2 - n^2H_n/2 - n^2/2 + nH_n/2$.
• Unit ($\pm 1$) mutation changes the picture. RLS with the $\pm 1$ step operator takes $\Theta(n^2)$ on $\mathcal{L}$-OneMax or FacVal (Theorem 5) and $2n^4/9 - 7n^3/18 + n^2/9 + n/18$ on $\mathcal{L}$-LeadingZeros (Theorem 6).
• $(1+1)$-EA with uniform mutation strength is asymptotically tight. The lower bound on $\mathcal{L}$-OneMax or FacVal is $\Omega(n^2 \log n)$ (Theorem 7); upper bounds are $e(n-1)^2 \ln n + 2e(n-1)^2 - 2e(n-1)$ on $\mathcal{L}$-OneMax (Theorem 8), $69.2(n-1)^2 \ln n + \mathcal{O}(n^2)$ on FacVal (Theorem 9), and on $\mathcal{L}$-LeadingZeros the exact form $(e-2)(n-1)^3 + (3-3e/2)(n-1)^2 + R_n$ with $R_n > 0$ and $R_n = \mathcal{O}(n \log n)$ (Theorem 11).
• $(1+1)$-EA with unit mutation on $\mathcal{L}$-OneMax and FacVal. Lower bound $(n-1)^2$ (Theorem 12); upper bounds $\mathcal{O}(n^2)$ on $\mathcal{L}$-OneMax (Theorem 13) and $\mathcal{O}(n^2 \log n)$ on FacVal (Theorem 14).
• One benchmark where Lehmer codes lose. On $\mathcal{L}$-LeadingZeros with the $\pm 1$ step operator, the expected optimization time is $\frac{32\sqrt{e}-52}{3}(n-1)^4 + \frac{28-16\sqrt{e}}{3}(n-1)^3 + \frac{13\sqrt{e}-12}{36}(n-1)^2 - \frac{\sqrt{e}}{48}(n-1) - \Theta(1)$ (Theorem 15), worse by a factor of $\Theta(n)$ than the classical approach because of a random-walk behavior; the authors note that uniform mutation remedies this.
• Contrast with prior classical-representation results. Scharnow et al. (2005) bound the $(1+1)$-EA using jump or transposition on INV by $\mathcal{O}(n^2 \log n)$ from above and $\Omega(n^2)$ from below; Baumann et al. (2024) show RLS with adjacent swap on INV is $\Theta(n^2)$; Doerr et al. (2023) show $(1+1)$-EA with transposition on PLeadingOnes is $\Theta(n^3)$ — the same polynomial appearing in Theorem 11, even with matching cubic and quadratic coefficients.
• Experiments on theoretical benchmarks. With $n$ from 50 to 350 and 1000 independent runs per algorithm-instance pair (100 runs for the third graph of Figure 1), at least one Lehmer-* algorithm always outperformed all Perm-* competitors, and Lehmer-Harmonic performed well across all theoretical benchmarks.
• Experiments on LOP and QAP. On the 20 selected real-world instances, Lehmer-Harmonic and Lehmer-Uniform were far more effective than Lehmer-Unit and approached the Perm-* algorithms in success rate and empirical runtime; in the LOP their success rates surpassed Perm-Trans and came very close to Perm-Jump.

Methodology in Plain English

The authors start from the observation that the Lehmer code space is a Cartesian product of domains of decreasing size, $[n] \times [n-1] \times \cdots \times [1]$, which resembles the multi-valued search space $[r]^n$ studied before but with shrinking dimensions. They adapt the standard randomized local search (RLS) and $(1+1)$-EA to this space, letting the algorithms change one coordinate at a time, either to a uniformly random other value in that coordinate's domain or by a single step up or down. Because coordinate domains differ in size, they also test whether choosing coordinates in proportion to domain size helps; it does not asymptotically. They design benchmark functions that mirror classical ones (OneMax, LeadingOnes, BinaryValue) and show via the bijection $L$ that each Lehmer-space function is equivalent to a known permutation-space function (for instance, $\mathcal{L}$-OneMax is equivalent to counting inversions). The main analytical engine is drift theory plus a coupon-collector argument with unequal probabilities, which is needed because the dimensions shrink. For the empirical side, they add a harmonic mutation operator as a middle ground between purely local and fully uniform changes, restrict the comparison to $(1+1)$-EAs since RLS cannot escape local optima, and run six algorithms — Lehmer-Harmonic, Lehmer-Uniform, Lehmer-Unit, Perm-Jump, Perm-Trans and Perm-AdjSwap — on two kinds of test: small instances of size $n=10$ created by subsampling, where exhaustive search gave the true optima and each run had a budget of 1,000,000 evaluations, and the original instances of size 42 to 100 with a budget of $1000n$ evaluations and unknown optima. Each algorithm was run 1000 times per instance, and results were summarized with success rates, an empirical runtime measure (average runtime divided by success rate, following Wang et al. 2022), and relative percentage deviations from the best observed value.

Why This Matters

Impact on research. Before this work, runtime analyses of EAs on permutations almost exclusively used the canonical vector-of-unique-entries representation; Lehmer codes had only been studied empirically (Regnier-Coudert and McCall 2014; Marmion and Regnier-Coudert 2015; Khalil and Abdou 2021; Uher and Kromer 2022). This paper provides the first runtime analysis of a non-canonical permutation representation, ties the behavior of local Lehmer mutations to classical permutation measures such as the inversion count, and sharpens a known bound for a multi-valued search space.

Real-world applications.

• Consensus ranking in computational social choice, modeled by the LOP (Marti and Reinelt 2022).
• Improving natural language translation, also via the LOP (Tromble and Eisner 2009).
• Graph matching tasks modeled by the QAP (Wang et al. 2021).
• Scheduling and transportation problems generally, which the paper cites as core applications of permutation-space metaheuristics.

Industry relevance. Constraint-free encodings remove the need for constraint-handling machinery, which simplifies implementation of metaheuristics for any domain where solutions are orderings or assignments. The paper's open-source implementation at https://github.com/TrendMYX/LehmerEA makes the Lehmer-EA variants directly reusable, and the finding that Lehmer-Harmonic and Lehmer-Uniform come close to the best classical operators on LOP and QAP suggests these encodings are a practical option rather than only a theoretical curiosity.

Future Directions

• The paper's stated future work — analyzing whether further runtime improvements for the Lehmer-EAs are possible with some other operator — is cut off in the provided text, so the remaining planned direction is not reported.
• Extending runtime analysis to other permutation representations beyond Lehmer codes, which the authors identify as an open gap in the literature.
• Investigating why the $\mathcal{L}$-LeadingZeros function suffers random-walk behavior under unit mutation, and to what extent more globally searching operators (uniform mutation, or the empirically strong harmonic operator) can close or reverse that gap in theory.
• Understanding the discrepancy between theory and practice: on the theoretical benchmarks Lehmer-EAs dominate, while on LOP and QAP the classical algorithms appear best in general — the paper reports that Lehmer-EAs with harmonic and uniform mutation are "not far behind" but does not explain the reversal.

Target Audience

This paper is aimed at researchers in the theory of evolutionary computation and randomized search heuristics who work on runtime analysis and permutation problems, as well as metaheuristic practitioners who implement solvers for scheduling, routing, ordering and assignment problems. It is also relevant to readers interested in solution representations more broadly, since it is the first study to run a rigorous runtime analysis on a permutation representation other than the canonical one. The mathematical sections require comfort with asymptotic notation, drift analysis and coupon-collector arguments, so the theoretical core is best suited to advanced readers; the experimental section and the structural lemmas are accessible to a wider audience.

Authors’ abstract

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.