Iterated local search and constructive heuristics for error correcting code design. (26th April 2007)

• Record Type: Journal Article
• Authors: Blum, Christian
• Is Part Of: International journal of innovative computing and applications. Volume 1:Number 1(2007)
• Page Start: 14
• Page End: 22
• Publication Date: 2007-04-26
• Subjects: iterated local search -- constructive heuristics -- error correcting codes -- code design -- ECCs -- nonlinear binary block codes -- metaheuristics; Evolutionary computation -- Periodicals; Neural networks (Computer science) -- Periodicals; Genetic programming (Computer science) -- Periodicals; Biologically-inspired computing -- Periodicals; Swarm intelligence -- Periodicals; Quantum computers -- Periodicals; 006.3
• Languages: English
• ISSNs: 1751-648X

Abstract

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.