Analisis Kinerja Greedy Crossover (Gx) Pada Algoritma Genetika untuk Rostering

Abstract

Genetic Algorithm is a heuristic search algorithm is very well used in solving optimization problems. Selection of the operator is used to determine the success of genetic algorithm to find the optimal solution. One operator that was instrumental in the genetic algorithm is a crossover operator that serves to produce a child chromosome. In classical genetic algorithm crossover operator used is One Point Crossover and Two Point Crossover, second crossover operator is working with the selection of cut point taken randomized (random). In research using a large population, these methods often cause adverse effects such as premature convergence in finding the optimal solution. In this study, the crossover method that will be analyzed is the method Greedy Crossover (GX) to the issues that are used are rostering subjects. In the method of Greedy Crossovers chromosome child obtained by examining each of the genes within each chromosome parent with a penalty as a function of their eligibility criteria. Genetic algorithms will stop if there is not found crash/conflicting or maximum number of generations has been reached. From the results of the analysis found that the performance of the method greedy crossover (GX) is better than the method of classical crossover genetic algorithm that is one point crossover and two point crossover.

Algoritma Genetika merupakan algoritma pencarian heuristik yang sangat baik digunakan dalam menyelesaikan masalah optimasi. Pemilihan operator yang digunakan sangat menentukan keberhasilan algoritma genetika dalam menemukan solusi yang optimal. Salah satu operator yang sangat berperan dalam algoritma genetika adalah operator crossover yang berfungsi untuk menghasilkan kromosom anak. Pada algoritma genetika klasik operator crossover yang biasa digunakan adalah One Point Crossover dan Two Point Crossover, kedua operator crossover ini bekerja dengan pemilihan titik potong yang diambil dengan metode acak (random). Pada penelitian dengan menggunakan jumlah populasi yang besar, metode ini sering menimbulkan efek yang kurang baik berupa konvergensi prematur dalam menemukan solusi yang optimal. Pada penelitian ini metode crossover yang akan dianalisis adalah metode Greedy Crossover (GX) dengan permasalahan yang digunakan adalah rostering mata pelajaran. Pada metode Greedy Crossover kromosom anak diperoleh dengan memeriksa setiap gen yang ada pada setiap kromosom induk dengan kriteria penalty sebagai fungsi kelayakannya. Algoritma genetika akan berhenti jika tidak ditemukan crash/bentrok atau sejumlah generasi maksimum telah tercapai. Dari hasil analisis ditemukan bahwa performance dari metode greedy crossover (GX) lebih baik dibandingkan dengan metode crossover pada algoritma genetika klasik yaitu one point crossover dan two point crossover.