Theoretical and Empirical Analysis of Lehmer Codes to Search Permutation Spaces with Evolutionary Algorithms
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Efficient Rank Aggregation via Lehmer Codes
We propose a novel rank aggregation method based on converting permutations into their corresponding Lehmer codes or other subdiagonal images. Lehmer codes, also known as inversion vectors, are vector representations of …
Lehmer Transform and its Theoretical Properties
We propose a new class of transforms that we call {\it Lehmer Transform} which is motivated by the {\it Lehmer mean function}. The proposed {\it Lehmer transform} decomposes a function of a sample into their constituting…
EEGElectroencephalogram (EEG)Federated Aggregation of Mallows Rankings: A Comparative Analysis of Borda and Lehmer Coding
Rank aggregation combines multiple ranked lists into a consensus ranking. In fields like biomedical data sharing, rankings may be distributed and require privacy. This motivates the need for federated rank aggregation pr…
Privacy PreservingQuantizationEfficient and Interpretable Neural Networks Using Complex Lehmer Transform
We propose an efficient and interpretable neural network with a novel activation function called the weighted Lehmer transform. This new activation function enables adaptive feature selection and extends to the complex d…
Computational EfficiencyDecision Makingfeature selectionConstrained PSLQ Search for Machin-like Identities Achieving Record-Low Lehmer Measures
Machin-like arctangent relations are classical tools for computing $π$, with efficiency quantified by the Lehmer measure ($λ$). We present a framework for discovering low-measure relations by coupling the PSLQ integer-re…