Karakteristik Algoritma Genetika
- 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:
- 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