Memilih secara acak

Selamat tahun baru 2011!. tahun lalu sepertinya blog ini agak terabaikan. sangat sedikit tulisan yang saya buat di blog ini yang ketika saya baca kembali memberikan kesan bahwa tidak banyak yang saya kerjakan di tahun 2010. Padahal justru di tahun 2010 ada banyak hal luar biasa yang terjadi diantaranya : saya dan istri lulus S2 dan saya lulus seleksi cpns dosen di lingkungan informatika itb. Ada yang bilang bahwa saya sangat beruntung tapi yang pasti saya sangat bersyukur bisa mengalami itu semua. mengawali tahun yang baru ada banyak keinginan yang ingin saya capai salah satunya adalah kembali mengurusi dan menghidupkan kembali blog ini dan kalau bisa menulis tiap bulan, tiap minggu, atau bahkan tiap hari.

Kembali ke topik tulisan, kali ini saya akan bercerita tentang pemilihan secara acak. Topik ini terkait dengan keterlibatan saya selama S2 yang mempelajari teknik-teknik yang berbasis stokastik(acak) dalam persoalan optimasi diskret dan kontinu seperti Genetic Algorithm, Ant Colony Optimization dan Particle Swarm Optimization. Teknik-teknik tersebut umumnya memanfaatkan fungsi pembangkitan bilangan acak dengan distribusi merata(uniform/iid) atau berbasis pemodelan densitas peluang tertentu.

Salah satu materi kuliah pemodelan dan simulasi yang seringkali digunakan di bidang lain seperti intelejensia buatan khususnya algoritma stokastik ataupun simulasi yang ada di dalam permainan adalah memilih secara acak atau membuat event atau kejadian yang terjadi secara ‘acak’ berdasarkan distribusi tertentu. Teknik yang digunakan untuk membangkitkan angka ‘acak’ (lebih tepatnya semi acak atau pseudo-random) biasanya diturunkan dari pembangkitan angka acak dari distribusi seragam (U, uniform). Adapun teknik pembangkitan angka semi-acak antara lain Linear Congruential Generator. LCG merupakan teknik yang digunakan berbagai compiler untuk menyediakan fasilitas pembangkit bilangan acak.

Bilangan acak, pada umumnya tidak terdistribusi merata bahkan ada yang tidak memiliki model matematis yang pas seperti misalnya distribusi peluang yang digunakan dalam simulasi koloni semut untuk persoalan optimasi (ant colony optimization) atau distribusi peluang yang berisi pilihan diskret yang antar elemennya tidak memiliki urutan atau istilahnya nominal. Lantas bagaimana membuat pilihan secara acak dari distribusi yang tidak seragam bahkan tidak beraturan (non-parametrik) tersebut? Cara yang dapat digunakan adalah metode invers yaitu dengan memanfaatkan distribusi peluang dalam bentuk histogram yang dibuat kumulatifnya (distribusi kumulatif) lalu di-inverskan dan memanfaatkan bilangan acak dari distribusi seragam sebagai parameternya. Teknik ini sebetulnya dimanfaatkan dalam pengolahan citra yaitu dalam melakukan ekualisasi histogram untuk meningkatkan kontras yang sebetulnya melakukan pemerataan distribusi intensitas piksel ke seluruh rentang intensitas citra.

Misalkan untuk suatu variabel ada 4 kemungkinan keadaannya yaitu a, b, c, dan d. berdasarkan statistik, peluang kemunculannya yaitu p(a) = 1/10, p(b) = 1/5, p(c) = 1/2, dan p(d) = 1/5 sehingga total peluangnya adalah 1. Distribusi peluang tersebut menceritakan bahwa jika kita memilih secara acak berdasarkan distribusi tersebut maka kemungkinan c muncul akan lebih besar dibandingkan tiga keadaan lainnya. Untuk memilih atau membangkitkan bilangan acak tersebut maka dari distribusi peluang tersebut (pdf) harus dibuat distribusi kumulatifnya (cdf). Walaupun variabel acak tersebut tidak memiliki urutan, agar memudahkan perhitungan bisa dianggap terurut (walaupun bisa ditukar posisinya yang mempertahankan kondisi bebas dari konfigurasi urutan).

Distribusi kumulatif dari contoh tersebut yaitu c(a) = 1/10, c(b) = 3/10, c(c) = 8/10, dan c(d) = 10/10. Misalkan dari pembangkit bilangan semi-acak menghasilkan bilangan acak dengan distribusi seragam yaitu x = 0.5 atau dalam pecahan bisa juga ditulis sebagai x = 5/10 maka untuk memilih diantara empat pilihan tersebut dilakukan dengan memilih keadaan yang fungsi distribusi kumulatifnya lebih besar dari x dan fungsi distribusi kumulatif keadaan sebelumnya lebih kecil dari x. Pada kasus ini keadaan yang dipilih adalah keadaan c. Jika kita membuat 10 pemilihan dengan distribusi yang seragam (katakanlah x = {1/10, 2/10, …, 10/10}) maka keadaan yang dipilih akan sesuai dengan deskripsi distribusi peluang di awal.

kalau divisualisasikan maka sumbu x adalah bilangan acak yang sebarannya seragam, sumbu y adalah bilangan acak hasil yang distribusi peluangnya seperti yang dideskripsikan di fungsi distribusi sebelumnya (gambar pdf).

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s