[Back]

B. Hu, G. Raidl:
"An evolutionary algorithm with solution archive for the generalized minimum spanning tree problem";
Talk: International Conference on Computer Aided Systems Theory (Eurocast), Gran Canaria, Spain; 2011-02-06 - 2011-02-11; in: "Extended Abstracts of EUROCAST 2011 - 13th International Conference on Computer Aided Systems Theory", (2011), ISBN: 978-84-693-9560-8; 256 - 258.

Attaching a solution archive to a metaheuristic for a combinatorial optimization
problem in order to completely avoid evaluating duplicate solutions is a relatively
novel approach [7]. When using a classical Evolutionary Algorithm (EA),
for example, frequent re-evaluation of duplicate solutions cannot be avoided.
This wastes valuable computation time which could have been spent in a more
meaningful way otherwise. The solution archive takes advantage of this observation
and stores already considered solutions in an appropriate data structure,
allowing a fast detection of duplicates and e cient conversion of them into similar
yet unvisited solutions.
This concept has been successfully applied on two problems where solutions
are encoded as binary strings [7]. Similar methods exist where solutions are
cached by hash tables [4] or stored in k-d trees [9]. However, these approaches
either do not support e cient conversion of duplicates or they are applied to
problems with rather simple solution representations.
In this paper we describe an archive-enhanced EA for the Generalized Minimum
Spanning Tree Problem (GMSTP) which is de ned as follows: Given an
undirected weighted complete graph G = hV;E; ci with node set V partitioned
into r pairwise disjoint clusters V1; V2; : : : ; Vr, edge set E and edge cost function
c : E ! R+, a solution S = hP; Ti is de ned as P = fp1; p2; : : : ; prg V
containing exactly one node from each cluster, i.e. pi 2 Vi; i = 1; : : : ; r, and
T E being a tree spanning the nodes in P. The costs of S are the total edge
costs, i.e. C(T) =
P
(u;v)2T c(u; v) and the objective is to identify a solution
with minimum costs. The GMSTP was introduced in [5] and has been proven
to be NP-hard. In recent years, many successful metaheuristic approaches [1{3]
were developed for this problem.

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