Leveraging a Hybrid Genetic Algorithm for the Optimal Teacher Placement

Abstract

The teacher placement problem is a hard problem or a Non-Polynomial Algorithm with factorial complexity. One way to solve this kind of problem is by using Genetic Algorithm. The performance of this Genetic Algorithm can be improved by trying various sub algorithms in generating new chromosomes such as crossbreeding and mutation. In addition, this Genetic Algorithm can also be improved by inserting another algorithm in the middle of the process known as the Hybrid Genetic Algorithm with the intention of preventing the condition of the solution trapped in the local optimum. In this research, a Hybrid Genetic Algorithm is used by using the single point crossover method as the crossover operator and insertion mutation as the mutation operator, and inserting a local search algorithm in the middle. The data used came from the Magelang District Education Office, with a total of 636 teachers and 106 schools. This study found that the Hybrid Genetic Algorithm could always produce better results than the Pure Genetic Algorithm using the population size parameter (20 and 40) and the probability of mutation/crossover (1:100 and 1:200). Using the Hybrid Genetic Algorithm, the shortest total distance is 11,286.908 km, while using the Pure Genetic Algorithm, the shortest distance is 11,562.830 km with the same number of iterations.