poster

An efficient approximation to the barrier tree using the great deluge algorithm

Authors:

Hansang Yun,

Byung-Ro MoonAuthors Info & Claims

GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Pages 151 - 152

https://doi.org/10.1145/3205651.3205715

Published: 06 July 2018 Publication History

Get Access

Abstract

A barrier tree is a model for representing the hierarchical distribution of local optima and valleys. While it is useful, constructing a barrier tree is challenging for a large problem instance. In this paper, we propose an efficient method to approximate the barrier tree. One important subgoal is to estimate a saddle point between two solutions, and it is achieved by exploiting the bias of the Great Deluge Algorithm. We also present a case study of a pseudo-boolean problem of size 296, which is roughly 6 times larger than the scale that the existing methods can handle.

References

[1]

Olivier Catoni. 1999. Simulated annealing algorithms and Markov chains with rare transitions. In Séminaire de probabilités XXXIII. Springer, 69--119.

Google Scholar

[2]

Vasil S Denchev, Sergio Boixo, Sergei V Isakov, Nan Ding, Ryan Babbush, Vadim Smelyanskiy, John Martinis, and Hartmut Neven. 2016. What is the computational value of finite-range tunneling? Physical Review X 6, 3 (2016), 031015.

Crossref

Google Scholar

[3]

Gunter Dueck. 1993. New optimization heuristics: The great deluge algorithm and the record-to-record travel. Journal of Computational physics 104, 1 (1993), 86--92.

Digital Library

Google Scholar

[4]

Christoph Flamm, Ivo L Hofacker, Peter F Stadler, and Michael T Wolfinger. 2002. Barrier trees of degenerate landscapes. Zeitschrift für physikalische chemie 216, 2 (2002), 155.

Google Scholar

[5]

Jonathan Hallam and A Prugel-Bennett. 2005. Large barrier trees for studying search. IEEE Transactions on Evolutionary Computation 9, 4 (2005), 385--397.

Digital Library

Google Scholar

Recommendations

An improved approximation algorithm for the terminal Steiner tree problem
ICCSA'11: Proceedings of the 2011 international conference on Computational science and its applications - Volume Part III

Given a complete graph G = (V,E) with a length function on edges and a subset R of V, the terminal Steiner tree is defined to be a Steiner tree in G with all the vertices of R as its leaves. Then the terminal Steiner tree problem is to find a terminal ...
An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2

Given a complete graph G = ( V , E ) with a metric cost function c : E R + and two vertex subsets R V and R ' R , a partial-terminal Steiner tree is a Steiner tree which contains all the vertices in R such that all the vertices in R ' are leaves. The ...
A Better Constant-Factor Approximation for Selected-Internal Steiner Minimum Tree

The selected-internal Steiner minimum tree problem is a generalization of original Steiner minimum tree problem. Given a weighted complete graph G=(V,E) with weight function c, and two subsets RźźR⊆V with |RźRź|ź2, selected-internal Steiner minimum tree ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference Companion

July 2018

1968 pages

ISBN:9781450357647

DOI:10.1145/3205651

Editor:
Hernan Aguirre
Shinshu University
,
General Chair:
Keiki Takadama
The University of Electro-Communications

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2018

Check for updates

Qualifiers

Poster

Conference

GECCO '18

Sponsor:

SIGEVO

GECCO '18: Genetic and Evolutionary Computation Conference

July 15 - 19, 2018

Kyoto, Japan

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
69
Total Downloads

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

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

View Options

Login options

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

Recommendations

An improved approximation algorithm for the terminal Steiner tree problem

An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2

A Better Constant-Factor Approximation for Selected-Internal Steiner Minimum Tree