Scatter Search and Memetic Approaches to the Error Correcting Code Problem

C. Cotta

Evolutionary Computation in Combinatorial Optimization, J. Gottlieb, G. Raidl (eds.), Lecture Notes in Computer Science 3004, pp. 51-60, Springer-Verlag Berlin, 2004 (EvoCOP'04 best paper award)

© Springer-Verlag Berlin Heidelberg 2004. All rights reserved.


We consider the problem of designing error correcting codes (ECC), a hard combinatorial optimization problem of relevance in the field of telecommunications. This problem is tackled here with two related techniques, scatter search and memetic algorithms. The instantiation of these techniques for ECC design will be discussed. Specifically, the design of the local improvement strategy and the combination method will be treated. The empirical evaluation will show that these techniques can dramatically outperform previous approaches to this problem. Among other aspects, the influence of the update method, or the use of path relinking is also analyzed on increasingly large problem instances.

Download BibTEX entry
Download PDF version (144K)
[Back to publications page].