BAB II TINJAUAN PUSTAKA
2.1
Teori Graf Suatu graf G terdiri atas himpunan yang tidak kosong dari elemen–elemen
yang disebut titik (vertek), dan suatu daftar pasangan vertek yang tidak terurut disebut sisi (edge). Himpunan vertek dari suatu graf G dinotasikan dengan V, dan daftar himpunan edge dari graf tersebut dinotasikan dengan E. Untuk selanjutnya suatu graf G dapat dinotasikan dengan G = (V, E).
Gambar 2.1 Contoh Graf G (Leksono, 2009) Gambar 2.1 menunjukkan graf G dengan V = {A, B, C, D, E, F} dan E = {e1, e2, e3, ... , e10}. Dua edge atau lebih yang menghubungkan pasangan vertek yang sama disebut sisi ganda, dan sebuah edge yang mengubungkan sebuah vertek ke dirinya sendiri disebut loop.
Gambar 2.2 Sisi Ganda dan Loop (Leksono, 2009)
6
7
Misal G suatu graf dengan himpunan vertek V dan himpunan edge E. Suatu subgraf G’ adalah suatu himpunan pasangan berurutan (V’, E’) dimana V’ merupakan himpunan bagian dari V dan E’ adalah himpunan bagian dari E. Dengan kata lain, subgraf dari G adalah suatu graf yang semua verteknya anggota V dan semua edgenya anggota E. Jika G suatu graf terhubung seperti pada gambar 2.2, dengan V = {1, 2, 3, 4} dan E = {(1,3), (1,4), (2,4), (3,3), (3,4), (4,2)}, maka berikutnya adalah contoh dari subgraf G’ yang ditunjukkan pada gambar 2.3.
Gambar 2.3 Contoh Graf G dan Subgraf G’ (Leksono, 2009) Pada gambar 2.3 (a) merupakan subgraf G’ dari graf G, dengan himpunan vertek V’ = {1, 2, 3, 4} yang merupakan himpunan bagian dari V dan himpunan edge E’ = {(1,3), (1,4), (2,4), (3,3), (3,4), (4,2) yang merupakan himpunan bagian dari E. Gambar 2.3 (b) juga merupakan subgraf G’ dari graf G dengan himpunan vertek V’ = {1, 3, 4} dan himpunan edge E’ = {(1,3), (1,4), (3,4)} yang masing – masing merupakan himpunan bagian dari V dan E. Gambar 2.3 (c) juga merupakan subgraf G’ dari graf G dengan himpunan vertek V’ = {3} dan himpunan edge E’ = {(3,3)} yang masing – masing merupakan himpunan bagian dari V dan E.
2.2
Traveling Salesman Problem (TSP) Masalah Travelling Salesman Problem (TSP) adalah salah satu contoh
yang paling banyak dipelajari dalam combinatorial optimization. Masalah ini mudah untuk dinyatakan tetapi sangat sulit untuk diselesaikan. TSP termasuk kelas NP-Hard problem dan tidak dapat diselesaikan secara optimal dalam
8
Polynomial computation time dengan algoritma eksak. Bila diselesaikan secara eksak waktu komputasi yang diperlukan akan meningkat secara eksponensial seiring bertambah besarnya masalah. TSP dapat dinyatakan sebagai permasalahan dalam mencari jarak minimal sebuah tour tertutup terhadap sejumlah n kota dimana kota-kota yang ada hanya dikunjungi sekali. TSP direpresentasikan dengan menggunakan sebuah graf lengkap dan berbobot G = (V, E) dengan V himpunan vertek yang merepresentasikan himpunan titik - titik, dan E adalah himpunan dari edge. Setiap edge (r,s) ϵ E adalah nilai (jarak) drs yang merupakan jarak dari kota r ke kota s, dengan (r,s) ϵ V. Dalam TSP simetrik (jarak dari kota r ke titik s sama dengan jarak dari titik s ke titik r), drs = dsr untuk semua edge (r,s) ϵ E. Misalkan terdapat n buah titik maka graf tersebut memiliki kombinasi dan juga memiliki
buah edge, sesuai dengan rumus
buah tour yang mungkin.
Dalam sebuah graf, TSP digambarkan seperti gambar 2.4
Gambar 2.4 Ilustrasi Masalah TSP (Leksono, 2009) 2.3
Algoritma Ant Colony
2.3.1
Pengertian Algoritma Ant Colony Koloni semut merupakan algorima yang bersifat heuristik untuk
menyelesaikan masalah optimasi. Algoritma ini terinspirasi dari tingkah laku dari semut dalam menemukan jalan dari koloninya ke titik makanan. Dalam dunia
9
nyata, semut berkeliaran secara acak dan dalam proses pencarian makanan, mereka akan kembali ke dalam koloni mereka dengan meninggalkan jejak berupa cairan yang disekresikan lewat tubuhnya agar dapat dideteksi oleh semut yang lainnya. Jika semut lainnya menemukan jejak seperti ini, mereka tidak akan tetap berjalan secara acak lagi namun akan mengikuti jejak tersebut untuk kembali dan memberi tahu koloni bahwa mereka menemukan makanan. 2.3.2
Cara Kerja Algoritma Ant Colony Secara sederhana algoritma ini dapat dijelaskan melalui gambar 2.5
Gambar 2.5 Perjalanan Semut Mencari Makanan (Yuwono, 2009) Gambar 2.5 menujukkan perjalanan semut dalam menemukan jalur terpendek dari sarang ke sumber makanan, terdapat dua kelompok semut yang melakukan perjalanan. Kelompok semut L berangkat dari arah kiri ke kanan dan kelompok semut R berangkat dari kanan ke kiri. Kedua kelompok berangkat dari titik yang sama dan dalam posisi pengambilan keputusan jalan sebelah mana yang akan diambil. Kelompok L membagi dua kelompok lagi. Sebagian melewati jalan atas dan sebagian melewati jalan bawah. Hal ini juga berlaku pada kelompok R. Gambar 2.5.b dan Gambar 2.5.c menunjukkan bahwa kelompok semut berjalan pada kecepatan yang sama dengan meninggalkan pheromone atau jejak kaki di jalan yang telah dilalui. Pheromone yang ditinggalkan oleh kumpulan semut yang melewati jalan atas telah mengalami banyak penguapan karena semut yang melewati jalan atas berjumlah lebih sedikit dibandingkan jalan yang di bawah. Hal ini disebabkan jarak yang ditempuh lebih panjang dibandingkan jalan bawah. Sedangkan pheromone yang berada pada bagian bawah penguapannya cenderung
10
lebih lama. Karena semut yang melewati jalan bawah lebih banyak daripada semut yang melewati jalan atas. Gambar 2.5.d menunjukkan bahwa semut-semut yang lain pada akhirnya memutuskan untuk melewati jalan bawah karena pheromone yang ditinggalkan masih banyak, sedangkan pheromone pada jalan atas sudah banyak menguap sehingga semut-semut tidak memilih jalan atas. Semakin banyak semut yang melewati jalan maka semakin banyak semut yang mengikutinya, semakin sedikit semut yang melewati jalan, maka pheromone yang ditinggalkan semakin berkurang bahkan hilang. Dari sinilah kemudian terpilihlah jalur terpendek antara sarang dan sumber makanan. 2.3.3
Langkah-Langkah untuk Menentukan Jalur Terpendek Langkah 1 : a. Inisialisasi harga parameter-parameter algoritma. Parameter-parameter yang di inisialisasikan adalah : 1. Intensitas jejak semut antar kota dan perubahannya (τij) 2. Banyak kota (n) termasuk x dan y (koordinat) atau dij (jarak antar kota) 3. Penentuan kota berangkat dan kota tujuan 4. Tetapan siklus-semut (Q) 5. Tetapan pengendali intensitas jejak semut (α) 6. Tetapan pengendali visibilitas (β) 7. Visibilitas antar kota =
(ηij)
8. Jumlah semut (m) 9. Tetapan penguapan jejak semut (ρ) 10. Jumlah siklus maksimum (NCmax) bersifat tetap selama algoritma dijalankan, sedangkan τij akan selalu diperbaharui harganya pada setiap siklus algoritma mulai dari siklus pertama (NC=1) sampai tercapai jumlah siklus maksimum (NC=NCmax) atau sampai terjadi konvergensi. b. Inisialisasi kota pertama setiap semut.
11
Setelah
inisialisasi
τij
dilakukan,
kemudian
m
semut
ditempatkan pada kota pertama yang telah ditentukan. Langkah 2 : Pengisian kota pertama ke dalam tabu list. Hasil inisialisasi kota pertama semut pada langkah 1 harus diisikan sebagai elemen pertama tabu list. Hasil dari langkah ini adalah terisinya elemen pertama tabu list setiap semut dengan indeks kota pertama. Langkah 3 : Penyusunan jalur kunjungan setiap semut ke setiap kota. Koloni semut yang sudah terdistribusi ke kota pertama akan mulai melakukan perjalanan dari kota pertama sebagai kota asal dan salah satu kota-kota lainnya sebagai kota tujuan. Kemudian dari kota kedua, masing-masing koloni semut akan melanjutkan perjalanan dengan memilih salah satu dari kota-kota yang tidak terdapat pada tabuk sebagai kota tujuan selanjutnya. Perjalanan koloni semut berlangsung terus menerus hingga mencapai kota yang telah ditentukan. Jika s menyatakan indeks urutan kunjungan, kota asal dinyatakan sebagai tabuk(s) dan kota-kota lainnya dinyatakan sebagai {N-tabuk}, maka untuk menentukan kota tujuan digunakan persamaan probabilitas kota untuk dikunjungi sebagai berikut,
dengan i sebagai indeks kota asal dan j sebagai indeks kota tujuan. Langkah 4 : a.
Perhitungan panjang jalur setiap semut. Perhitungan panjang jalur tertutup (length closed tour) atau Lk
setiap semut dilakukan setelah satu siklus diselesaikan oleh semua semut. Perhitungan
dilakukan
persamaan berikut:
berdasarkan
tabuk
masing-masing
dengan
12
dengan dij adalah jarak antara kota i ke kota j yang dihitung berdasarkan persamaan:
b.
Pencarian rute terpendek. Setelah Lk setiap semut dihitung, akan diperoleh harga minimal
panjang jalur tertutup setiap siklus atau LminNC dan harga minimal panjang jalur tertutup secara keseluruhan adalah atau Lmin. c.
Perhitungan perubahan harga intensitas jejak kaki semut antar kota. Koloni semut akan meninggalkan jejak-jejak kaki pada lintasan
antar kota yang dilaluinya. Adanya penguapan dan perbedaan jumlah semut yang lewat, menyebabkan kemungkinan terjadinya perubahan harga intensitas jejak kaki semut antar kota. Persamaan perubahannya adalah:
dengan
adalah perubahan harga intensitas jejak kaki semut antar kota
setiap semut yang dihitung berdasarkan persamaan
untuk (i,j) ϵ kota asal dan kota tujuan dalam tabuk
Langkah 5 : a. Perhitungan harga intensitas jejak kaki semut antar kota untuk siklus selanjutnya. Harga intensitas jejak kaki semut antar kota pada semua lintasan antar kota ada kemungkinan berubah karena adanya penguapan dan
13
perbedaan jumlah semut yang melewati. Untuk siklus selanjutnya, semut yang akan melewati lintasan tersebut harga intensitasnya telah berubah. Harga intensitas jejak kaki semut antar kota untuk siklus selanjutnya dihitung dengan persamaan :
b. Atur ulang harga perubahan intensitas jejak kaki semut antar kota. Untuk siklus selanjutnya perubahan harga intensitas jejak semut antar kota perlu diatur kembali agar memiliki nilai sama dengan nol. Langkah 6 : Pengosongan tabu list, dan ulangi langkah dua jika diperlukan. Tabu list perlu dikosongkan untuk diisi lagi dengan urutan kota yang baru pada siklus selanjutnya, jika jumlah siklus maksimum belum tercapai atau belum terjadi konvergensi. Algoritma diulang lagi dari langkah dua dengan harga parameter intensitas jejak kaki semut antar kota yang sudah diperbaharui. Untuk parameter aturannya digunakan sebagai berikut: 1. Intensitas awal jejak semut antar kota dan perubahannya (τij) = 0,01 2. Tetapan siklus-semut (Q) = 1 3. Tetapan pengendali intensitas jejak semut (α) = 1 4. Tetapan pengendali visibilitas (β) = 1 5. Jumlah semut (m) = 100. 6. Tetapan penguapan jejak semut (ρ) = 0,99 7. Jumlah siklus maksimum (NCmax) = 30 kali Jumlah siklus menentukan keoptimalan hasil, semakin banyak siklus maka hasil rute yang dihasilkan semakin mendekati optimal. 2.3.4
Multi Objective Ant Colony Beberapa penelitian mengenai algoritma Ant Colony menunjukkan
beberapa permasalahan multi-tujuan (multi-objective). Penelitian-penelitian tersebut
menggunakan
beberapa
ukuran
visibilitas
menggabungkannya untuk menentukan visibilitas global.
antar
titik
dan
14
Selain memperhitungkan kuantitas pheromone, semut juga dipandu oleh ukuran pendekatan yang disebut visibilitas. Nilai visibilitas dapat disimpan dalam matriks yang menghubungkan titik i ke masing-masing titik j. Contohnya, dalam ukuran visibilitas
didefinisikan untuk masing-masing obyektivitas c (c = 1, …,
u) dan dikombinasikan. Kemudian, masing-masing semut (k) yang meninggalkan titik i memilih titik selanjutnya (j) untuk dikunjungi mengikuti persamaan 2.9, di mana q adalah variabel random dan q0 adalah parameter, dengan q≥0, q0≤1. α dan adalah parameter kontrol dan tabuk adalah penyimpanan titik yang sudah dipilih oleh semut.
Informasi heuristik atau nilai visibilitas antar kota
digunakan oleh
keobyektivan i untuk memilih kandidat obyek j didefinisikan dengan persamaan 2.8.
di mana
merupakan nilai keuntungan obyek j terhadap keobyektivan i dan
merupakan bobot jika memilih obyek j (Alaya, 2010). Pengembangan algoritma ini akan menghasilkan himpunan solusi optimal Pareto dimana antar anggota himpunan tidak saling mendominasi, himpunan ini diharapkan dapat memberikan alternatif solusi bagi pengguna (decision maker) dalam pemilihan jalur.
2.4
Sistem Informasi Geografis (SIG) Sistem Informasi Georafis atau Georaphic Information Sistem (GIS)
merupakan suatu sistem informasi yang berbasis komputer, dirancang untuk bekerja dengan menggunakan data yang memiliki informasi spasial (bereferensi keruangan).
Sistem
ini
mengcapture,
mengecek,
mengintegrasikan,
memanipulasi, menganalisa, dan menampilkan data yang secara spasial
15
mereferensikan kepada kondisi bumi. Teknologi SIG mengintegrasikan operasioperasi umum database, seperti query dan analisa statistik, dengan kemampuan visualisasi dan analisa yang unik yang dimiliki oleh pemetaan. Kemampuan inilah yang membedakan SIG dengan Sistem Informasi lainya yang membuatnya menjadi berguna berbagai kalangan untuk menjelaskan kejadian, merencanakan strategi, dan memprediksi apa yang terjadi. Sistem ini pertama kali diperkenalkan di Indonesia pada tahun 1972 dengan nama Data Banks for Develompment. Munculnya istilah Sistem Informasi Geografis seperti sekarang ini setelah dicetuskan oleh General Assembly dari International Geographical Union di Ottawa Kanada pada tahun 1967. Dikembangkan oleh Roger Tomlinson, yang kemudian disebut CGIS (Canadian GIS-SIG Kanada), digunakan untuk menyimpan, menganalisa dan mengolah data yang dikumpulkan untuk inventarisasi Tanah Kanada (CLI-Canadian Land Inventory) sebuahinisiatif untuk mengetahui kemampuan lahan di wilayah pedesaan Kanada dengan memetakan berbagai informasi pada tanah, pertanian, pariwisata, alam bebas, unggas dan penggunaan tanah pada skala 1:250000. Sejak saat itu Sistem Informasi Geografis berkembang di beberapa benua terutama Benua Amerika, Benua Eropa, Benua Australia, dan Benua Asia. 2.4.1
Layer dalam Sistem Informasi Geografis Layer adalah lapisan atau lembaran. Layer dalam SIG adalah lapisan peta
yang berisi informasi dari peta. Layer bisa berupa gambar polygon, garis, text, symbol atau lainnya. Pemisahan gambar dalam beberapa layer ditujukan untuk memudahkan dalam menggambar peta, selain itu informasi yang ditampilkan akan lebih detail. Ada beberapa tujuan peta dipisahkan beberapa layer, yaitu : 1. Memudahkan dalam menggambar peta. 2. Informasi yang ditampilkan lebih detail. 3. Informasi/data yang ditampilkan dapat diatur sesuai kebutuhan. 4. Memudahkan dalam melakukan analisis
16
Gambar 2.6 Konsep Layer (Puntodewo, 2003)
2.5
Google Maps Google Maps memberikan sebuah jasa peta globe virtual gratis dan online
dengan menyediakan peta dan gambar satelit yang dapat diintegrasikan di dalam sistem yang sebelumnya telah terdaftar. Google Maps mengijinkan pengguna untuk mengubah atau menambah fitur yang disediakan sehingga dapat mempermudah pengguna untuk memvisualisasikan data spasial yang ada. Google Maps merupakan salah satu penyedia layanan pemetaan dan kartografi berbasis web dengan waktu loading yang relatif lebih cepat. Google Maps juga menampilkan peta secara tiled map dan menyediakan layanan script API (Aplication Program Interface) yang kaya dan bisa dikembangkan dengan mudah.
2.5.1
Google Maps API Google Maps API merupakan layanan untuk mengintegrasikan Google
Maps pada halaman situs yang dikembangkan secara mandiri. API ini menyediakan fungsi-fungsi untuk memanipulasi peta dan menambahkan konten pada peta. Layanan ini dikembangkan dalam beberapa versi seperti Javascript dan Flash. Informasi yang dapat digunakan dengan penambahan Google Maps API antara lain nama kota, nama tempat, nama jalan, panjang jalan, pencarian rute dari suatu tempat ke tempat lain, pencarian lokasi berdasarkan koordinat, dan lain sebagainya. Informasi-informasi ini dapat dimanfaatkan bagi para pengembang dalam membangun sistem yang akan dibuatnya. Berikut merupakan contoh Google Maps API <script type="text/javascript" src="http://maps.google.com/maps/api/js?sensor=true&key=ABQIAA
17
AA8tt4eKTuBZMVnLJfP2BZrBT2yXp_ZAY8_ufC3CFXhHIE1NvwkxS4Rz1LFzG0odNP tk8VLkdrQF5grA">
Kode yang dicetak tebal adalah Google Maps API key. Pengguna harus mendaftar untuk mendapatkan key untuk websitenya. Setelah mendaftar, termasuk memberikan alamat website, Google akan member Anda sebuah API key.
2.6
Android
2.6.1
Perkembangan Android Google Inc, Intel, T-Mobile, Sprint, HTC, Qualcomm, Motorola dan lain-
lain telah berkolaborasi dalam pengembangan Android melalui Open Handset Alliance, sebuah aliansi multinasional yang memimpin industri mobile dan teknologi. Aliansi ini bertujuan mendorong inovasi pada perangkat mobile dan memberikan konsumen pengalaman yang jauh lebih baik daripada apa yang tersedia pada platform mobile saat ini. Melalui Android, pengembang, operator nirkabel, dan produsen handset akan dibawa ke dalam pasar produk baru yang inovatif lebih cepat dan dengan biaya yang jauh lebih rendah. Hasil akhirnya adalah platform mobile yang belum pernah ada sebelumnya yang akan memungkinkan operator nirkabel dan produsen memberikan pelayanan yang lebih baik kepada pelanggan. Platform Android adalah langkah pertama dalam mengatasi permasalahan ini, sebuah ponsel terintegrasi yang terdiri dari sebuah sistem operasi, middleware, user-friendly interface dan aplikasi. Android berjanji memberikan manfaat yang belum pernah terjadi sebelumnya bagi konsumen, pengembang dan produsen layanan mobile. Produsen handset dan operator nirkabel akan bebas menyesuaikan Android untuk produk baru yang lebih inovatif dan dengan biaya yang jauh lebih murah. Pengembang akan memiliki akses lengkap pada handset yang memungkinkan mereka untuk membangun layanan yang lebih menarik dan user-friendly. 2.6.2
Kelebihan Android
18
Sudah banyak platform untuk perangkat selular saat ini, termasuk didalamnya Symbian, iPhone, Windows Mobile, BlackBerry, Java Mobile Edition, Linux Mobile (LiMo), dan banyak lagi. Namun ada beberapa hal yang menjadi kelebihan Android. Walaupun beberapa fitur-fitur yang ada telah muncul sebelumnya pada platform lain, Android adalah yang pertama menggabungkan hal seperti berikut: 1. Keterbukaan, Bebas pengembangan tanpa dikenakan biaya terhadap system karena berbasiskan Linux dan open source. Pembuat perangkat menyukai hal ini karena dapat membangun platform yang sesuai yang diinginkan tanpa harus membayar royality. Sementara pengembang software menyukai karena Android dapat digunakan diperangkat manapun dan tanpa terikat oleh vendor manapun. 2. Arsitektur komponen dasar Android terinspirasi dari teknologi internet Mashup. Bagian dalam sebuah aplikasi dapat digunakan oleh aplikasi lainnya, bahkan dapat diganti dengan komponen lain yang sesuai dengan aplikasi yang dikembangkan. 3. Banyak dukungan service, kemudahan dalam menggunakan berbagai macam layanan pada aplikasi seperti penggunaan layanan pencarian lokasi, database SQL, browser dan penggunaan peta. Semua itu sudah tertanam pada Android sehingga memudahkan dalam pengembangan aplikasi. 4. Siklus hidup aplikasi diatur secara otomatis, setiap program terjaga antara satu sama lain oleh berbagai lapisan keamanan, sehingga kerja system. menjadi lebih stabil. Pengguna tak perlu kawatir dalam menggunakan aplikasi pada perangkat yang memorinya terbatas. 5. Dukungan grafis dan suarat terbaik, dengan adanya dukungan 2D grafis dan animasi yang diilhami oleh Flash menyatu dalam 3D menggunakan OpenGL memungkinkan membuat aplikasi maupun game yang berbeda. 6. Portabilitas aplikasi, aplikasi dapat digunakan pada perangkat yang ada saat ini maupun yang akan datang. Semua program ditulis dengan menggunakan bahas pemrograman Java dan dieksekusi oleh mesin virtual
19
Dalvik, sehingga kode program portabel antara ARM, X86, dan arsitektur lainnya. Sama halnya dengan dukungan masukan seperti penggunaan Keyboard, layar sentuh, trackball dan resolusi layar semua dapat disesuaikan dengan program.
