Algoritma Genetika (Genetic Algorithm) adalah salah satu teknik dalam kecerdasan buatan yang terinspirasi dari proses evolusi biologis. Algoritma ini sangat berguna dalam menyelesaikan berbagai permasalahan optimasi, seperti pencarian layout terbaik untuk sirkuit elektronik (PCB), penjadwalan yang efisien, serta permainan tebak kata.
Permasalahan
Bayangkan kita dihadapkan pada pilihan dua lagu, maka memilih yang terbaik bukanlah hal sulit. Namun, bagaimana jika terdapat ratusan atau ribuan lagu dengan variasi genre, durasi, dan timbre? Otak manusia akan kesulitan untuk mengevaluasi semua kombinasi tersebut dengan cepat. Biasanya, kita akan cenderung memilih secara acak atau berdasarkan intuisi tanpa proses analisis yang optimal.
Secara alami, manusia melakukan seleksi bertahap dengan mengelompokkan lagu berdasarkan genre, durasi, atau karakteristik lainnya, lalu mempersempit pilihan hingga akhirnya menemukan yang terbaik.
Solusi: Genetic Algorithm
Pendekatan Algoritma Genetika bekerja dengan cara membentuk solusi secara bertahap, bukan memilih secara acak dalam satu langkah. Algoritma ini meniru proses seleksi alam dengan menciptakan populasi kandidat solusi yang berevolusi melalui seleksi, crossover, dan mutasi.
Sebagai contoh, kita akan menerapkan algoritma ini dalam permainan tebak kata dengan target kata kunci:
kata kunci : INFORMATIKAPopulasi Awal. Kita akan membuat populasi awal yang terdiri dari string acak, yang dibentuk dari kumpulan huruf berikut:
ABCDEFGHIJKLMNOPQRS TUVWKode untuk menghasilkan huruf acak
function randomChar() {
const chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ ";
return chars.charAt(Math.floor(Math.random() * chars.length));
}Kode di atas menggunakan Math.random() untuk memilih indeks huruf secara acak.
Apa fungsi Math.random()?
Menghasilkan nilai desimal secara acak mulai dari 0 hingga 1 ( 0 hingga 0,99 angka satu tidak termasuk ).
console.log(Math.random()); // 0.5231 console.log(Math.random()); // 0.8314 console.log(Math.random()); // 0.0912Bagaimana dengan Math.random() * chars.length?
Mengalikan angka acak tersebut denganchars.length (berjumlah 27).
Math.random() * chars.length;
console.log(Math.random() * 27); // Example: 14.6723 console.log(Math.random() * 27); // Example: 3.2211 console.log(Math.random() * 27); // Example: 25.9458Terus Fungsi Math.floor()?
Math.floor() digunakan untuk pembulatan kebawah menjadi bilangan bulat terdekat. Sehingga fungsi ini akan mendapatkan nilai integer antara 0 hingga 26.
Math.floor(Math.random() * chars.length);
console.log(Math.floor(14.6723)); // Output: 14
console.log(Math.floor(3.2211)); // Output: 3
console.log(Math.floor(25.9458)); // Output: 25Ekspresi akhir yang digunakan
Math.floor(Math.random() * chars.length);Ekspresi ini menghasilkan indeks acak antara 0 hingga 26. Indeks tersebut dapat digunakan untuk memilih karakter secara acak dari kumpulan karakter (chars).
Membentuk Populasi Awal
Kita akan membentuk 100 kandidat awal yang memiliki panjang sama dengan kata kunci (INFORMATIKA = 11 karakter).
populationSize = 100;
target = "INFORMATIKA";
let population = Array.from({ length: populationSize }, () => randomString(target.length));
function randomString(length) {
return Array.from({ length }, randomChar).join('');
}
Contoh populasi awal
IHI RUSTCEA,
IGLUMGMSMKP,
BCUQAMAEvaluasi Fitness (Kecocokan dengan Target)
Setiap kandidat dalam populasi diberikan skor berdasarkan seberapa mirip dengan target menggunakan fungsi calculateFitness():
function calculateFitness(target, candidate) {
let score = 0;
for (let i = 0; i < target.length; i++) {
if (target[i] === candidate[i]) {
score++;
}
}
return score / target.length;
}Jika ada dua huruf yang cocok dengan target misalnya huruf pertama dan terakhir IGLUMGMSMKA, maka skor fitness adalah 2/11 = 0.1818.
setiap individupopulation dihitung nilai ketepatnnya kemudian diurutkan paling atas nilai tertinggi menggunakan fungsi sort
scoredPopulation.sort((a, b) => b.fitness - a.fitness);Hasil pengurutannya kemudian dipotong 50% teratas dan dicuplik sebagai berikut.
[{"candidate":"IHI RUSTCEA","fitness":0.36363636363636365},{"candidate":"IGLUMGMSMKP","fitness":0.18181818181818182},
{"candidate":"WDSLGCAIIRT","fitness":0.18181818181818182}{"candidate":"EJKBFBSSLSA","fitness":0.09090909090909091},
{"candidate":"REMODVMSCJB","fitness":0.09090909090909091}
//..
]Apa yang terjadi berikutnya?
Proses Crossover dan Mutasi
Untuk menghasilkan generasi baru, kita memilih dua kandidat terbaik sebagai “orang tua” (parents) dan membuat “anak” (child) melalui crossover serta mutasi.
Crossover (Penyilangan):
Menggabungkan dua individu dengan membelah pada titik acak
function crossover(parent1, parent2) {
let midpoint = Math.floor(Math.random() * parent1.length);
return parent1.slice(0, midpoint) + parent2.slice(midpoint);
}contoh
Parent 1: IHI RUSTCEA
Parent 2: EJKBFBSSLSA
Child (Crossover): IHI RUSTLSApopulation = [];
while (population.length < populationSize) {
let parent1 = parents[Math.floor(Math.random() * parents.length)];
let parent2 = parents[Math.floor(Math.random() * parents.length)];
let child = crossover(parent1, parent2);
let childMutate = mutate(child, mutationRate);
population.push(childMutate);
}Mutasi (Perubahan Acak)
Mutasi membantu menciptakan variasi agar tidak terjebak dalam solusi yang stagnan.
function mutate(str, mutationRate = 0.1) {
return str.split('').map(char => (Math.random() < mutationRate ? randomChar() : char)).join('');
}Hasil mutasi
Child (Crossover): IHI RUSTLSA
Mutate : IHIORPSRLSAEvolusi hingga Solusi Ditemukan
Proses crossover dan mutasi dilakukan berulang kali hingga diperoleh kandidat yang 100% cocok dengan target.
Iterasi ke-29
Candidate terbaik: INVORMATIKA (fitness: 0.909)
Candidate lain:
INPORIATIKA (fitness: 0.818)
INFOPMATIWA (fitness: 0.818)Iterasi ke-30
Akhirnya ditemukan
Candidate: INFORMATIKA (fitness: 1.0) ✅Full script bisa dilihat pada tautan ini. Happy Coding!
Refernsi
Russell, Stuart J., Norvig, Peter. (2010). Artificial intelligence : a modern approach (3rd ed. International ed.). Tokyo: Pearson.
Leave a Reply