Enhancing Grammar-Based Approaches for the Automatic Design of Algorithms

Abstract

Os Algoritmos Evolucionários (AE) são métodos computacionais de procura estocástica inspirados pelos conceitos da selecção natural e da genética. Este tipo de algoritmos tem sido usado com sucesso para resolver problemas em dominios da aprendizagem, do design e da optimização.

Para utilizar um AE é necessário definir as suas componentes principais, como por exemplo os operadores de variação, os operadores de selecção de pais, e os mecanismos de selecção de sobreviventes. O desempenho de um AE pode ser altamente melhorado se cada uma destas componentes for ajustada para o problema especifico que se pretende resolver. Normalmente estas modificações são feitas manualmente e requerem um grau de conhecimento elevado. Para tentar melhorar este processo, os investigadores têm vindo a propor algoritmos para automaticamente criar AE. Estes novos métodos usam um (meta-) algoritmo que combina as diversas componentes e parâmetros, de maneira a criar a estratégia que melhor se aplica ao problema em questão. Neste contexto surge a área das Híper-Heurísticas (HH), cujo principal objectivo é o desenvolvimento de meta-algoritmos que sejam eficientes.

A Programação Genética (PG), e em particular as variantes baseadas em representações gramaticais são habitualmente utilizadas como motor de pesquisa nas HH. Este trabalho prentende estudar e analisar em que condições a eficácia dos métodos de pesquisa pode ser melhorada, no contexto da evolução automática de AE.

As principais contribuições podem ser divididas em três aspectos. A primeira consiste na construção de uma framework de HH baseada em Evolução Gramatical (EG). A framework está dividida em duas fases complementares: Aprendizagem e Validação. Na aprendizagem, um motor de EG é usado para combinar as componentes de baixo nível que estão especificadas numa Gramática Livre de Contexto. Na validação, os melhores algoritmos encontrados são aplicados a cenários diferentes dos da aprendizagem, para analisar a sua capacidade de generalização.

A segunda contribuição está relacionada com a análise do impacto que as condições de aprendizagem têm na estrutura final dos algoritmos que estão a ser aprendidos e consequentemente na sua capacidade de optimização. Além disso é feita uma análise da relação que existe entre a qualidade dos algoritmos na fase de aprendizagem, e a qualidade dos algoritmos na fase de validação. Em concreto, analisa-se se os melhores algoritmos da fase de aprendizagem mantêm o seu bom desempenho na fase de validação.

Por fim, a última contribuição é uma proposta de uma nova representação para EG que permite resolver alguns problemas relacionados com a exploração do espaço de procura.

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 behavior in validation.

Our final contribution addresses some of the limitations exhibited by Grammatical Evolution. The result is a novel representation with an enhanced performance.