Perbandingan Fluid Genetic Algorithm dan Genetic Algorithm untuk Penjadwalan Perkuliahan

Muhammad Ezar Al Rivan; Bhagaskara Bhagaskara

doi:10.32736/sisfokom.v9i3.879

Authors

Muhammad Ezar Al Rivan STMIK Global Informatika MDP
Bhagaskara Bhagaskara STMIK Global Informatika MDP

DOI:

https://doi.org/10.32736/sisfokom.v9i3.879

Keywords:

Genetic Algorithm, Fluid Genetic Algorithm, Timetabling

Abstract

The lecture schedule is a problem that belongs to the NP-Hard problem and multi-objective problem because it has several variables that affect the preparation of the schedule and has limitations that must be met. One solution that has been found is using a Genetic Algorithm (GA). GA has been proven to be able to provide a schedule that can meet limitations in scheduling. Besides, it also found a new concept of thought from GA, namely the Fluid Genetic Algorithm (FGA). The most visible difference between FGA and GA is that there is no mutation process in each iteration. FGA has a new stage, namely individual born and new constants, namely global learning rate, individual learning rate, and diversity rate. This concept of thinking was tested in previous studies and found that FGA is superior to GA for the problem of finding the optimum value of a predetermined function, but this function is not included in the multi-objective problem. In this study, the testing and comparison of FGA and GA were conducted for the problem of scheduling lectures at STMIK XYZ. Based on the results obtained, FGA can produce a schedule without any hard constraint violations. FGA can be used to solve multi-objective problems. FGA has a smaller number of generations than GA. However, overall GA is superior in producing schedules without any problems.

References

E. Ghasemi, P. Moradi, and M. Fathi, “Integrating ABC with genetic grouping for university course timetabling problem,” in 2015 5th International Conference on Computer and Knowledge Engineering (ICCKE), 2015, pp. 24–29, doi: 10.1109/ICCKE.2015.7365857.

E. A. Abdelhalim and G. A. [El Khayat], “A Utilization-based Genetic Algorithm for Solving the University Timetabling Problem (UGA),” Alexandria Eng. J., vol. 55, no. 2, pp. 1395–1409, 2016, doi: https://doi.org/10.1016/j.aej.2016.02.017.

R. Lewis and J. Thompson, “Analysing the effects of solution space connectivity with an effective metaheuristic for the course timetabling problem,” Eur. J. Oper. Res., vol. 240, no. 3, pp. 637–648, 2015, doi: https://doi.org/10.1016/j.ejor.2014.07.041.

A. A. Mahiba and C. A. D. Durai, “Genetic Algorithm with Search Bank Strategies for University Course Timetabling Problem,” Procedia Eng., vol. 38, pp. 253–263, 2012, doi: https://doi.org/10.1016/j.proeng.2012.06.033.

Y. Lei, J. Shi, and Z. Yan, “A memetic algorithm based on MOEA/D for the examination timetabling problem,” Soft Comput., vol. 22, no. 5, pp. 1511–1523, 2018, doi: 10.1007/s00500-017-2886-y.

L. L. [de Oliveira], A. A. Freitas, and R. Tinós, “Multi-objective genetic algorithms in the study of the genetic code’s adaptability,” Inf. Sci. (Ny)., vol. 425, pp. 48–61, 2018, doi: https://doi.org/10.1016/j.ins.2017.10.022.

C. Akkan and A. Gülcü, “A bi-criteria hybrid Genetic Algorithm with robustness objective for the course timetabling problem,” Comput. Oper. Res., vol. 90, pp. 22–32, 2018, doi: https://doi.org/10.1016/j.cor.2017.09.007.

Y. Fang, X. Xiao, and J. Ge, “Cloud computing task scheduling algorithm based on improved genetic algorithm,” Proc. 2019 IEEE 3rd Inf. Technol. Networking, Electron. Autom. Control Conf. ITNEC 2019, no. Itnec, pp. 852–856, 2019, doi: 10.1109/ITNEC.2019.8728996.

P. Naithani, “Genetic algorithm based scheduling to reduce energy consumption in cloud,” PDGC 2018 - 2018 5th Int. Conf. Parallel, Distrib. Grid Comput., pp. 616–620, 2018, doi: 10.1109/PDGC.2018.8745801.

A. H. Yousef, C. Salama, M. Y. Jad, T. El-Gafy, M. Matar, and S. S. Habashi, “A GPU based genetic algorithm solution for the timetabling problem,” in 2016 11th International Conference on Computer Engineering Systems (ICCES), 2016, pp. 103–109, doi: 10.1109/ICCES.2016.7821982.

S. Parera, H. T. Sukmana, and L. K. Wardhani, “Application of genetic algorithm for class scheduling (Case study: Faculty of science and technology UIN Jakarta),” in 2016 4th International Conference on Cyber and IT Service Management, 2016, pp. 1–5, doi: 10.1109/CITSM.2016.7577525.

R. Jafari-Marandi and B. K. Smith, “Fluid Genetic Algorithm (FGA),” J. Comput. Des. Eng., vol. 4, no. 2, pp. 158–167, Apr. 2017, doi: 10.1016/j.jcde.2017.03.001.

R. E. Febrita and W. F. Mahmudy, “Modified genetic algorithm for high school time-table scheduling with fuzzy time window,” in 2017 International Conference on Sustainable Information Engineering and Technology (SIET), 2017, pp. 88–92, doi: 10.1109/SIET.2017.8304115.

W. Liu, H. Zhu, Y. Wang, S. Zhou, Y. Bai, and C. Zhao, “Topology optimization of support structure of telescope skin based on bit-matrix representation NSGA-II,” Chinese J. Aeronaut., vol. 26, no. 6, pp. 1422–1429, Dec. 2013, doi: 10.1016/j.cja.2013.07.046.

S. Gao and C. W. de Silva, “A modified estimation distribution algorithm based on extreme elitism,” Biosystems, vol. 150, pp. 149–166, Dec. 2016, doi: 10.1016/j.biosystems.2016.10.001.