» » » BAB IV

BAB IV




BAB IV KARAKTERISTIK ALGORITMA GENETIKA 

1. Schema Theorem [Kembali]

  • 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.

2. Konvergensi Prematur [Kembali]

  • 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.









0 Response to "BAB IV"

Posting Komentar