Multi Population Hybrid Genetic Algorithms for University Course Timetabling
University course timetabling is one of the important and time consuming issues that each University is involved with at the beginning of each university year. This problem is in class of NP-hard problem and is very difficult to solve by classic algorithms. Therefore optimization techniques are used...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Dunarea de Jos University of Galati
2012-08-01
|
| Series: | Annals of Dunarea de Jos University. Fascicle I : Economics and Applied Informatics |
| Subjects: | |
| Online Access: | http://www.eia.feaa.ugal.ro/sites/default/files/Meysam%20Shahvali%20KOHSHORI_Mehrnaz%20Shirani%20LIRI.pdf http://www.ann.ugal.ro/eco/Doc2012.2/Meysam%20Shahvali%20KOHSHORI_Mehrnaz%20Shirani%20LIRI.pdf |
| _version_ | 1811201742666203136 |
|---|---|
| author | Mehrnaz Shirani LIRI Meysam Shahvali KOHSHORI |
| author_facet | Mehrnaz Shirani LIRI Meysam Shahvali KOHSHORI |
| author_sort | Mehrnaz Shirani LIRI |
| collection | DOAJ |
| description | University course timetabling is one of the important and time consuming issues that each University is involved with at the beginning of each university year. This problem is in class of NP-hard problem and is very difficult to solve by classic algorithms. Therefore optimization techniques are used to solve them and produce optimal or almost optimal feasible solutions instead of exact solutions. Genetic algorithms, because of their multidirectional search property, are considered as an efficient approach for solving this type of problems. In this paper three new hybrid genetic algorithms for solving the university course timetabling problem (UCTP) are proposed: FGARI, FGASA and FGATS. In the proposed algorithms, fuzzy logic is used to measure violation of soft constraints in fitness function to deal with inherent uncertainty and vagueness involved in real life data. Also, randomized iterative local search, simulated annealing and tabu search are applied, respectively, to improve exploitive search ability and prevent genetic algorithm to be trapped in local optimum. The experimental results indicate that the proposed algorithms are able to produce promising results for the UCTP |
| first_indexed | 2024-04-12T02:27:00Z |
| format | Article |
| id | doaj.art-c967f48254164ed5bf024f97d215ff2c |
| institution | Directory Open Access Journal |
| issn | 1584-0409 |
| language | English |
| last_indexed | 2024-04-12T02:27:00Z |
| publishDate | 2012-08-01 |
| publisher | Dunarea de Jos University of Galati |
| record_format | Article |
| series | Annals of Dunarea de Jos University. Fascicle I : Economics and Applied Informatics |
| spelling | doaj.art-c967f48254164ed5bf024f97d215ff2c2022-12-22T03:51:56ZengDunarea de Jos University of GalatiAnnals of Dunarea de Jos University. Fascicle I : Economics and Applied Informatics1584-04092012-08-0112516Multi Population Hybrid Genetic Algorithms for University Course TimetablingMehrnaz Shirani LIRIMeysam Shahvali KOHSHORIUniversity course timetabling is one of the important and time consuming issues that each University is involved with at the beginning of each university year. This problem is in class of NP-hard problem and is very difficult to solve by classic algorithms. Therefore optimization techniques are used to solve them and produce optimal or almost optimal feasible solutions instead of exact solutions. Genetic algorithms, because of their multidirectional search property, are considered as an efficient approach for solving this type of problems. In this paper three new hybrid genetic algorithms for solving the university course timetabling problem (UCTP) are proposed: FGARI, FGASA and FGATS. In the proposed algorithms, fuzzy logic is used to measure violation of soft constraints in fitness function to deal with inherent uncertainty and vagueness involved in real life data. Also, randomized iterative local search, simulated annealing and tabu search are applied, respectively, to improve exploitive search ability and prevent genetic algorithm to be trapped in local optimum. The experimental results indicate that the proposed algorithms are able to produce promising results for the UCTPhttp://www.eia.feaa.ugal.ro/sites/default/files/Meysam%20Shahvali%20KOHSHORI_Mehrnaz%20Shirani%20LIRI.pdf http://www.ann.ugal.ro/eco/Doc2012.2/Meysam%20Shahvali%20KOHSHORI_Mehrnaz%20Shirani%20LIRI.pdfUniversity course timetabling problem(UCTP)Genetic algorithmMulti populationFuzzy logicLocal searchHeurestics |
| spellingShingle | Mehrnaz Shirani LIRI Meysam Shahvali KOHSHORI Multi Population Hybrid Genetic Algorithms for University Course Timetabling Annals of Dunarea de Jos University. Fascicle I : Economics and Applied Informatics University course timetabling problem(UCTP) Genetic algorithm Multi population Fuzzy logic Local search Heurestics |
| title | Multi Population Hybrid Genetic Algorithms for University Course Timetabling |
| title_full | Multi Population Hybrid Genetic Algorithms for University Course Timetabling |
| title_fullStr | Multi Population Hybrid Genetic Algorithms for University Course Timetabling |
| title_full_unstemmed | Multi Population Hybrid Genetic Algorithms for University Course Timetabling |
| title_short | Multi Population Hybrid Genetic Algorithms for University Course Timetabling |
| title_sort | multi population hybrid genetic algorithms for university course timetabling |
| topic | University course timetabling problem(UCTP) Genetic algorithm Multi population Fuzzy logic Local search Heurestics |
| url | http://www.eia.feaa.ugal.ro/sites/default/files/Meysam%20Shahvali%20KOHSHORI_Mehrnaz%20Shirani%20LIRI.pdf http://www.ann.ugal.ro/eco/Doc2012.2/Meysam%20Shahvali%20KOHSHORI_Mehrnaz%20Shirani%20LIRI.pdf |
| work_keys_str_mv | AT mehrnazshiraniliri multipopulationhybridgeneticalgorithmsforuniversitycoursetimetabling AT meysamshahvalikohshori multipopulationhybridgeneticalgorithmsforuniversitycoursetimetabling |