Master's Thesis

Automated Program Design with Large Language Model and Grammatical Evolution

Final Thesis 1.7 MB

Author of thesis: Ing. Michaela Pařilová

Acad. year: 2025/2026

Supervisor: prof. Ing. Lukáš Sekanina, Ph.D.

Reviewer: Ing. Martin Hurta, Ph.D.

Abstract:

Automated program synthesis using grammatical evolution often suffers from a combinatorial explosion of the search space when universal grammars are used. While recent methods use large language models (LLMs) to predict minimal specialized grammars, these static predictions fail if critical rules are omitted. This thesis proposes an iterative grammar refinement (IGR) framework to overcome this limitation. IGR introduces an automated feedback loop that detects evolutionary stagnation, extracts the best failing program, and prompts the LLM to diagnose and iteratively repair the grammar. Evaluated on 28 problems from the PSB1 benchmark suite, IGR solved 18 problems, outperforming standard grammatical evolution and a static LLM baseline. The results demonstrate that using LLMs as dynamic diagnostic agents is an effective strategy for resolving grammar-based bottlenecks in evolutionary program synthesis.

Keywords:

automated program synthesis, grammatical evolution, large language models, genetic programming, evolutionary computation

Date of defence

22.06.2026

Result of the defence

Defended (thesis was successfully defended)

znamkaAznamka

Grading

A

Process of defence

Studentka nejprve prezentovala výsledky, kterých dosáhla v rámci své práce. Komise se poté seznámila s hodnocením vedoucího a posudkem oponenta práce. Studentka následně odpověděla na otázky oponenta a na další otázky přítomných. Komise se na základě posudku oponenta, hodnocení vedoucího, přednesené prezentace a odpovědí studentky na položené otázky rozhodla práci hodnotit stupněm A.

Topics for thesis defence

  1. Na základě jakých kritérií byl pro vaši metodu zvolen model deepseek-v3.2-thinking namísto GPT-4?
  2. Jak vypadá srovnání fitness dosažené vaší metodou s existujícími přístupy a v kolika úlohách je tento rozdíl statisticky významný?
  3. Jaká byla přibližná časová náročnost provedených experimentů a o kolik by se zvýšila při provedení 100 nezávislých běhů pro každé nastavení?
  4. Má LLM přístup k fitness funkci?

Language of thesis

English

Faculty

Department

Study programme

Information Technology and Artificial Intelligence (MITAI)

Specialization

Machine Learning (NMAL)

Composition of Committee

prof. Dr. Ing. Jan Černocký (předseda)
prof. Ing. Martin Čadík, Ph.D. (místopředseda)
doc. Ing. Vladimír Janoušek, Ph.D. (člen)
doc. Ing. Michal Bidlo, Ph.D. (člen)
doc. Ing. František Zbořil, Ph.D. (člen)
Ing. Petr Veigend, Ph.D. (člen)

Diplomantka prozkoumala nové téma vynikajícím způsobem. Vzhledem k náročnosti tématu, množství odvedené práce, dosaženým výsledkům a solidní technické zprávě hodnotím tuto práci stupněm výborně. Dále práci navrhuji na vhodné ocenění.

Evaluation criteria Verbal classification
Informace k zadání

Jedná se o náročnější zadání výzkumného charakteru. Navazuje na výzkumnou činnost realizovanou v oblasti genetického programování výzkumnou skupinou EvoAIHW na UPSY. Diplomantka do evolučního návrhu zabudovala velký jazykový model, který vhodně upravuje gramatiku použitou pro návrh programů. Získané výsledky vylepšují metodu popsanou v referenční publikaci. Zadání bylo splněno v plném rozsahu.

Aktivita při dokončování

Implementace byla dokončena v předstihu. Obsah předfinální verze technické zprávy byl konzultován, mé připomínky byly zapracovány.

Publikační činnost, ocenění

Práce obsahuje zajímavé výsledky, které by mohly být (po doplnění) předmětem vědeckého článku.

Práce s literaturou

Diplomantka samostatně vyhledávala odbornou literaturu a využívala ji.

Aktivita během řešení, konzultace, komunikace

Diplomantka konzultovala dle potřeby, v posledních měsících intenzivně. Na konzultace byla výborně připravena a samostatně navrhovala vhodná pokračování řešení projektu.

Points proposed by supervisor: 95

Grade proposed by supervisor: A

Reviewer’s report
Ing. Martin Hurta, Ph.D.

Studentka splnila zadání, provedla kvalitní rešerši a navrhla i implementovala funkční metodu pro automatizovaný návrh programů založenou na kombinaci GE a LLM. S ohledem na dobrou kvalitu technické zprávy a dosažené výsledky, i přes uvedené dílčí nedostatky experimentální části, navrhuji celkové hodnocení stupněm A – výborně.

Evaluation criteria Verbal classification Points
Rozsah splnění požadavků zadání

Evaluation level: zadání splněno

Zadání bylo splněno.

Rozsah technické zprávy

Evaluation level: je v obvyklém rozmezí

Technická zpráva je svým rozsahem v obvyklém rozmezí.

Prezentační úroveň technické zprávy

Zpráva je logicky strukturovaná a členěná do kapitol, které postupně představují problematiku automatického návrhu programů, genetického programování, gramatické evoluce, velkých jazykových modelů a existujících přístupů kombinujících LLM s evolučními algoritmy. Následně jsou popsány návrh, implementace a experimentální vyhodnocení navržené metody. Teoretická část vhodně shrnuje jednotlivé oblasti související s tématem a systematicky buduje znalostní základ pro návrhovou část. Samotný návrh metody je přehledný a implementace je popsána velmi podrobně, včetně ukázek konfiguračních souborů, implementovaných metod a textových vstupů pro LLM. Experimenty jsou prezentovány v logickém sledu, doplněné odpovídajícími obrázky a slovním komentářem.

Drobné výtky lze směřovat k opakovanému vysvětlování techniky „wrapping“ v kapitole 4.1, k prezentaci některých aspektů návrhu až v části implementace, k nejednoznačnému používání termínu „baseline“ (pro variantu čisté GE i pro metodu citovanou ze zdroje [36]) a k větě odkazující na tabulku 9.3, která je pravděpodobně omylem umístěna o odstavec níže.

94
Formální úprava technické zprávy

Text je dobře čitelný a napsaný kvalitní angličtinou bez zjevných jazykových chyb. Z typografického hlediska lze vytknout pouze použití rastrové grafiky pro schémata návrhu a grafy experimentálních výsledků.

95
Práce s literaturou

Seznam použité literatury obsahuje 38 vhodně zvolených položek (vědecké články a odbornou literaturu), které jsou správně citovány.

95
Realizační výstup

Studentka v rámci práce navrhla a implementovala metodu pro automatizovaný návrh programů kombinující GE a LLM. V této metodě GE zajišťuje nalezení korektního programu, zatímco LLM slouží k iterativnímu omezování prohledávacího prostoru prostřednictvím redukce dostupných gramatických pravidel. Zdrojové kódy jsou implementovány v jazyce Python, jsou logicky strukturované a kvalitně komentované.

V experimentální části jsou nejprve prezentovány výsledky zaměřené na nastavení parametrů navržené metody a následně výsledky jejího porovnání se základní GE a metodou ze zdroje [36], kterou navržená metoda dále rozvíjí. Experimentální vyhodnocení je provedeno na datové sadě PSB1 a je celkově navrženo i prezentováno přehledně a metodicky správně. Nastavení experimentů je popsáno srozumitelně, pouze chybí explicitní uvedení pravděpodobnosti křížení u navržené metody. Prezentované výsledky pro různá nastavení parametrů však ukazují značnou variabilitu (úspěšnost 53%, 43% a 63% pro shodné nastavení), což souvisí zejména s relativně nízkým počtem 30 nezávislých běhů pro každé nastavení. Zvýšení počtu běhů by přispělo k robustnějším závěrům a přesvědčivějšímu statistickému vyhodnocení. Zároveň není zcela přesvědčivě zdůvodněno finální nastavení s populací o velikosti 500 a 50 generacích, přestože výsledky ukazují, že menší populace s větším počtem generací mohou vést k lepším výsledkům.

Při porovnání navržené metody s GE a metodou ze zdroje [36] je důraz kladen především na metriku úspěšnosti na jednotlivých úlohách, neboli v kolika případech metoda nalezne zcela funkční řešení. Podrobnější výsledky jsou uvedeny pro vybrané úlohy, což poskytuje užitečný vhled do chování metod. Pro komplexnější posouzení by však bylo vhodné doplnit také informace o dosažených hodnotách fitness napříč všemi úlohami. Porovnání je navíc provedeno na základě pouze 10 nezávislých běhů, což omezuje sílu statistických závěrů, nikoli však správnost samotného experimentálního postupu.

Vzhledem k tomu, že navržená metoda využívá model z rodiny DeepSeek, zatímco práce [36] pracuje s modelem GPT-4, by bylo přínosné doplnit i experimentální srovnání vlivu použitého LLM na dosažené výsledky.

84
Využitelnost výsledků

Práce představuje novou metodu pro automatizovaný návrh programů, která podle provedených experimentů dosahuje lepších výsledků než současné přístupy v této oblasti. Po rozšíření experimentálního vyhodnocení (zejména zvýšením počtu běhů a zahrnutím analýzy doby běhu a dosažené fitness) by výsledky mohly tvořit dobrý základ vědecké publikace.

Náročnost zadání

Evaluation level: průměrně obtížné zadání

Jedná se o zadání střední obtížnosti, které vyžaduje nastudování genetického programování (GP), velkých jazykových modelů (LLM) a metod kombinujících GP a LLM pro automatizovaný návrh programů. Na základě těchto znalostí bylo následně nutné navrhnout, implementovat a experimentálně vyhodnotit metodu pro automatizovaný návrh programů využívající kombinaci gramatické evoluce (GE) a LLM.

Topics for thesis defence:
  1. Na základě jakých kritérií byl pro vaši metodu zvolen model deepseek-v3.2-thinking namísto GPT-4?
  2. Jak vypadá srovnání fitness dosažené vaší metodou s existujícími přístupy a v kolika úlohách je tento rozdíl statisticky významný?
  3. Jaká byla přibližná časová náročnost provedených experimentů a o kolik by se zvýšila při provedení 100 nezávislých běhů pro každé nastavení?
Points proposed by reviewer: 90

Grade proposed by reviewer: A

Responsibility: Mgr. et Mgr. Hana Odstrčilová