On the Bias and Performance of the Edge-Set Encoding


Rothlauf, Franz ; Tzschoppe, Carsten


[img]
Vorschau
PDF
abwl_11_04.pdf - Veröffentlichte Version

Download (299kB)

URL: https://ub-madoc.bib.uni-mannheim.de/986
URN: urn:nbn:de:bsz:180-madoc-9869
Dokumenttyp: Arbeitspapier
Erscheinungsjahr: 2004
Titel einer Zeitschrift oder einer Reihe: None
Sprache der Veröffentlichung: Englisch
Einrichtung: Fakultät für Betriebswirtschaftslehre > Sonstige - Fakultät für Betriebswirtschaftslehre
MADOC-Schriftenreihe: Area Information Systems and Institute for Enterprise Systems > Working Papers Lehrstuhl für ABWL und Wirtschaftsinformatik (Heinzl) (bis 2011)
Fachgebiet: 004 Informatik
Normierte Schlagwörter (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.
Zusätzliche Informationen:




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




Metadaten-Export


Zitation


+ Suche Autoren in

+ Download-Statistik

Downloads im letzten Jahr

Detaillierte Angaben



Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail


Actions (login required)

Eintrag anzeigen Eintrag anzeigen