Algoritme genetika (GA) mengaplikasikan prinsip evolusi alam ke dalam permasalahan optimisasi. Penggunaan GA untuk mengoptimasi kinerja klasifikasi pada KNN disebut Genetik KNN (GKNN). Nilai fitness yang dihasilkan GA dipengaruhi oleh ukuran populasi yang semakin tinggi. Namun, jika ukuran populasi dan generasi semakin tinggi maka tidak didapatkan kenaikan fitness yang signifikan dan waktu komputasinya akan berjalan semakin lama. Sebagai upaya untuk menghindari nilai fitness terjebak pada nilai yang rendah maka digunakan clustering pada GA untuk meningkatkan kemampuan eksplorasi solusi pada search space. Algoritma clustering K-Means digunakan untuk mengelompokkan kromosom dalam populasi GA berdasarkan kemiripan nilai fitness. Cluster dengan ratarata nilai fitness yang tinggi akan diberikan probabilitas mutasi yang rendah karena kebutuhan yang kecil untuk memperkenalkan struktur genetik baru yang lebih baik. Sebaliknya, cluster dengan rata-rata nilai fitness yang rendah akan diberikan probabilitas mutasi yang tinggi karena kebutuhan yang besar untuk memperkenalkan struktur genetik baru yang lebih baik. Penelitian ini menganalisa hasil performa klasifikasi antara GKNN yang dimodifikasi dengan K-Means dan GKNN. Hasil penelitian menunjukkan bahwa GKNN yang dimodifikasi dengan K-Means berhasil mendapatkan kenaikan nilai rata-rata performa untuk Dermatology = 0.00138, Cleveland Heart = 0.00204, Lung Cancer = 0.01044, Breast Cancer = 0.00021.