Unifying a Geometric Framework of Evolutionary Algorithms and Elementary Landscapes Theory
Created by W.Langdon from
gp-bibliography.bib Revision:1.8010
- @PhdThesis{Diez-GarciaM,
-
author = "Marcos {Diez Garcia}",
-
title = "Unifying a Geometric Framework of Evolutionary
Algorithms and Elementary Landscapes Theory",
-
school = "Computer Science, University of Exeter",
-
year = "2021",
-
address = "UK",
-
month = jan,
-
keywords = "genetic algorithms, genetic programming",
-
URL = "https://ore.exeter.ac.uk/repository/bitstream/handle/10871/126174/Diez-GarciaM.pdf",
-
size = "270 pages",
-
abstract = "Evolutionary algorithms (EAs) are randomised
general-purpose strategies, inspired by natural
evolution, often used for finding (near) optimal
solutions to problems in combinatorial optimisation.
Over the last 50 years, many theoretical approaches in
evolutionary computation have been developed to analyse
the performance of EAs,design EAs or measure problem
difficulty via fitness landscape analysis. An open
challenge is to formally explain why a general class of
EAs perform better, or worse,than others on a class of
combinatorial problems across representations.
However,the lack of a general unified theory of EAs and
fitness landscapes, across problems and
representations, makes it harder to characterise pairs
of general classes of EAs and combinatorial problems
where good performance can be guaranteed provably. This
thesis explores a unification between a geometric
framework of EAs and elementary landscapes theory, not
tied to a specific representation nor problem, with
complementary strengths in the analysis of
population-based EAs and combinatorial landscapes. This
unification organises around three essential aspects:
search space structure induced by crossovers, search
behaviour of population-based EAs and structure of
fitness landscapes. First, this thesis builds a
crossover classification to systematically compare
crossovers in the geometric framework and elementary
landscapes theory, revealing a shared general subclass
of crossovers: geometric recombination P-structures,
which covers well-known crossovers. The crossover
classification is then extended to a general framework
for axiomatically analysing the population behaviour
induced by crossover classes on associated EAs. This
shows the shared general class of all EAs using
geometric recombination P-structures, but no mutation,
always do the same abstract form of convex evolutionary
search. Finally, this thesis characterises a class of
globally convex combinatorial landscapes shared by the
geometric framework and elementary landscapes theory:
abstract convex elementary landscapes. It is formally
explained why geometric recombination P-structure EAs
expectedly can out perform random search on abstract
convex elementary landscapes related to low-order graph
Laplacian eigenvalues. Altogether, this thesis paves a
way towards a general unified theory of EAs and
combinatorial fitness landscapes.",
-
notes = "supervisor: Alberto Moraglio",
- }
Genetic Programming entries for
Marcos Diez Garcia
Citations