Algorithms and Complexity Group
  • People
  • Research
  • Courses
  • Talks
  • Jobs
  • Contact

Solution Archives

Biesinger, Hu, Raidl

A common drawback of metaheuristic approaches, especially evolutionary algorithms (EAs) is that they usually do not keep track of the search history, and already evaluated solutions are often revisited. This leads to premature convergence, wasting resources for re-evaluations, and other malicious effects.

Ea-sa

The solution archive (SA) is a concept for dealing with this problem. By attaching it to a classical EA, it enables detecting already evaluated candidate solutions and efficiently transforming them into similar but yet unvisited solutions, i.e., performing an "intelligent mutation". The figure above illustrates the cooperation between the EA and the archive.

Application

Since this concept causes additional overhead for inserting and transforming solutions in the SA data structure, following conditions should hold in order to maximize the efficiency:

  • A compact solution representation keeps memory consumption for the archive low.
  • Problems with expensive solution evaluations benefit most from avoiding re-evaluations.
  • Problems with few feasibility constraints so that the transformation procedure can be kept simple.

Following combinatorial optimization problems were particularly successful with this approach:

  • Royal road functions
  • NK landscapes
  • Generalized minimum spanning tree problem
  • (r|p)-centroid problem and other competitive facility location problem

Publications related to Solution Archives

2014

1 result
2014
[1]An Evolutionary Algorithm for the Leader-Follower Facility Location Problem with Proportional Customer Behavior
Benjamin Biesinger, Bin Hu, Günther R. Raidl
Conference Proceedings of Learning and Intelligent Optimization Conference (LION 8), volume 8426 of LNCS, pages 203–217, 2014, Springer.
[bibtex] [pdf]

2013

1 result
2013
[1]Reconstructing Cross Cut Shredded Documents with a Genetic Algorithm with Solution Archive
Benjamin Biesinger, Christian Schauer, Bin Hu, Günther R. Raidl
Extended Abstracts of the 14th International Conference on Computer Aided Systems Theory, pages 226–228, 2013.
[bibtex] [pdf]

2012

3 results
2012
[3]An Evolutionary Algorithm with Solution Archive for the Generalized Minimum Spanning Tree Problem
Bin Hu, Günther R. Raidl
Proceedings of the 13th International Conference on Computer Aided Systems Theory: Part I (R. Moreno-Díaz, F. Pichler, A. Quesada-Arencibia, eds.), volume 6927 of LNCS, pages 287–294, 2012, Springer.
[bibtex] [pdf]
[2]An Evolutionary Algorithm with Solution Archives and Bounding Extension for the Generalized Minimum Spanning Tree Problem
Bin Hu, Günther R. Raidl
Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation (GECCO), pages 393–400, 2012, ACM Press.
[bibtex] [pdf]
[1]Enhancing an Evolutionary Algorithm with a Solution Archive to Reconstruct Cross Cut Shredded Text Documents
Benjamin Biesinger
May 2012, Master's thesis, Vienna University of Technology, Institute of Computer Graphics and Algorithms.
Note: supervised by G. Raidl and C. Schauer and B. Hu
[bibtex] [pdf]

2011

1 result
2011
[1]Ein Lösungsarchiv mit Branch-and-Bound-Erweiterung für das Generalized Minimum Spanning Tree Problem
Christian Gruber
Sep 2011, Master's thesis, Vienna University of Technology, Institute of Computer Graphics and Algorithms.
Note: supervised by G. Raidl and B. Hu
[bibtex] [pdf]

2010

2 results
2010
[2]Enhancing Genetic Algorithms by a Trie-Based Complete Solution Archive
Günther R. Raidl, Bin Hu
Evolutionary Computation in Combinatorial Optimisation – EvoCOP 2010 (Peter Cowling, Peter Merz, eds.), volume 6022 of LNCS, pages 239–251, 2010, Springer.
Note: best paper award winner
[bibtex] [pdf]
[1]Ein neues Lösungsarchiv für das Generalized Minimum Spanning Tree-Problem
Mika Sonnleitner
Sep 2010, Master's thesis, Vienna University of Technology, Institute of Computer Graphics and Algorithms.
Note: supervised by G. Raidl and B. Hu
[bibtex] [pdf]

2009

1 result
2009
[1]Ein Lösungsarchiv-unterstützter evolutionärer Algorithmus für das Generalized Minimum Spanning Tree-Problem
Markus Wolf
Jul 2009, Master's thesis, Vienna University of Technology, Institute of Computer Graphics and Algorithms.
Note: supervised by G. Raidl and B. Hu
[bibtex] [pdf]

News

  • Martin Nöllenburg: promotion to Full Professor

    Martin Nöllenburg: promotion to Full Professor

    2020-12-17
    By December 1st, 2020, our colleague Martin Nöllenburg has been promoted to Full Professor for Graph and Geometric Algorithms.  Martin has …Read More »
  • Martin Kronegger wins the Best Teaching Award 2020

    Martin Kronegger wins the Best Teaching Award 2020

    2020-10-23
    Congratulations to Martin Kronegger who received a Best Teaching Award 2020 from TU Wien. The Algorithms and Complexity group is …Read More »
  • Welcome to our Feodor Lynen Fellow Dr. Manuel Sorge

    Welcome to our Feodor Lynen Fellow Dr. Manuel Sorge

    2020-10-12
    On October 1, 2020, Dr. Manuel Sorge has joined the Algorithms and Complexity group with a prestigious Feodor Lynen postdoc …Read More »
  • TU Wien students excel at the 2020 Graph Drawing Contest

    TU Wien students excel at the 2020 Graph Drawing Contest

    2020-10-01
    The 27th annual Graph Drawing Contest, held (virtually) in conjunction with the 28th International Symposium on Graph Drawing and Network …Read More »
  • Best Paper Award at CP’2020

    Best Paper Award at CP’2020

    2020-09-11
    Tomáš Peitl and Stefan Szeider won the Best Paper Award at the main track of CP'2020, the 26th International Conference on Principles …Read More »

News archive

All news for 2015, 2016, 2017, 2018 and 2019.
TU Wien Informatics
Offenlegung (§25 MedienG) Inhaber der Website ist das Institut für Logic and Computation an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. – Disclaimer – Datenschutzerklärung
Log in requires cookies.