[Back]

B. Hu, G. Raidl:
"An evolutionary algorithm with solution archives and bounding extension for the generalized minimum spanning tree problem";
Talk: GECCO: Genetic and Evolutionary Computation Conference, Philadelphia, USA; 2012-07-07 - 2012-07-11; in: "Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation", (2012), 393 - 400.

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 e ciently 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.

http://dx.doi.org/10.1145/2330163.2330220

http://publik.tuwien.ac.at/files/PubDat_213069.pdf