Solving scheduling problems with genetic programming fitness landscape features

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