Iterated local search and constructive heuristics for error correcting code design

摘要

Error Correcting Codes (ECCs) play an important role, for example, in the transmission of messages over telecommunication networks or in reading information from digital data media such as DVDs or CDs. The design of ECCs is computationally a hard problem. Due to its hardness several metaheuristic approaches for its solution have been proposed in the literature. In this paper we present different algorithms based on solution construction and iterated local search. The experimental evaluation shows that a simple multistart constructive heuristic is often between two and three orders of magnitude faster than current state-of-the-art metaheuristics when applied to rather small problem instances. When bigger problem instances are concerned, the proposed iterated local search algorithm has advantages over both the multistart constructive heuristic and state-of-the-art metaheuristics.