BAB 2 LANDASAN TEORI

BAB 2

LANDASAN TEORI

2.1 Tsunami

Tsunami adalah gelombang laut yang terjadi karena adanya gangguan impulsif pada laut. Gangguan impulsif tersebut terjadi akibat adanya perubahan bentuk dasar laut secara tiba-tiba dalam arah vertikal atau dalam arah horizontal. Perubahan tersebut disebabkan oleh tiga sumber utama, yaitu gempa tektonik, letusan gunung api, atau longsoran yang terjadi di dasar laut. Dari ketiga sumber tersebut, di Indonesia gempa merupakan penyebab utama[11].

Indonesia merupakan daerah rawan gempa bumi karena dilalui oleh jalur pertemuan 3 lempeng tektonik, yaitu: Lempeng Indo-Australia, lempeng Eurasia, dan lempeng Pasifik. Lempeng Indo-Australia bergerak relatip ke arah utara dan menyusup kedalam lempeng Eurasia, sementara lempeng Pasifik bergerak relatip ke arah barat. Jalur pertemuan lempeng-lempeng tersebut berada di laut, sehingga apabila terjadi gempa bumi dengan skala yang besar dan dengan kedalaman yang dangkal, maka akan berpotensi menimbulkan tsunami.

Gelombang tsunami yang terjadi akibat deformasi di dasar laut memiliki karakteristik sebagai berikut[11]: 1. Memiliki panjang gelombang sekitar 100-200 km atau lebih. 2. Memiliki perioda 10-60 menit 3. Kecepatan perambatan gelombang bergantung pada kedalaman dasar laut.

dimana: v = kecepatan gelombang

Universitas Sumatera Utara

g = percepatan gravitasi h = kedalaman laut

Gelombang tsunami memiliki kecepatan antara 500 hingga 1.000 km/jam (sekitar 0,14 - 0,28 kilometer per detik) di perairan terbuka. Meskipun demikian, peristiwa tsunami tetap dapat diketahui lebih awal, yakni dengan mendeteksi getaran gempa penyebab tsunami tersebut. Getaran gempa bumi memiliki kecepatan sekitar 4 kilometer per detik (14.400 km/jam). Hal ini menyebabkan tsunami bisa terdeteksi sebelum mencapai tanah.

Gambar 2.1 Tsunami saat Menerjang Daratan[12]

Gambar 2.1 menunjukkan karakteristik tsunami saat mencapai pantai (dimana laut menjadi dangkal), maka kecepatannya akan menurun namun ketinggian gelombang semakin bertambah. Saat tsunami mencapai pantai, sejumlah besar energi yang awalnya tersimpan dalam bentuk panjang gelombang tsunami berubah menjadi bentuk tinggi gelombang dengan kekuatan menghancurkan yang luar biasa. Di daratan ketinggian tsunami bisa mencapai ratusan meter. Istilah run-up pada tsunami mengacu pada ketinggian tertinggi tsunami yang diukur dari permukaan laut.

Pada umumnya tsunami tidak hanya gelombang tunggal saja, namun merupakan rangkaian gelombang. Gelombang pertama yang mencapai daratan adalah yang tertinggi. Rangkaian gelombang tersebut lebih merusak daripada yang gelombang tunggal. Oleh karena itu, meskipun kita bisa selamat dari gelombang pertama, namun kita masih beresiko terkena gelombang yang berikutnya.


2.2 Graph

Suatu graph sederhana G adalah suatu pasangan terurut (V, E), dimana V adalah suatu himpunan berhingga yang tak kosong yang elemen-elemennya disebut verteks dan E adalah suatu himpunan garis yang menghubungkan dua elemen subset dari E yang disebut edges [2].

v

e1

v4

e4

e5

e2

v2

e3

v3

Gambar 2.2 Graph dengan 4 verteks dan 5 edges Pada contoh diatas graph G = (V, E) dimana: 1. V adalah himpunan titik, simpul, verteks atau nodes dari G, yaitu V = {v1, v2, v3, v4} 2. E adalah himpunan rusuk, edges, atau sisi dari G, yaitu E = {e1, e2, e3, e4, e5}

2.2.1 Macam – macam Graph Menurut Arah dan Bobotnya Menurut arah dan bobotnya, graph dibagi menjadi empat bagian, yaitu : 1. Graph berarah (digraph) dan berbobot: setiap edges mempunyai arah (yang ditunjukkan dengan anak panah) dan bobot. Gambar 8.2 adalah contoh graph berarah dan berbobot, yang terdiri dari tujuh verteks yaitu verteks A, B, C, D, E, F, G dan 12 edges. Verteks A mempunyai dua edges yang masing-masing menuju ke verteks B dan verteks C, verteks B mempunyai tiga edges yang masing-masing menuju ke verteks C, verteks D dan verteks E dan seterusnya. Tiap-tiap edges mempunyai arah dan bobot yang telah diketahui.


2

B

2

E 2

1

1

A D 1

4

G

2

1

2 3

C

F

4

Gambar 2.3 Graph berarah dan berbobot

2. Graph tidak berarah dan berbobot: setiap edges tidak mempunyai arah tetapi mempunyai bobot. Gambar 8.3 adalah contoh graph tidak berarah dan berbobot. Edges yang menghubungkan antar verteks mempunyai bobot yang telah diketahui namun tidak mempunyai arah. 2 2

B

E 1

2

1

A

2

1

G

D 1

4

2 3

C

F

4

Gambar 2.4 Graph tidak berarah dan berbobot

3. Graph berarah (digraph) dan tidak berbobot: setiap edges mempunyai arah tetapi tidak mempunyai bobot. Gambar 8.4 adalah contoh graph berarah dan tidak berbobot. B

E

A G D

C

F

Gambar 2.5 Graph berarah dan tidak berbobot


4. Graph tidak berarah dan tidak berbobot: setiap edges tidak mempunyai arah dan tidak mempunyai bobot. Gambar 8.5 adalah contoh graph tidak berarah dan tidak berbobot. B

E

A G D

C

F

Gambar 2.6 Graph tidak berarah dan tidak berbobot

2.3 Algoritma Ant Colony

Algoritma Ant Colony atau disebut juga Ant Colony Optimization (ACO), merupakan metode pencarian metaheuristik yang diinspirasi oleh perilaku semut dalam menyelesaikan permasalahan optimisasi, termasuk dalam permasalahan pencarian jalur terpendek [3]. Pada tugas akhir ini penulis menggunakan algoritma Ant Colony System (ACS), yang merupakan variasi dari algoritma Ant Colony Optimization.

Dalam mencari makanan, setiap semut akan berusaha mencari jalur terpendek dari sarang ke tempat makanan. Kemudian semut tersebut akan meninggalkan pheromone di jalur yang dilaluinya. Pheromone adalah zat kimia yang berasal dari kelenjar endokrin dan digunakan oleh makhluk hidup untuk mengenali sesama jenis, individu lain, kelompok, dan untuk membantu proses reproduksi. Berbeda dengan hormon, Pheromone menyebar ke luar tubuh dan hanya dapat mempengaruhi dan dikenali oleh individu lain yang sejenis (satu spesies). Proses peninggalan Pheromone ini dikenal sebagai stigmery, yaitu sebuah proses memodifikasi lingkungan yang tidak hanya bertujuan untuk mengingat jalan pulang ke sarang, tetapi juga memungkinkan para semut berkomunikasi dengan koloninya.


Pheromone akan menarik semut lain untuk mengikuti jalurnya dan meninggalkan pheromone miliknya. Semakin banyak semut yang mengikuti jalur tersebut maka intensitas pheromone pada jalur tersebut akan semakin kuat, sehingga menarik semut-semut lain untuk mengikuti jalur tersebut. Jika ada semut lain yang menemukan jalur yang lebih baik maka semut tersebut akan mengeluarkan pheromone yang lebih kuat sehingga menarik semut lain untuk mengikuti jalurnya. Jalur terbaik akan memiliki kadar pheromone yang tinggi, karena banyak semut yang melaluinya, dan jalur yang buruk akan memiliki kadar pheromone yang rendah atau bahkan kosong, karena semakin lama pheromone akan menguap dan akhirnya menghilang.

Pada algoritma ACO, semut-semut buatan akan diciptakan dan yang kemuadian akan bekerja sama untuk menemukan jalur terbaik dengan pertukaran informasi melalui kualitas pheromone pada setiap jalurnya [1].

2.3.1 Ant Colony System (ACS)

ACS merupakan pengembangan dari Ant Colony Optimization. Secara informal, ACS bekerja sebagai berikut: pertama kali, sejumlah m semut ditempatkan pada sejumlah n titik berdasarkan beberapa aturan inisialisasi (misalnya, secara acak). Setiap semut membuat sebuah tour (yaitu, sebuah solusi TSP yang mungkin) dengan menerapkan sebuah aturan transisi status secara berulang kali. Selagi membangun tournya, setiap semut juga memodifikasi jumlah pheromone pada edge-edge yang dikunjunginya dengan menerapkan aturan pembaruan pheromone local yang telah disebutkan tadi. Setelah semua semut mengakhiri tour mereka, jumlah pheromone yang ada pada edgeedge dimodifikasi kembali (dengan menerapkan aturan pembaruan pheromone global). Dalam membuat tour, semut ‘dipandu’ oleh informasi heuristic (mereka lebih memilih edge-edge yang pendek) dan oleh informasi pheromone. Sebuah edge dengan jumlah pheromone yang tinggi merupakan pilihan yang sangat diinginkan. Kedua aturan pembaruan pheromone itu dirancang agar semut cenderung untuk memberi lebih banyak pheromone pada edge-edge yang harus mereka lewati. Tiga karakteristik utama dari ACS, yaitu aturan transisi status, aturan pembaharuan pheromone global, dan aturan pembaharuan pheromone lokal [1].


2.3.1.1 Aturan Transisi Status

Aturan transisi status adalah aturan yang digunakan dalam memilih titik tujuan berikutnya dengan melakukan perhitungan probabilitas masing-masing titik tujuan yang mungkin. Aturan transisi status yang berlaku pada ACS [2] adalah sebagai berikut: seekor semut yang ditempatkan pada kota r memilih untuk menuju ke kota s. Kemudian dibangkitkan bilangan acak q, dimana 0 ≤ q ≤ 1. Dan inisiasi sebuah parameter q0, dimana 0 ≤ q0 ≤ 1. Jika q ≤ q0 maka 𝐬𝐬 = 𝐦𝐦𝐦𝐦𝐦𝐦 �[𝛕𝛕(𝐫𝐫, 𝐮𝐮)] ∙ [𝛈𝛈(𝐫𝐫, 𝐮𝐮)]𝛃𝛃 �

………………………………………. (1)

Dimana: 𝛕𝛕 = intensitas pheromone

𝛈𝛈 = visibilitas antar kota (1/d)

u = kota-kota yang mungkin dikunjungi semut yang berada di kota r. s = kota tujuan 𝛃𝛃 = parameter yang mengontrol bobot (weight) relatif dari pheromone terhadap jarak (β>0).

Sedangkan jika q > q0 maka

𝒑𝒑𝒌𝒌 (𝒓𝒓, 𝒔𝒔) =

[𝛕𝛕(𝐫𝐫,𝐬𝐬)]∙[𝛈𝛈(𝐫𝐫,𝐬𝐬)𝛃𝛃 ]

∑𝐮𝐮 𝛜𝛜 𝑱𝑱 (𝒓𝒓)[𝛕𝛕(𝐫𝐫,𝐮𝐮)]∙[𝛈𝛈(𝐫𝐫,𝐮𝐮)𝛃𝛃 ] 𝒌𝒌

………………………….. (2)

dimana: 𝒑𝒑𝒌𝒌 = probabilitas tiap kota berikutnya yang akan dikunjungi dari kota r Setelah hasil perhitungan probabilitas kota yang akan dipilih berikutnya selesai, kemudian dicari probabilitas kumulatifnya (qk) dimana q1 = 𝒑𝒑𝟏𝟏 sedangkan qk = qk-1

+ 𝒑𝒑𝒌𝒌 untuk k = 2,3,4, ..., n. Kemudian dibangkitkan bilangan random (v) antara 0 sampai 1. Titik ke-k akan terpilih jika qk-1 < v ≤ qk.


2.3.1.2 Aturan Pembaruan Pheromone Lokal

Selagi melakukan perjalanan untuk mencari solusi pencarian rute terpendek, semut mengunjungi sisi-sisi dan mengubah tingkat feromon pada sisi-sisi tersebut dengan menerapkan aturan pembaruan feromon lokal [1] yang ditunjukkan oleh persamaan dibawah ini. 𝝉𝝉(𝒓𝒓, 𝒔𝒔) ← (𝟏𝟏 − 𝝆𝝆) ∙ 𝝉𝝉(𝒓𝒓, 𝒔𝒔) + 𝝆𝝆 ∙ ∆𝝉𝝉(𝒓𝒓, 𝒔𝒔) ………………………………... (3)

dimana: 𝝆𝝆

= tetapan penguapan pheromone

∆𝝉𝝉(𝒓𝒓, 𝒔𝒔) = 𝜸𝜸. 𝐦𝐦𝐦𝐦𝐦𝐦𝐳𝐳 ∈𝐉𝐉𝐤𝐤 (𝐬𝐬) 𝝉𝝉(𝒔𝒔, 𝒛𝒛)

𝜸𝜸

, dimana:

= parameter (0≤ 𝜸𝜸 ≤1)

𝝉𝝉(𝒔𝒔, 𝒛𝒛) = tho yang paling maksimum dari seluruh edges yang menghubungkan titik s ke z.

2.3.1.3 Aturan Pembaruan Pheromone Global

Pada sistem ini, pembaruan pheromone secara global hanya dilakukan oleh semut yang membuat tur terpendek sejak permulaan percobaan. Pada akhir sebuah iterasi, setelah semua ants menyelesaikan tur mereka, sejumlah pheromone ditaruh pada ruasruas yang dilewati oleh seekor semut yang telah menemukan tur terbaik (ruas-ruas yang lain tidak diubah). Tingkat pheromone itu diperbarui dengan menerapkan aturan pembaruan pheromone global [1] yang ditunjukkan oleh persamaan 4. 𝝉𝝉(𝒓𝒓, 𝒔𝒔) ← (𝟏𝟏 − 𝜶𝜶) ∙ 𝝉𝝉(𝒓𝒓, 𝒔𝒔) + 𝜶𝜶 ∙ ∆𝝉𝝉(𝒓𝒓, 𝒔𝒔)

.......................................................... (4)

dimana: ∆𝝉𝝉(𝒓𝒓, 𝒔𝒔) = �

𝑳𝑳𝒈𝒈𝒈𝒈

(𝑳𝑳𝒈𝒈𝒈𝒈 )−𝟏𝟏 , 𝒋𝒋𝒋𝒋𝒋𝒋𝒋𝒋 (𝒓𝒓, 𝒔𝒔) ∈ 𝒓𝒓𝒓𝒓𝒓𝒓𝒓𝒓 𝒕𝒕𝒕𝒕𝒕𝒕𝒕𝒕𝒕𝒕𝒕𝒕𝒕𝒕 𝒌𝒌𝒌𝒌𝒌𝒌𝒌𝒌𝒌𝒌𝒌𝒌𝒌𝒌𝒌𝒌𝒌𝒌𝒌𝒌𝒌𝒌 𝟎𝟎

= panjang rute terbaik pada akhir siklus


𝜶𝜶

= tetapan pengendali pheromone

2.3.1.4 Penjelasan Alur Kerja Algoritma Ant Colony System

Algoritma Ant Colony System memiliki langkah-langkah untuk mencari rute terpendek yaitu: 1.

Menginsialisasi harga parameter-parameter algoritma semut: a.

Intensitas pheromone (τij).

b.

Tetapan siklus semut (q0).

c.

Tetapan pengendali intensitas visibilitas (β).

d.

Tetapan pengendali pheromone (α), nilai α ≥ 0.

e.

Jumlah semut (m).

f.

Tetapan penguapan pheromone (ρ), nilai ρ harus > 0 dan < 1.

g.

Jumlah siklus maksimum (NCmax).

2. Setelah itu menentukan titik selanjutnya yang akan dituju dengan aturan transisi status. Sesuai dengan nilai q0 yang didapat, aturan transisi status akan menggunakan persamaan (1) atau persamaan (2) dengan syarat:

3.

a.

Jika q≤q0 maka aturan transisi status menggunakan persamaan (1).

b.

Jika q>q0 maka aturan transisi status menggunakan persamaan (2).

Apabila telah mendapat titik yang dituju, titik tersebut disimpan ke dalam daftar_kota untuk menyatakan bahwa titik tersebut telah menjadi bagian dari rute perjalanan. Setelah itu intensitas pheromone di sisi tersebut diubah dengan menggunakan persamaan (3). Perubahan pheromone tersebut dinamakan pembaruan pheromone lokal. Aturan transisi kembali dilakukan, mencari titik berikutnya, sampai titik tujuan tercapai.

4. Apabila titik tujuan telah dicapai, panjang rute masing-masing semut akan diakumulasikan, kemudian diurutkan sehingga akan didapatkan rute yang terpendek.


5. Pembaruan pheromone pada titik-titik yang termuat dalam rute terpendek tersebut menggunakan persamaan (4). Perubahan pheromone ini dinamakan pembaruan pheromone global. 6. Pengosongan daftar_kota. Daftar_kota perlu dikosongkan untuk diisi lagi dengan urutan titik yang baru. Algoritma diulang lagi dari langkah 2 dengan harga parameter intensitas feromon yang sudah diperbarui.

Setelah semua proses telah dilalui (jumlah siklus maksimum sudah terpenuhi), maka akan didapatkan rute dengan panjang rute yang terpendek. Langkah-langkah pencarian rute terpendek dengan Algoritma Ant Colony diatas dapat digambarkan dengan flowchart seperti pada Gambar 2.7.


Mulai

Tetapkan Parameter, Kota Awal, Kota Tujuan

For i=1 to JmulahSiklus (Ncmax) do

Kosongkan daftar kota Pembaruan pheromones global

Ya For j=1 to JumlahSemut (m) do

TIdak

Hitung jarak rute masing-masing semut

Ya

Aturan transisi dengan pers. 1 atau 2

Tidak

Ya

Simpan Kota Terpilih

Tidak

Pembaruan pheromone lokal

Titik tujuan dicapai ?

Tampilkan rute terpendek

Berhenti

Gambar 2.7 Flowchart Ant Colony System 2.4 Sistem Informasi Geografis

Sistem Informasi Geografis (SIG) merupakan sistem yang dirancang untuk bekerja dengan data yang tereferensi secara spasial atau koordinat-koordinat geografis. SIG memiliki kemampuan untuk melakukan pengolahan data dan melakukan operasioperasi tertentu dengan menampilkan dan menganalisa data.


Menurut Gou Bo, Sistem Informasi Geografis adalah teknologi informasi yang dapat menganalisis, menyimpan dan menyimpan baik data spasial maupun data non spasial. Sedangkan menurut Nicholas Chrisman, Sistem Informasi Geografis adalah sistem yang terdiri dari perangkat keras, perangkat lunak, data, manusia, organisasi dan lembaga yang digunakan untuk mengumpulkan, menyimpan, menganalisisis, dan menyebarluaskan informasi mengenai daerah-daerah di permukaaan bumi [6].

Sistem informasi geografis adalah sistem komputer yang digunakan untuk memasukkan,

menyimpan,

memeriksa,

mengintegrasikan,

memanipulasi,

menganalisis, dan menampilkan data-data yang berhubungan dengan posisi-posisinya dipermukaan bumi [6]. Secara sederhana SIG adalah sistem yang memiliki referensi bentuk muka bumi (daratan, lautan, jalan, perkotaan dan lain sebagainya), yang memungkinkan kita untuk mengolah data-data bentuk muka bumi tersebut untuk tujuan tertentu.

Salah satu alasan mengapa konsep-konsep Sistem Informasi Geografis (SIG) beserta sistem aplikasinya menjadi menarik untuk digunakan di berbagai disiplin ilmu karena SIG dapat menurunkan informasi secara otomatis tanpa keharusan untuk selalu melakukan interpretasi secara manual sehingga SIG dengan mudah dapat menghasilkan data spasial tematik yang merupakan (hasil) turunan dari data spasial yang lain (primer) dengan hanya memanipulasi atribut-atributnya dengan melibatkan beberapa operator logika dan matematis [6].

2.4.1 Komponen Sistem Informasi Geografis

Sistem Informasi Geografis merupakan hasil dari beberapa komponen. Komponen Sistem Informasi Geografis terbagi menjadi empat, yaitu sebagai berikut [6]:

1.

Perangkat Keras (Hardware)


Sistem Informasi Geografis membutuhkan komputer untuk menyimpan data dan dalam melakukan pengolahan data. Semakin kompleks data yang ingin diolah, maka semakin besar juga kebutuhan memori dan kecepatan pengolah datanya.

2.

Perangkat Lunak (Software) Perangkat

lunak

dibutuhkan

untuk

memasukkan,

menyimpan

dan

mengeluarkan data bila diperlukan. Perangkat lunak Sistem Informasi Geografis harus memiliki beberapa elemen seperti mampu melakukan input dan transformasi data geografis, sistem manajemen basis data, mampu mendukung query geografis, analisis dan visualisasi, dan memiliki Grafical User Interface (GUI) untuk memudahkan akses.

3.

Data Dalam SIG semua data dasar geografis harus diubah terlebih dahulu ke dalam bentuk digital untuk memudahkan dalam pengolahan data. Data dalam SIG dibagi menjadi dua bentuk yakni geografical atau data spasial dan data atribut.

a.

Data spasial adalah data hasil pengukuran, pencatatan dan pencitraan terhadap suatu unsur keruangan yang berada di bawah, pada atau di atas permukaan bumi dengan posisi keberadaannya mengacu pada sistem koordinat nasional.

b.

Data atribut adalah gambaran data yang terdiri dari informasi yang relevan terhadap suatu lokasi seperti kedalaman, ketinggian, lokasi penjualan, dan lain-lain dan bisa dihubungkan dengan lokasi tertentu dengan maksud untuk memberikan identifikasi seperti alamat, kode pos, dan lain-lain.

4.

Manusia (Brainware) Manusia dibutuhkan untuk mengendalikan seluruh Sistem Informasi Geografis. Adanya koordinasi dalam Sistem Informasi Geografis sangat diperlukan agar informasi yang diperoleh menjadi benar, tepat dan akurat.


Selain informasi dapat diperoleh secara cepat, tepat dan akurat, keuntungan SIG dengan menggunakan komputer adalah: 1.

Mudah dalam mengolah.

2.

Pengumpulan data dan penyimpanannya hemat tempat dan ringkas.

3.

Mudah diulang kalau sewaktu-waktu diperlukan.

4.

Mudah diubah kalau sewaktu-waktu ada perubahan.

5.

Mudah dibawa, dikirim dan ditransformasikan (dipindahkan).

6.

Aman, karena dapat dikunci dengan kode atau manual.

7.

Relatif lebih murah dibandingkan dengan survei lapangan.

8.

Data yang sulit ditampilkan secara manual, dapat diperbesar bahkan dapat ditampilkan dengan gambar tiga dimensi.

9.

Berdasarkan data SIG dapat dilakukan pengambilan keputusan dengan tepat dan cepat.


BAB 2 LANDASAN TEORI

Recommend Documents