Algoritma Genetika dalam Komputasi

Hai hai kawan-kawan blogger, kali ini kita akan bicara dikit tentang GA. Artikel ini dipersembahkan khusus buat teman saya yang sekarang ambil studi Master Tambahan di Warsaw, Polandia :D. Semoga bermanfaat :))
 source : www.graphics.com
 Algoritma genetika adalah salah satu contoh algoritma evolusi. Algoritma ini sangat akrab untuk digunakan dalam masalah optimasi. Inti dari algoritma ini adalah mencari solusi optimal dalam suatu permasalahan. Permasalahan yang dimaksud bisa mencakup masah diskrit (e.g. TSP) atau continou (e.g. maksimasi fungsi). 

Dari namanya kita sudah bisa menebak bahwa algoritma genetika disadur dari konsep genetika yang bercerita tentang kromosom. Konsep yang dimaksud adalah bagaimana sebuah kromosom berpindah silang dan bermutasi. Well, seperti itulah sekilas tentang Algoritma Genetika a.k.a GA.


Secara mudah, prosedur GA dapat dilihat pada diagram berikut:
Prosedur Algoritma Genetika

Metode ini dijalankan secara bertahap sebagai berikut:

1. Membangkitkan Populasi
Populasi yang dimaksud adalah sekumpulan solusi permasalahan yang fisibel. Solusi disini sudah harus dalam bentuk kode-kode yang siap diolah. Kriteria solusi sangat bergantung pada permasalahan, contohnya :
* Jika masalah yang dibahas adalah TSP, maka solusinya adalah rute perjalanan.
* Jika masalah yang dibahas adalah optimasi fungsi, maka solusinya adalah suatu bilangan real.
* Jika masalah yang dibahas adalah optimasi metode learning ANN, maka solusinya adalah bobot dan bias.
* Jika masalah yang dibahas Anda belum paham, maka konsultasikan pada dosen Anda :D
Jumlah populasi sering disebut dengan istilah pop_size (baca : population size). Nilai dari pop_size bervariasi tergantung user atau programmer. Umumnya bilangan genap seperti 10, 50, 100, atau 1000. Jarang saya temui user mematok angka seperti 17, 23, atau 349 untuk ukuran sebuah populasi. :D. 
input : pop_size
proses : generate populasi secara random
output : populasi 

2. Evaluasi
Populasi yang telah dibangkitkan dihitung cost atau fungsi tujuan atau fungsi objektif. Evaluasi disini bertujuan untuk mengetahui fitness atau keunggulan dari masing-masing kromosom. Pada prinsipnya, semakin bagus nilai fitness, akan semakin bagus kromosom, sehingga akan semakin besar peluang kromosom terpilih kembali di populasi selanjutnya. Kriteria evaluasi pun sangat bergantung pada permasalahan, contohnya :
* Jika masalah yang dibahas adalah TSP, maka fungsi tujuannya adalah jarak total rute perjalanan.
* Jika masalah yang dibahas adalah optimasi fungsi, maka fungsi tujuannya adalah error.
* Jika masalah yang dibahas adalah optimasi metode learning ANN, maka fungsu tujuannya adalah error.
input : populasi
proses : perhitungan cost
output : fitness tiap kromosom dalam populasi

3. Seleksi
Tahap ini bertujuan untuk memilih kromosom yang akan melakukan crossover atau mutasi. seleksi ini bermacam-macam. tiga yang paling populer adalah roullet wheel, turnamen, dan elitism. 
input : populasi
proses : memilih kromosom untuk crossover atau mutasi
output : calon kromosom induk untuk crossover atau mutasi

4. Crossover
Operator genetika ini membutuhkan dua kromosom untuk menghasilkan anak. Pada proses crossover, dua induk akan berpindah silang sehingga memiliki dua anakan. Ada berbagai macam tipe crossover. Lebih lanjut dapat dilihat di sini. "Calon kromosom induk crossover" yang diperoleh dari proses seleksi tidak serta merta menjadi induk. Namun, dibutuhkan sebuah bilangan probabilitas untuk menentukan apakah kromosom ini didaulat menjadi induk atau tidak. Bilangan tersebut disebut probability of crossover (pc). Jika bilangan random yang disematkan pada masing-masing kromosom tersebut kurang dari pc, maka kromosom tersebut telah sah menjadi "kromosom induk crossover".
input : calon kromosom induk crossover, pc
proses : memindah silangkan gen pada 2 kromosom induk crossover
output : kromosom anak hasil crossover

5. Mutasi
Operator genetika ini membutuhkan satu saja kromosom untuk menghasilkan anak. Pada proses mutasi, induk akan merubah gen sehingga kromosom dengan gen yang baru menjadi anak. Ada berbagai macam tipe mutasi. Lebih lanjut dapat dilihat di sini. Seperti halnya crossover, "calon kromosom induk mutasi" yang diperoleh dari proses seleksi tidak serta merta menjadi induk. Namun, dibutuhkan sebuah bilangan probabilitas untuk menentukan apakah kromosom ini didaulat menjadi induk atau tidak. Bilangan tersebut disebut probability of mutation (pm). Jika bilangan random yang disematkan pada masing-masing kromosom tersebut kurang dari pm, maka kromosom tersebut telah sah menjadi "kromosom induk mutasi".
input : calon kromosom induk mutasi
proses : merekayasa gen pada kromosom induk mutas
output : kromosom anak hasil mutasi

6. Populasi baru
Tahapan ini adalah tahapan akhir dari satu iterasi atau satu generasi GA. Setelah kromosom melakukan crossover dan mutasi, maka anakan tersebut dikumpulkan bersama populasi sebelumnya. Selanjutnya dipilih populasi baru sebanyak pop_size untuk dilanjutkan ke generasi selanjutnya.
input : kromosom dalam populasi sekarang, kromosom anak hasil crossover dan mutasi
proses : memilih populasi baru
output : populasi baru

 Next, kita coba implementasikan metode ini untuk masalah Travelling Salesman Problem. Yuk ke TKP :))

Komentar

Posting Komentar

Postingan populer dari blog ini

Artikel: Kaya vs Miskin

Suatu saat seseorang menemui nabi Musa dan berkata, "Wahai nabi Allah, aku ini adalah orang miskin. Maka berikanlah kepadaku amalan yang dapat membuatku kaya karena sesungguhnya aku sudah bosan menjadi orang miskin," Berkatalah nabi Musa, "bersyukurlah kamu niscaya Allah akan menambahkan nikmatmu." "Wahai nabi Musa, untuk minum dan makan sehari saja aku kesulitan Bagaimana aku bisa bersyukur? Apa yang harus aku syukuri wahai nabi?", orang itu bertanya. "Kalau begitu, pulanglah engkau", jawab nabi Musa. Maka pulanglah orang itu. Setelah itu dan sampai akhir hayatnya hiduplah ia dalam keadaan miskin karena ia enggan bersyukur ... Lalu beberapa saat kemudian seseorang menemui nabi Musa dan berkata, "Wahai nabi Allah, aku ini adalah orang kaya. Maka berikanlah kepadaku amalan yang dapat membuatku miskin karena sesungguhnya aku sudah bosan menjadi orang kaya," Berkatalah nabi Musa, "janganlah engkau bersyukur niscaya Allah t
Baca selengkapnya

Definisi Cinta

Gambar
CINTA adalah KEKUATAN yang mampu mengubah duri jadi mawar, mengubah cuka jadi anggur, mengubah malang jadi untung, mengubah sedih jadi riang, mengubah setan jadi nabi, mengubah iblis jadi malaikat, mengubah sakit jadi sehat, mengubah kikir jadi dermawan, mengubah kandang jadi taman, mengubah penjara jadi istana, mengubah amarah jadi ramah, mengubah musibah jadi muhibbah, itulah CINTA !!! .:. Bait Puisi yang dibacakan oleh Ayatul Husna dalam novel Ketika Cinta Bertasbih
Baca selengkapnya

Hafalan Shalat Delisa

Gambar
Pertama kali aku mendengar judul ini saat dalam perjalanan Kediri-Surabaya via status salah satu teman mayaku, “Habis nonton Hafalan Shalat Delisa, Terharu”, Oooh habis nonton film pikirku. Sesampainya di kos ku lihat bapak dan ibu kos beserta 3 mutiaranya bergegas pergi, “ mau nonton Delisa", jelasnya waktu ku tanya akan kemana. Hmm… Bukan karena namaku (Lisa, red ) yang sering dipanggil “de” menjadi “De’ Lisa” menjadi mirip dengan si tokoh lantas aku penasaran, hehe, tapi karena film ini diadopsi dari novel dan rata-rata film begini (adopsi novel) memiliki nilai beda di mata pecinta karya sastra. Mau nonton, tapi lihat tugas kuliah (UAS dan Skripsi) menghadang, akhirnya kuurungkan niatku. Dan aku berencana nonton film ini selepas skripsi (Kamis, 12 Januari 2012), tapi akhirnya pun tidak jadi karena hujan (_ _“)
Baca selengkapnya