Pertemuan 11 — Algoritma Genetika

Pada pertemuan ini, kita akan mempelajari salah satu teknik optimasi paling populer dalam Kecerdasan Buatan, yaitu Algoritma Genetika (Genetic Algorithm/GA). Terinspirasi dari mekanisme evolusi biologis dan seleksi alam, GA mampu mencari solusi optimal pada berbagai permasalahan kompleks yang sulit diselesaikan dengan metode konvensional.

Melalui konsep kromosom, fitness, seleksi, crossover, dan mutasi, kita akan melihat bagaimana sebuah populasi solusi dapat "berevolusi" secara bertahap menuju hasil terbaik. Pertemuan ini tidak hanya memberikan dasar teoretis, tetapi juga membuka wawasan mengenai penerapan GA dalam optimasi rute, penjadwalan, dan berbagai permasalahan nyata lainnya.

Capaian Pembelajaran Pertemuan (CPL-P)

Setelah mengikuti pertemuan ini, mahasiswa mampu:

1. Menjelaskan konsep dasar evolusi dan seleksi alam yang menjadi landasan kerja Algoritma Genetika.
2. Mengidentifikasi dan mendeskripsikan struktur kromosom serta fungsi fitness dalam representasi solusi masalah optimasi.
3. Menganalisis cara kerja operator GA (seleksi, crossover, dan mutasi) serta perannya dalam proses evolusi solusi.
4. Menerapkan prinsip dasar Algoritma Genetika untuk memecahkan contoh kasus sederhana seperti optimasi rute atau penjadwalan.
5. Mengevaluasi kualitas solusi GA berdasarkan nilai fitness dan performa evolusi populasi.

A. Konsep Evolusi dan Seleksi Alam

1. Evolusi sebagai Proses Optimasi

Algoritma Genetika (Genetic Algorithm/GA) terinspirasi dari teori evolusi biologis yang dikemukakan oleh Charles Darwin, khususnya prinsip bahwa organisme yang paling sesuai (fit) dengan lingkungannya akan memiliki peluang lebih besar untuk bertahan hidup dan berkembang biak.

Dalam konteks komputasi, konsep ini diterjemahkan menjadi proses pencarian solusi optimal melalui mekanisme evolusi buatan. Setiap solusi diwakili sebagai individu dalam suatu populasi, dan GA menghasilkan solusi yang lebih baik melalui proses iteratif: seleksi → crossover → mutasi.

• Terdapat populasi yang berisi banyak kandidat solusi.
• Setiap individu memiliki kromosom (representasi karakteristik solusi).
• Individu mengalami proses "reproduksi" untuk menghasilkan keturunan.
• Populasi secara bertahap berkembang menuju solusi yang lebih optimal.

2. Prinsip Seleksi Alam

Konsep inti seleksi alam adalah:

"Yang paling fit akan memiliki peluang terbesar untuk bertahan dan menghasilkan keturunan."

Dalam GA, tingkat fitness menentukan kualitas sebuah solusi. Individu dengan nilai fitness tinggi:

• Lebih mungkin dipilih untuk reproduksi.
• Memiliki probabilitas lebih besar untuk mewariskan karakteristiknya.
• Mempercepat konvergensi menuju solusi optimal.

3. Metode Seleksi dalam GA

• Roulette Wheel Selection — peluang dipilih sebanding dengan nilai fitness; individu dengan fitness besar mendapat porsi "roda" lebih besar.
• Tournament Selection — beberapa individu dipilih secara acak, lalu individu dengan fitness terbaik di antara mereka menjadi pemenang.
• Rank Selection — individu diurutkan berdasarkan ranking fitness, sehingga mengurangi dominasi individu dengan fitness ekstrem.

4. Analogi Antara Evolusi Biologi dan GA

5. Mengapa Seleksi Alam Efektif dalam Optimasi?

Algoritma Genetika unggul karena:

• Mampu mencari solusi global, bukan hanya solusi lokal.
• Tidak memerlukan turunan matematis atau bentuk fungsi tertentu.
• Efektif untuk masalah kompleks seperti penjadwalan, optimasi rute, dan tuning parameter.

B. Representasi Kromosom dan Fungsi Fitness

1. Representasi Kromosom

Dalam Algoritma Genetika, kromosom adalah bentuk representasi solusi dari suatu masalah. Kromosom tersusun dari beberapa gen yang menyimpan nilai variabel. Cara merepresentasikan kromosom bergantung pada jenis masalah yang ingin diselesaikan.

Bentuk Representasi yang Umum

• Representasi Biner (Binary Encoding)
  Gen berupa angka 0 dan 1. Cocok untuk optimasi sederhana, pemilihan fitur, atau masalah logika.
  Contoh: 101011
• Representasi Bilangan Real (Real-Valued Encoding)
  Gen berupa angka pecahan/bilangan real. Cocok untuk optimasi fungsi matematis atau parameter algoritma.
  Contoh: [0.25, 3.41, 1.87]
• Representasi Permutasi (Permutation Encoding)
  Digunakan untuk masalah berbasis urutan seperti TSP dan penjadwalan.
  Contoh: [3, 1, 4, 2, 5]
• Representasi Simbolik/String Karakter
  Digunakan untuk ekspresi matematika, program, atau pola tertentu.
  Contoh: "ABCDAB"

Umumnya, kromosom bersifat fixed length (panjang tetap) dan mewakili satu solusi lengkap dari masalah yang dianalisis.

2. Fungsi Fitness

Fungsi fitness adalah inti utama dalam GA, karena menentukan kualitas suatu solusi. Fitness adalah nilai numerik yang menggambarkan seberapa baik individu tersebut dalam menyelesaikan masalah.

Tujuan Fungsi Fitness

• Mengukur kualitas solusi.
• Menentukan peluang individu untuk dipilih dalam proses seleksi.
• Mengarahkah proses evolusi menuju solusi yang optimal.

Karakteristik Fungsi Fitness yang Baik

• Merefleksikan tujuan optimasi (memaksimalkan keuntungan atau meminimalkan biaya).
• Menghasilkan nilai numerik yang dapat dibandingkan antar individu.
• Mampu membedakan solusi yang baik dan buruk.
• Cukup stabil, tidak terlalu sensitif terhadap perubahan kecil.

3. Contoh Fungsi Fitness

• Optimasi Fungsi Matematis
  Misal ingin memaksimalkan fungsi: f(x) = x^2
  Fitness dapat didefinisikan sebagai: fitness = x^2.
• Travelling Salesman Problem (TSP)
  Tujuan: meminimalkan total jarak tempuh.
  Fitness dapat didefinisikan sebagai: fitness = 1 / (total_jarak).
• Penjadwalan
  Fitness dapat mempertimbangkan minimasi keterlambatan atau konflik jadwal, misalnya: fitness = 1 / (jumlah_konflik + 1).
• Seleksi Fitur pada Machine Learning
  Fitness bisa berupa akurasi model: fitness = accuracy(model).

C. Operator GA: Seleksi, Crossover, Mutasi

Operator dalam Algoritma Genetika adalah mekanisme kunci yang memungkinkan terjadinya proses evolusi solusi, yaitu seleksi, crossover, dan mutasi. Operator-operator ini meniru mekanisme biologis pada organisme hidup.

1. Seleksi (Selection)

Seleksi adalah proses memilih individu yang akan menjadi orang tua (parents) dalam menghasilkan generasi berikutnya. Individu dengan fitness lebih tinggi mendapatkan peluang lebih besar untuk terpilih, mewakili konsep survival of the fittest.

Tujuan Seleksi

• Memastikan individu terbaik berpeluang lebih besar melanjutkan keturunannya.
• Mengatur tekanan evolusi agar pencarian solusi lebih cepat dan tidak stagnan.

Metode Seleksi yang Umum

• Roulette Wheel Selection — peluang terpilih proporsional dengan nilai fitness.
• Tournament Selection — memilih beberapa individu secara acak dan mengambil yang terbaik dari kelompok kecil tersebut.
• Rank Selection — menggunakan ranking fitness untuk mengurangi dominasi individu dengan fitness yang terlalu besar.

2. Crossover (Rekombinasi)

Crossover meniru proses rekombinasi genetik saat reproduksi biologis. Dua kromosom induk bertukar bagian tertentu untuk menghasilkan satu atau dua individu baru (offspring).

Tujuan Crossover

• Menggabungkan sifat terbaik dari dua individu.
• Mengeksplorasi kombinasi solusi baru.
• Meningkatkan kualitas populasi secara bertahap.

Jenis-Jenis Crossover

• Single-Point Crossover
  Dua induk dipotong pada satu titik dan segmen setelah titik tersebut dipertukarkan.
  Contoh:
  Parent1: 110|101
  Parent2: 011|001
  Offspring: 110001, 011101
• Two-Point Crossover
  Menggunakan dua titik potong, bagian di antara dua titik dipertukarkan.
• Uniform Crossover
  Setiap gen memiliki probabilitas tertentu (misalnya 0.5) untuk ditukar.
• Order Crossover (OX)
  Digunakan untuk representasi permutasi, misalnya pada TSP atau masalah penjadwalan, agar tidak terjadi elemen duplikat pada offspring.

3. Mutasi (Mutation)

Mutasi adalah operator yang mengubah satu atau beberapa gen dalam kromosom secara acak. Tujuan utama mutasi adalah menjaga keberagaman genetik dan mencegah populasi terjebak pada solusi lokal.

Tujuan Mutasi

• Menjaga keragaman populasi.
• Mencegah konvergensi prematur.
• Membuka kemungkinan munculnya solusi baru yang lebih baik.

Jenis Mutasi yang Umum

• Bit Flip Mutation (untuk representasi biner)
  Mengubah gen 0 menjadi 1 atau sebaliknya.
  Contoh: 101011 → 100011
• Swap Mutation (untuk permutasi)
  Menukar posisi dua gen. Cocok untuk masalah penjadwalan dan TSP.
  Contoh: [1, 3, 5, 2] → [1, 2, 5, 3]
• Random Resetting (untuk bilangan real)
  Mengganti nilai suatu gen dengan nilai acak baru dalam rentang tertentu.
• Scramble dan Inversion Mutation
  Digunakan pada kromosom berbasis urutan, dengan cara mengacak atau membalik urutan bagian tertentu dari kromosom.

4. Sinergi Tiga Operator GA

Ketiga operator ini bekerja secara sinergis: populasi awal dibentuk, fitness dihitung, seleksi memilih individu terbaik, crossover menggabungkan sifat, dan mutasi menjaga keragaman. Proses tersebut diulang selama beberapa generasi hingga tercapai solusi yang dianggap optimal atau memenuhi kriteria berhenti.