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

Created from the Publication Database of the Vienna University of Technology.