Linear representation of categorical values
This addresses a specific challenge in evolutionary algorithms for combinatorial optimization, but it appears incremental as it builds on existing encoding methods.
The authors tackled the problem of representing categorical values in evolutionary algorithms by proposing a linear binary representation that preserves neighborhood structure, enabling single-mutation reachability. They applied this to Sudoku puzzles, showing promising results in fixed-budget experiments with high-dimensional instances and fixed-target experiments with small-dimensional instances.
We propose a binary representation of categorical values using a linear map. This linear representation preserves the neighborhood structure of categorical values. In the context of evolutionary algorithms, it means that every categorical value can be reached in a single mutation. The linear representation is embedded into standard metaheuristics, applied to the problem of Sudoku puzzles, and compared to the more traditional direct binary encoding. It shows promising results in fixed-budget experiments and empirical cumulative distribution functions with high dimension instances, and also in fixed-target experiments with small dimension instances.