On the Bias and Performance of the Edge-Set Encoding

Rothlauf, Franz ; Tzschoppe, Carsten

abwl_11_04.pdf - Published

Download (299kB)

URL: https://ub-madoc.bib.uni-mannheim.de/986
URN: urn:nbn:de:bsz:180-madoc-9869
Document Type: Working paper
Year of publication: 2004
Publication language: English
Institution: Business School > Sonstige - Fakultät für Betriebswirtschaftslehre
MADOC publication series: Area Information Systems and Institute for Enterprise Systems > Working Papers Lehrstuhl für ABWL und Wirtschaftsinformatik (Heinzl) (bis 2011)
Subject: 004 Computer science, internet
Subject headings (SWD): Heuristik , Netzwerk , Problem
Abstract: The edge-set encoding is a direct encoding for trees which directly represents trees as sets of edges. In contrast to indirect representations, where usually standard operators are applied to a list of strings and the resulting phenotype is constructed by an appropriate genotype-phenotype mapping, encoding-specific initialization, crossover, and mutation operators have been developed for the edge-set encoding, which are directly applied to trees. There are two different variants of operators: heuristic versions that consider the weights of the edges and non-heuristic versions. An investigation into the bias of the different variants of the operators shows that the heuristic variants are biased towards the minimum spanning tree (MST), that means solutions similar to the MST are favored. In contrast, non-heuristic versions are unbiased. The performance of edgesets is investigated for the optimal communication spanning tree (OCST) problem. Results are presented for randomly created problems as well as for test instances from the literature. Although optimal solutions for the OCST problem are similar to the MST, evolutionary algorithms using the heuristic crossover operator fail if the optimal solution is only slightly different from the MST. The non-heuristic version shows similar performance as the network random key encoding, which is an unbiased indirect encoding and is used as a benchmark. With proper parameter setting the heuristic version of the mutation operator shows good results for the OCST problem as it can make use of the fact that optimal solutions of the OCST problem are similar to the MST. The results suggest that the heuristic crossover operator of the edge-set encoding should not be used for tree problems as its bias towards the MST is too strong.
Additional information:

Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.

Metadata export


+ Search Authors in

+ Download Statistics

Downloads per month over past year

View more statistics

You have found an error? Please let us know about your desired correction here: E-Mail

Actions (login required)

Show item Show item