Rješavanje problema raspoređivanja primjenom značajki krajolika dobrote genetskoga programiranja

disertacija

• Naslov (engleski): Solving scheduling problems with genetic programming fitness landscape features
• Autor: Rebeka Čorić
• Mentor: Domagoj Jakobović (mentor)
• Član povjerenstva: Domagoj Jakobović (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; (Zavod za elektroniku, mikroelektroniku, računalne i inteligentne sustave); Zagreb
• Datum i država obrane: 2021, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo
• Univerzalna decimalna klasifikacija (UDC): 004 - Računalna znanost i tehnologija. Računalstvo. Obrada podataka

Sažetak

Problemi raspoređivanja su NP teški problemi čije se primjene mogu pronaći u raznim područjima. Jedna od hiperheuristika koja se koristi za njihovo rješavanje je genetsko programiranje (GP). Snaga GP-a leži u prilagodljivosti parametara promatranom problemu kako bi se dobili bolji rezultati. Određivanje vrijednosti parametara je dugotrajno pa se često koristi automatizirano određivanje vrijednosti parametara. Kako bi se dobio uvid u strukturu problema, može se iskoristiti analiza krajolika dobrote koja na temelju relevantnih značajki može razlikovati instance problema i zatim se za svaku grupu instanci mogu odrediti odgovarajući parametri. Ova disertacija bavi se istraživanjem značajki krajolika dobrote problema raspoređivanja, određivanjem grupa sličnih instanci problema na temelju odabranih značajki te određivanjem parametara za GP u svakoj od dobivenih grupa. Provedena ispitivanja pokazuju da se grupiranjem instanci i korištenjem parametara prilagođenih grupi primjera problema mogu postići bolji rezultati nego korištenjem ručno određenih parametara. Znanstveni doprinos sastoji se od sljedećih točaka: • Skup operatora za sintaktička stabla u svrhu prolaska kroz prostor pretraživanja slučajnom šetnjom. • Grupiranje problema raspoređivanja temeljeno na značajkama krajolika dobrote prostora rješenja genetskog programiranja. • Određivanje prikladnih parametara genetskog programiranja temeljem krajolika dobrote. • Model učenja koji odabirom ili konstrukcijom značajki krajolika dobrote određuje optimalne parametre za rješavanje problema genetskim programiranjem.

Sažetak (engleski)

Scheduling problems are NP-hard problems that have many applications. One of the hyperheuristics that can be used for solving those problems is genetic programming (GP). The strength of GP lies in the adaptability of its parameters to the problem at hand to get better solutions. Parameter configuration is a long-lasting process and because of that automatic parameter configuration is often used. Fitness landscape analysis can help to obtain insight into the problem structure which can help to differentiate problem instances and determine appropriate parameter values for every cluster of problems. This thesis explores fitness landscape features of scheduling problems, clusters similar instances based on selected features, and determines GP parameters for every obtained cluster. Conducted experiments show that clustering the instances and using appropriate parameters for every cluster yields better results than using manually determined GP parameters. The following original scientific contributions were made in the thesis: • Operator set for syntactic trees in order to obtain random walk in search space. • Grouping of scheduling problems based on fitness landscape characteristics of search space of genetic programming. • Using fitness landscape analysis in order to determine suitable parameters for genetic programming. • Learning model which selects or construct fitness landscape characteristics in order to determine optimal parameters for solving scheduling problems by using genetic programming.

• Ključne riječi: problemi raspoređivanja; genetsko programiranje; analiza krajolika dobrote; stabla; grupiranje; automatizirano određivanje parametara; automatizirani odabir značajki
• Ključne riječi (engleski): scheduling problems; genetic programming; fitness landscape analysis; trees; clustering; automatic parameter configuration; automatic feature selection
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:493940
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: poslijediplomski znanstveni (doktorski); Akademski / stručni naziv: Doktor znanosti (dr. sc.)
• URL zapisa u katalogu: http://lib.fer.hr/cgi-bin/koha/opac-detail.pl?biblionumber=52328
• Vrsta resursa: Tekst
• Opseg: viii, 171 str.
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2022-03-09 14:18:46