prikaz prve stranice dokumenta Objektni pristup rješavanju problema rasporeda sati genetičkim algoritmom
No public access
scientific master's theses
Objektni pristup rješavanju problema rasporeda sati genetičkim algoritmom
Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing, 2001. urn:nbn:hr:168:791213
Glavač, Vjekoslav
University of Zagreb
Faculty of Electrical Engineering and Computing
Department of Applied Mathematics

Institutional repository: FER Repository

Cite this document

Glavač, V. (2001). Objektni pristup rješavanju problema rasporeda sati genetičkim algoritmom (Scientific master's theses). Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing. Retrieved from https://urn.nsk.hr/urn:nbn:hr:168:791213

Glavač, Vjekoslav. "Objektni pristup rješavanju problema rasporeda sati genetičkim algoritmom." Scientific master's theses, University of Zagreb, Faculty of Electrical Engineering and Computing, 2001. https://urn.nsk.hr/urn:nbn:hr:168:791213

Glavač, Vjekoslav. "Objektni pristup rješavanju problema rasporeda sati genetičkim algoritmom." Scientific master's theses, University of Zagreb, Faculty of Electrical Engineering and Computing, 2001. https://urn.nsk.hr/urn:nbn:hr:168:791213

Glavač, V. (2001). 'Objektni pristup rješavanju problema rasporeda sati genetičkim algoritmom', Scientific master's theses, University of Zagreb, Faculty of Electrical Engineering and Computing, accessed 22 November 2024, https://urn.nsk.hr/urn:nbn:hr:168:791213

Glavač V. Objektni pristup rješavanju problema rasporeda sati genetičkim algoritmom [Scientific master's theses]. Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing; 2001 [cited 2024 November 22] Available at: https://urn.nsk.hr/urn:nbn:hr:168:791213

V. Glavač, "Objektni pristup rješavanju problema rasporeda sati genetičkim algoritmom", Scientific master's theses, University of Zagreb, Faculty of Electrical Engineering and Computing, Zagreb, 2001. Available at: https://urn.nsk.hr/urn:nbn:hr:168:791213

Metadata
TitleObjektni pristup rješavanju problema rasporeda sati genetičkim algoritmom
Title (english)Object Oriented Approach to Timetable Problem Solving Using a Genetic Algorithm
AuthorVjekoslav Glavač
MentorVedran Mornar (mentor)
Committee memberLeo Budin (predsjednik povjerenstva)
Committee memberVedran Mornar (član povjerenstva)
Committee memberRobert Manger (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Electrical Engineering and Computing
(Department of Applied Mathematics)
Zagreb
Defense date and country2001-06-04, Croatia
Scientific / art field,
discipline and subdiscipline		TECHNICAL SCIENCES
Computing
Universal decimal classification
(UDC)		004 - Computer science and technology. Computing. Data processing
Abstract
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 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.
Abstract (english)
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 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.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:168:791213
Study programmeTitle: Postgraduate master programe in computing
Study programme type: university
Study level: postgraduate
Academic / professional title: magistar inženjer računarstva (magistar inženjer računarstva)
Type of resourceText
File originBorn digital
Access conditionsClosed access
Terms of useLicence In copyright icon
Created on2019-04-16 13:43:21