Operatory krzyżowania w ewolucyjnym generowaniu gramatyk bezkontekstowych

• Autorzy: Pałka D. , Piekarczyk M.
• Języki publikacji: PL

Abstrakty

PL

Omówiono trzy rodzaje operatorów krzyżowania stosowanych do celów programowania genetycznego: operatory krzyżowania standardowego, krzyżowania zachowującego rozmiar oraz krzyżowania homologicznego. Przedstawiono wyniki porównujące skuteczność tych operatorów w zastosowaniu ich w celach ewolucyjnego generowania gramatyk bezkontekstowych na podstawie przykładów języka. W ramach prezentowanych wyników pokazany został wpływ różnych rodzajów operatorów krzyżowania na rozmiar osobników powstających w wyniku ewolucji, na wartość ich przystosowania, które jest miarą poprawności znalezionego rozwiązania zadanego problemu, oraz na zróżnicowanie powstającej populacji osobników w poszczególnych pokoleniach ewolucji.

EN

Three types of crossover operators used for genetic programming purposes: standard crossover operator, size fair crossover, and homologous crossover are presented in the article. It also analyses the results of the comparison of the effectives of those operators in evolutionary grammatical inference of context-free grammars based on positive and negative language samples. The results include the influence of various crossover operators on the individuals created by the process of evolution, on their fitness value, which is the measure of the correctness of the solution of a given problem, and on the diversity of the resulting population in given generations of the evolution.

Słowa kluczowe

PL

operatory krzyżowania; krzyżowanie standardowe; krzyżowanie zachowujące rozmiar; krzyżowanie homologiczne

EN

crossover operators; standard crossover; size fair crossover; homologous crossover

• Wydawca: Wydawnictwo Politechniki Częstochowskiej
• Czasopismo: Informatyka Teoretyczna i Stosowana
• Rocznik: 2006
• Tom: R. 6, nr 10
• Strony: 51--62
• Opis fizyczny: Bibliogr. 6 poz., rys.

Twórcy

autor

Pałka D.

autor

Piekarczyk M.

• Katedra Informatyki i Metod Komputerowych, Akademia Pedagogiczna ul. Podchorążych 2, 30-084 Kraków

Bibliografia

• [1] Palka D., Ewolucyjne generowanie gramatyk bezkontekstowych z wykorzystaniem algorytmów genetycznych, Półrocznik AGH Elektrotechnika i Elektronika 2004, 23, 1, 58-63.
• [2] Palka D., Generowanie gramatyk bezkontekstowych dla potrzeb syntaktycznego rozpoznawania wzorców, Informatyka Teoretyczna i Stosowana 2004, 4. 7, 139-147.
• [3] D'haeseleer P., Context preserving crossover in genetic programming, Proceedings of the 1994 IEEF World Congress on Computational Intelligence, 1994, l, 256-261.
• [4] Koza J.R., Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press 1992.
• [5] Langdon W.B., Size fair and homologous tree genetic programming crossovers, Proceedings of the Genetic and Evolutionary Computation Conference 1999, 2, 1092-1097.
• [6] Rosca J.P., Entropy-driven adaptive representation, Proceedings of the Workshop on Genetic Programming: Prom Theory to Real-World Applications, 1995, 9, 23-32.