Solution Archives in Evolutionary Combinatorical Optimization

In this project we investigate an extension of genetic algorithms (GAs) and memetic algorithms (MAs) called complete solution archive. A common drawback of classical GAs (MAs) lies in revisiting already evaluated solutions during the optimization process. In general re-evaluations do not make sense as they waste precious computation time that could have been spent in a more meaningful way. In the concept of the complete solution archive, all evaluated candidate solutions are stored in a special compact data structure. Newly derived solutions are checked if they have already been considered, and if so, an efficient transformation operation takes place converting each duplicate into a guaranteed new, not yet visited candidate solution by applying typically small changes. This transformation function is the particular feature which distinguishes the new approach from techniques such as standard population management and solution caching. The data structure we primarily focus on for realizing this concept is a variant of a trie, which is typically used for storing large collections of words in dictionary applications. It allows the essential insert, find, and transform operations to be implemented in constant time w.r.t. the number of already contained solutions. In addition to the basic functionality, enhanced features including bounding strategies for pruning parts of the search space, heuristically guided transformation, and methods for improving scalability will be studied. Three combinatorial optimization problems will be considered as primary test cases in order to study the problem- specific realizability and impacts of the complete solution archive in detail: the generalized minimum spanning tree problem, the probabilistic traveling salesman problem, and the discrete (r|p)-centroid problem. The envisioned algorithms for these problems cover different direct as well as indirect/incomplete solution representations based on bit and integer vectors, permutations, and tree structures, as well as local improvement and repair strategies. Besides GAs, the archive approach also appears promising for certain other metaheuristics, and we will therefore additionally investigate its applicability in variable neighborhood search, simulated annealing, tabu search, large neighborhood search, and ant colony optimization. In GAs, the solution archive can be seen as a combination of population management, intelligent mutation, as well as a hybridization with branch-and-bound concepts. When adequately applied, the issue of duplicate solutions may be finally resolved efficiently, even without requiring fundamental changes in the basic structures of the GA themselves. From a theoretical point of view, the considered approach turns the GA into a complete optimization technique which is guaranteed to find an optimal solution in limited time. In practice, we expect the method to be particularly beneficial for difficult optimization problems with rather compact solution representations and/or expensive evaluation or genotype decoding functions. By effectively avoiding revisits and instead deriving not yet considered similar solutions, we expect substantial performance boosts. Preliminary work in fact already documents the high potential of the approach.

This project considers a new combination of exact and heuristic solution approaches for solving hard combinatorial optimization problems (COPs). Such problems frequently occur in the areas of transportation, logistics, telecommunication, scheduling, network design, location planning and many more. A common goal of these problems is to find a feasible solution out of a huge set of possibilities which minimizes or maximizes a stated objective function, e.g., costs, duration, or profit. In many cases these optimization problems are hard to solve and no efficient methods are known. Algorithms which are guaranteed to find an optimal solution like, e.g., tree search based methods, can often not be applied anymore due to their excessive running times. Metaheuristics are algorithms which are frequently able to find excellent solutions to COPs in a relatively moderate amount of time. Evolutionary algorithms, which are in the focus of this project, belong to this category of methods and provide a broad spectrum of applications. A disadvantage of these algorithms is, however, that the lack of information on the search history usually leads to unnecessary re-evaluations, a loss of diversity, and premature convergence.We focused in this project on the combination of tree search and evolutionary algorithms using so-called complete solution archives. Such a solution archive stores all generated solution candidates in an efficient tree data structure and thereby avoids duplicates. Whenever a potential duplicate solution is identified it is efficiently converted into a guaranteed new, usually similar solution directly by the archive. Applying this archive to a metaheuristic turns it, in principle, into a complete exact search algorithm, which finds an optimal solution when given enough time. In practice, however, it is typically still only possible to solve small problem instances to proven optimality, and the hybrid metaheuristic will therefore be terminated prematurely. Especially in these cases, the solution archive is frequently able to improve the performance significantly. Within this project we investigated such solution archives in detail, extended them with more advanced techniques, and evaluated their impact on evolutionary algorithms for two types of practical COPs in the domain of competitive assignment and routing.The results of the computational tests on these problems showed that complete solution archives are able to significantly boost the performance of evolutionary algorithms for COPs with a compact solution representation and a time-consuming evaluation function. When properly designed, extensions to the solution archive exploiting their tree structure can lead to further significant improvements. Last but not least, this project resulted in new, more effective state-of-the-art algorithms for the considered location and routing problems.