Cover Image

The Edge-Set Encoding Revisited: On the Bias of a DirectRepresentation for Trees

The edge-set encoding is a direct tree representation which directly representstrees as sets of edges. There are two variants of the edge-set encoding:the edge-set encoding without heuristics, and the edge-set encoding withheuristics. An investigation into the bias of the edge-set encoding showsthat the crossover operator of the edge-set encoding without heuristics isunbiased, that means it does not favor particular types of trees. In contrast,the crossover operator with heuristics is biased towards the simpleminimum spanning tree (MST) and generates more likely trees that areMST-like. As a result, the performance of the edge-set encoding withoutheuristics does not depend on the structure of the optimal solution. Usingthe heuristic crossover operator results only in high GA performance if theoptimal solution of the problem is slightly dierent from the simple MST.[...]
Year of publication:
2004-01-26
Authors: Tzoppe, Carsten ; Rothlauf, Franz ; Pesch, Hans-Josef
Institutions: Betriebswirtschaftliches Institut <Mannheim> ; Universität <Mainz> / Lehrstuhl für Wirtschaftsinformatik und BWL
Subject: Heuristik | Heuristic Optimization | Repräsentation | Minimal spannender Baum | minimum communication spanning tree
  • 1 Introduction
  • 2 Setting up the Stage: The OCST Problem and theEdge-Set Encoding
  • 2.1 The OCST Problem
  • 2.2 The Edge-Set Encoding without Heuristics
  • 2.3 The Edge-Set Encoding with Heuristics
  • 3 Investigating the Bias of the Edge-Set Encoding
  • 4 The Performance of the Edge-Set Encoding for theOCST problem
  • 4.1 Finding Optimal Solutions for OCST Problems
  • 4.2 Comparing Heuristic and Non-heuristic Crossover Operators
  • 5 Summary and Conclusions
  • References
Persistent link: https://ebvufind01.dmz1.zbw.eu/10005868132
Similar items by subject
Similar items by person