Naslov Objektni pristup rješavanju problema rasporeda sati genetičkim algoritmom
Naslov (engleski) Object Oriented Approach to Timetable Problem Solving Using a Genetic Algorithm
Autor Vjekoslav Glavač
Mentor Vedran Mornar (mentor)
Član povjerenstva Leo Budin (predsjednik povjerenstva)
Član povjerenstva Vedran Mornar (član povjerenstva)
Član povjerenstva Robert Manger (član povjerenstva)
Ustanova koja je dodijelila akademski / stručni stupanj Sveučilište u Zagrebu Fakultet elektrotehnike i računarstva (Zavod za primijenjenu matematiku) Zagreb
Datum i država obrane 2001-06-04, 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 Genetički algoritmi danas predstavljaju moćnu adaptivnu metodu rješavanja mnogih kombinatornih problema i problema optimizacije. Od posebnog je interesa rješavanje složenih, NP teških kombinatornih problema, a jedan od takvih problema je i izrada školskog rasporeda sati. Problem se u osnovi sastoji od smještanja svih (nastavnim planom određenih) predavanja u unaprijed definirani skup vremenskih termina (sati) uz poštivanje određenih ograničenja. U ovom radu načinjen je genetički algoritam i
... Više računalni program za izradu školskog rasporeda sati koji uzima u obzir sve specifičnosti hrvatskog školstva. Algoritam je verificiran na realnom slučaju. Za probne podatke uzeta je gimnazija u Bjelovaru s nastavnim programom za 1999/2000. školsku godinu. Cilj je bio pronaći alternativu napornoj ručnoj izradi rasporeda i ocijeniti primjenjivost, učinkovitost i ograničenja genetičkog algoritma na ovoj problematici u realnim uvjetima. Provedeni su pokusi s različitim varijantama genetičke jezgre algoritma, a isprobana je i hibridizacija s nekoliko tehnika lokalne potrage i simulacijom klasičnih metoda. Algoritam je implementiran u objektnom programskom jeziku Smalltalk u kombinaciji s DB2 bazom podataka u okviru razvojnog alata IBM VisualAge for Smalltalk. Rad je podijeljen u nekoliko cjelina. Na početku je ukratko predstavljena povijest genetičkih algoritama, osnovni pojmovi, operatori, teoretska podloga i usporedba s ostalim tehnikama optimizacije. Sljedeće poglavlje općenito opisuje problematiku rasporeda sati uz matematički model i iznosi dosadašnje rezultate u primjeni genetičkih algoritama u rješavanju problematike. Četvrto poglavlje detaljno opisuje problem školskog rasporeda u Hrvatskoj sa svim specifičnostima, oslanjajući se na primjer bjelovarske gimnazije. U petom poglavlju opisan je korišteni algoritam, njegov dizajn i implementacija na računalu. U sljedećem poglavlju prikazani su dobiveni rezultati i performanse algoritma. Sedmo poglavlje donosi ocjenu rezultata i zaključke. Sakrij dio sažetka
Sažetak (engleski) Today, genetic algorithms represent a powerful adaptive method in solving many optimization and combinatorial problems. Solving complex, NP hard combinatorial and optimization problems is of particular interest and school timetable problem is one of that kind. The essence of the problem is placing all the lectures (determined by a curriculum) in a set of predefined timeslots without breaking certain constraints at the same time. A genetic algorithm and a computer program for creating a
... Više school timetable were developed in this thesis. All specific details of Croatian school system were taken into account and the solution was tested on a real world problem. The curriculum for school year 1999/2000 of Bjelovar grammar school was taken as a test set of data. The goal was to find an alternative solution to hard manual process of creating a school timetable and to estimate usefulness, performance and limitations of genetic algorithms when applied to real timetable problems. Different variations of genetic kernel of algorithm were tested. Hybridization with a few local search techniques and simulated manual methods were also tried. Algorithm was implemented with object oriented programming language Smalltalk and DB2 database within IBM VisualAge for Smalltalk developing environment. The thesis is organized as follows. First of all, a short history of genetic algorithms, basic terms, operators, theoretical background and comparison with other optimization techniques are presented. The next chapter describes the timetable problem in general using a mathematical model. It outlines current achievements in applying genetic algorithms in solving timetable problems. The fourth chapter brings detailed description of the school timetable problem in Croatia with reference to Bjelovar grammar school example. Design and computer implementation of the algorithm are described in the fifth chapter. Obtained results and algorithm performance are presented in the next chapter. The seventh chapter brings the evaluation of obtained results and conclusions. Sakrij dio sažetka
Ključne riječi
Genetički algoritam
memetički algoritam
raspored sati
indirektna reprezentacija
heurističke metode
hibridizacija
lokalna potraga
objektno orijentirana paradigma
Ključne riječi (engleski)
Genetic algorithm
memetic algorithm
timetable
indirect representation
heuristic methods
hybridization
local search
object oriented paradigm
Jezik hrvatski
URN:NBN urn:nbn:hr:168:791213
Studijski program Naziv: Računarstvo Vrsta studija: sveučilišni Stupanj studija: poslijediplomski znanstveni (magistarski) Akademski / stručni naziv: magistar inženjer računarstva (mag. ing. comp.)
Vrsta resursa Tekst
Način izrade datoteke Izvorno digitalna
Prava pristupa Zatvoreni pristup
Uvjeti korištenja
Datum i vrijeme pohrane 2019-04-16 13:43:21