The $(1+(λ,λ))$ Genetic Algorithm for Permutations
This work addresses a gap in evolutionary algorithm theory for permutation problems, though it is incremental as it extends an existing algorithm to a new domain.
The researchers tackled the problem of adapting the $(1+(\\lambda,\\lambda))$ genetic algorithm from pseudo-Boolean to permutation-based problems, achieving a runtime of $O(n^2)$ fitness queries on the Ham problem, compared to $\\Theta(n^2 \\log n)$ for mutation-based algorithms.
The $(1+(λ,λ))$ genetic algorithm is a bright example of an evolutionary algorithm which was developed based on the insights from theoretical findings. This algorithm uses crossover, and it was shown to asymptotically outperform all mutation-based evolutionary algorithms even on simple problems like OneMax. Subsequently it was studied on a number of other problems, but all of these were pseudo-Boolean. We aim at improving this situation by proposing an adaptation of the $(1+(λ,λ))$ genetic algorithm to permutation-based problems. Such an adaptation is required, because permutations are noticeably different from bit strings in some key aspects, such as the number of possible mutations and their mutual dependence. We also present the first runtime analysis of this algorithm on a permutation-based problem called Ham whose properties resemble those of OneMax. On this problem, where the simple mutation-based algorithms have the running time of $Θ(n^2 \log n)$ for problem size $n$, the $(1+(λ,λ))$ genetic algorithm finds the optimum in $O(n^2)$ fitness queries. We augment this analysis with experiments, which show that this algorithm is also fast in practice.