Algorytmy genetyczne w automatycznym generowaniu gramatyk bezkontekstowych dla potrzeb syntaktycznej interpretacji wzorców

Abstract

The thesis presents the grammar inference system for context-free grammars based on genetic programming. This system allows for generating grammars for an unknown context-free language based on finite sets of patterns belonging to this language (i.e. positive examples) as well as patterns belonging to the complement of this language (i.e. negative examples). The thesis analyses the influence of various types of crossover operators on the process of grammar inference, as well as suggests and tests mutation operators, whose function is to increase the efficiency of the evolution process in grammatical inference. It also develops an algorithm which compensates the growth of the size of the trees, during the evolution process, which represent the production of grammars. The thesis presents the model of 'continuous' evolution, developed by the author, which is an alternative for the standard model used in genetic programming. This model is characterised by the lack of division of the evolution stages into generations and the decomposition of the set of individuals into disjunctive subsets differing from each other by parameters of evolution. The results obtained by the author indicate that 'continuous' evolution model is better suited for the inference of context-free grammars thanks to its better convergence of the process of generating grammars, and the fact that the grammars obtained are less complex. W pracy zaproponowany został system wnioskowania gramatycznego dla gramatyk bezkontekstowych oparty na bazie ewolucyjnych formalizmów programowania genetycznego. System ten pozwala generować gramatyki dla nieznanego języka bezkontekstowego w oparciu o skończone zbiory wzorców należących do tego języka (przykłady pozytywne) oraz wzorców należących do dopełnienia tego języka (przykłady negatywne). W pracy zbadano wpływ różnych typów operatorów krzyżowania na proces generowania gramatyk, zaproponowano i przetestowano operatory mutacji, których zadaniem jest poprawa efektywności procesu ewolucyjnego wnioskowania gramatycznego, oraz stworzono algorytm kompensujący nadmierny wzrost rozmiaru drzew reprezentujących produkcje gramatyk w trakcie procesu ewolucji. W pracy przedstawiony został również opracowany przez autora model ewolucji 'ciągłej' będący alternatywą dla stosowanego w programowaniu genetycznym modelu standardowego. Model ewolucji ciągłej charakteryzuje się brakiem podziału procesu ewolucji na poszczególne pokolenia oraz dekompozycją zbioru osobników na rozłączne podzbiory różniące się parametrami ewolucji. Przedstawione w pracy wyniki badań pokazują, że model ewolucji 'ciągłej' jest korzystniejszy w zastosowaniu do procesu generowania gramatyk bezkontekstowych, zarówno ze względu na lepszą zbieżność procesu jak i dlatego, że znajdowane gramatyki charakteryzują się mniejszą złożonością.