- author = "Nuno Antonio Marques Lourenco",
- title = "Enhancing Grammar-Based Approaches for the Automatic Design of Algorithms",
- school = "Department of Informatics Engineering of the Faculty of Sciences and Technology of the University of Coimbra",
- year = "2015",
- address = "Portugal",
- month = sep,
- keywords = "genetic algorithms, Genetic Programming, Grammatical Evolution, Automatic Design of Algorithms, Evolutionary Algorithms, Evolutionary Computation, Hyper-Heuristics",
- isbn13 = "979-8-8415-5220-8",
-
URL = "
http://hdl.handle.net/10316/29450",
-
URL = "https://estudogeral.uc.pt/handle/10316/29450",
-
URL = "https://www.proquest.com/docview/2018648958",
-
URL = "
https://estudogeral.uc.pt/bitstream/10316/29450/1/Enhancing%20Grammar-Based%20Approaches%20for%20the%20Automatic%20Design%20of%20Algorithms.pdf",
-
URL = "https://dl.acm.org/doi/10.5555/AAI29196626",
- size = "177 pages",
-
abstract = "Evolutionary Algorithms (EA) are stochastic
computational methods loosely inspired by the
principles of natural selection and genetics. They have
been successfully used to solve complex problems in the
domains of learning, design and optimization.
When using an EA practitioners have to define its main components such as the variation operators, the selection and replacement mechanisms. The performance of an EA can be greatly enhanced if the components are tailored to the specific situation being addressed. These modifications are usually done manually and require a reasonable degree of expertise. In order to ease the use of EAs some researchers have developed methods to automatically design this type of algorithms. Usually, these methods rely on an (meta-) algorithm that combine components and parameters, in order to learn the one that is most suited for the problem being addressed. The area of Hyper-Heuristics (HH) emerges in this context focusing on the development of efficient meta-algorithms.
Genetic Programming (GP), specifically the grammar based variants, are commonly used as HH. In this work, we study and analyze the conditions in which Grammatical Evolution (GE) can be enhanced to automatically design EAs.
The main contributions can be divided in three aspects. Firstly, we propose an HH framework that relies on GE as the search algorithm. The proposed framework is divided in two complementary phases: Learning and Validation. In Learning the GE engine is used to combine low level components that are specified in a Context Free Grammar. In the second phase, Validation, the best algorithms learned are selected to be applied to scenarios different from the learning, in order to evaluate their generalization capacity.
Secondly we study the impact that the learning conditions have in the final structure of the algorithms that are being learned. Moreover, we analyze the relationship between the quality exhibited by the algorithms during learning and their effective optimization ability when used in unseen scenarios. In concrete we analyze if the best strategies discover in learning still have the same good behaviour in validation.
Our final contribution addresses some of the limitations exhibited by Grammatical Evolution. The result is a novel representation with an enhanced performance.",
-
notes = "In English
SFRH/BD/79649/2011 Order Number:AAI29196626
Cover Image: Evolved using the SGE algorithm and the ideas behind NEvAr \cite{Machado:2002:AI}
Knapsack Problem Data
Supervisors: Ernesto Jorge Fernandes Costa and Francisco Jose Baptista Pereira",
