Evolutionary Approaches to the Generation of Optimal Error Correcting Codes

Error-correcting codes allow for reliable transmission of data over mediums subject to interference. They guarantee detection and recovery from a level of transmission corruption. Larger error-correcting codes increase the maximum sizes of messages transmittable, which improves communication efficiency. However, discovering optimal error-correcting codes for different code specifications is equivalent to the NP-Hard problem of determining maximum cliques of a graph. In this research, three different binary error correcting code problems are considered. Both genetic algorithms and genetic programming are examined for generating optimal error correcting codes for these problems. A new chromosome representation of the GA system is examined, which shows some benefits in certain conditions. The use of GP is novel in this problem domain, and in combination with the Baldwin effect, it is shown to be a promising new approach for code discovery.