On the Difficulty of Evolving Permutation Codes
This is an incremental study on permutation codes for applications like powerline communications, with limited practical impact due to scalability issues.
The paper tackled the design of permutation codes using evolutionary algorithms, finding that neither the EA approach nor random search scaled well with increasing problem size.
Combinatorial designs provide an interesting source of optimization problems. Among them, permutation codes are particularly interesting given their applications in powerline communications, flash memories, and block ciphers. This paper addresses the design of permutation codes by evolutionary algorithms (EA) by developing an iterative approach. Starting from a single random permutation, new permutations satisfying the minimum distance constraint are incrementally added to the code by using a permutation-based EA. We investigate our approach against four different fitness functions targeting the minimum distance requirement at different levels of detail and with two different policies concerning code expansion and pruning. We compare the results achieved by our EA approach to those of a simple random search, remarking that neither method scales well with the problem size.