BAB IV GENERATOR BILANGAN RANDOM
4.1. Generator Bilangan Random dan Fungsi Distribusi Pada simulasi seringkali dibutuhkan bilangan-bilangan yang mewakili keadaan sistem yang disimulasikan. Biasanya, kegiatan dimulai dengan mengumpulkan data pengamatan. Namun demikian, data hasil pengamatan tidak dapat dipakai langsung untuk simulasi sebab jika demikian maka simulasi dilakukan terhadap performansi sistem pada saat yang telah dilampaui padahal tujuan studi simulai adalah untuk mengkaji keadaan sistem pada saat yang akan datang. Maka, biasanya setelah banyak data pengamatan diperoleh, data dianalisis untuk diketahui distribusi statistiknya. Setelah mendapat distribusi yang paling “cocok” sesuai dengan data sampel, hargaharga yang mewakili sistem dibangkitkan dengan generator. Random Number Generator adalah suatu algoritma yang digunakan untuk menghasilkan urutan-urutan atau sequence dari angka-angka sebagai hasil dari perhitungan dengan komputer yang diketahui distribusinya sehingga angka-angka tersebut muncul secara random dan digunakan terus menerus. Salah satu generator terpenting yang akan dipakai untuk semua generator bilangan random lain adalah generator bilangan random terdistribusi uniform (yang mempunyai probabilitas sama untuk suatu daerah harga tertentu).
4.2. Generator Bilangan Random Terdistribusi Uniform Cara pembangkitan bilangan random mula-mula dipakai adalah secara manual, dengan : Melempar kartu, dadu, bola yang diberi nomor. Memutar piringan bernomor Mengambil nomor sembarang dari buku telepon, data sensus, dll. Karena sampel yang dibutuhkan seringkali banyak, maka mulai dipikirkan mesinmesin yang dapat menghasilkan bilangan random, yang terkenal adalah ERNIE (Electric Random Number Indicator Equiment) dan alat eletronik yang dikeluarkan oleh RAND Corp.
Pemodelan &Simulasi : Generator Bil Random
18
Munculnya komputer memungkinkan untuk mendapatkan sampel, dengan cara : 1. Mula-mula dengan menyimpan hasil pembangkitan mesin dalam tabel, cara ini memakan banyak memori karena simulasi seringkali membutuhkan data yang bahkan sampai jutaan banyaknya. 2. Pembangkitan bilangan random melalui rumus-rumus aritmatika, yang akan dibahas selanjutnya. Biasanya setiap kompilator menyertakan generator bilangan random Kriteria generator bilangan random dengan rumus aritmatika yang baik adalah sbb : Hasil pembangkitannya adalah bilangan-bilangan yang terdistribusi uniform antara 0 – 1 dan tak ada korelasi satu sama lain (dense/density Probabilitas Distribusi). Performansinya cepat dan tidak memerlukan banyak memori komputer (efficient). Harus mampu mereproduksi sederetan bilangan yang persis sama (uniform), karena dalam simulasi dibutuhkan untuk mengeksekusi model yang berbeda-beda dengan data yang sama untuk membandingkan model-model yang mewakili persoalan nyata yang sama. Sampel data yang identik juga dibutuhkan dalam tahapan verifikasi dan debugging dari program komputer yang mewakili model tersebut. Mampu menghasilkan beberapa “stream” (deret) yang independent, setiap deret biasanya dipakai untuk mewakili hal yang berbeda, misalnya deret yang satu mewakili waktu antar kedatangan sedangkan yang lain untuk mewakili waktu pelayanan. Generator Bilangan Random Terdistribusi Uniform : 1. Metoda MID-SQUARE Bilangan random dengan metoda ini dibangkitkan dengan cara : - ambil Z0 sebuah bilangan yang terdiri dari 4 digit - kuadratkan Z0, sehingga diperoleh bilangan 8 digit - ambil 4 digit ditengah dari hasil kuadrat tsb. - pakai 4 digit tengah tersebut untuk membangkitkan bilangan berikutnya. Jika tidak diperoleh bilangan 8 digit (karena 4 digit tengah mengandung nol diawal), maka buat menjadi 8 digit dengan menambahkan nol di depan.
Pemodelan &Simulasi : Generator Bil Random
19
Contoh : I
Z
Z2
0
7182
51581124
1
5811
33767721
0,5811
2
7677
58936329
0,7677
U
3 2. Metoda LCG (Linear Conguential Generator)/Additive RNG Yang ditulis dengan rumus : Zi = (a Zi-1 + c) modulo m Dimana : a : faktor pengali, nilainya harus lebih besar dari √m Biasanya dinyatakan dengan syarat : m a m m 100 m ma 100
m
c : faktor penjumlah, c harus berangka ganjil apabila m bernilai pangkat dua. Tidak boleh nilai berkelipatan dari m. m : modulo, harus bilangan prima atau bilangan tidak terbagikan. Z0 : nilai awal, harus angka integer, ganjil dan cukup besar. Untuk memulai harus dipunyai Z0 yang disebut “benih”, dan terlihat seperti pada contoh bahwa bilangan terbangkit adalah bilangan random yang sebenarnya “berulang”, sesuai dengan pemilihan faktor pengali dan faktor penjumlah. Contoh : m = 16, a = 5, c = 3, Z0 = 7 maka diperoleh 7,6,1,8,11,10,5,12,15,14,9,0,3,2,13,4,7,6,1,8,... pada contoh di atas terlihat bahwa setelah 16 bilangan, maka deret berulang. Pengulangan ini tidak dapat dihindarkan, namun diharapkan agar deret yang didapat mempunyai periode yang panjang karena untuk simulasi dibutuhkan banyak sekali bilangan. Bilangan-bilangan random yang dibangkitkan dikatakan mempunyai periode “penuh“, jika periodenya sama dengan m (p <= m). Jika c = 0 maka generator disebut multiplikatif.
Pemodelan &Simulasi : Generator Bil Random
20
3. Metoda Multiplikatif rumus : Zi = a * Zi-1 modulo m Dimana : m : merupakan satu angka integer yang cukup besar dan merupakan satu kata (word) dari yang dipakai pada komputer. Contoh : Dalam komputer IBM 360/370 sistem sebuah kata adalah 32 bits panjangnya, berarti angka integer yang terbesar dalam satu kata komputer adalah : 232-1 – 1 = 231 -1 = 2147488647, maka nilai m harus lebih satu integer, atau : m = 232-1 + 1 = 2.147.488.648 Untuk mesin komputer sistem 1130/1800 IBM dikenal dengan 16 bits words maka untuk memilih m adalah : m = 216-1 = 32.768 Untuk microkomputer dengan 8 bits, maka m = 28-1 = 128 a : konstanta multiplier, harus tepat Pemilihan nilai a harus bilangan prima terhadap m, a juga harus bilangan ganjil. Pemilihan yang terbaik adalah dengan rumus : a = 2b/2 ± 3 yang lebih mendekat pada ketepatan. Untuk sistem IBM 1130/1800 dengan 16 bits akan diperoleh a = 216/2 ± 3 = 259 Untuk microkomputer dengan 8 bits akan diperoleh a = 28/2 ± 3 = 19 Z0 : Seed, prima terhadap m, dapat diambil sembarang bilangan ganjil dan cukup besar.
Pemodelan &Simulasi : Generator Bil Random
21
4. Metoda General Congruent rumus : Zi = g( Zi-1, Zi-2,
...) modulo m
Dimana : g adalah kuadratik : Zi = (a1 * Zi-12 + a2 * Zi-22
+ c) mod m
g adalah fungsi linier : Zi = (a1 * Zi-1 + a2 * Zi-2 + ... + an * Zi-n) mod m g adalah fungsi Fibonacci : Zi = Zi-1 + * Zi-2
4.3. Bilangan Random Terdistribusi Kontinu dan Tidak Uniform Umumnya simulasi membutuhkan sederetan bilangan random yang diturunkan dari distribusi yang kontinu dan tidak uniform. Beberapa metoda yang dipakai kebanyakan berdasarkan penggunaan dari sekumpulan bilangan random yang terdistribusi uniform. Metoda yang sering digunakan adalah : 1. Metoda transformasi invers (inverse transformation method) 2. Metoda penolakan (rejection method) A. Metoda Transformasi Invers Jika diketahui : a. μ (i = 1, 2, ...) adalah bilangan random terdistribusi uniform antara 0 – 1 b. F-1 (x) adalah inverse dari fungsi distribusi kumulatif untuk suatu variabel random x, maka X1 = F-1 (μ1) adalah sampel random dari variabel x yang mempunyai fungsi distribusi kumulatif F(x) Contoh : Diberikan fungsi kepadatan F(x) = a (1 – x), = 0,
Pemodelan &Simulasi : Generator Bil Random
0<x<1 untuk x yang lain
22
maka : F(x) =
x
0
a (1 x )
x2 a( x ) 2 Harga a = 2
supaya
f ( x )dx 1
(dari definisi fungsi distribusi kumulatif).
Untuk μ = F(x), maka cari x dari fungsi invers : x2 ) 2
a( x
1
x 1 (1 ) 2 karena x adalah random antara 0 – 1 maka demikian juga halnya dengan 1 – μ sehingga rumus di atas dapat disederhanakan
x 1
1 2
dengan mengambil 5 bilangan random dari generator sebagai input maka outputnya adalah : μ
x
0,1009
0,6823
0,3754
0,3873
0,0842
0,7098
0,0901
0,6998
0,1280
0,6422
Maka output x di atas adalah bilangan random dengan fungsi kepadatan f(x) dimaksud
Pemodelan &Simulasi : Generator Bil Random
23
