research-article

Orientation matters: how to efficiently solve ocst problems with problem-specific EAs

Authors:

Wolfgang Steitz,

Franz RothlaufAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 563 - 570

https://doi.org/10.1145/1389095.1389205

Published: 12 July 2008 Publication History

Abstract

The optimal communication spanning tree (OCST) problem is a well known $\mathcal{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 \emph{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.

References

[1]

T. Fischer and P. Merz. A memetic algorithm for the optimum communication spanning tree problem. In T. Bartz-Beielstein, M. J. B. Aguilera, C. Blum, B. Naujoks, A. Roli, G. Rudolph, and M. Sampels, editors, Hybrid Metaheuristics, 4th International Workshop, HM 2007, Dortmund, Germany, October 8-9, 2007, Proceedings, volume 4771 of LNCS, pages 170--184. Springer, 2007.

Digital Library

[2]

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979.

Digital Library

[3]

T. C. Hu. Optimum communication spanning trees. SIAM Journal on Computing, 3(3):188--195, 1974.

[4]

B. A. Julstrom and G. R. Raidl. Weight-biased edge-crossover in evolutionary algorithms for two graph problems. In SAC '01: Proceedings of the 2001 ACM symposium on Applied computing, pages 321--326, New York, NY, USA, 2001. ACM.

Digital Library

[5]

C. C. Palmer. An approach to a problem in network design using genetic algorithms. PhD thesis, Polytechnic University, Troy, NY, USA, 1994.

Digital Library

[6]

C. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. In STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 229--234, New York, NY, USA, 1988. ACM Press.

Digital Library

[7]

D. Peleg and E. Reshef. Deterministic polylog approximation for minimum communication spanning trees. In ICALP '98: Proceedings of the 25th International Colloquium on Automata, Languages and Programming, pages 670--681, London, UK, 1998. Springer-Verlag.

Digital Library

[8]

G. Raidl. An efficient evolutionary algorithm for the degree-constrained minimum spanning tree problem. In Proc. of the 2000 Congress on Evolutionary Computation, pages 104--111, Piscataway, NJ, 2000. IEEE Service Center.

[9]

G. R. Raidl and B. A. Julstrom. Edge sets: an effective evolutionary coding of spanning trees. IEEE Transactions on Evolutionary Computation, 7(3):225--239, June 2003.

Digital Library

[10]

F. Rothlauf. Representations for Genetic and Evolutionary Algorithms. Heidelberg: Springer, 2 edition, 2006.

Digital Library

[11]

F. Rothlauf. Design and Application of Metaheuristics. Universitat Mannheim, Habilitationsschrift, 2007.

[12]

F. Rothlauf, D. E. Goldberg, and A. Heinzl. Network random keys: a tree representation scheme for genetic and evolutionary algorithms. Evolutionary Computaton, 10(1):75--97, 2002.

Digital Library

[13]

F. Rothlauf and A. Heinzl. On optimal solutions for the optimal communication spanning tree problem. Technical report, Department of Information Systems 1, University of Mannheim, 2003.

[14]

P. Sharma. Algorithms for the optimum communication spanning tree problem. Annals of Operations Research, 143(1):203--209, 2006.

[15]

S.-M. Soak. A new evolutionary approach for the optimal communication spanning tree problem. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, E89--A(10):2882--2893, 2006.

Digital Library

[16]

C. Tzschoppe, F. Rothlauf, and H.-J. Pesch. The edge-set encoding revisited: On the bias of a direct representation for trees. In Deb, Kalyanmoy et al., editor, Proceedings of the Genetic and Evolutionary Computation Conference 2004, pages 1174--1185, Heidelberg, 2004. Springer.

[17]

B. Y. Wu and K.-M. Chao. Spanning Trees and Optimization Problems. Discrete Mathematics and Its Applications. Chapman & Hall/CRC, 2004.

[18]

B. Y. Wu, K.-M. Chao, and C. Y. Tang. Approximation algorithms for some optimum communication spanning tree problems. Discrete Appl. Math., 102(3):245--266, 2000.

Digital Library

[19]

B. Y. Wu, K.-M. Chao, and C. Y. Tang. A polynomial time approximation scheme for optimal product-requirement communication spanning trees. J. Algorithms, 36(2):182--204, 2000.

Digital Library

Cited By

Steitz WRothlauf F(2012)Edge Orientation and the Design of Problem-Specific Crossover Operators for the OCST ProblemIEEE Transactions on Evolutionary Computation10.1109/TEVC.2010.209358016:1(108-116)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1109/TEVC.2010.2093580
Steitz WRothlauf FRothlauf F(2009)New insights into the OCST problemProceedings of the 11th Annual conference on Genetic and evolutionary computation10.1145/1569901.1569951(357-364)Online publication date: 8-Jul-2009
https://dl.acm.org/doi/10.1145/1569901.1569951

Index Terms

Orientation matters: how to efficiently solve ocst problems with problem-specific EAs
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction

Recommendations

New insights into the OCST problem: integrating node degrees and their location in the graph
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

This paper considers the Euclidean variant of the optimal communciation spanning tree (OCST) problem. Researches have analyzed the structure of the problem and found that high quality solutions prefer edges of low cost. Further, edges pointing to the ...
Improvement of bounded-diameter MST instances with hybridization of multi-objective EA
ICCCS '11: Proceedings of the 2011 International Conference on Communication, Computing & Security

The Bounded Diameter (a.k.a Diameter Constraint) Minimum Spanning Tree (BDMST/DCMST) is a well-known combinatorial optimization problem. In this work, we recast a few well-known heuristics, which are evolved for BDMST problem, to a Bi-Objective Minimum ...
Solving OCST problems with problem-specific guided local search
GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

This paper considers the Euclidean variant of the optimal communication spanning tree (OCST) problem. Previous work analyzed features of high-quality solutions and found that edges in optimal solutions have low weight and point towards the center of a ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
99
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Steitz WRothlauf F(2012)Edge Orientation and the Design of Problem-Specific Crossover Operators for the OCST ProblemIEEE Transactions on Evolutionary Computation10.1109/TEVC.2010.209358016:1(108-116)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1109/TEVC.2010.2093580
Steitz WRothlauf FRothlauf F(2009)New insights into the OCST problemProceedings of the 11th Annual conference on Genetic and evolutionary computation10.1145/1569901.1569951(357-364)Online publication date: 8-Jul-2009
https://dl.acm.org/doi/10.1145/1569901.1569951

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten