Genetic algorithms for optimization problems with symmetries

Genetic algorithms are a class of optimization algorithms inspired by the process of natural evolution: They have a population of candidate solutions that evolve as a population over time. That is, an individual is encoded by some sort of genetic code, fit parent individuals are selected from one generation and (genetic representations of) offspring are formed by applying genetic operators such as mutation and crossover.

Optimization problems with symmetries

Many optimization problems in practice possess strong symmetries in the solution space. Consider for instance the Traveling Salesperson Problem (TSP): The problem is to find the shortest tour that visits a set of cities exactly once and returns to the starting city. Take one solution and cyclically shift it and or reverse it. While this is technically a different solution individual, with a different genetic code, it is concerning TSP in essence the very same solution.

The harmful ignorance of symmetries

This research actually started with a student project on AI being applied to solve the commissioning optimization problem for a high-bay storage, which is quite literally the TSP problem. The students found the mlrose Python library providing a couple of metaheuristics including genetic algorithms and hill climbing. However, when they evaluated the library, it turned out to underperform unreasonably on the TSP implementation of mlrose.

The simple reason for this is that when the aforementioned symmetries are ignored then the genetic crossover of two quite fit individuals can quite likely produce a very unfit offspring.

Harmful ignorance of symmetries

Just think of the optimal solution $\pi$ as one parent, and its reversed version $\pi^*$ as the other parent. In the picture above we see the offspring $\pi \times \pi^*$ using the one-point crossover operator $\times$, which is much worse. That is, ignoring these symmetries is not just about missing out on some performance, it can undermine the whole optimization process.

The algebraic approach

In [UWH23] we presented a technique that would turn any crossover operator into a symmetry-aware crossover operator for the TSP problem by factoring out the equivalence relation $\equiv$ on space $\Pi$ of individuals. Given two individuals $x, y \in \Pi$, we say that $x \equiv y$ if and only if they represent equivalent solutions to the TSP problem, i.e., $\equiv$ shall capture the symmetries inherent to TSP. Consider two sets of parents $\pi_1, \pi_2$ and $\pi'_1, \pi'_2$ and a crossover operator $\times$ over the set $\Pi$ of individuals and for each parent consider the offsprings $\pi_1 \times \pi_2$ and $\pi'_1 \times \pi'_2$. Then $\times$ is ignorant or invariant or unaffected by $\equiv$ if for $\pi_1 \equiv \pi'_1$ and $\pi_2 \equiv \pi'_2$, we also have that $\pi_1 \times \pi_2 \equiv \pi'_1 \times \pi'_2$. This way, $\times$ actually acts on the quotient space $\Pi / \equiv$ of equivalence classes of individuals, which is much smaller than $\Pi$ and hence much more efficient and much more effective to search.

In [UWH23] we gave a technique that turns a crossover operator $\times$ on $\Pi$ into a crossover operator $\overline{\times}$ on the quotient space $\Pi / \equiv$ and demonstrate how this technique applied to the simple one-point crossover operator improves upon the tailored state-of-the-art BOX operator for TSP.

In a first version [LWUH23] we gave a preliminary version of this technique only considering reversals instead of the full symmetry equivalence relation $\times$ of individuals and we also gave some minor improvements of the hill climbing algorithm in mlrose for TSP.