[Zurück]

G. Raidl, B. Hu:
"Enhancing genetic algorithms by a trie-based complete solution archive";
Vortrag: EvoCOP 2010, Istanbul, Turkey; 07.04.2010 - 09.04.2010; in: "Evolutionary Computation in Combinatorial Optimisation - EvoCOP 2010", (2010), S. 239 - 251.

Genetic algorithms (GAs) share a common weakness with
most other metaheuristics: Candidate solutions are in general revisited
multiple times, lowering diversity and wasting precious CPU time. We
propose a complete solution archive based on a special binary trie struc-
ture for GAs with binary representations that e ciently stores all eval-
uated solutions during the heuristic search. Solutions that would later
be revisited are detected and e ectively transformed into similar yet un-
considered candidate solutions. The archive's relevant insert, nd, and
transform operations all run in time O(l) where l is the length of the so-
lution representation. From a theoretical point of view, the archive turns
the GA into a complete algorithm with a clear termination condition and
bounded run time. Computational results are presented for Royal Road
functions and NK landscapes, indicating the practical advantages.

http://publik.tuwien.ac.at/files/PubDat_189088.pdf