An Evolutionary Algorithm with Solution Archives and Bounding Extension for the Generalized Minimum Spanning Tree Problem

We consider the recently proposed concept of enhancing an evolutionary algorithm (EA) with a complete solution archive. It stores evaluated solutions during the optimization in order to detect duplicates and to efficiently transform them into yet unconsidered solutions. For this approach we introduce the so-called bounding extension in order to identify and prune branches in the trie-based archive which only contain inferior solutions. This extension enables the EA to concentrate the search on promising areas of the solution space. Similarly to the classical branch-and-bound technique, bounds are obtained via primal and dual heuristics. As an application we consider the generalized minimum spanning tree problem where we are given a graph with nodes partitioned into clusters and exactly one node from each cluster must be connected in the cheapest way. As the EA uses operators based on two dual representations, we exploit two corresponding tries that complement each other. Test results on TSPlib instances document the strength of this concept and that it can compete with the leading metaheuristics for this problem in the literature.