Probabilistic Grammatical Evolution

Abstract

Evolução Gramatical (GE) [1] é uma das variantes mais populares de Programação Genética(GP) [2] e tem sido utilizada com sucesso em problemas de vários domínios. Desde a pro-posta original, muitas melhorias foram introduzidas na GE para melhorar a sua perfor-mance abordando alguns dos seus principais problemas, nomeadamente a baixa localidadee a alta redundância [3, 4].Nos métodos de GP baseados em gramáticas a escolha da gramática tem um papel impor-tante na qualidade das soluções geradas, uma vez que é a gramática que define o espaçode procura [5]. Neste trabalho, propomos quatro variantes da GE, que durante o processoevolucionário realizam uma exploração do espaço de procura, alterando os pesos de cada re-gra da gramática. Estas variantes introduzem dois tipos de representação alternativas, doismétodos diferentes de ajustar a gramática e um novo método de mapeamento, utilizandouma Gramática Livre de Contexto Probabilistica (PCFG).O primeiro método é a Evolução Gramatical Probabilistica (PGE), no qual os individuossão representados por uma lista de probabilidades (genótipo), onde cada valor representa aprobabilidade de selecionar uma regra de derivação. O genótipo é mapeado numa soluçãopara o problema em questão (fenótipo), recorrendo a uma PCFG. A cada geração, as prob-abilidades de cada regra da gramática são atualizadas, com base nas regras de expansãousadas pelo melhor individuo. A Evolução Gramatical Probabilistica Co-Evolucionária(Co-PGE) utiliza a mesma representação dos individuos e introduz uma nova técnicade atualização das probabilidades da gramática onde as probabilidades de cada regra dederivação são alteradas a cada geração usando um operador semelhante à mutação. Emambos os métodos os individuos são remapeados após atualização da gramática.A Evolução Gramatical Estruturada Probabilistica (PSGE) e a Evolução Gramatical Estru-turada Probabilistica Co-Evolucionária (Co-PSGE) foram criadas adaptando a EvoluçãoGramatical Estruturada (SGE), um método que foi proposto para superar os problemas daGE melhorando a sua performance [6]. Estas variantes usam como genótipo um conjuntode listas dinâmicas, uma para cada não-terminal, em que cada elemento da lista é umaprobabilidade usada para mapear o individuo, usando uma PCFG.Analisamos e comparamos o desempenho dos métodos em seis problemas benchmark.Quando comparados com a GE, os resultados mostraram que a PGE e a Co-PGE sãoestatisticamente semelhantes ou melhores em todos os problemas, enquanto que a PSGE ea Co-PSGE foram estatisticamente melhores em todos os problemas do que a tradicionalGE. Destacamos também a Co-PSGE por superar estatisticamente a SGE em alguns prob-lemas, tornando-a competitiva com o estado da arte. Também realizamos uma análise nasrepresentações, e os resultados mostraram que a PSGE e a Co-PSGE tem menos redun-dancia, e todos os métodos apresentaram localidade mais elevada que o GE, o que permiteuma melhor exploração do espaço de procura.As análises efetuadas mostraram que as gramáticas evoluidas ajudam a guiar o processoevolucionario, e fornecem-nos informações sobre as regras de produção mais relevantespara gerar melhores soluções. Além disso, também podem ser utilizadas para gerar umaamostragem de soluções com melhor fitness médio.

Grammatical Evolution (GE) [1] is one of the most popular variants of Genetic Program-ming (GP) [2] and has been successfully used in a wide range of problem domains. Sincethe original proposal, many improvements have been introduced in GE to improve its per-formance by addressing some of its main issues, namely low locality and high redundancy[3, 4].In grammar-based GP methods the choice of the grammar has a significant impact onthe quality of the generated solutions, since it is the grammar that defines the searchspace [5]. In this work, we present four variants of GE, which during the evolutionaryprocess perform an exploration of the search space by updating the weights of each ruleof the grammar. These variants introduce two alternative representation types, two gram-mar adjustment methods, and a new mapping method using a Probabilistic Context-FreeGrammar (PCFG).The first method is Probabilistic Grammatical Evolution (PGE), in which individuals arerepresented by a list of real values (genotype), each value denoting the probability of select-ing a derivation rule. The genotype is mapped into a solution (phenotype) to the problemat hand, using a PCFG. At each generation, the probabilities of each rule in the grammarare upated, based on the expansion rules used by the best individual. Co-evolutionaryProbabilistic Grammatical Evolution (Co-PGE) employs the same representation of indi-viduals and introduces a new technique to update the grammar’s probabilities, where eachindividual is assigned a PCFG where the probabilities of each derivation option are changedat each generation using a mutation like operator. In both methods, the individuals areremapped after updating the grammar.Probabilistic Structured Grammatical Evolution (PSGE) and Co-evolutionary Probabilis-tic Structured Grammatical Evolution (Co-PSGE) were created by adapting the mappingand probabilities update mechanism from PGE and Co-PGE to Structured GrammaticalEvolution (SGE), a method that was proposed to overcome the issues of GE while improv-ing its performance [6]. These variants use as genotype a set of dynamic lists, one for eachnon-terminal of the grammar, with each element of the list being the probability used tomap the individual with the PCFG.We analyse and compare the performance of all the methods in six benchmarks. Whencompared to GE, the results showed that PGE and Co-PGE are statistically similar orbetter on all problems, while PSGE and Co-PSGE are statistically better on all problems.We also highlight Co-PSGE since it is statistically superior to SGE in some problems,making it competitive with the state-of-the-art. We also performed an analysis on therepresentations, and the results showed that PSGE and Co-PSGE have less redundancy,and all approaches exhibited better locality than GE, which allows for a better explorationof the search space.The analyses conducted showed that the evolved grammars help guide the evolutionaryprocess and provides us information about the most relevant production rules to generatebetter solutions. In addition, they can also be used to generate a sampling of solutionswith better average fitness.