Diploma and Master Theses (authored and supervised):
"A complete archive genetic algorithm for the multidimensional knapsack problem";
Supervisor: G. Raidl;
Institut für Computergraphik und Algorithmen,
final examination: 2008-05.
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.
In longer runs it is likely that this algorithm produces candidate solutions
that have already been generated and evaluated before. This e ect can
signi cantly reduce the algorithm's overall performance. To prevent the
reconsideration of already evaluated solutions, a solution archive based on
a Trie is studied.
Each newly generated candidate solution is inserted into this archive. 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 o . Each solution that is generated and would be located in
this sub Trie is considered to be a duplicate and an alternative solution is
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.
Created from the Publication Database of the Vienna University of Technology.