[Zurück]

M. Prandtstetter, G. Raidl:
"Meta-heuristics for reconstructing cross cut shredded text documents";
Vortrag: GECCO: Genetic and Evolutionary Computation Conference, Montreal, Kanada; 08.07.2009 - 12.07.2009; in: "Proceedings of the 11th annual conference on Genetic and evolutionary computation", (2009), 8 S.

In this work, we present two new approaches based on variable
neighborhood search (VNS) and ant colony optimization
(ACO) for the reconstruction of cross cut shredded text
documents. For quickly obtaining initial solutions, we consider
four di erent construction heuristics. While one of
them is based on the well known algorithm of Prim, another
one tries to match shreds according to the similarity of their
borders. Two further construction heuristics rely on the fact
that in most cases the left and right edges of paper documents
are blank, i.e. no text is written on them. Randomized
variants of these construction heuristics are applied within
the ACO. Experimental tests reveal that regarding the solution
quality the proposed ACO variants perform better
than the VNS approaches in most cases, while the running
times needed are shorter for VNS. The high potential of
these approaches for reconstructing cross cut shredded text
documents is underlined by the obtained results.

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