PEMBANGKITAN BILANGAN ACAK
(Random Number Generator)
1. Cara memperoleh
a. Zaman Dahulu, dengan cara:
·
Melempar
dadu
·
Mengocok
kartu
b. Zaman Modern (>1940), dengan cara:
Membentuk bilangan acak secara
numerik/aritmatik (menggunakan kompeter ), disebut “Pseudo Random Number” (bilangan
pseudo acak).
2. Pembangkitan Bilangan Acak Harus
a. Berdistribusi uniform(0,1) dan tidak
berkorelasi antar bilangan.
b. Membangkitkan cepat, storage tidak besar
c. Dapat di “reproduce”
d. Periode besar, karena mungkin bilangan
acak dibangkitkan berulang.
3. Pengertian Bilangan Acak
a. Bialangan acak adalah bilangan yang tidak
dapat diprediksi kemunculannya.
b. Tidak ada komputasi yang benar-benar
menghasilkan deret bilangan acak secara sempurna.
c. Bilangan acak yang dibangkitkan oleh
komputer adalah bilangan acak semu (Pesudo Random Number), karena menggunakan
rumus-rumus matematika.
d. Banyak algoritma atau metode yang dapat
digunakan untuk membangkitkan bilangan acak.
e. Bilangan acak dapat dibangkitkan dengan
pola tertentu yang dinamakan dengan distribusi mengikuti fungsi distribusi yang
ditentukan.
4. Sifat-Sifat Pembangkitan Bilangan
Acak
a. Independen : tiap variabelnya harus bebas dari ketentuan,
seperti:
·
Zi-1 = merupakan hasil akhir
·
Z0 = merupakan angka pertama
yang bebas tertentu
·
a = merupakan angka pertama yang bebas
dengan ketentuan tersendiri
·
c = merupakan angka bebastetapi tidak
ada hubungan tertentu dengan m
b. Uniform : suatu distribusi yang umum (
distribusi probabilitas) dan sama untuk semua besaran yang dikeluarkan/diambil.
Hal ini berarti bahwa diusahakan probabilitasnya sama untuk setiap penarikan
random number tersebut.
c. Dense: Density Probabilitas Distribution
harus mengikuti syarat probabilitas (antara 0 dan 1). Hal ini berarti dalam
penarikan angka-angka yang dibutuhkan dari Random Number Genrator cukup untuk
banyak dan dibuat sedemikian rupa sehingga 0 ≤ R.N.≤ 1.
d. Efficient : artinya dapat cukup Sederhana
dan dalam menggunakan cara ini harus terlebih dahulu memilih angka-angka untuk
variabel-variabel yang cocok. Hal ini berarti dalam penarikan random number
tersebut harus dapat menentukan angka-angka untuk variabel yang sesuai sehingga
dapat berjalan terus-menerus.
5. Penentuan Random Number
a. Tabel Random Number, tabel ini sudah banyak ditemukan mulai dari
enam digit sampai dengan belasan digit.
b. Electronic Random Number, number ini
banyak juga dipergunakan dalam percobaan penelitian.
c. Conguential Pseudo Random Number
Generator, yang terdiri dari tiga bagian:
·
Linear
Congruential Generator (LCG)
·
Multiplicative
Random Number Generator
·
Mixed
Congruential Random Number Generator
Berikut
penjelasan bagian-bagian dari Conguential Pseudo Random Number Generator
1. Linear Congruential Generator (LCG)
a. Metode ini digunakan untuk membangkitkan
bilangan acak denagn distribusi uniform.
b. Pseudo RNG, berbentuk:
Zi =
(aZi-1 +c) mod m
Dimana :
Zi =
bilangan acak ke-i dari deretnya
Zi-1
= bilangan acak
sebelumnya
a = faktor pengali
c = increment
m = modulus
kunci
pembangkit adalah Z0 yang disebut umpan (seed)
Contoh
1. LCG:
Membangkitkan bilangan acak sebanyak 8
kali dengan a = 2, c = 7, m = 10, dan Z0 = 2
Z1 = (2.2+7) mod 10 = 1
Z2 = (2.1+7) mod 10 = 9
Z3
= (2.9+7) mod 10 = 5
Z4
= (2.5+7) mod 10 = 7
Z5
= (2.7+7) mod 10 = 1
Z6
= (2.1+7) mod 10 = 9
Z7
= (2.9+7) mod 10 = 5
Z8
= (2.5+7) mod 10 = 7
Bilangan acak yang dibangkitkan adalah
:
1 9 5 7 1 9 5 7
jadi terjadi pengulangan bilangan
secara periodik (4).
Contoh 2. LCG:
Membangkitkan bilangan acak sebanyak 8
kali dengan a = 4, c = 7, m = 15, dan Z0 = 3
Z1 = (4.2+7) mod 15 = 4
Z2 = (4.4+7) mod 15 = 8
Z3
= (4.8+7) mod 15 = 9
Z4
= (4.9+7) mod 15 = 13
Z5
= (4.13+7) mod 15 = 14
Z6
= (4.14+7) mod 15 = 3
Z7
= (4.3+7) mod 15 = 4
Z8
= (4.4+7) mod 15 = 8
Bilangan acak yang dibangkitkan adalah
:
4 8 9 13 14 4 8 jadi
tidak terjadi pengulangan secara periodik.
c. Terjadi pengulangan pada periode
tertentu atau setelah sekian kali pembangkitan, hal ini adalah salah satu sifat
pembangkitan dari metode ini dan PRNG pada umumnya.
d. LCG mempunyai periode tidak lebih besar
dari m, dan pada kebanyakan kasus periodenya kurang dari itu.
e. LCG mempunyai periode penuh (m – 1) jika
memenuhi syarat berikut:
1. c relatif prima terhadap m
2. a-1 dapat dibagi dengan semua faktor
prima dari m
3. a-1 adalah kelipatan 4 juka m adalah
kelipatan 4
4. m> maks(a,c, Z0)
5. a>0,c>0
f. penentuan konstanta LCG (a,c dan m)
sangat menentukan baik tidaknya bilangan acak yang diperoleh dalam arti
memperoleh bilangan acak yang seakan-akan terjadi pengulangan.
2. Multiplicative Random Number
Generator
Zi
= (a.Zi-1) mod m
Dimana:
a. Bilangan pseudo dimulai dengan nilai
awal Z0 yang disebut benih.
b. a & m : bilangan bulat positif
tertentu
c. a. Zi-1 dibagi dengan m dan
sisanya diambil sebagai nilai Zn
d. Agar Zn berprilaku acak yang
dapat dipertanggungjawabkan maka:
·
Modulo
m dipilih sebesar mungkin untuk memperbesar periode
·
a
dipilih agar korelasi antar Zn minimum
·
benih
Z0 : bilangan Bulat positif ganjil, Z0 <m
·
Bilangan
acak : U = Zn/m
Untuk pemilihan nilai-nilai yang terbaik
dijabarkan sebagai berikut:
a. Pemilihan nilai: m (modulo) merupakan
suatu angka integer yang cukup besar dan merupakan satu kata dari yang dipakai
pada komputer.
b. Pemilihan konstanta multipliter: a harus
tepat.
c. Pemilihan untuk Z0 yang
dikenal dengan : SEED = Z0 mengharuskan relative belakangan prima
terhadap m. Hal ini dapat diperhatikan dengan mudah apabila dicari untuk m
adalah angka berpangkat 2. Dengan demikian untuk Z0 adalah setiap
angka- angka yang ganjil seperti : ISEED =12357 dapat diambil sembarang
asalkan bilangan ganjil dan biasanya cukup besar.
d. Bilangan c yang dipilih harus bukan
merupakan kelipatan dari m dan juga harus bilangan ganjil.
3. Mixed Congruential Random Number
Generator
a. Pseudo Random Number ini dapat
dirumuskan dengan:
Zn
= an Z0 an-1/a-1.c+ (mod.m)
b. Rumus Pseudo Number generator ini adalah
dengan syarat utama n harus sejumlah bilangan integer (bulat) dan lebih besar
dari nol, runus ini dikenal juga dengan nama’ Linier Congruential RNG’
c. Namun apabila nilai C = 0 maka akan
diperoleh rumus yang dikenal ‘Multiplicative Congruen RNG’. Rumus multiplivative
in sukup baik untuk masa-masa yang akan
dating karena sedikit sekali storage memori yang dibutuhkan.
d. Beberapa kondisi syart-syaratnya sebagai
berikut:
·
C
= adalah bilangan relative prima terhadap n
·
N
= 1 (mod.q) untuk setiap factor prima q dari m
·
A
= 1 (mod 4) apabila 4 adalah suatu factor dari m
e. Kondisi 1 berarti bahwa pembagi umum
yang terbesar dari c dan m adalah satu. Dan kondisi ini mudah disari.
f. Kondisi 2 berarti:
a-q(a/q) =1
Apabila k
=
(a/q) akan dapat diperoleh untuk a, yaitu a =1+ qk
Diman q adalah faktor prima dari m
g. Kondisi 3 : berarti a = 1+4k
Apabila
: = adalah integer. Artinya m bilangan bulat dapat dibagi 4
6. Penerapannya
Simulasi
kejadian”acak” (“random” events) dalam sebuah restorsn drive-through
a. Waktu tiba mobil di jendela restoran drive-through
b. Waktu yang diperlukan pengemudi untuk
memesan
c. Jumlah hamburger, minuman, dan kentang
yang diorder
d. Waktu yang diperlukan oleh restoran
untuk menyiapkan pesanan
e. Panjang renntetan bilangan acak dapat
dibagi-bagi dalam segmen yang lebih kecil, yang disebut aliran/stream.
f. Contoh : stream 1: pola kedatangan mobil
ke jendela restoran drive-through; stream 2 : xwaktu yang diperlukan oleh
pengemudi untuk memesan.