english Steitz, Wolfgang; Rothlauf, Franz: Orientation matters: How to efficiently solve OCST problems with problem-specific EAs, In: Maarten Keijzer et al. (eds.): Proceedings of the Genetic and Evolutionary Computation Conference, Atlanta, 12.-16.Juli. ACM Press, 2008


The optimal communication spanning tree (OCST) problem is a well known NP-hard combinatorial optimization problem which seeks a spanning tree that satisfies all given communication requirements for minimal total costs. It has been shown that optimal solutions of OCST problems are biased towards the much simpler minimum spanning tree (MST) problem. Therefore, problem-specific representations for EAs like heuristic variants of edge-sets that are biased towards MSTs show high performance. In this paper, additional properties of optimal solutions for Euclidean variants of OCST problems are studied. Experimental results show that not only edges in optimal trees are biased towards low-distance weights but also edges which are directed towards the graph''s center are overrepresented in optimal solutions. Therefore, efficient heuristic search algorithms for OCST should be biased towards edges with low distance weight *and* edges that point towards the center of the graph. Consequently, we extend the recombination operator of edge-sets such that the orientation of the edges is considered for constructing offspring solutions. Experimental results show a higher search performance in comparison to EAs using existing crossover strategies of edge-sets. As a result, we suggest to consider not only the distance weights but also the orientation of edges in heuristic solution approaches for the OCST problem.


optimal communications spanning tree problem, heuristics, evolutionary algorithm, Recombination operators


  author = \{Steitz, Wolfgang and Rothlauf, Franz},
  title = \{Orientation matters: How to efficiently solve OCST problems with problem-specific EAs},
  year = \{2008},
  editor = \{Maarten Keijzer et al.},
  booktitle = \{Proceedings of the Genetic and Evolutionary Computation Conference},
  publisher = \{ACM Press},
  url = \{},
  date = \{12.-16.Juli},

BibTeX Download for BibTeX


EndNote Download for EndNote