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
, ,
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
, , ,
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
,
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
,
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

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

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
,
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

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

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]