Optimization & Genetic Algorithm

Kenapa slide mulai dari heuristic

PDF Ali Ridho Barakbah membuka dengan masalah yang terlalu besar untuk dihitung persis. Heuristic adalah jalan pintas: jawaban cukup bagus dalam waktu masuk akal, dipakai kalau metode exact (cek semua kemungkinan) butuh ribuan tahun atau memori yang tidak muat.

Contohnya kurir 100 alamat, rute terpendek. Itu TSP, kelas NP-Hard. Exact menguji semua urutan kota. Untuk n kota, jumlah tur (n−1)!/2. Di n = 100 angkanya astronomis; komputer mungkin belum selesai sampai pensiun, hasilnya memang optimal. Heuristic “selalu ke lokasi terdekat berikutnya” (nearest neighbour) selesai dalam detik. Rutenya belum tentu terpendek, tapi bisa dipakai.

Slide lalu menaruh empat heuristic sejenis. Genetic algorithm meniru seleksi alam (induk bagus, kawin, mutasi). Ant colony meniru semut yang menandai jalan ke makanan dengan feromon. Simulated annealing meniru pendinginan logam sampai kristalnya kuat. Hill climbing selalu pindah ke yang lebih bagus sampai mentok. Hill climbing pegang satu posisi. GA pegang banyak kandidat sekaligus.

GA yang dibahas di sini dikembangkan di AS 1970-an oleh John Holland, Kenneth DeJong, dan David Goldberg. Versi asli Holland sekarang disebut simple genetic algorithm (SGA). Biasanya untuk masalah diskrit / kombinatorial. Tidak terlalu cepat, heuristic yang bagus. Buku Holland Adaptation in Natural and Artificial Systems (1975) dan Goldberg Genetic Algorithms in Search, Optimization, and Machine Learning (1989) merangkum SGA: populasi berukuran tetap, seleksi sebanding fitness, crossover, mutasi, ganti generasi. Penekanan tradisionalnya: gabungkan informasi parent bagus lewat crossover. Varian kemudian mengubah representasi, operator, dan cara seleksi.

Sebelum jalan: nama kotak, dan lima keputusan

Analogi biologi, isinya data. Gene = satu kotak bermakna (biner, float, integer, huruf, atau urutan kota). Allele = nilai di kotak itu: 0/1, 1–26, atau 1.2. Chromosome = rangkaian gene, “DNA” satu kandidat. Individual = satu calon solusi. Population = banyak individu yang diproses bersama. Generation = satu putaran. Fitness = angka kualitas.

Slide “How to Prepare GA?” memaksa lima keputusan itu sebelum loop dijalankan. (1) Bentuk individu: satu individu = satu jawaban sah. Rute TSP = urutan kota tanpa dobel. Kata = delapan angka 1–26. (2) Fungsi fitness: cara mengubah individu jadi skor. (3) Cara isi populasi awal, biasanya acak, tetap harus valid. (4) Cara pilih induk. (5) Cara crossover dan mutasi, plus probabilitasnya. Kalau salah satu kosong, loop di slide berikutnya tidak punya bahan.

Dari kotak gene ke populasi awal

Slide representasi menggambar populasi sebagai tumpukan baris. Tiap baris individu, terbagi chromosome, terbagi gene. Satu baris = satu solusi. Baru sesudah gambar itu ada siklus, karena siklus mengolah baris-baris itu.

Populasi awal dibuat acak atau lewat prosedur. Tiap individu harus memenuhi syarat solusi sah. Di TSP, populasi = kumpulan rute. Contoh slide, empat individu, tujuh kota:

1 2 4 3 6 5 7
5 7 4 6 2 3 1
7 2 6 4 5 1 3
4 6 5 7 3 2 1

Masing-masing permutasi 1–7, tiap kota sekali. Kalau crossover menukar sembarang potongan, rute bisa dobel kota. Itu sebabnya TSP biasanya pakai operator khusus (PMX, order crossover). Tugas kata GENETIKA lebih longgar: huruf boleh berulang, jadi two-point biasa aman.

Satu generasi, dari nilai sampai populasi baru

Slide siklus: populasi awal dinilai, induk dipilih, kawin dan mutasi, populasi baru, lalu kembali ke penilaian. Itu satu generasi. Di bawah ini loop itu dijalankan sekali, memakai angka yang sama dengan slide, tanpa loncat ke elitisme dulu.

flowchart LR
  Init["Initial Population"]
  Fit["Fitness Evaluation"]
  Sel["Individual Selection"]
  Rep["Crossover dan Mutation"]
  New["New Population"]
  Init --> Fit --> Sel --> Rep --> New --> Fit

Hitung fitness dulu

Setiap individu dapat satu angka. Tanpa angka itu seleksi tidak punya roda. Masalah minimisasi (jarak, biaya rute) biasanya dibalik dulu jadi maksimisasi, karena roulette butuh nilai positif dan “lebih besar = lebih sering kepilih.” Di tugas kata, jarak diubah jadi 208 minus jarak. Tutorial SGA (Whitley; Eiben & Smith) memakai langkah yang sama: nilai dulu, baru spin.

Seleksi roulette, angka slide

“Good parents will produce good offspring.” Fitness lebih tinggi, peluang terpilih lebih besar. Dua nama di slide: roulette wheel dan tournament. Fitness proportionate selection menulis peluang individu i:

pᵢ = fᵢ / (f₁ + f₂ + … + fₙ)

Empat individu slide, fitness 10, 20, 40, 30. Total 100, jadi rentang 1–100 sama dengan persen:

Empat putaran acak di slide mengisi mating pool:

Mating pool: 3, 4, 3, 2. Individu 3 muncul dua kali karena irisan rodanya paling lebar. Individu 1 (fitness 10) tidak muncul di empat spin ini. Empat terpilih ini yang masuk slide berikutnya, crossover.

Tournament hanya disebut namanya di PDF. Selection (GA): ambil k individu acak (sering k = 2), yang fitnessnya paling tinggi di kelompok itu yang lolos. Tidak perlu memetakan skor ke roda.

Crossover: induk yang baru dipilih menukar gene

Dua induk menghasilkan anak. Slide: tukar gene secara acak. Dua jenis: direct gene exchange (salin potongan apa adanya) dan arithmetic (campur nilai). Flowchart: undi p di 0–1. Kalau p < probCO, kawin. Kalau tidak, anak menyalin induk. Tutorial Eiben & Smith memakai pc di kisaran 0.6–0.9; slide mengambil 0.9.

Contoh two-point di slide ganti bahan: string biner 7 bit, bukan keempat orang roulette. Dua titik potong, segmen di antaranya ditukar. Ken DeJong (dikutip tutorial GA JHU / Whitley) mencatat two-point memperlakukan ujung string lebih merata daripada one-point.

Kasus 1, P = 0.70 < 0.9, kawin jalan. Parent 1100111 dan 1101011, titik di gene 4–6: tengah 011 dan 101 ditukar, kepala-ekor tetap. Anak: 1101011 dan 1100111.

Kasus 2, P = 0.95 ≥ 0.9, tidak kawin. Parent 1101100 dan 0110001 disalin utuh.

Kasus 3, P = 0.35. Parent 1100000 dan 1010101, titik antara gene 1–2 dan 5–6. Anak: 1010100 dan 1100001.

Kasus 4, P = 0.65. Parent 1011111 dan 1110001, titik antara gene 3–4 dan 5–6. Anak: 1010011 dan 1111101.

Arithmetic dipakai kalau gene-nya bilangan real, bukan bit. Rumus real-coded GA (Eiben & Smith; catatan Busoniu):

anak₁ = r·p₁ + (1−r)·p₂
anak₂ = r·p₂ + (1−r)·p₁

Slide hanya mencampur dua gene di antara titik potong, gene lain disalin. r = 0.4, bobot 0.4 dan 0.6:

(0.4)(0.2) + (0.6)(1.0) = 0.68, digambar 0.7
(0.4)(1.0) + (0.6)(0.2) = 0.52, digambar 0.5
(0.4)(1.5) + (0.6)(1.0) = 1.2
(0.4)(1.0) + (0.6)(1.5) = 1.3

Anak “berada di antara” kedua induk. Cocok untuk vektor float. Permutasi kota tidak memakai rumus ini.

Mutasi, sesudah anak ada

Anak hasil kawin belum langsung jadi populasi baru. Tiap individu masih bisa diubah sedikit. Slide: tukar gene dengan inversinya (0 jadi 1), atau geser nilainya, di posisi acak, menurut probabilitas mutasi. Flowchart slide masih menulis P < probCO; isi kotaknya probabilitas mutasi. Di SGA, pm terpisah dari pc, biasanya jauh lebih kecil (orde 1/panjang chromosome).

Binary, r = 2 (kotak kedua): 1 0 0 1 1 menjadi 1 1 0 1 1. Float, ε = 0.1 di posisi yang sama: 0.2 menjadi 0.3.

Crossover hanya menggabungkan yang sudah ada di induk. Mutasi memasukkan bit / angka / huruf yang belum muncul. Tanpa itu populasi bisa berhenti di GENETIKB: B dekat A, tidak ada operator yang mengubah kotak terakhir. Whitley: pm rendah, tetap wajib supaya pencarian tidak macet.

Populasi baru, lalu ulang dari fitness

Setelah mutasi, kumpulan anak itu (di SGA klasik, sebanyak n) mengganti populasi lama. Panah di slide kembali ke “Fitness Evaluation.” Generasi ke-2 menilai anak yang baru saja dibuat, spin roulette lagi, kawin lagi, mutasi lagi. Berhenti kalau solusi cukup bagus, atau kuota generasi habis.

Di titik ini loop sudah utuh. Yang belum ada: perlindungan individu terbaik. Itu slide terakhir.

Elitisme, disisip sebelum penilaian berikutnya

Crossover dan mutasi bisa merusak individu terbaik. DeJong memasukkan elitism justru karena SGA generasional berisiko membuang solusi yang sudah mahal dicari. Varian literatur yang sering: salin 1 (atau k) individu terbaik ke generasi berikutnya tanpa diubah.

Slide memakai ranking. Gabung parent n dan offspring n jadi 2n, urutkan, ambil n terbaik. Kalau anak lebih jelek, induk tetap lolos. Kalau anak lebih bagus, anak yang masuk. Panah elitisme di diagram mengarah ke evaluasi fitness: yang lolos ranking itulah yang dinilai di generasi berikutnya.

flowchart LR
  P["Parent n"]
  O["Offspring n"]
  C["Combined 2n"]
  N["New Individual n"]
  P --> C
  O --> C
  C -->|"ranked, ambil n terbaik"| N

Tugas GENETIKA memakai loop yang sama, dengan huruf 1–26. Fitness 208 minus jarak, roulette, two-point, mutasi, ranking n+n. Simulasi membuka operator itu satu per satu.

Sumber

• Optimization Problem & Genetic Algorithm (Barakbah, iKnow / PENS)
• Wikipedia: Genetic algorithm
• Wikipedia: Fitness proportionate selection
• Wikipedia: Selection
• Whitley, A Genetic Algorithm Tutorial (SGA, roulette, two-point / DeJong)
• A.E. Eiben & J.E. Smith, Introduction to Evolutionary Computing (pc 0.6–0.9, pm, arithmetic recombination, elitisme)
• J. Holland (1975); D. Goldberg (1989); K. DeJong (elitism pada model generasional)