Enhancing an evolutionary algorithm with a solution archive to reconstruct cross cut shredded text documents

Abstract

In dieser Arbeit wird eine Methode vorgestellt, die existierende Metaheuristiken für das Reconstruction of Cross-Cut Shredded Text Documents (RCCSTD) Problem verbessert. Um dieses Ziel zu erreichen wurde ein memetischer Algorithmus durch ein Lösungsarchiv erweitert, welches auf zwei unterschiedliche Arten implementiert wurde. Zuletzt werden die Resultate verglichen, die durch das Verwenden des Lösungsarchiv mit verschiedenen Konfigurationen des memetischen Algorithmus entstanden sind.<br />Cross-Cut zerkleinerte Textdokumente sind Dokumente, die von einem Papierschredder in rechteckige Teile zerschnitten wurden. Das Ziel ist, diese Teile so zusammenzusetzen, damit das Originaldokument wieder rekonstruiert wird. Da dieses Problem NP-vollständig ist, existieren diverse heuristische Lösungsansätze. Einige der besten Ergebnisse liefert ein memetischer Algorithmus (MA), der eine Erweiterung eines evolutionären Algorithmus (EA) darstellt, d.h. eine populationsbasierte Metaheuristik. Eines der größten Probleme solcher Algorithmen ist der Verlust von Diversität in späteren Generationen, da viele gleiche Lösungen generiert werden. Um dieses Problem zu umgehen, können schon besuchte Lösungen in einem Lösungsarchiv gespeichert und nachgeschlagen werden, sodass nur neue Lösungen vom EA akzeptiert werden. Die Einfüge- und Suchmethode für die benötigte Datenstruktur muss so effizient wie möglich sein, da alle vom EA generierten Lösungen in dem Archiv gespeichert und nachgeschlagen werden. Eine weitere Anforderung ist, dass, wenn eine Duplikatlösung gefunden wurde, eine neue Lösung effizient generiert wird. Eine Trie-basierte Datenstruktur erfüllt alle Anforderungen, da die Einfüge- und Suchmethode in $O(h)$ läuft, wobei $h$ die Höhe des Tries ist, die wiederum durch die Größe des Inputs beschränkt ist.<br />Zuerst wurde eine geeignete Lösungsrepräsentation entwickelt -- die Integer-IDs der Schnipsel in einem Array, das den rechten und den unteren Nachbar von jedem Schnipsel enthält. Mit dieser Repräsentation wurde die maximale Größe einer Lösung im Vergleich zu der bisherigen drastisch reduziert, die die absoluten Positionen der Schnipsel speicherte.<br />Es wurden zwei verschiedene Strategien entwickelt, um neue, noch unbesuchte Lösungen zu generieren. In der ersten Methode wurde ein zufälliger Permutationspunkt gewählt. Von diesem Punkt aus wurde die Entscheidung, welches Schnipsel als nächstes gewählt wird, ausschließlich auf Basis einer Liste von verfügbaren Schnipseln, die in jedem Trie-Knoten gespeichert wird, getroffen. Diese Liste enthält alle Schnipsel, die auf dieser Ebene eingefügt werden können. Das verdeutlicht auch die Schwierigkeit dieser Methode -- nicht alle Schnipsel können auf jeder Ebene eingefügt werden und manchmal kann sogar nur ein Schnipsel auf der Ebene gewählt werden. Die zweite Methode basiert auch auf einem zufällig gewählten Permutationspunkt. Auf diesem Punkt wird der Schnipsel, der in der Duplikatlösung auf diesem Level eingefügt wurde, mit einem verfügbaren Schnipsel getauscht. In diesem Fall kann die Liste der verfügbaren Schnipsel leichter berechnet werden.<br />Schlussendlich wurde das Archiv auf diversen Instanzen mit verschiedenen Schnittmustern (daher auch unterschiedlichen Größen) getestet. Es wurde getestet, ob das Lösungsarchiv mit gleichem Zeitaufwand dem memetischen Algorithmus hilft, eine bessere Lösung zu finden. Die Ergebnisse zeigten auf, dass in den meisten Fällen der memetische Algorithmus in Kombination mit dem Lösungsarchiv nur genauso gut wie der memetische Algorithmus alleine ist. Das kommt unter Anderem daher, dass das Lösungsarchiv einen riesigen Speicherbedarf hat, was das Testen deutlich erschwerte.<br />

In this thesis a method for improving existing metaheuristics for the Reconstruction of Cross-Cut Shredded Text Documents (RCCSTD) problem is presented. For this purpose a memetic algorithm is enhanced by a solution archive, which is implemented in two different ways.<br />Finally, the results of using the solution archive with different configurations of the memetic algorithm are compared to each other.<br />Cross-cut shredded text documents are documents that are cut in rectangular pieces using a shredding device. The aim is to fit the pieces in such a way next to each other so that the original document is reconstructed. Since this problem is NP-complete several heuristic approaches exist. Some of the best results are delivered by a memetic algorithm (MA), which is an extension of an evolutionary algorithm (EA), i.e., a population based metaheuristic. One of the main problems of this kind of algorithms is the loss of diversity in later generations because a lot of solutions are equal to each other.<br />To circumvent this problem, already generated solutions can be stored and looked up in a solution archive so that only new solutions are accepted by the EA. The insert and the search method for this datastructure have to be as efficient as possible because all solutions generated by the EA are inserted and looked up in the archive. Another requirement of the solution archive is to generate a new solution efficiently if a duplicate was found. A trie-based datastructure meets all the requirements since insertion and search run in time O(h) where h is the height of the trie, which is bounded by the size of the input.<br />First an appropiate solution representation is developed-an array of shreds, which are represented by their integer IDs, containg the right and the bottom neighbor of each shred. With this representation the maximum solution size is drastically reduced compared to the currently used representation which stores the absolute positions of the shreds.<br />Two different strategies for generating new, yet unvisited, solutions are presented. In the first method a random permutation point is chosen.<br />From this point on the decision which shred is chosen is entirely based on a list of available shreds, which is stored in each trie node. This list contains all shreds that can possibly be inserted at this level, which reveals also the difficulty of this approach-not all shreds can be chosen on every level and sometimes there is even only one shred left to choose. The second method is also based on a random permuation point. On that point the shred that has been inserted in the duplicate solution is swapped with an available shred. In this case the list of available shreds can be computed more easily.<br />In the end the archive is tested on several instances with different cutting patterns, thus different sizes. It was tested if the solution archive helps the memetic algorithm to find a better solution in the same amount of time. The results showed that in most cases the memetic algorithm in combinaion with the solution archive performed only as good as the memetic algorithm alone. This is also because of the vast memory consumption of the solution archive, which made testing very difficult.<br />