Schauer, C. (2010). Reconstructing cross-cut shredded documents by means of evolutionary algorithms [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-36198
Der Fokus dieser Masterarbeit liegt auf der Rekonstruktion von zerstörten Textdokumenten, die durch den maschinellen Einsatz von sogenannten Cross-Cut Schreddern vernichtet wurden.<br />Diese Geräte schneiden das Papier in regelmäßige, gleichgroße - bevorzugterweise rechteckige - Teile, was dazu führt, dass diese Schnipsel anhand ihrer Form nicht mehr unterscheidbar sind.<br />Das Bestreben dieser Masterarbeit ist nun maschinell durch Cross-Cut Schredder vernichtete Dokumente originalgetreu wiederherzustellen.<br />Hierfür wurde ein Genetischer Algorithmus (GA) entwickelt, implementiert und getestet um sich dieser Herausforderung zu stellen.<br />Zu allererst wird aber eine formale Definition dieses Problems gegeben und auf verwandte Themen verwiesen.<br />Während nämlich für die Papierrekonstruktion an sich ein paar wenige Ansätze bereits publiziert wurden, ist das Gebiet rund um den Cross-Cut Schredder noch kaum erschlossen.<br />Weiters wird eine Einführung in das Funktionsprinzip von GAs und darüber hinaus in die anderen Gebiete der Evolutionären Algorithmen gegeben.<br />Das behandelte Problem bezieht sich, im geometrischen Sinne, auf einen zweidimensional Raum.<br />Da die ausgereiften GA Operatoren aber auf eindimensionalen Lösungsrepräsentationen arbeiten, mussten für diese Masterarbeit bewährte Operatoren adaptiert und neue entworfen werden.<br />Um den GA noch weiter zu verbessern wurde eine lokale Suche mittels variabler Nachbarschaftssuche (VNS) eingebunden.<br />Schlussendlich werden die Testergebnisse von neunzig Instanzen basierend auf zehn Dokumenten präsentiert, wobei diese Resultate zur Evaluation der erstellten Operatoren dienen.<br />Einer dieser Ansätze war nachweisbar im Stande die bisherigen Methoden aufbauend auf Ameisenkolonie Optimierung und alleiniger VNS zu schlagen.<br />
de
This master thesis focuses on the reconstruction of destroyed text documents, which were mechanically destructed with the help of so-called cross-cut shredders.<br />These machines cut a piece of paper into equally sized, usually rectangular, slices, which leads to the fact that these shreds are indistinguishable on the basis of their shape.<br />The ambition of this master thesis is to automatically reconstruct cross-cut shredded text documents true to original.<br />To fulfil this aim a genetic algorithm (GA) has been developed, implemented and tested.<br />At the beginning a formal definition of this problem and references to related work will be given.<br />While there are some approaches published dealing with the reconstruction of destroyed paper in general, there is barely work done in the field of cross-cut shredding.<br />An introduction to the working principle of GAs as well as other mainstreams of evolutionary computation will be given.<br />The considered problem obviously also has two-dimensional geometric aspects.<br />Due to the fact that the most popular GA operators were designed to work on one-dimensional solution representations, some proved operators were adapted and others newly created to match the needs of this master thesis.<br />To further improve the GA a local search phase based on variable neighbourhood search (VNS) is embedded.<br />Finally computational results for ninety instances based on ten different documents are presented, which were used for evaluating the designed operators.<br />It could be shown that one of the presented approaches outperforms previously described methods based on ant colony optimisation and VNS only.