Multi-parent order crossover mechanism of genetic algorithm for minimizing violation of soft constraint on course timetabling problem

Ahmad Miftah Fajrin; Chastine Fatichah

doi:10.26594/register.v6i1.1663

Multi-parent order crossover mechanism of genetic algorithm for minimizing violation of soft constraint on course timetabling problem

Ahmad Miftah Fajrin^(1*), Chastine Fatichah⁽²⁾,

(1) Institut Teknologi Sepuluh Nopember, Surabaya
(2) Institut Teknologi Sepuluh Nopember, Surabaya
(*) Corresponding Author

Ahmad Miftah Fajrin
Chastine Fatichah

Abstract

A crossover operator is one of the critical procedures in genetic algorithms. It creates a new chromosome from the mating result to an extensive search space. In the course timetabling problem, the quality of the solution is evaluated based on the hard and soft constraints. The hard constraints need to be satisfied without violation while the soft constraints allow violation. In this research, a multi-parent crossover mechanism is used to modify the classical crossover and minimize the violation of soft constraints, in order to produce the right solution. Multi-parent order crossover mechanism tends to produce better chromosome and also prevent the genetic algorithm from being trapped in a local optimum. The experiment with 21 datasets shows that the multi-parent order crossover mechanism provides a better performance and fitness value than the classical with a zero fitness value or no violation occurred. It is noteworthy that the proposed method is effective to produce available course timetabling.

Keywords

course timetabling problem; Genetic Algorithm; multi-parent crossover; order crossover; soft constraint

Full Text:

Article

References

J. S. Gill and G. k. Kaur, "Optimizing the Energy Efficiency of the Modern Data Centers using Ant Colony Optimization," Indian Journal of Science and Technology, vol. 9, no. S1, 2016.

S. Innet, "A noval approach of genetic algorithm for solving examination timetabling problems: A case study of Thai Universities," in 13th International Symposium on Communications and Information Technologies (ISCIT), Surat Thani, Thailand, 2013.

M. Assi, B. Halawi and R. A. Haraty, "Genetic Algorithm Analysis using the Graph Coloring Method for Solving the University Timetable Problem," Procedia Computer Science, vol. 126, no. 2018, pp. 899-906, 2018.

H. Babaei, J. Karimpour and A. Hadidi, "A survey of approaches for university course timetabling problem," Computers & Industrial Engineering, vol. 86, no. August, pp. 43-59, 2015.

N. Metawa and M. K. H. M. Elhoseny, "Genetic algorithm based model for optimizing bank lending decisions," Expert Systems with Applications, vol. 80, no. September, pp. 75-82, 2017.

R. Kumar, G. Gopal and R. Kumar, "Novel Crossover Operator for Genetic Algorithm for Permutation Problems," International Journal of Soft Computing and Engineering (IJSCE), vol. 3, no. 2, pp. 252-258, 2013.

Y. Song, F. Wang and X. Chen, "An improved genetic algorithm for numerical function optimization," Applied Intelligence, vol. 49, no. 5, pp. 1880-1902, 2018.

W. Chinnasri, S. Krootjohn and N. Sureerattanan, "Performance comparison of Genetic Algorithm's crossover operators on University Course Timetabling Problem," in 8th International Conference on Computing Technology and Information Management (NCM and ICNIT), Seoul, South Korea, 2012.

S. S. A. Alves, S. A. F. Oliveira and A. R. R. Neto, "A Recursive Genetic Algorithm-Based Approach for Educational Timetabling Problems," in Designing with Computational Intelligence, Cham, pp. 161-175,2017.

C. Akkan and A. Gülcü, "A bi-criteria hybrid Genetic Algorithm with robustness objective for the course timetabling problem," Computers & Operations Research, vol. 90, no. February, pp. 22-32, 2018.

M. Z. Ali, N. H. Awad, P. N. Suganthan, A. M. Shatnawi and R. G. Reynolds, "An improved class of real-coded Genetic Algorithms for numerical optimization," Neurocomputing, vol. 275, no. January, pp. 155-166, 2018.

X. Zhao, J. Chen, R. Li, D. Gong and X. Li, "An Orthogonal Genetic Algorithm with Multi-parent Multi-point Crossover for Knapsack Problem," in International Conference on Bio-Inspired Computing: Theories and Applications BIC-TA 2018: Bio-inspired Computing: Theories and Applications, Singapore, 2018.

D. Kristianto, C. Fatichah, B. Amaliah and K. Sambodho, "Prediction of Wave-induced Liquefaction using Artificial Neural Network and Wide Genetic Algorithm," Lontar Komputer: Jurnal Ilmiah Teknologi Informasi, vol. 8, no. 1, pp. 1-10, 2017.

M. S. Kohshori, D. Zeynolabedini, M. S. Liri and L. Jadidi, "Multi Population Hybrid Genetic Algorithms for University Course Timetabling Problem," I.J. Information Technology and Computer Science, vol. 4, no. 6, pp. 1-11, 2012.

J. B. Matias, A. C. Fajardo and R. M. Medina, "A fair course timetabling using genetic algorithm with guided search technique," in 5th International Conference on Business and Industrial Research (ICBIR), Bangkok, Thailand, 2018.

T. Song, S. Liu, X. Tang, X. Peng and M. Chen, "An iterated local search algorithm for the University Course Timetabling Problem," Applied Soft Computing, vol. 68, no. July, pp. 597-608, 2018.

S. Jaengchuea and D. Lohpetch, "A hybrid genetic algorithm with local search and tabu search approaches for solving the post enrolment based course timetabling problem: Outperforming guided search genetic algorithm," in 7th International Conference on Information Technology and Electrical Engineering (ICITEE), Chiang Mai, Thailand, 2015.

H. Sani and M. Yabo, "Solving timetabling problems using genetic algorithm technique," Int. J. Comput. Appl, vol. 134, no. 15, pp. 33-38, 2016.

A. Hideg, "Comparing genetic operators for the timetabling problem," in 13th International Symposium on Applied Machine Intelligence and Informatics (SAMI), Herl'any, Slovakia, 2015.

S. Karakatič and ViliPodgorelec, "A survey of genetic algorithms for solving multi depot vehicle routing problem," Applied Soft Computing, vol. 27, no. February, pp. 519-532, 2015.

S. Abdullah, H. Turabieh, B. McCollum and P. McMullan, "A hybrid metaheuristic approach to the university course timetabling problem," Journal of Heuristics, vol. 18, p. 1–23, 2012.

DOI: https://doi.org/10.26594/register.v6i1.1663