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.