[Back]

C. Schauer, M. Prandtstetter, G. Raidl:
"A memetic algorithm for reconstructing cross-cut shredded text documents";
Talk: International Workshop on Hybrid Metaheuristics (HM), Wien; 2010-10-01 - 2010-10-02; in: "Proceedings of Hybrid Metaheuristics - Seventh International Workshop, HM 2010", (2010), 103 - 117.

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 elds 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 nal
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.

http://publik.tuwien.ac.at/files/PubDat_189098.pdf