An evolutionary algorithm with solution archive 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 optimiza-tion 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 so-lution space. Similarly to the classical branch-and-bound technique, bounds are obtained via primal and dual heuris-tics. As an application we consider the generalized min-imum 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 representa-tions, 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