Optimization of Genetic Algorithm Computation Time with Mutation Probability Variations in Course Scheduling

Abstract

Genetic Algorithm (GA) often requires a long computation time due to the complexity of its processes. Therefore, efforts are needed to optimize GA computation time, particularly in scheduling lectures at the Electrical Engineering Study Program of Universitas Negeri Medan, which is the focus of this research. One possible approach is determining the appropriate mutation probability (Pm) value. This study employs the Mutation Probability Variation Method, where Pm is constrained between 0 and 1 and varied from a minimum value of 0.01 (1%) to a maximum value of 0.1 (10%). Simulations were conducted using Matlab R2012b, with constant parameters including a population size of 100 and a crossover probability (Pc) of 0.85. Iterations were performed to evaluate the effect of Pm on computation time and solution performance. The results show that at Pm = 0.06, the Genetic Algorithm achieved the fastest computation time, averaging 0.382 seconds. This study also identifies that GA computation time is significantly influenced by algorithm parameters and the complexity of the problem. By selecting an appropriate Pm, a balance between exploration and exploitation can be achieved, reducing computation time without sacrificing solution quality. This research contributes significantly to the development of more efficient algorithms for optimization applications, particularly in lecture scheduling.

Waktu komputasi dalam Algoritma Genetika (AG) sering kali memerlukan waktu yang lama akibat kompleksitas komputasi yang dikerjakan. Oleh karena itu, perlu dilakukan upaya untuk mengoptimalkan waktu komputasi AG, khususnya dalam perencanaan jadwal kuliah di Program Studi Teknik Elektro Universitas Negeri Medan, yang menjadi objek penelitian. Salah satu upaya yang dapat dilakukan adalah dengan menentukan nilai probabilitas mutasi (Pm) yang tepat. Penelitian ini menggunakan Metode Variasi Probabilitas Mutasi, di mana nilai Pm dibatasi antara 0 hingga 1 dan divariasikan dari nilai minimum 0,01 (1%) hingga nilai maksimum 0,1 (10%). Simulasi dilakukan menggunakan perangkat lunak Matlab R2012b, dengan parameter konstan yaitu ukuran populasi 100 dan probabilitas crossover (Pc) 0,85. Proses iterasi dilakukan untuk mengevaluasi pengaruh Pm terhadap waktu komputasi dan performa solusi. Hasil simulasi menunjukkan bahwa pada Pm = 0,06, Algoritma Genetika mencapai waktu komputasi tercepat, yaitu 0,382 detik. Penelitian ini juga mengidentifikasi bahwa waktu komputasi AG sangat dipengaruhi oleh parameter algoritma dan kompleksitas masalah yang dihadapi. Dengan pemilihan Pm yang tepat, keseimbangan antara eksplorasi dan eksploitasi dapat dicapai, sehingga waktu komputasi berkurang tanpa mengorbankan kualitas solusi. Penelitian ini memberikan kontribusi signifikan dalam pengembangan algoritma yang lebih efisien untuk aplikasi optimasi penjadwalan kuliah.