Rozprawa doktorska  

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

DOI:
Link do zdalnego zasobu
Data publikacji
Data prezentacji
Data obrony
2007
Data nadania stopnia
2007-05-31
Autorzy (rel.)
Pałka, Dariusz
Nr albumu:
Prawa dostępu
Dostęp: otwarty dostęp
Uwagi:
Prawa: Licencja AGH
AGH Licence - Fair Use
Licencja AGH - Dozwolony użytek chronionych utworów

Inny tytuł
Genetic algorithms in context-free grammar inference for the syntactic pattern recognition
Typ zasobu:
rozprawa doktorska, pełny tekst
Wersja
Sygnatura:
R.9804
Nr normy / patentu
Numer czasopisma (rel.)
Szczegóły wydania / pracy
Uczelnia: Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
Opublikowane w:. -:,,
Skala:Zasięg:
ISBN:e-ISBN:
Seria:ISSN:e-ISSN:
Jednostka AGH: Wydział Elektrotechniki, Automatyki, Informatyki i Elektroniki
Kierunek:
Forma studiów:
Stopień studiów:
Uzyskany tytuł: doktor
Redaktorzy (rel.)
Promotorzy (rel.)
Ogiela, Marek Romuald
Recenzenci (rel.)
Lubaszewski, Wiesław Michał
Skomorowski, Marek Tadeusz
Projekty badawcze (rel.)
Projekt
Tytuł:
ID:Program:
Instytucja Finansująca
ROR: 
Dane badawcze:
Jednostki organizacyjne (rel.)
Wydarzenia (rel.)
Dyscyplina
Słowa kluczowe
języki formalne - zastosowania naukowe, algorytmy genetyczne, rozpoznawanie obrazów (informatyka), programowanie genetyczne (informatyka)
Dyscyplina (2011-2018)
informatyka
Specjalność
Klasyfikacja MKP
Abstrakt

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ą.

Opis
Bibliogr.
Contains