A Memetic Algorithm for Reconstructing Cross-Cut Shredded Text Documents

Christian Schauer (Speaker), Matthias Prandtstetter, G. Raidl

Research output: Chapter in Book or Conference ProceedingsConference Proceedings with Oral Presentationpeer-review

Abstract

The reconstruction of destroyed paper documents became of more interest during the last years. On the one hand it (often) occurs that documents are destroyed by mistake while on the other hand this type of application is relevant in the fields of forensics and archeology, e.g., for evidence or restoring ancient documents. Within this paper, we present a new approach for restoring cross-cut shredded text documents, i.e., documents which were mechanically cut into rectangular shreds of (almost) identical shape. For this purpose we present a genetic algorithm that is extended to a memetic algorithm by embedding a (restricted) variable neighborhood search (VNS). Additionally, the memetic algorithm's final solution is further improved by an enhanced version of the VNS. Computational experiments suggest that the newly developed algorithms are not only competitive with the so far best known algorithms for the reconstruction of cross-cut shredded documents but clearly outperform them.
Original languageEnglish
Title of host publicationHybrid Metaheuristics 7th International Workshop, HM 2010, Vienna, Austria, October 1-2, 2010. Proceedings
EditorsMaría J. Blesa, C. Blum, G. Raidl, Andrea Roli, Michael Samples
Pages103-117
Number of pages15
DOIs
Publication statusPublished - 2011
Event7th International Workshop on Hybrid Metaheuristics - HM 2010, Vienna, Austria, October 1-2, 2010. Proceedings -
Duration: 1 Oct 20112 Oct 2011

Conference

Conference7th International Workshop on Hybrid Metaheuristics - HM 2010, Vienna, Austria, October 1-2, 2010. Proceedings
Period1/10/112/10/11

Research Field

  • Former Research Field - Mobility Systems

Fingerprint

Dive into the research topics of 'A Memetic Algorithm for Reconstructing Cross-Cut Shredded Text Documents'. Together they form a unique fingerprint.

Cite this