Hybridizing Genetic Algorithm with Biased Chance Local Search
This paper explores university course timetabling
problem. There are several characteristics that make scheduling and
timetabling problems particularly difficult to solve: they have huge
search spaces, they are often highly constrained, they require
sophisticated solution representation schemes, and they usually
require very time-consuming fitness evaluation routines. Thus
standard evolutionary algorithms lack of efficiency to deal with
them. In this paper we have proposed a memetic algorithm that
incorporates the problem specific knowledge such that most of
chromosomes generated are decoded into feasible solutions.
Generating vast amount of feasible chromosomes makes the progress
of search process possible in a time efficient manner. Experimental
results exhibit the advantages of the developed Hybrid Genetic
Algorithm than the standard Genetic Algorithm.
[1] Abdullah S. and H. Turabieh, (2008). Generating University Course
Timetable Using Genetic Algorithms and Local Search. Third 2008
International Conference on Convergence and Hybrid Information
Technology.
[2] Abdullah, S., E. K. Burke, B. McCollum, (2005). An Investigation of
Variable Neighborhood Search for Course Timetabling. In: The
Proceedings of the 2nd Multidisciplinary International Conference on
Scheduling: Theory and Applications (MISTA 2005), New York, USA,
July 18 -21, pp. 413-427.
[3] Abdullah, S., E. K. Burke, B. McCollum, (2007). A hybrid evolutionary
approach to the university course timetabling problem. IEEE congress
on evolutionary computation 2007, pp. 1764-1768, Singapore.
[4] Al-Betar, M. A. and A. T. Khader, (2010). A harmony search algorithm
for university course timetabling. Annals of Operations Research, In
press.
[5] Aubin, J. and J. A. Ferland, (1989). A Large Scale Timetabling Problem.
Computers and Operational Research 16(1): 67-77.
[6] Balakrishnan, N., Lucena, A., Wong, R.T., (1992). Scheduling
examinations to reduce second-order conflicts. Computers and
Operations Research 19, 353-361.
[7] Brailsford, S. C., C. N. Potts, B. M. Smith, (1999). Constraint
satisfaction problems: Algorithms and applications. European Journal of
Operational Research 119, 557-581.
[8] Burke E. K. and J. D. Landa Silva, (2005). The Design of Memetic
Algorithms for Scheduling and Timetabling Problems, in "Recent
Advances in Memetic Algorithms", Springer Berlin / Heidelberg, 289-
311.
[9] Burke E. K. and J. P. Newall, (1999). A Multi-Stage Evolutionary
Algorithm for Timetable Problem, IEEE Transactions in Evolutionary
Computation 3(1), 63-74.
[10] Burke, E. K. and S. Petrovic, (2002). Recent research directions in
automated timetabling. European Journal of Operational Research,
140(2): 266-280.
[11] Carter, M. W. and G. Laporte, (1998). Recent developments in practical
course timetabling. Proc of the 2nd Int Conf on Practice and Theory of
Automated Timetabling, LNCS 1408, pp. 3-19.
[12] Carter, M. W., (1986). A survey of practical applications of examination
timetabling algorithms. Operations Research 34, 193-202.
[13] de Werra, D., (1985). An introduction to timetabling. European Journal
of Operational Research 19, 151-162.
[14] Eiselt, H. A. and G. Laporte, (1987). Combinatorial Optimization
Problems with Soft and Hard Requirements. Journal of the Operational
Research Society 38: 785-795.
[15] Even, S., A. Itai, and A. Shamir, (1976). On the complexity of timetable
and multicommodity flow problems. SIAM Journal on Computing, 5(4),
691-703.
[16] Hart, W. E., N. Krasnogor and J. E. Smith, (2004). Memetic
Evolutionary Algorithms, Recent Advances in Memetic Algorithms:
Studies in Fuzziness and Soft Computing, Springer-Verlag, 3-27.
[17] Jat, S. N. and S. Yang, (2008). A Memetic Algorithm for the University
Course Timetabling Problem. 20th IEEE International Conference on
Tools with Artificial Intelligence.
[18] Krasnogor N., (2002). Studies on the theory and design space of
memetic algorithms. PhD thesis, Faculty of computing, engineering and
mathematical sciences, University of the West of England, UK.
[19] Rossi-Doria O., M. Sampels, M. Birattari, M. Chiarandini, M. Dorigo, L.
Gambardella, J. Knowles, M. Manfrin, M. Mastrolilli, B. Paechter, L.
Paquete, and T. Stutzle, (2002). A comparison of the performance of
different metaheuristics on the timetabling problem. Lecture Notes in
Computer Science 2740, pp. 329-351.
[20] Talbi, E. G., (2002). A Taxonomy of hybrid metaheuristics. Journal of
heuristics, 8, 541-564.
[1] Abdullah S. and H. Turabieh, (2008). Generating University Course
Timetable Using Genetic Algorithms and Local Search. Third 2008
International Conference on Convergence and Hybrid Information
Technology.
[2] Abdullah, S., E. K. Burke, B. McCollum, (2005). An Investigation of
Variable Neighborhood Search for Course Timetabling. In: The
Proceedings of the 2nd Multidisciplinary International Conference on
Scheduling: Theory and Applications (MISTA 2005), New York, USA,
July 18 -21, pp. 413-427.
[3] Abdullah, S., E. K. Burke, B. McCollum, (2007). A hybrid evolutionary
approach to the university course timetabling problem. IEEE congress
on evolutionary computation 2007, pp. 1764-1768, Singapore.
[4] Al-Betar, M. A. and A. T. Khader, (2010). A harmony search algorithm
for university course timetabling. Annals of Operations Research, In
press.
[5] Aubin, J. and J. A. Ferland, (1989). A Large Scale Timetabling Problem.
Computers and Operational Research 16(1): 67-77.
[6] Balakrishnan, N., Lucena, A., Wong, R.T., (1992). Scheduling
examinations to reduce second-order conflicts. Computers and
Operations Research 19, 353-361.
[7] Brailsford, S. C., C. N. Potts, B. M. Smith, (1999). Constraint
satisfaction problems: Algorithms and applications. European Journal of
Operational Research 119, 557-581.
[8] Burke E. K. and J. D. Landa Silva, (2005). The Design of Memetic
Algorithms for Scheduling and Timetabling Problems, in "Recent
Advances in Memetic Algorithms", Springer Berlin / Heidelberg, 289-
311.
[9] Burke E. K. and J. P. Newall, (1999). A Multi-Stage Evolutionary
Algorithm for Timetable Problem, IEEE Transactions in Evolutionary
Computation 3(1), 63-74.
[10] Burke, E. K. and S. Petrovic, (2002). Recent research directions in
automated timetabling. European Journal of Operational Research,
140(2): 266-280.
[11] Carter, M. W. and G. Laporte, (1998). Recent developments in practical
course timetabling. Proc of the 2nd Int Conf on Practice and Theory of
Automated Timetabling, LNCS 1408, pp. 3-19.
[12] Carter, M. W., (1986). A survey of practical applications of examination
timetabling algorithms. Operations Research 34, 193-202.
[13] de Werra, D., (1985). An introduction to timetabling. European Journal
of Operational Research 19, 151-162.
[14] Eiselt, H. A. and G. Laporte, (1987). Combinatorial Optimization
Problems with Soft and Hard Requirements. Journal of the Operational
Research Society 38: 785-795.
[15] Even, S., A. Itai, and A. Shamir, (1976). On the complexity of timetable
and multicommodity flow problems. SIAM Journal on Computing, 5(4),
691-703.
[16] Hart, W. E., N. Krasnogor and J. E. Smith, (2004). Memetic
Evolutionary Algorithms, Recent Advances in Memetic Algorithms:
Studies in Fuzziness and Soft Computing, Springer-Verlag, 3-27.
[17] Jat, S. N. and S. Yang, (2008). A Memetic Algorithm for the University
Course Timetabling Problem. 20th IEEE International Conference on
Tools with Artificial Intelligence.
[18] Krasnogor N., (2002). Studies on the theory and design space of
memetic algorithms. PhD thesis, Faculty of computing, engineering and
mathematical sciences, University of the West of England, UK.
[19] Rossi-Doria O., M. Sampels, M. Birattari, M. Chiarandini, M. Dorigo, L.
Gambardella, J. Knowles, M. Manfrin, M. Mastrolilli, B. Paechter, L.
Paquete, and T. Stutzle, (2002). A comparison of the performance of
different metaheuristics on the timetabling problem. Lecture Notes in
Computer Science 2740, pp. 329-351.
[20] Talbi, E. G., (2002). A Taxonomy of hybrid metaheuristics. Journal of
heuristics, 8, 541-564.
@article{"International Journal of Information, Control and Computer Sciences:53860", author = "Mehdi Basikhasteh and Mohamad A. Movafaghpour", title = "Hybridizing Genetic Algorithm with Biased Chance Local Search", abstract = "This paper explores university course timetabling
problem. There are several characteristics that make scheduling and
timetabling problems particularly difficult to solve: they have huge
search spaces, they are often highly constrained, they require
sophisticated solution representation schemes, and they usually
require very time-consuming fitness evaluation routines. Thus
standard evolutionary algorithms lack of efficiency to deal with
them. In this paper we have proposed a memetic algorithm that
incorporates the problem specific knowledge such that most of
chromosomes generated are decoded into feasible solutions.
Generating vast amount of feasible chromosomes makes the progress
of search process possible in a time efficient manner. Experimental
results exhibit the advantages of the developed Hybrid Genetic
Algorithm than the standard Genetic Algorithm.", keywords = "University Course Timetabling, Memetic Algorithm, Biased Chance Assignment, Optimization.", volume = "5", number = "9", pages = "989-6", }
