Órarendtervezés genetikus algoritmus segítségével
Az órarendtervezés öt évtizede intenzíven kutatott problémakör, mivel ismert NP-teljes feladatról van szó [1]. Egy órarend elkészítése során korlátozott erőforrások figyelembevételével kell előállítani egy olyan beosztást (helyszínek, oktatók, csoportok és egyéb erőforrások összerendelését), mely adott feltételeknek felel meg. A probléma nem csak a lehetséges megoldások megtalálásáról szól, de azok között az adott mérőszámok szerinti optimum megkereséséről is.
Dolgozatomban a 2007-es International Timetabling Contest által kiírt feladatot oldottam meg, mely egy valós, egyetemi órarend elkészítésén alapul. A verseny lezárása óta számos, az órarendkészítéssel kapcsolatos kutatás vette kiindulási alapul ezt az adathalmazt és igyekeztek különböző módszerekkel minél jobb megoldásokat adni. A nagyméretű keresési tér miatt én genetikus algoritmus segítségével adtam az optimumhoz konvergáló megoldást. Dolgozatomban bemutatom és mérésekkel alátámasztom, miként lehet egy órarendtervező algoritmust a feladathoz igazítani, és konkrét módszereket ajánlok a konvergencia gyorsítására.
Az elkészült algoritmusom képes a feltételeknek megfelelő órarendet előállítani, majd a megoldásokat iteratívan javítva az optimumhoz konvergáló eredményt adni. Amennyiben a bemeneti és kimeneti formátumok megfelelnek a fenti verseny formátumának, szinte bármely más órarend-készítési feladatra képes lehetséges megoldást adni.
Felhasznált irodalom:
[1] S. Even, A. Itai, A. Shamir, On the complexity of time table and multi-commodity flow problems, 1976.
szerző
-
Hideg Attila Dr.
mérnökinformatikus
nappali
konzulens
-
Dr. Kővári Bence
docens, Automatizálási és Alkalmazott Informatikai Tanszék
