Evolucija strategija zamjene stranica korištenjem gramatičke evolucije

undergraduate thesis

• Title (english): Evolving cache replacement policies using grammatical evolution
• Author: Mihael Miličević
• Mentor: Domagoj Jakobović (mentor)
• Committee member: Domagoj Jakobović (predsjednik povjerenstva)
• Committee member: Josip Jukić (član povjerenstva)
• Committee member: Franjo Matković (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2022-07-15, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Genetsko programiranje je grana evolucijskog računarstva u kojoj populaciju čine računalni programi. Gramatička evolucija je popularan pristup genetskom programiranju koji se bazira na formalnim gramatikama, sposoban evoluirati programe u proizvoljnom jeziku, koristeći polja cijelih brojeva fiksne duljine za genotipe, kontekstno neovisnu gramatiku za definiciju jezika, i mapiranje s genotipa na fenotip koje koristi definiranu gramatiku za preslikavanje s polja cijelih brojeva na računalne programe. Evolucija strategija zamjene stranica je popularan problem u području genetskog programiranja. Tema ovog rada je korištenje gramatičke evolucije za evoluiranje strategija zamjene stranica. Generirane strategije su uspoređene s klasičnim heurističkim pristupima za upravljanje memorijom, uključujući algoritme FIFO, LRU i CLOCK.

Abstract (english)

Genetic programming is a branch of evolutionary computing in which the population consists of computer programs. Grammatical evolution is a popular grammar-based approach to genetic programming, capable of evolving programs in an arbitrary language, using fixed-length arrays of integers as genotypes, a context-free grammar for the definition of the language, and a genotype-phenotype mapping which uses the specified grammar to map integer arrays to computer programs. Evolving cache replacement policies is a popular benchmark problem in the field of genetic programming. The topic of this thesis is using grammatical evolution to evolve cache replacement policies. Generated strategies are compared to classic heuristic approaches to cache management, including FIFO, LRU and CLOCK algorithms.

• Keywords: evolucijsko računarstvo; genetsko programmiranje; genetski algoritam; gramatička evolucija; strategije zamjene stranica; optimizacija; formalne gramatike; ECF
• Keywords (english): evolutionary computing; genetic programming; genetic algorithm; grammatical evolution; cache replacement policies; optimization; formal grammars; ECF
• Language: english
• URN:NBN: urn:nbn:hr:168:228982
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-15 10:52:18