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