Implementation of Hybrid Genetic Algorithm for Solving the Teacher Placement Problem

Haris Sriwindono; Ni Komang Ayu Wirayanti

doi:10.18535/sshj.v9i01.1460

Abstract

The teacher placement problem is a combinatorial problem that would take a very long time to solve in a deterministic way. In this study, the problem will be solved using a hybrid genetic algorithm, which combines genetic algorithms with local search methods. The genetic algorithm operators used include roulette wheel selection, two point crossover, and scramble mutation. While the local search used is reverse, insert, and swap local search. The results showed that from the three experiments using hybrid genetic algorithms, it was found that hybrid genetic algorithms were more effective than ordinary genetic algorithms. The use of hybrid genetic algorithm with swap local search technique produces the best total minimum distance (10099.09 km) at a mutation probability ratio of 1:250, number of chromosomes 10, and number of iterations 500. The hybrid genetic algorithm can improve the placement of teachers and is expected to contribute to improving the quality of education in Magelang district where the primary data is obtained.

Keywords

AgricultureCrops ProductionAgricultural Production

References

Park, Yang-Byung, and Sung-Chul Hong. "Integrated production and distribution planning for single-period inventory products." Taylor & Francis, vol. 22, no. 5, (2009), p. 443-457.Google Scholar ↗
Estivill‐Castro, Vladimir. The design of competitive algorithms via genetic algorithms. (2002)Google Scholar ↗
Park, Ho, Jae, et al. "Optimal Project Planning for Public Rental Housing in South Korea." Multidisciplinary Digital Publishing Institute, vol. 12, no. 2, (2020), p. 600-600.Google Scholar ↗
Swerhun, Mekaal, et al. "A summary of the prevalence of Genetic Algorithms in Bioinformatics from 2015 onwards." Cornell University, (2020)Google Scholar ↗
Srinivas, M., and L.M. Patnaik. "Genetic algorithms: a survey." IEEE Computer Society, vol. 27, no. 6, (1994), p. 17-26.Google Scholar ↗
Mitchell, Melanie. An Introduction to Genetic Algorithms. (1998)Google Scholar ↗
H. Sriwindono, P.H.P. Rosa, A.M. Polina, and R.A. Nugroho, “The Model of Elementary Teacher School Placement in Magelang District by Using Genetic Algorithm,” In Proc. CSAI’17, (2017), p. 143.Google Scholar ↗
P.H.P. Rosa, H. Sriwindono, R.A. Nugroho, A.M. Polina, and K. Pinaryanto, “Comparison of Crossover and Mutation Operators to Solve Teachers Placement Problem by Using Genetic Algorithm,” Journal of Physics: Conference Series, vol. 1566, no. 1, (2020) pp. 012021Google Scholar ↗
H. Sriwindono, P.H.P. Rosa, and K. Pinaryanto, “The Teacher Placement using K-Means Clustering and Genetic Algorithm,” In Proc. CORIS’22, vol. 4, No. 1. (2022) p.43-51Google Scholar ↗
Whitley, Darrell. "A genetic algorithm tutorial." Springer Science+Business Media, vol. 4, no. 2, (1994)Google Scholar ↗
Spears, M., William, et al. "Evolutionary Algorithms: The Role of Mutation and Recombination." Springer Nature, (2000)Google Scholar ↗
Yao, Xin. "An empirical study of genetic operators in genetic algorithms." Elsevier BV, vol. 38, no. 1-5, (1993)Google Scholar ↗
Chan, Yan, Kit, et al. A Taguchi method-based crossover operator for the parametrical problems. (2004)Google Scholar ↗

[refR-1] Park, Yang-Byung, and Sung-Chul Hong. "Integrated production and distribution planning for single-period inventory products." Taylor & Francis, vol. 22, no. 5, (2009), p. 443-457.Google Scholar ↗

[refR-2] Estivill‐Castro, Vladimir. The design of competitive algorithms via genetic algorithms. (2002)Google Scholar ↗

[refR-3] Park, Ho, Jae, et al. "Optimal Project Planning for Public Rental Housing in South Korea." Multidisciplinary Digital Publishing Institute, vol. 12, no. 2, (2020), p. 600-600.Google Scholar ↗

[refR-4] Swerhun, Mekaal, et al. "A summary of the prevalence of Genetic Algorithms in Bioinformatics from 2015 onwards." Cornell University, (2020)Google Scholar ↗

[refR-5] Srinivas, M., and L.M. Patnaik. "Genetic algorithms: a survey." IEEE Computer Society, vol. 27, no. 6, (1994), p. 17-26.Google Scholar ↗

[refR-6] Mitchell, Melanie. An Introduction to Genetic Algorithms. (1998)Google Scholar ↗

[refR-7] H. Sriwindono, P.H.P. Rosa, A.M. Polina, and R.A. Nugroho, “The Model of Elementary Teacher School Placement in Magelang District by Using Genetic Algorithm,” In Proc. CSAI’17, (2017), p. 143.Google Scholar ↗

[refR-8] P.H.P. Rosa, H. Sriwindono, R.A. Nugroho, A.M. Polina, and K. Pinaryanto, “Comparison of Crossover and Mutation Operators to Solve Teachers Placement Problem by Using Genetic Algorithm,” Journal of Physics: Conference Series, vol. 1566, no. 1, (2020) pp. 012021Google Scholar ↗

[refR-9] H. Sriwindono, P.H.P. Rosa, and K. Pinaryanto, “The Teacher Placement using K-Means Clustering and Genetic Algorithm,” In Proc. CORIS’22, vol. 4, No. 1. (2022) p.43-51Google Scholar ↗

[refR-10] Whitley, Darrell. "A genetic algorithm tutorial." Springer Science+Business Media, vol. 4, no. 2, (1994)Google Scholar ↗

[refR-11] Spears, M., William, et al. "Evolutionary Algorithms: The Role of Mutation and Recombination." Springer Nature, (2000)Google Scholar ↗

[refR-12] Yao, Xin. "An empirical study of genetic operators in genetic algorithms." Elsevier BV, vol. 38, no. 1-5, (1993)Google Scholar ↗

[refR-13] Chan, Yan, Kit, et al. A Taguchi method-based crossover operator for the parametrical problems. (2004)Google Scholar ↗