BAB 4

Karakteristik Algoritma Genetika





1. Skema Theorem [BACK] 
  • Suatu schema didefinisikan sebagai suatu pola yang berisi posisi-posisi tetap yang berisi gen-gen bernilai 0 atau 1, dan posisi tidak tetao yang berisi gen-gen bernilai x.
  • e.g : 10xx, xx01, 1x10, dan sebagainya.
    • 10xx merepresentasikan empat kromosom (1000,1001,1010,1011)
  • Karena adanya x, maka posisi dalam skema bisa berisi 1, 0, atau x.
  • rumus skema =3^n.
  • Jumlah copy skema S pada generasi g+1:
  • Probabilitas skema rusak saat pindah silang:
  • Probabilitas skema bertahan hidup saat pindah silang:


  • Dengan pengaruh adanya defining length (jarak antara posisi bukan x yang pertama dengan bukan x yang terakhir) dan mutasi skema, maka persamaan skema generasi g+1 menjadi :


  • Karena kondisi awal hampir semua kromosom bernilai jauh dari optimum, namun ada satu kromosom A yang mendekati nilai optimum, maka A akan memproduksi lebih banyak anak.
  • Keturunan A akan mendominasi populasi, pindah silang dan mutasi hanya akan menghasilkan kromosom lokal optimun, dan terjadilah konvergensi prematur.
  • Cara mencegah Konvergensi Prematur :
    • Fitness Ranking
Dengan menggunakan Fitness Ranking, perbedaan nilai fitness antar individu bisa diturunkan.
Pada gambar diatas, rasio antara nilai fitness terbaik dengan nilai fitness terbaik kedua adalah sekitar 2.
Jika terdapat N individu, fitness ranking akan menurunkan rasio ini menjadi N/(N-1) atau mendekati 1 jika N cukup besar.
    • SubPopulasi
Pada Subpopulasi, N kromosom dalam satu populasi dibagi menjadi Nk kelompok. Masing-masing kelompok berisi v = N/Nk individu.

Dalam metode ini, pindah silang dan mutasi hanya terjadi di dalam subpopulasi. Tetapi dengan tunneling probability Pt, suatu individu bisa dipindah ke subpopulasi lain. Agar jumlah individu dalam suatu subpopulasi tidak berubah, suatu individu dipilih secara random untuk dipindah ke subpopulasi lainnya.

    • Memvariasikan probabilitas mutasi
Ketika konvergensi terjadi, perbedaan nilai fitness antar individu menjadi sangat kecil. Dengan kata lain, variasinya menjadi rendah. Dengan demikian jika variasi sudah berada di bawah nillai tertentu, probabilitas mutasi diturunkan.



Tidak ada komentar:

Posting Komentar

Bahan Presentasi Untuk Matakuliah Sistem Digital 2023 OLEH: Fadhila Amanda 2110952031 Dosen Pengampu: Dr. Darwison,MT Referensi: a. Anil K. ...