A complete archive genetic algorithm for the Multidimensional Knapsack Problem

Abstract

In dieser Arbeit wird ein vollständiges Lösungsarchiv vorgestellt, das einen genetischen Algorithmus zur Lösung des multidimensionalen Rucksack Problems (MKP) erweitert. Der genetische Algorithmus, auf dem diese Arbeit aufbaut, verwendet einen repair operator, um ungültige Lösungen auszuschließen und jede gültige Lösung zu einer lokal optimalen Lösung zu transformieren.<br />Es ist wahrscheinlich, dass der genetische Algorithmus Lösungen produziert, die während der Laufzeit schon einmal generiert und ausgwertet wurden. Um die Berücksichtigung von schon ausgewerteten Lösungen zu verhindern, wird ein Lösungsarchiv auf der Basis eines Tries analysiert.<br />Jede erzeugte Kandidatenlösung wird in das Archiv eingefügt. Wird eine schon enthaltene Lösung in das Archiv eingefügt, so wird mit einer speziellen Prozedur aus dieser doppelten Lösung eine neue, noch unbesuchte Lösung generiert, die ebenfalls lokal optimal ist. Des weiteren werden während des Einfügens von Lösungen obere Schranken an jedem Knoten des Tries berechnet. Wird für einen Teilbaum des Tries eine obere Schranke ermittelt, die kleiner als die bisher beste gefundene Lösung ist, so wird der entsprechende Teilbaum abgeschnitten. Sind in einem Teilbaum alle lokal optimalen Lösungen schon einmal besucht worden, so wird dieser Teilbaum ebenfalls abgeschnitten. Jede Lösung, die später generiert wird und in diesem abgeschnittenen Teilbaum liegen würde, wird als schon besuchte Lösung identifiziert, und in eine noch unbesuchte Alternativlösung transformiert.<br />In dieser Arbeit werden die zur Implementierung notwendigen Algorithmen und Datenstrukturen dieses Lösungsarchivs vorgestellt. Dieser erweiterte genetische Algorithmus wird mit dem ursprünglichen Algorithmus verglichen, und es zeigt sich, dass durch dieses Lösungsarchiv bei vielen Instanzen bessere Lösungen gefunden werden.<br />

This thesis presents a complete solution archive enhancing a genetic algorithm for the Multidimensional Knapsack Problem (MKP). The genetic algorithm on which this work is based on uses a special repair operator to prevent the generation of infeasible solutions and to transform each feasible solution into a locally optimal solution.<br />In longer runs it is likely that this algorithm produces candidate solutions that have already been generated and evaluated before. This effect can significantly reduce the algorithm's overall performance. To prevent the reconsideration of already evaluated solutions, a solution archive based on a Trie is studied.<br />Each newly generated candidate solution is inserted into this archive.<br />If during insertion into the archive a solution is recognized to be a duplicate of an already visited solution, a special procedure transforms this duplicate solution into a new solution that is not contained in the archive and is locally optimal. Furthermore upper bounds are calculated during the insertion at each node of the Trie. If the upper bound calculated at some level of the Trie is smaller than the best solution found so far the corresponding sub Trie is cut off. Each solution that is generated and would be located in this sub trie is considered to be a duplicate and an alternative solution is generated.<br />This thesis presents the algorithms and data structures that are needed to implement the solution archive together with the procedures that operate on this archive. This enhanced genetic algorithm is compared with the original algorithm, showing that for many test instances better solutions can be found.