[Back]

B. Biesinger:
"Enhancing an Evolutionary Algorithm with a Solution Archive to Reconstruct Cross Cut Shredded Text Documents";
Supervisor: G. Raidl, C. Schauer, B. Hu; Institut für Computergraphik und Algorithmen, 2012; final examination: 2012-05.

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. Finally,
the results of using the solution archive with different configurations of the memetic algorithm
are compared to each other.
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.
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.
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.
Two different strategies for generating new, yet unvisited, solutions are presented. In the
first method a random permutation point is chosen. 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.
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.

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

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