BAB IV

DAFTAR ISI

1. Schema Theorem

BAB IV KARAKTERISTIK ALGORITMA GENETIKA

Schema dalam AG adalah pola genetik yang terdiri dari kombinasi gen yang tetap (0 atau 1) dan gen yang fleksibel (dapat berupa 0 atau 1, dilambangkan sebagai 'x'). Schema ini membantu AG untuk menyeleksi dan mempertahankan pola genetik yang memiliki fitness tinggi dari generasi ke generasi.

Contoh Schema: Misalnya, schema 10xx merepresentasikan empat kromosom: 1000, 1001, 1010, dan 1011.
Rata-rata Fitness Schema: Rata-rata fitness dari suatu schema (Î(S)) adalah rata-rata fitness dari semua kromosom dalam populasi yang memiliki pola genetik tersebut.
Pertumbuhan Eksponensial Schema: Jika schema memiliki fitness rata-rata yang lebih tinggi dari populasi keseluruhan, maka jumlah schema tersebut akan bertambah secara eksponensial dari generasi ke generasi.
Pindah Silang dan Mutasi: Setelah seleksi, dua proses penting dalam AG, yaitu pindah silang (crossover) dan mutasi, memengaruhi keberlangsungan schema.
Pindah Silang: Schema dengan defining length yang besar (jarak antara gen tetap paling awal dan paling akhir) memiliki risiko lebih tinggi untuk dirusak saat pindah silang. Probabilitas kerusakan schema S selama pindah silang adalah pc * D(S), di mana pc adalah probabilitas pindah silang dan D(S) adalah defining length schema.
Mutasi: Selama mutasi, gen tetap dalam schema dapat berubah secara acak. Probabilitas schema tidak berubah setelah mutasi adalah (1 - pm)^O(S), di mana pm adalah probabilitas mutasi dan O(S) adalah jumlah gen tetap dalam schema tersebut.

Konvergensi prematur terjadi ketika AG terlalu cepat mengarah ke solusi lokal, menghambat pencapaian solusi optimal global. Beberapa penyebab dan solusi untuk konvergensi prematur adalah:
- Dominasi Kromosom Lokal Optimum: Jika ada satu kromosom yang lebih baik dari lainnya, kromosom tersebut dan keturunannya bisa mendominasi populasi, menyebabkan AG terjebak dalam solusi lokal.
Solusi untuk Mencegah Konvergensi Prematur:
1. Fitness Ranking: Menggunakan ranking untuk mengurangi nilai fitness ekstrem dari kromosom dengan fitness tinggi, menjaga variasi dalam populasi.
2. Subpopulasi: Membagi populasi menjadi beberapa subpopulasi yang terisolasi untuk mengurangi risiko dominasi kromosom tunggal. Pindah silang hanya terjadi dalam subpopulasi, namun individu dapat berpindah antar-subpopulasi dengan tunneling probability (pt).
3. Probabilitas Mutasi Variabel: Menaikkan probabilitas mutasi ketika variasi antar individu rendah, dan menurunkannya jika variasi tinggi. Pendekatan ini menjaga diversitas genetik selama proses AG.
4. Kesimpulan: Bab ini menggarisbawahi bagaimana AG bekerja untuk mempertahankan pola genetik berkualitas tinggi (melalui schema theorem) serta strategi untuk mengatasi tantangan konvergensi prematur agar AG lebih efektif dalam mencari solusi optimal.

4. Link Download [Kembali]