Pengantar Automata Seluler

Bab 2 Pengantar Automata Seluler 2.1

Automata Seluler Dua Dimensi

Pada umumnya, model penyebaran kebakaran hutan dibagi dalam dua tipe, yaitu model stokastik dan model deterministik. Model stokastik untuk penyebaran kebakaran hutan digunakan untuk memprediksi kemungkinan perilaku api dalam kondisi tertentu berdasarkan percobaan dan data dari laboratorium. Sementara itu, model deterministik mengkaji perilaku api saat kebakaran berdasarkan karakteristik api, hutan, dan sekitar hutan serta sistem yang terbentuk di antara ketiganya. Secara matematis, model penyebaran api yang deterministik terbagi ke dalam dua kategori yaitu model vektor dan model automata seluler. Salah satu penggunaan model vektor adalah untuk mengkaji sebaran api dengan meninjau gelombang sebaran api dan temperatur. Sedangkan model automata seluler mengkaji sebaran api dengan aturan yang dide…nisikan berdasarkan sistem dinamik yang diskrit dalam dimensi ruang tertentu. Automata seluler (CA) merupakan sistem dinamik diskrit dari sekumpulan sel yang identik. Masing-masing kumpulan sel tersebut memiliki keadaan yang berubah setiap langkah waktu yang diskrit berdasarkan aturan deterministik. CA dua dimensi yang berhingga dapat dide…nisikan sebagai suatu ruang A = (C; S; V; f ) yang terdiri dari sel-sel identik dengan C = f(a; b); 1 b

a

r; 1

cg; untuk suatu (r; c) 2 Z, yaitu himpunan bilangan asli . Ruang sel heksa-

gonal dapat dilihat pada Gambar 2.1. Adapun sel (a; b) dide…nisikan sebagai pasangan terurut sel (a; b). Setiap sel (a; b) diasumsikan sebagai keadaan dan 3

BAB 2. PENGANTAR AUTOMATA SELULER

4

merupakan elemen dari suatu kumpulan keadaan, S. Keadaan dari sel (a; b) (t)

pada waktu t dide…nisikan sebagai sab .

Gambar 2.1: Ruang Sel Heksagonal.

Ketetanggaan sel (a; b) dinyatakan oleh Vab dan j V j= m, untuk 8 sel (a; b). Adapun Vab dide…nisikan: Vab = f(a +

1; b

+

1 ); :::; (a

+

m; b

+

m)

:(

k;

k)

2 V g:

Gambar 2.2: Lingkungan Sel O.

Dalam tugas akhir ini, ketetanggaan sel O = (a; b) seperti yang ditunjukkan


5

pada Gambar 2.2, adalah: Vo = fO; N; N E; SE; S; SW; N W; N N E; E; SSE; SSW; W; N N W g: Berdasarkan jenis ketetanggaan tersebut, dide…nisikan dua macam ketetanggaan sel (a; b), yaitu: 1. sel tetangga dekat (Gambar 2.2 yang berwarna hijau), Vn = fN; N E; SE; S; SW; N W g 2. sel tetangga jauh (Gambar 2.2 yang berwarna jingga), Vd = fN N E; E; SSE; SSW; W; N N W g: Dalam tugas akhir ini, terdapat indeks pelabelan untuk setiap sel tetangga yang akan digunakan untuk perhitungan keadaan tiap sel yaitu (a; b). Indeks pelabelan ini dibedakan berdasarkan b genap atau ganjil.

Gambar 2.3: Indeks Ketetanggaan: (a) b ganjil dan (b) b genap.

Ketetanggaan sel (a; b), dengan b ganjil (Gambar 2.3(a)) adalah odd = f(a; b); (a V(a;b)

(a + 1; b

1; b); (a; b + 1); (a + 1; b + 1); (a + 1; b); 1); (a; b

1); (a

(a + 2; b + 1); (a + 2; b

1; b + 1); (a; b + 2);

1); (a; b

2); (a

1; b

1)g:

(2.1)


6

Ketetanggaan sel (a; b), dengan b genap (Gambar 2.3(b)) adalah even = f(a; b); (a V(a;b)

(a; b

1; b); (a

1); (a

1; b

1; b + 1); (a; b + 1); (a + 1; b); 1); (a

(a + 1; b + 1); (a + 1; b

2; b + 1); (a; b + 2);

1); (a; b

2); (a

2; b

1)g: (2.2)

(t)

Keadaan setiap sab berubah secara deterministik dalam suatu perubahan waktu yang diskrit. Perubahan setiap keadaan dari sel (a; b) memenuhi suatu fungsi transisi lokal f : S 13 ! S, yaitu (t+1)

sab

(t)

= f (sa+

(t)

1 ;b+ 1

; :::; sa+

13 ;b+ 13

(2.3)

);

dengan S 13 adalah kumpulan keadaan sel (a; b) dan 12 sel tetangganya. Kon…gurasi CA dua dimensi pada waktu t adalah C (t) = s(t) ,1 a ab n o (0) (t) 1 b c, dan C adalah kon…gurasi awal dari CA. Barisan C

r,

0 t k

merupakan perubahan kon…gurasi CA dua dimensi dari waktu ke nol sampai waktu ke k. Kondisi batas untuk CA dua dimensi yang berhingga bergantung pada pende…nisian keadaan sel (a; b). Dalam tugas akhir ini, digunakan kondisi batas nol, yaitu: jika (a; b) 2 = f(u; v); 1

u

r; 1

(t)

v

cg maka sab = 0:

(t+1)

dan kondisi batas tersebut,

Berdasarkan fungsi transisi lokal untuk sab

CA dua dimensi yang linear memiliki diskritisasi fungsi transisi lokal yang dide…nisikan sebagai berikut: (t+1)

sab

0

= g@

X

(a;b) (t) sa+ ;b+

( ; )2V

dengan

2.2

(a;b)

2 R+ ; ( ; ) 2 V dan g : R ! Zk .

1

A;

(2.4)

Model Dasar Automata Seluler untuk Penyebaran Api

Pada model dasar CA untuk penyebaran api ini hutan dimisalkan sebagai kumpulan sel (a; b) berbentuk heksagonal yang identik. Panjang sisi heksagonal L. Setiap sel area hutan bersesuaian dengan setiap sel CA.


7

Keadaan sel (a; b) pada waktu t dide…nisikan sebagai (t)

sab =

area yang terbakar dari sel (a; b) ; total area sel (a; b)

di mana total area dari sel heksagonal adalah Dengan demikian, 0

(t)

sab

(2.5)

p 3 3L2 : 2

(t)

1. Jika sab = 0, maka sel (a; b) belum terbakar

(t)

pada waktu t; jika 0 < sab < 1, maka sel (a; b) terbakar sebagian pada waktu (t)

t; dan jika sab = 1, maka sel (a; b) terbakar seluruhnya pada waktu t. Dalam tugas akhir ini, himpunan keadaan S yang dipilih adalah f0; 0:25; 0:5; 0:75; 1g. Automata Seluler yang digunakan dalam kajian ini merupakan CA linear, sehingga keadaan sel (a; b) pada waktu t+1 bergantung linear dengan keadaan tetangga sel (a; b) pada waktu t , sehingga 0 X X (t+1) (t) (a;b) (t) sab = g @sab + sa+ ;b+ + ( ; )2Vn

dimana

(a;b)

(a;b) (t) sa+ ;b+

( ; )2Vd

1

A;

(2.6)

2 R merupakan parameter-parameter ukuran …sis setiap sel. Dan

fungsi diskritisasi g diberikan oleh: [0; 1] ! S b4xc : x 7 ! g(x) = 4 g

:

(2.7)

Pada bagian selanjutnya akan dibahas parameter yang mempengaruhi penyebaran kebakaran hutan, yaitu kecepatan dan arah angin, topogra…, dan tingkat penyebaran api.

2.2.1

Kecepatan dan Arah Angin (! )

Kecepatan dan arah angin sangat mempengaruhi arah penyebaran api dan besarnya ukuran api pada proses penjalaran api di suatu hutan. Pengaruh angin pada sel (a; b) dari tetangganya dide…nisikan: W(a;b) = f!

(a;b)

; ( ; ) 2 V g; dengan !

(a;b)

Jika tidak ada angin yang bertiup di sel (a; b), maka !

(a;b)

1: = 1 untuk setiap

( ; ) 2 V . Jika angin bertiup dari arah Utara ke Selatan, maka koe…sien sel yang berada di bagian utara harus harus lebih besar dari koe…sien yang berada di selatannya.


2.2.2

8

Topogra… (h )

Selain faktor kecepatan dan arah angin, topogra… hutan yang terbakar juga mempengaruhi penyebaran api. H(a;b) dide…nisikan ketinggian sel (a; b) yang diasumsikan sebagai ketinggian di titik tengah sel (a; b). Pengaruh ketinggian (a;b)

dari sel tetangganya dinotasikan h

, bergantung pada perbedaan ketinggian

di antara sel-sel yang terkait: Pengaruh ketinggian sel tetangga dekat, misal sel N dide…nisikan: hO N = (HO

HN );

(2.8)

Pengaruh ketinggian sel tetangga jauh misal sel N N E dide…nisikan: 1 hO N N E = [ (HO HN )+ (HN HN N E )+ (HO HN E )+ (HN E HN N E )]; 4 (2.9) dengan fungsi dari

(x) adalah sebagai berikut:

1. jika x > 0, maka

(x) > 1;

2. jika x = 0, maka

(x) = 1; dan

3. jika x < 0, maka 0 < (x) < 1: Untuk hutan dengan topogra… datar (setiap selnya memiliki ketinggian sel yang sama), maka

(a;b)

(x) = 1. Akibatnya h

= 1 untuk setiap sel (a; b) dan

( ; )2V.

2.2.3

Tingkat Penyebaran Api (r )

Faktor tingkat penyebaran api dianalogikan dengan vegetasi yang dimiliki oleh hutan. Proses penyebaran api pada kebakaran hutan dengan vegetasi tanaman yang kering akan lebih cepat daripada hutan dengan vegetasi yang basah. Misalkan laju penyebaran api di sel O = (a; b) adalah RO dan R = maxfR(a;b) ; 1 a

r; 1

b

cg, sehingga RO

R. Terdapat t0 yaitu waktu yang dibutuhkan

satu sel untuk terbakar sepenuhnya.


9

Kasus Tetangga Dekat Terbakar Penuh Jika seluruh ketetanggaan sel O belum terbakar, tetapi hanya satu tetangga dekat dari sel O yang telah terbakar penuh, misalkan sel N . Asumsi yang p L digunakan adalah api bergerak seperti pada Gambar 2.4 sehingga t0 = 3 R .

Gambar 2.4: Penyebaran api dari tetangga ke sel O

Setelah waktu t0 , jarak yang telah dilalui api adalah r = RO t0 =

p RO 3 L: R

Akibatnya terdapat 2 kasus yaitu ketika r 1. Jika r

L, maka

p

3 RRO L

L, dan

(2.10)

L dan r > L : RO R

p

3 3

0:57735.

Gambar 2.5: Penyebaran dari tetangga dekat (N ) ke sel O untuk kasus r

L:

Dapat dilihat pada Gambar 2.5, area yang terbakar pada sel O setelah


10

waktu t0 adalah area terbakar =

RO RO 2 p L 3+ R 2 R

(2.11)

:

Oleh karena itu, tingkat penyebaran api (r) dari sel N ke sel O adalah area terbakar total p area sel RO 2 3 RO p = 3+ 9 R 2 R

O rN =

2. Jika r > L, maka L <

p

3 RRO L, dan 0:57735

(2.12)

:

p

3 3

<

RO R

1.

Gambar 2.6: Penyebaran dari tetangga dekat (N ) ke sel O untuk kasus r > L:

Dapat dilihat pada Gambar 2.6, area yang terbakar pada sel O setelah waktu t0 adalah area terbakar = dengan

= arcsin

p RO 2 3 L 1 + sin R 6 R 2RO

6

dan

R RO

+3

RO R

;

(2.13)

< 2, yang merepresentasikan

perbedaan vegetasi pada hutan heterogen tidak terlalu signi…kan. Oleh karena itu, tingkat penyebaran api (r) dari sel N ke sel O adalah area terbakar total area sel 2 RO = 1 + sin 3 R 6

O rN =

Kasus Tetangga Jauh Terbakar Penuh

+

p

3

RO R

:

(2.14)


11

Jika seluruh ketetanggaan sel O belum terbakar, tetapi hanya satu tetangga jauh dari sel O yang telah terbakar penuh, misalkan sel N N E, maka setelah waktu t0 , api menjalar melalui garis batas (border line) antara tetangga dekat N dan N E dan memberikan pengaruh pada sel O dengan waktu t0O = L ; maxfRN ;RN E g

dan akibatnya jarak yang telah dilalui api adalah r = RO (t0

t0O ) =

p

3 R

1 maxfRN ; RN E g

!

RO L:

Gambar 2.7: Penyebaran dari tetangga jauh (N N E) ke sel O.

Dapat dilihat pada Gambar 2.7, area yang terbakar pada sel O setelah waktu t0 adalah area terbakar =

3

2 2 RO L

p

3 R

1 maxfRN ; RN E g

!2

:

(2.15)

Oleh karena itu, tingkat penyebaran api (r) dari sel N N E ke sel O adalah area terbakar total area sel p p 2 3 3RO = 27 R

O rN NE =

RO maxfRN ; RN E g

!2

:

(2.16)

Untuk hutan homogen, maka R(a;b) = R untuk setiap sel (a; b). Akibatnya O O rN = 1 dan rN N E = 0:216.


2.3

12

Fungsi Transisi Lokal

Berdasarkan hasil perumusan parameter-parameter yang telah diperoleh sebelumnya, dapat disimpulkan bahwa fungsi transisi lokal dari automata seluler berbentuk heksagonal untuk memprediksi proses penyebaran api pada kebakaran hutan adalah sebagai berikut: 2 X (a;b) (a;b) (a;b) (t) 1 (t+1) sab = 44 ! h r sa+ 4

;b+

( ; )2V

di mana jika ( ; ) 2 Vn ,

(a;b)

h

= (H(a;b)

H(a+

3

5;

(2.17)

(2.18)

;b+ ) );

dan jika ( ; ) 2 Vd , (a;b)

h

1 [ (H(a;b) H(a+ + ;b+ + ) ) + (H(a+ + ;b+ + ) H(a+ ;b+ ) ) + 4 (H(a;b) H(a+ ;b+ ) ) + (H(a+ ;b+ ) H(a+ ;b+ ) )]; (2.19)

=

dan

r

(a;b)

=

dengan

8 > > > > < > > > > :

2

p

3

p

3R(a;b) R

2

, jika ( ; ) 2 Vd ; p R , jika ( ; ) 2 V dan R 3 + 2 (a;b) 3R(a;b) ; n R p R 2 R(a;b) + 3 (a;b) 1 + sin 6 , lainnya 3 R R

27 p 2 3 R(a;b) 9 R

= arcsin

R(a;b) + ;b+ + ) ;R(a+

p

maxfR(a+

;b+

)g

(2.20) R 2R(a;b)

6

dan

R R(a;b)

< 2.

Pengantar Automata Seluler

Recommend Documents