IMPLEMENTASI ALGORITMA SEMUT UNTUK PENCARIAN RUTE TERPENDEK BERBASIS SISTEM INFORMASI GEOGRAFIS

Edi Iskandar

Teknik Informatika STMIK Akakom

e-mail: edi_iskandar@akakom.ac.id

Abstrak Dalam kehidupan global ini, masyarakat sering melakukan perjalanan dari satu tempat

ke tempat yang lain. Tentu saja perjalanan yang dilakukan tidak tanpa pertimbangan terlebih dahulu. Pertimbangan yang dilakukan tentu berdasarkan beberapa faktor seperti : biaya, waktu, dan efisiensi. Sehingga dalan perjalanan perlu menentukan jalur terpendek dari tempat asal menuju ke tempat tujuan.

Algoritma semut merupakan teknik probabilistik untuk menyelesaikan masalah komputasi dengan menemukan jalur terbaik melalui grafik, Sistem Informasi Geografis (SIG) sebagai salah satu alat yang bermanfaat untuk menangani data spasial dan menyimpan format digital, dapat sebagai alat untuk melakukan analisis yaitu melakukan hubungan spasial antara informasi geografis mengenai bentukan tertentu pada peta yang disimpan sebagai atribut, sehingga dengan SIG memberikan kemudahan dalam menentukan jalan yang akan dilewati.

Tujuan dari penelitian ini adalah menganalisis jalur atau jalan yang bisa dilewati untuk menentukan jalur terpendek dengan menggunakan algoritma semut dalam bentuk peta dengan memanfaatkan Sistem Informasi Geografis.

Penelitian mampu menyajikan peta Yogyakarta yang menampilkan lokasi sekolah SMA, SMK dan MA, dan menyajikan informasi dari lokasi yang di klik yang berupa informasi sekolah, seperti nama sekolah, alamat, jurusan dan informasi lainnya serta mampu menncarikan rute terpendek dari jalur yang akan dilalui dengan menentukan tempat asal dan tempat tujuan, sehingga dapat membantu mengambil keputusan untuk penentuan rute perjalanan. Kata Kunci : Algoritma semut, Sistem Informasi Geografis, Rute terpendek PENDAHULUAN

Dalam kehidupan global ini, masyarakat sering melakukan perjalanan dari satu tempat ke tempat yang lain. Tentu saja perjalanan yang dilakukan tidak tanpa pertimbangan terlebih dahulu. Pertimbangan yang dilakukan tentu berdasarkan beberapa faktor seperti : biaya, waktu, dan efisiensi. Sehingga dalan perjalanan perlu menentukan jalur terpendek dari tempat asal menuju ke tempat tujuan.

Secara umum, pencarian jalur terpendek dapat terbagi menjadi dua metode, metode konvensional dan metode heuristik. Metode konvensional cenderung lebih mudah dipahami daripada metode heuristik, yaitu hanya membandingkan jarak masing-masing node dan kemudian mencari jarak yang terpendek. Tetapi, bila dibandingkan hasilnya, hasil yang diperoleh dari metode heuristik lebih variatif, hasil yang didapatkan lebih akurat, tingkat kesalahan yang dihasilkan pada perhitungan lebih kecil, dan waktu perhitungan yang diperlukan lebih singkat. Metode heuristik terdiri dari beberapa macam algoritma, salah satunya adalah algoritma semut (Ant Colony, Antco). Antco diambil dari perilaku koloni semut dalam pencarian jalur terpendek antara sarang dan sumber makanan.

Algoritma semut diperkenalan oleh Moyson dan Manderick dan secara meluas dikembangkan oleh Marco Dorigo. Algoritma semut merupakan teknik probabilistik untuk menyelesaikan masalah komputasi dengan menemukan jalur terbaik melalui grafik. Pada dunia nyata, semut berkeliling secara acak, dan ketika menemukan makanan mereka kembali ke koloninya sambil memberikan tanda dengan jejak feromon. Jika semut-semut lain menemukan jalur tersebut, semut-semut tersebut tidak akan bepergian dengan acak lagi, melainkan akan mengikuti jejak tersebut, kembali dan menguatkannya jika pada akhirnya menemukan makanan.

Seiring waktu, bagaimanapun juga jejak feromon akan menguap dan akan mengurangi kekuatan daya tariknya. Lebih lama seekor semut pulang pergi melalui jalur tersebut, lebih lama jugalah feromon menguap. Sebagai perbandingan, sebuah jalur yang pendek akan berbaris lebih cepat, dan dengan demikian kerapatan feromon akan tetap tinggi karena terletak pada jalur secepat penguapannya. Penguapan feromon juga mempunyai keuntungan untuk mencegah konvergensi pada penyelesaian optimal secara lokal. Jika tidak ada penguapan sama sekali, jalur yang dipilih semut pertama akan cenderung menarik secara berlebihan terhadap semut-semut yang mengikutinya.

Pada kasus yang demikian, eksplorasi ruang penyelesaian akan terbatasi. Oleh karena itu, ketika seekor semut menemukan jalur yang bagus (jalur yang pendek) dari koloni ke sumber makanan, semut lainnya akan mengikuti jalur tersebut, dan akhirnya semua semut akan mengikuti sebuah jalur tunggal.

Sistem Informasi Geografis (SIG) sebagai salah satu alat yang bermanfaat untuk menangani data spasial dan menyimpan format digital. Sistem Informasi Geografis (SIG) juga dapat digunakan sebagai alat bantu utama yang interaktif, menarik, dan menantang di dalam usaha-usaha untuk meningkatkan pemahaman, pengertian, pembelajaran mengenai konsep lokasi, ruang (spasial), kependudukan dan unsur-unsur geografis yang terdapat di permukaan bumi berikut data-data atribut terkait yang menyertainya. Dengan adanya SIG yang berbasis komputer akan memudahkan dalam pembuatan peta dalam berbagai skala, proyeksi maupun warna. Lebih utamanya adalah SIG dapat sebagai alat untuk melakukan analisis yaitu melakukan hubungan spasial antara informasi geografis mengenai bentukan tertentu pada peta yang disimpan sebagai atribut, sehingga dengan SIG memberikan kemudahan dalam menentuka jalan yang akan dilewati.

Sistem Informasi Geografis digunakan dalam penelitian ini karena mampu menyediakan informasi data geospasial setiap objek dipermukaan bumi secara cepat, sekaligus menyediakan sistem analisa keruangan yang akurat. Sehingga dapat dilakukan upaya pencarian rute terpendek dengan menggunakan algoritma semut. Tujuan dari penelitian ini adalah menganalisis jalur atau jalan yang bisa dilewati untuk menentukan jalur terpendek dengan menggunakan algoritma semut dalam bentuk peta dengan memanfaatkan Sistem Informasi Geografis LANDASAN TEORI Algortima Semut

Koloni semut merupakan algoritma yang bersifat heuristik untuk menyelesaikan masalah optimasi. Algoritma ini diinspirasikan oleh lingkungan koloni semut pada saat mencari makanan. Semut dapat mencari lintasan terpendek dari suatu sumber makanan menuju sarangnya tanpa harus melihatnya secara langsung. Semut - semut mempunyai penyelesaian yang sangat unik dan sangat maju, yaitu dengan menggunakan jejak pheromon pada suatu jalur untuk berkomunikasi dan membangun solusi, semakin banyak jejak pheromon ditinggalkan maka jalur tersebut akan diikuti oleh semut lain

Gambar 1. Semut dalam Proses menemukan sumber makanan

Dalam algoritma semut, diperlukan beberapa variabel dan langkah-langkah untuk menentukan jarak terpendek. Langkah 1: a. Parameter-parameter yang diperlukan pada algoritma semut adalah sebagai berikut: 1. Intensitas jejak semut antar tempat (τij) dan perubahannya τij harus diinisialisasikan sebelum

memulai siklus. Τij digunakan dalam persamaan probabilitas tempat yang akan dikunjungi. ∆τij diinisialisasikan setelah selesai satu siklus. ∆τij digunakan untuk menentukan τij untuk siklus selanjutnya.

2. Tetapan siklus semut (Q) Q merupakan konstanta yang digunakan dalam persamaan untuk menentukan ∆τij. Nilai Q ditentukan oleh pengguna.

3. Tetapan pengendali intensitas jejak semut (α) α digunakan dalam persamaan probabilitas tempat yang akan dikunjungi dan berfungsi sebagai pengendali intensitas jejak semut. Nilai α ditentukan oleh pengguna.

4. Tetapan pengendali visibilitas (β) β digunakan dalam persamaan probabilitas kota yang akan dikunjungi dan berfungsi sebagai pengendali visibilit as. Nilai β ditentukan oleh pengguna.

5. Visibilitas antar tempat (ηij) ηij digunakan dalam persamaan probabilitas tempat yang akan dikunjungi. Nilai ηij merupakan hasil dari 1/η ij (jarak tempat).

6. Banyak semut (m). m merupakan banyak semut yang akan melakukan siklus dalam algoritma semut. Nilai m ditentukan oleh pengguna.

7. Tetapan penguapan jejak semut (ρ) ρ digunakan untuk menentukan τij untuk siklus selanjutnya. Nilai ρditentukan oleh pengguna.

8. Jumlah siklus maksimum (NCmax) Ncmax adalah jumlah maksimum siklus yang akan berlangsung. Siklus akan berhenti sesuai dengan NC max yang telah ditentukan atau telah konvergen. Nilai Ncmax ditentukan oleh pengguna.

9. Pengisian koordinat tempat Pada pengisian koordinat tempat dapat diinputkan sesuai dengan yang kita inginkan. Dengan bertambahnya koordinat maka jalur yang ditempuh akan lebih panjang.

b. Inisialisasi tempat pertama setiap semut Setelah inisialisasi τij dilakukan, kemudian m semut ditempatkan pada tempat pertama tertentu secara acak. Untuk nilai parameter α sebaiknya diberi nilai 0 ≤ α ≤ 1, hal ini dimaksudkan untuk menghindari akumulasi pheromone yang tidak terbatas pada sisi tersebut. Karena jumlah pheromone yang ditinggalkan tidak mungkin

bertambah kuat tetapi akan bertambah kurang. Untuk nilai parameter β sebaiknya tidak diberi nilai 0 karena jika diberi nilai 0 maka hasil yang dicapai tidak maksimum. Tidak optimum disini berarti suatu kondisi dimana panjang perjalanan yang dicapai tidak minimum. Langkah 2:

Pengisian tempat pertama ke dalam tabu list. Hasil inisialisasi tempat pertama setiap semut dalam langkah 1 harus diisikan sebagai elemen pertama tabu list. Hasil dari langkah ini adalah terisinya tabu list setiap semut dengan indeks tempattertentu, yang berarti bahwa setiap tab uk (1) bisa berisi indeks tempat antara 1 sampai n sebagaimana hasil inisialisasi pada langkah 1. Langkah 3:

Penyusunan rute kunjungan setiap semut ke setiap tempat. Koloni semut yang sudah terdistribusi ke sejumlah atau setiap tempat, akan mulai melakukan perjalanan dari tempat pertama masing -masing sebagai tempat asal dan salah satu tempat – tempat lainnya sebagai tempat tujuan. Kemudian dari tempat kedua masing - masing, koloni semut akan melanjutkan perjalanan dengan memilih salah satu dari tempat - tempat yang tidak terdapat pada tabu k sebagai tempat tujuan selanjutnya. Perjalanan koloni semut berlangsung terus menerus sampai semua tempat satu persatu dikunjungi atau telah menempati tabu k. Jika s menyatakan indeks urutan kunjungan, tempat asal dinyatakan sebagai tabu k (s) dan tempat – tempat lainnya dinyatakan sebagai {N-tabuk}, maka untuk menentukan tempat tujuan digunakan persamaan probabilitas tempat untuk dikunjungi sebagai berikut:

dengan i sebagai indeks tempat asal dan j sebagai indeks tempat tujuan. Langkah 4: a. Perhitungan panjang rute setiap semut

Perhitungan panjang rute tertutup ( length closed tour) atau Lk setiap semut dilakukan setelah satu siklus diselesaikan oleh semua semut. Perhitungan dilakukan berdasarkan tabu k masing-masing dengan persamaan berikut:

Dengan dij adalah jarak antara tempat i ke tempat j yang dihitung berdasarkan persamaan:

b. Pencarian jarak terpendek

Setelah Lk setiap semut dihitung, akan diperoleh harga minimal panjang rute 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 tempat Δτij Koloni semut akan meninggalkan jejak -jejak kaki pada lintasan antar tempat yang

dilaluinya. Adanya penguapan dan per bedaan jumlah semut yang lewat, menyebabkan kemungkinan terjadinya perubahan harga intensitas jejak kaki semut antar tempat. Persamaan perubahannya adalah:

keterangan:

m = banyak semut ττij = panjang jalur setiap semut

dengan ∆ Δτij adalah perubahan harga intensitas jejak kaki semut antar tempat setiap semut yang dihitung berdasarkan persamaan.

adalah perubahan harga intensitas jejak kaki semut antar tempat setiap semut yang dihitung berdasarkan persamaan.

keterangan:

Q = tetapan siklus semut Lk =length close tour(lct)

untuk (i.j) ∈ tempat asal dan tempat tujuan dalam tabu k

Langkah 5: 1. Perhitungan harga intensitas jejak kaki semut antar tempat untuk siklus selanjutnya.

Harga intensitas jejak kaki semut antar tempat pada semua lintasan antar tempat ada kemungkinan berubah karena adanya penguapan dan perbedaan jumlah semut yang melewati. Untuk siklus selanjutnya, semut yang akan melewati lintasan tersebut harga intensitasnya telah berubah. Harga intensitas jejak kaki semut antar tempat untuk siklus selanjutnya dihitung dengan persamaan :

2. Atur ulang harga perubahan intensitas jejak kaki semut antar tempat.

Untuk siklus selanjutnya perubahan harga intensitas jejak semut antar tempat perlu diatur kembali agar memiliki nilai sama dengan nol. Langkah 6:

Pengosongan tabu list, dan ulangi langkah 2 jika diperlukan. Tabu list perlu dikosongkan untuk diisi lagi dengan urutan tempat yang baru pada siklus selanjutnya, jika jumlah siklus maksimum belum tercapai atau belum terjadi konvergensi. Algoritma diulang lagi dari langkah pengisian tabu list dengan harga parameter intensitas jejak kaki semut antar tempat yang sudah diperbaharui. 3.1 Sistem Informasi Geografis (SIG)

Geografi adalah informasi mengenai permukaan bumi dan semua objek yang berada diatasnya, yang menjadi kerangka bagi pengaturan dan pengorganisasian bagi semua tindakan selanjutnya. Sistem Informasi Geografis adalah system yang berbasis komputer yang digunakan untuk menyimpan data dan memanipulasi informasi geografis.

Sistem informasi Geografis memiliki beberapa definisi, seperti Sistem informasi geografis adalah sebuah tools yang untuk memproses data spasial ke dalam sebuah informasi, dimana informasi terikat secara eksplisit, dan digunakan untuk membuat suatu keputusan (Demers, 1997). Diambil dalam arti luas sebuah system informasi geografis adalah pengaturan atau prosedur berbasis computer atau manual yang digunakan untuk menyimpan dan memanipulasi data referensi geografis (Aronof, 1989). PERANCANGAN SISTEM Aturan Bisnis

Beberapa aturan bisnis dalam rancangan basis data dalam Sistem Informasi Geografis ini adalah : 1. Pengguna bisa melakukan proses view informasi yang sudah disediakan yaitu: peta wilayah

Yogyakarta beserta informasi dari masing – masing lokasi yang berupa informasi sekolah, dan jalan terpendek yang akan dilewati dengan menentukan titik asal dan rute titik tujuan.

2. Pengguna bisa melakukan zoom terhadap peta yang akan ditampilkan. 3. Admin dapat mengupdate data lokasi yang berupa data sekolah

Data Flow Diagram

DFD yang dibuat dalam sistem ini mencakup dua entitas luar yaitu administrator dan user. Data Context Diagram dapat juga disebut Diagram Aliran Data level 0. Data Context Diagram berisi penjelasan umum atau global tentang proses yang terjadi dalam sistem yang menggambarkan interaksi antara sistem dan entity luar. Berdasarkan pemahaman tersebut, maka Diagram Konteks dapat dilihat pada Gambar 4.1

Administrator

User

0

SIG

Data Sekolah

Data Jenis_Sekolah

Data Jurusan

Data Jalan

Sekolah

Tempat Asal

Tempat Tujuan

Info Sekolah

Rute Perjalanan

Sekolah

Jenis_Sekolah

Jurusan

jalan

Gambar 4.1. Diagram Konteks

Administrator melakukan transaksi data Lokasi yang berupa data sekolah, jenis sekolah

dan data jurusan serta data jalan. Administrator juga menerima laporan lokasi, jenis sekolah dan jurusan serta jalan.

User adalah pengguna yang membutuhkan informasi lokasi yang berupa informasi sekolah, dan tempat asal ke tempat tujuan dengan mencentang combo box pada layar, maka akan mendapatkan aliran data yang dibutuhkan.

Dari diagram diagram pada Gambar 4.2, dekomposisi kedalam DFD level 1 akan lebih memperjelas sistem yang akan diusulkan dapat dilihat pada Gambar 4.2.

1

Proses

Autentikasi

2

Proses

Setup Data

3

Proses

Tampilan

Administrator

Login

User, pass

Data Sekolah

Data Jenis_sekolah

Data Jurusan

Data Jalan

Sekolah

Jenis_Sekolah

Jurusan

Jalan

User, pass

Data SEkolah

Jenis_Sekolah

Jurusan

Jalan

User

Sekolah

Tempat Asal

Tempat Tujuan

Data Sekolah

Jenis_Sekolah

Data Jurusan

Data Jalan

Info Sekolah

Rute Perjalanan

Sekolah

Jenis_Sekolah

Jurusan

jalan

Hak akses login

Gambar 4.2. DAD Level 1

Gambar 4.2 untuk membuka halaman administrator maka administrator harus login terlebih

dahulu jika login valid maka akan memasuki fasilitas administrator yang bertugas untuk mengatur data letak lokasi sekolah berdasarkan kategori yang diinputkan sehingga informasi yang disajikan akan selalu update. Administrator juga dapat memasukkan data dan mengaupdate data sekolah, data jenis sekolah dan data jurusan serta data jalan kemudian disimpan di berkas, selain itu juga administrator menerima laporan data sekolah, data jenis sekolah, data jurusan dan data jalan.

Proses Tampilan, user dapat memilih menu yang ada yaitu : menu sekolah, dan menu jalan dengan penentuan rute yang akan dilewati dengan masukan rute awal dan rute akhir serta dapat melakukan zoom, User juga akan menerima laporan sesuai dengan menu yang dipilihnya.

DAD level 1 pada Gambar 4.2 dapat dijabarkan lagi guna memperjelas proses yang dilakukan oleh sistem, seperti Gambar 4.3 DAD Level 2 Proses Setup Data dan Gambar 4.4 DAD Level 2 Proses Tampilan

Administrator

2.1

Proses

Sekolah

2.3

Proses

Jurusan

2.2

Proses

Jenis_Sekolah

2.4

Proses

Jalan

Sekolah

Jenis_Sekolah

Jurusan

Jalan

DataSekolah

Data Jenis_Sekolah

Data Jurusan

Data

JalanData Jalan

Data jalan

Data Jenis_Sekolah

Data Sekolah

Data Jenis_Sekolah

Sekolah

Jenis_Sekolah

Jurusan

Jalan

Data Sekolah

Data Sekolah

Gambar 4.3. DAD Level 2 Proses Setup Data

Pada Gambar 4.3 DAD Level 2 Proses Setup Data dapat dijelaskan masing–masing

prosesnya sebagai berikut : 1. Proses Sekolah

Proses Sekolah, administrator memasukkan dan atau mengupdate data sekolah kemudian disimpan di berkas sekolah dan proses sekolah memberikan informasi sekolah ke administrator. 2. Proses Jenis_Sekolah

Proses Jenis_Sekolah, administrator memasukkan dan atau mengupdate data Jenis_Sekolah, sistem akan mengecek data tersebut pada berkas sekolah kemudian disimpan di berkas Jenis_Sekolah dan proses Jenis_Sekolah memberikan informasi Jenis_Sekolah kepada administrator. 3. Proses Jurusan

Proses Jurusan administrator memasukkan dan atau mengupdate data Jurusan dan melakukan pengecekan pada berkas Jenis_Sekolah, kemudian disimpan di berkas Jurusan dan proses Jurusan memberikan informasi Jurusan kepada administrator. 4. Proses Jalan

Proses Jalan administrator memasukkan dan atau mengupdate data Jalan dan melakukan pengecekan pada berkas Sekolah kemudian disimpan di berkas jalan. proses Jalan memberikan informasi Jalan kepada administrator.

User

3.1

Proses

Layer Sekolah

3.3

Proses

Algoritma

Semut

Sekolah

Rute terpendek

Titik awal

Titik akhirData Jalan

SekolahData

SekolahPeta

Sekolah

3.2

Proses

Layer Jalan

JalanPeta

Jalan

JalanData

Sekolah

Gambar 4.4. DAD Level 2 Proses Tampilan

Gambar 4.4 DAD Level 2 Proses Tampilan dapat dijelaskan masing– masing prosesnya

sebagai berikut : 1. Proses layer Sekolah

Proses ini user memilih menu layer Sekolah, sistem melakukan pengecekan ke berkas Sekolah, dari hasil pengecekan akan ditampilkan peta digital Lokasi sekolah. 2. Proses layer Jalan

Proses ini user memilih menu layer jalan, sistem melakukan pengecekan ke berkas jalan, dari hasil pengecekan akan ditampilkan peta digital jalan. 3. Proses algoritma Semut

Proses ini user menentukan titik awal dan titik akhir untuk menentukan jalur evakuasi yang bisa dilewati, sistem akan mengecek ke berkas jalan kemudian menampilkan rute jalan yang bisa dilewati.

Perancangan Basis Data

Basis data ini dirancang untuk memberikan petunjuk dan penjelasan mengenai tempat dan struktur penyimpanan data yang akan digunakan.

Tabel 4.1. Struktur Tabel login

Field Type Null Default Key Keterangan

Uname Character (30) No PK

Password Character (32) Yes Null

cookie Character (32) Yes Null

Tabel 4.2. Struktur Sekolah

Field Type Null Default Key Keterangan

Id_sekolah Serial No PK

Nama_sekolah Character(50) Yes Null

The_geom Geometry Yes Null

Id_jenis Serial Yes Null FK1

Id_Jalan Seria Yes Null FK2

Tabel 4.2 Struktur Tabel Sekolah terdiri dari Id_sekolah yang merupakan Primary Key,

nama_sekolah yang merupakan nama dari sekolah, the_geom merupakan geometri dari sekolah, Id_jenis merupakan Foreign key dari tabel jenis sekolah yang menentukan jenis dari

sekolah (SMA, SMK atau MA) Id_jalan juga merupakan foreign key dari tabel jalan yang menentukan alamat sekolah.

Tabel 4.3. Struktur Tabel Jenis_Sekolah

Field Type Null Default Key Keterangan

Id_jenis Serial No PK

Nama_jenis Character(50) Yes Null

Id_sekolah Serial Yes Null FK1

Tabel 4.3 Struktur Tabel Jenis_sekolah terdiri dari Id_jenis yang merupakan Primary Key

tabel jenis_sekolah, nama_jenis yang merupakan jenis (SMA, SMK atau MA) dari sekolah, Id_sekolah merupakan Foreign Key dari tabel sekolah yang berfungsi untuk menentukan nama sekolah.

Tabel 4.4. Struktur Jurusan

Field Type Null Default Key Keterangan

Id_jurusan Serial No PK

Nama_jurusan Character(50) Yes Null

Id_jenis Serial Yes Null FK

Tabel 4.4 Struktur Jurusan terdiri dari Id_Jurusan yang merupakan Primary Key dari

tabel jurusan, nama_jurusan yang merupakan nama dari suatu jurusan, Id_jenis merupakan foreign key dari tabel jenis_sekolah yang menentukan jenis dari suatu jurusan.

PEMBAHASAN

Implementasi Algoritma Semut untuk Pencarian Rute Terpendek berbasis Sistem Informasi Geografis adalah pencarian jalur terpendek sebagai dasar pengambilan keputusan untuk menentukan rute perjalanan Gambar 5.5 dengan menggunakan algoritma Semut.

Gambar 5.5. Jalur Terpendek Algoritma semut memerlukan variabel dan langkah – langkah untuk menentukan jalur

terpendek, langkah – langkah tersebut :

Langkah 1: a. Inisialisasi harga parameter-parameter algoritma, parameter – parameter yang

diinisialisasikan adalah : 1. Intensitas jejak semut antar titik (τij) dan perubahannya 2. Banyak titik (n) termasuk x dan y (koordinat) atau dij (jarak antar titik) 3. Penentuan titik asal dan titik tujuan 4. Tetapan siklus semut (Q) 5. Tetapan pengendali intensitas jejak semut (α) 6. Tetapan pengendali visibilitas (β). 7. Visibilitas antar titik (ηij) ηij digunakan dalam persamaan probabilitas titik yang akan

dikunjungi. Nilai ηij merupakan hasil dari 1/dij (jarak titik). 8. Banyak semut (m). m merupakan banyak semut yang akan melakukan siklus dalam

algoritma semut. Nilai m ditentukan oleh pengguna. 9. Tetapan penguapan jejak semut (ρ) ρ digunakan untuk menentukan τij untuk siklus

selanjutnya. Nilai ρditentukan oleh pengguna. 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 siklus maksimum (NC=NCmax) atau sampai terjadi konvergen.

b. Inisialisasi titik pertama setiap semut. Setelah inisialisasi τij dilakukan, kemudian m semut dititikkan pada titik pertama yang telah ditentukan. Untuk nilai parameter α sebaiknya diberi nilai 0 ≤ α ≤ 1, hal ini dimaksudkan untuk menghindari akumulasi pheromone yang tidak terbatas pada sisi tersebut. Karena jumlah pheromone yang ditinggalkan tidak mungkin bertambah kuat tetapi akan bertambah kurang. Untuk nilai parameter β sebaiknya tidak diberi nilai 0 karena jika diberi nilai 0 maka hasil yang dicapai tidak maksimum. Tidak optimum disini berarti suatu kondisi dimana panjang perjalanan yang dicapai tidak minimum.

Langkah 2:

Pengisian titik pertama ke dalam tabu list. Hasil inisialisasi titik pertama setiap semut dalam langkah 1 harus diisikan sebagai elemen pertama tabu list. Hasil dari langkah ini adalah terisinya elemen pertama tabu list setiap semut dengan indeks titik pertama. Langkah 3:

Penyusunan rute kunjungan setiap semut ke setiap titik. Koloni semut yang sudah terdistribusi ke sejumlah atau setiap titik, akan mulai melakukan perjalanan dari titik pertama masing -masing sebagai titik asal dan salah satu titik– titik lainnya sebagai titik tujuan. Kemudian dari titik kedua masing - masing, koloni semut akan melanjutkan perjalanan dengan memilih salah satu dari titik - titik yang tidak terdapat pada tabuk sebagai titik tujuan selanjutnya. Perjalanan koloni semut berlangsung terus menerus sampai semua titik satu persatu dikunjungi atau telah menempati tabuk. Jika s menyatakan indeks urutan kunjungan, titik asal dinyatakan sebagai tabuk(s) dan titik – titik lainnya dinyatakan sebagai {N- tabuk }, maka untuk menentukan titik tujuan digunakan persamaan probabilitas titik untuk dikunjungi sebagai berikut:

dengan i sebagai indeks titik asal dan j sebagai indeks titik tujuan. Langkah 4: d. Perhitungan panjang rute setiap semut

Perhitungan panjang rute tertutup ( length closed tour) atau Lk setiap semut dilakukan setelah satu siklus diselesaikan oleh semua semut. Perhitungan dilakukan berdasarkan tabuk masing-masing dengan persamaan berikut:

Dengan dij adalah jarak antara titik i ke titik j yang dihitung berdasarkan persamaan:

e. Pencarian jarak terpendek Setelah Lk setiap semut dihitung, akan diperoleh harga minimal panjang rute tertutup

setiap siklus atau LminNC dan harga minimal panjang jalur tertutup secara keseluruhan adalah atau Lmin.

f. Perhitungan perubahan harga intensitas jejak kaki semut antar titik Δτij Koloni semut akan meninggalkan jejak -jejak kaki pada lintasan antar titik yang

dilaluinya. Adanya penguapan dan per bedaan jumlah semut yang lewat, menyebabkan kemungkinan terjadinya perubahan harga intensitas jejak kaki semut antar titik. Persamaan perubahannya adalah:

keterangan:

m = banyak semut τij = panjang jalur setiap semut

dengan ∆ Δτij adalah perubahan harga intensitas jejak kaki semut antar titik setiap semut yang dihitung berdasarkan persamaan.

adalah perubahan harga intensitas jejak kaki semut antar titik setiap semut yang dihitung berdasarkan persamaan.

keterangan:

Q = tetapan siklus semut Lk =length close tour(lct)

untuk (i.j) ∈ titik asal dan titik tujuan dalam tabu k

Langkah 5: 3. Perhitungan harga intensitas jejak kaki semut antar titik untuk siklus selanjutnya.

Harga intens itas jejak kaki semut antar titik pada semua lintasan antar titik ada kemungkinan berubah karena adanya penguapan dan perbedaan jumlah semut yang melewati. Untuk siklus selanjutnya, semut yang akan melewati lintasan tersebut harga intensitasnya telah berubah. Harga intensitas jejak kaki semut antar titik untuk siklus selanjutnya dihitung dengan persamaan :

4. Atur ulang harga perubahan intensitas jejak kaki semut antar titik.

Untuk siklus selanjutnya perubahan harga intensitas jejak semut antar titik perlu diatur kembali agar memiliki nilai sama dengan nol. Langkah 6: Pengosongan tabu list, dan ulangi langkah 2 jika diperlukan. Tabu list perlu dikosongkan untuk diisi lagi dengan urutan titik yang baru pada siklus selanjutnya, jika jumlah siklus maksimum belum tercapai atau belum terjadi konvergensi. Algoritma diulang lagi dari langkah pengisian tabu list dengan harga parameter intensitas jejak kaki semut antar titik yang sudah diperbaharui. Contoh Jika diketahui suatu graph Dengan jarak antar titik(dij) sebagai berikut :

Tabel 5.1. Jarak antar titik

A B C D E

A 0 5 7 3

B 5 0 4

C 7 4 0 5

D 3 0 4

E 5 4 0

1 5

4 3

2

Parameter – parameter yang digunakan adalah α=1.00 β=1.00 ρ=0.50 τij (awal) = 0.01 maksimum siklus (NCmax) = 2 tetapan siklus semut (Q) = 1 banyak semut (m) = 4 dari jarak titik yang telah diketahui dapat dihitung visibilitas antar titik ηij = 1/dij tabel visibilitas antar titik

Tabel 5.2. Visibilitas antar titik

A B C D E

A 0 0.2 0.143 0.33 0

B 0.2 0 0.25 0 0

C 0.1 0.25 0 0 0.2

D 0.3 0 0 0 0.25

E 0 0 0.2 0.25 0

Siklus ke-1 Panjang jalur semut :

Tabel 5.3. Hasil pada siklus pertama

Semut ke- Rute Panjang rute

1 A C B

2 A C E 12

3 A B C E 14

4 A D E 7

Siklus ke-2 Panjang jalur semut :

Tabel 5.4. hasil pada siklus kedua

Semut ke- Rute Panjang rute

1 A C B E 14

2 A C E E 14

3 A B C E 14

4 A D E 7

Dari dua siklus pada tabel 5.1 dan tabel 5.2 diketahui lintasan terpendek yang dihasilkan ke-4 semut dengan panjang lintasan = 7 dengan melewati titik A-D-E. KESIMPULAN

Penelitian yang sudah dilakukan serta pembahasan pada bab–bab sebelumnya, Implementasi Algoritma Semut untuk Pencarian Rute Terpendek berbasis Sistem Informasi Geografis dapat disimpulkan bahwa : 1. Sistem Informasi Geografis mampu menyajikan peta Yogyakarta yang menampilkan

lokasi sekolah SMA, SMK dan MA.

2. Sistem Informasi Geografis mampu menyajikan informasi dari lokasi yang di klik yang berupa informasi sekolah, seperti nama sekolah, alamat, jurusan dan informasi lainnya.

3. Sistem Informasi Geografis memiliki kemampuan mencarikan rute terpendek dari jalur yang akan dilalui dengan menentukan tempat asal dan tempat tujuan, sehingga dapat membantu mengambil keputusan untuk penentuan rute perjalanan dengan menggunakan algoritma Semut.

SARAN

Sesuai dengan pembahasan yang diuraikan pada kesimpulan diatas, maka penulis menyarankan kepada peneliti selanjutnya untuk melengkapi penelitian ini dengan : 1. Pengembangan sistem yang dapat melakukan perhitungan jarak terpendek dengan tempat

tujuan lebih dari satu. 2. Pengembangan sistem yang dapat mempertimbangkan tingkat kemacetan suatu jalan dan

faktor kecepatan kendaraan pada analisis rute terpendek. DAFTAR PUSTAKA [1] Aronoff, S., 1989, Geographic Information System : a Management Persepective, WDL Publications. [2] Buckey, D.J., 2009, Bgis Introduction to GIS, Bio Diversity GIS,

http://bgis.sanbi.org/gis-primer/page_16.htm, <Diakses 09 Januari 2015> [3] Demers, M.N., 1997, Fundamentals of Geographic Information Systems, John Wiley and Sons. [4] Dwidasmara,I.B.G, 2009, Sistem Informasi Geografis berbasis SVG untuk perjalanan Wisata

dengan Dukungan Teknologi Mobile dan Pencarian Rute Terpendek dengan Algoritma Dijkstra, Tesis Program Magister Ilmu Komputer Sekolah Pasca Sarjana Universitas Gadjah Mada, Yogyakarta.

[5] Friendly Purba (2009), Aplikasi Pencari Rute Optimum Menggunakan Algoritma Semut Di Kampus Universitas Sumatera Utara Dengan Dukungan Sistem Informasi Geografis, http://s3.amazonaws.com/academia.edu.documents/37464170/Friendly_Purba_-_Jurnal_Skripsi.pdf?AWSAccessKeyId=AKIAJ56TQJRTWSMTNPEA&Expires=1476345857&Signature=aGbe4u8A21%2BClEANTX%2F6aL1uraE%3D&response-content-disposition=inline%3B%20filename%3DAPLIKASI_PENCARI_RUTE_OPTIMUM_MENGGUNAKA.pdf

[6] Hidayatullah,P., Kawistara, JK., 2014, Pemrograman WEB, Informatika, Bandung. [7] Iskandar, E., 2012, Sistem Informasi Geografis Pemetaan Daerah Rawan Gempa Tektonik serta

Jalur Evakuasi di Yogyakarta, IPTEK-KOM, Volume 14, No.1, Juni 2012. [8] PostgreSQL, 2008, PostgreSQL 8.3.7 Documentation, PostgreSQL Global Development Group,

University of California. [9] Prahasta, E., 2005, Konsep – Konsep Dasar Sistem Informasi Geografis, Informatika, Bandung. [10] Yusman, Y., 2009, Sistem Informasi Geografis dengan MapInfo Profesional, Andi Offset

Yogyakarta. [11] Yuwono, B., dkk., 2009, Implementasi Algoritma Koloni Semut Pada Proses Pencarian Jalur

Terpendek Jalan Protokol di Kota Yogyakarta, Seminar Nasional Informatika 2009 (semnasIF 2009) ISSN: 1979-2328 UPN ”Veteran” Yogyakarta.