Random Number Generator

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:

_·         Z_i-1 = merupakan hasil akhir

_·         Z₀ = 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:

Z_i = (aZ_i-1 +c) mod m

     Dimana :

     Z_i    = bilangan acak ke-i dari deretnya

               Z_i-1 =  bilangan acak sebelumnya

               a    = faktor pengali

               c    = increment

               m  = modulus

               kunci pembangkit adalah Z₀ yang disebut umpan (seed)

    Contoh 1. LCG:

          Membangkitkan bilangan acak sebanyak 8 kali dengan a = 2, c = 7, m = 10, dan Z₀ = 2

              Z₁ = (2.2+7) mod 10 = 1

              Z₂ = (2.1+7) mod 10 = 9

                   Z3 = (2.9+7) mod 10 = 5

                   Z₄ = (2.5+7) mod 10 = 7

                   Z₅ = (2.7+7) mod 10 = 1

                   Z₆ = (2.1+7) mod 10 = 9

                   Z₇ = (2.9+7) mod 10 = 5

                   Z₈ = (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 Z₀ = 3

              Z₁ = (4.2+7) mod 15 = 4

              Z₂ = (4.4+7) mod 15 = 8

                   Z3 = (4.8+7) mod 15 = 9

                   Z₄ = (4.9+7) mod 15 = 13

                   Z₅ = (4.13+7) mod 15 = 14

                   Z₆ = (4.14+7) mod 15 = 3

                   Z₇ = (4.3+7) mod 15 = 4

                   Z₈ = (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, Z₀)

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

Z_i = (a.Z_i-1) mod m

Dimana:

a.     Bilangan pseudo dimulai dengan nilai awal Z₀ yang disebut benih.

b.     a & m : bilangan bulat positif tertentu

c.      a. Z_i-1 dibagi dengan m dan sisanya diambil sebagai nilai Z_n

d.     Agar Z_n berprilaku acak yang dapat dipertanggungjawabkan maka:

·        Modulo m dipilih sebesar mungkin untuk memperbesar periode

·        a dipilih agar korelasi antar Z_n minimum

·        benih Z₀ : bilangan Bulat positif ganjil, Z₀ <m

·        Bilangan acak : U = Z_n/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 Z₀ yang dikenal dengan : SEED = Z₀ mengharuskan relative belakangan prima terhadap m. Hal ini dapat diperhatikan dengan mudah apabila dicari untuk m adalah angka berpangkat 2. Dengan demikian untuk Z₀ adalah setiap angka- angka yang ganjil seperti : I_SEED =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:

Z_n = aⁿ Z₀ aⁿ-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.

Model Simulasi Monte Carlo

Simulasi Monte Carlo adalah proses menurunkan secara acak nilai variabel tidak pasti  secara berulang-ulang untuk mensimulasikan model. Metode Monte Carlo karena itu merupakan teknik stokastik. Kita dapat menemukan metode Monte Carlo diaplikasikan dalam berbagai bidang, mulai dari ekonomi sampai fisika nuklir untuk pengaturan lalu lintas aliran. Tentu saja cara aplikasinya berbeda dari satu bidang ke bidang lainnya, dan ada banyak sekali himpunan bagian Monte Carlo meskipun dalam satu bidang yang sama. Hal yang menyamakan semua itu adalah bahwa percobaan Monte Carlo membangkitkan bilangan acak untuk memeriksa permasalahan.

Jika suatu sistem mengandung elemen yang mengikut sertakan faktor kemungkinan, model yang digunakan adalah model Monte Carlo. Dasar dari simulasi Monte Carlo adalah percobaan elemen kemungkinan dengan menggunakan sampel random (acak). Metode ini terbagi dalam 5 tahapan:

1.      Membuat distribusi kemungkinan untuk variabel penting

2.      Membangun distribusi kemungkinan kumulatif untuk tiap‐tiap variabel di tahap pertama

3.       Menentukan interval angka random untuk tiap variabel

4.      Membuat angka random

5.      Membuat simulasi dari rangkaian percobaan.

 Penjelasan dari ke 5 tahapan tersebut adalah sebagai berikut:

1.      Membuat distribusi kemungkinan untuk variabel penting

Gagasan dasar dari simulasi monte carlo adalah membuat nilai dari tiap variabel yang merupakan bagian dari model yang dipelajari. Banyak variabel di dunia nyata yang secara alami mempunyai berbagai kemungkinan yang mungkin ingin kita simulasikan. Salah satu cara umum untuk membuat distribusi kemungkinan untuk suatu variabel adalah memperhitungkan hasil di masa lalu. Kemungkinan atau frekuensi relative untuk tiap kemungkinan hasil dari tiap variabel ditentukan dengan membagi frekuensi observasi dengan jumlah total observasi

Contoh: Permintaan akan ban di toko ban “Benjol” selama 200 hari kebelakang terlihat di tabel berikut:

Permintaan	Frekuensi
0	10
1	20
2	40
3	60
4	40
5	30
200 hari

Tabel 1.

Kita dapat merubah keadaan tersebut diatas menjadi distribusi kemungkinan (bila kita asumsikan tingkat penjualan dimasa lalu akan tetap bertahan sampai ke masa depan) dengan membagi tiap permintaan dengan total permintaan. Seperti pada tabel berikut:

Variabel Permintaan	Kemungkinan terjadi
0	10/200 = 0.05
1	20/200 = 0.10
2	40/200 = 0.20
3	60/200 = 0.30
4	40/200 = 0.20
5	30/200 = 0.15
200/200 = 1.00

Tabel 2.

2.      Membangun distribusi kemungkinan kumulatif untuk tiap‐tiap variabel di tahap pertama

Konversi dari distribusi kemungkinan biasa, seperti pada kolom kanan tabel 2 menjadi distribusi kumulatif dilakukan dengan menjumlahkan tiap angka kemungkinan dengan jumlah sebelumnya seperti pada tabel 3.

Variabel Permintaan	Kemungkinan	Kemungkinan Kumulatif
0	0.05	0.05
1	0.10	0.15
2	0.20	0.35
3	0.30	0.65
4	0.20	0.85
5	0.15	1.00

Tabel 3.

Probabilitas kumulatif terlihat pada gambar dibawah, digunakan pada tahap ke 3 untuk membantu menempatkan nilai random

3.      Menentukan interval angka random untuk tiap variabel

Setelah kita menentukan probabilitas kumulatif untuk tiap variabel yang termasuk dalam simulasi, kita harus menentukan batas angka yang mewakili tiap kemungkinan hasil. hal tersebut ditujukan pada interval angka random. Penentuan interval didasari oleh kemungkinan kumulatif

Permintaan	Kemungkinan	Kemungkinan Kumulatif	Interval Angka Random
0	0.05	0.05	01 s/d 05
1	0.10	0.15	06 s/d 15
2	0.20	0.35	16 s/d 35
3	0.30	0.65	36 s/d 65
4	0.20	0.85	66 s/d 85
5	0.15	1.00	86 /d 100

Tabel 4. Interval Angka Random

4.      Membuat angka random

Untuk membuat angka random kita bisa menggunakan software Microsoft Excel dengan menggunakan perintah Randbetween, misal untuk angka random dari 1‐100, kita tuliskan perintah: =randbetween(1,100) dan diulangi sejumlah baris yang diperlukan

5.      Membuat simulasi dari rangkaian percobaan

Kita bisa membuat simulasi dari sebuah eksperimen dengan mengambil angka random dari gambar diatas, misal kita akan membuat simulasi untuk 10 hari, kita ambil Kolom A1‐A10. Cara penentuan permintaan adalah dengan ditentukan oleh angka random. Contohnya bila angka random adalah 56, angka itu terletak pada interval 36 s/d 65 yang berarti permintaan 3 buah ban

Hari	Angka Random	Permintaan (Simulasi)
1	28	2
2	50	3
3	78	4
4	8	1
5	16	2
6	61	3
7	98	5
8	51	3
9	45	3
10	21	2
28

Total permintaan untuk 10 hari adalah 28 ban, rata‐rata permintaan per hari adalah 2,8 ban.