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

Authors

  • Ahmad Miftah Fajrin Institut Teknologi Sepuluh Nopember, Surabaya
  • Chastine Fatichah Institut Teknologi Sepuluh Nopember, Surabaya

DOI:

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

Keywords:

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

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.

Author Biographies

Ahmad Miftah Fajrin, Institut Teknologi Sepuluh Nopember, Surabaya

Department of Informatic Engineering

Chastine Fatichah, Institut Teknologi Sepuluh Nopember, Surabaya

Department of Informatic Engineering

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.

Downloads

Published

2020-04-03

How to Cite

[1]
A. M. Fajrin and C. Fatichah, “Multi-parent order crossover mechanism of genetic algorithm for minimizing violation of soft constraint on course timetabling problem”, regist. j. ilm. teknol. sist. inf., vol. 6, no. 1, pp. 43–51, Apr. 2020.

Issue

Vol. 6 No. 1 (2020): January

Section

Article

License


Please find the rights and licenses in Register: Jurnal Ilmiah Teknologi Sistem Informasi. By submitting the article/manuscript of the article, the author(s) agree with this policy. No specific document sign-off is required.

1. License

The non-commercial use of the article will be governed by the Creative Commons Attribution license as currently displayed on Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

2. Author(s)' Warranties

The author warrants that the article is original, written by stated author(s), has not been published before, contains no unlawful statements, does not infringe the rights of others, is subject to copyright that is vested exclusively in the author and free of any third party rights, and that any necessary written permissions to quote from other sources have been obtained by the author(s).

3. User/Public Rights

Register's spirit is to disseminate articles published are as free as possible. Under the Creative Commons license, Register permits users to copy, distribute, display, and perform the work for non-commercial purposes only. Users will also need to attribute authors and Register on distributing works in the journal and other media of publications. Unless otherwise stated, the authors are public entities as soon as their articles got published.

4. Rights of Authors

Authors retain all their rights to the published works, such as (but not limited to) the following rights;

Copyright and other proprietary rights relating to the article, such as patent rights,
The right to use the substance of the article in own future works, including lectures and books,
The right to reproduce the article for own purposes,
The right to self-archive the article (please read out deposit policy),
The right to enter into separate, additional contractual arrangements for the non-exclusive distribution of the article's published version (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal (Register: Jurnal Ilmiah Teknologi Sistem Informasi).
5. Co-Authorship

If the article was jointly prepared by more than one author, any authors submitting the manuscript warrants that he/she has been authorized by all co-authors to be agreed on this copyright and license notice (agreement) on their behalf, and agrees to inform his/her co-authors of the terms of this policy. Register will not be held liable for anything that may arise due to the author(s) internal dispute. Register will only communicate with the corresponding author.

6. Royalties

Being an open accessed journal and disseminating articles for free under the Creative Commons license term mentioned, author(s) aware that Register entitles the author(s) to no royalties or other fees.

7. Miscellaneous

Register will publish the article (or have it published) in the journal if the article’s editorial process is successfully completed. Register's editors may modify the article to a style of punctuation, spelling, capitalization, referencing and usage that deems appropriate. The author acknowledges that the article may be published so that it will be publicly accessible and such access will be free of charge for the readers as mentioned in point 3.