BAB II KAJIAN TEORI. semut, dan travelling salesman problem. Teori graf digunakan untuk menerapkan

BAB II KAJIAN TEORI

Pada bab kajian teori akan dibahas tentang teori graf, algoritma, algoritma semut, dan travelling salesman problem. Teori graf digunakan untuk menerapkan aplikasi rute Trans Jogja. Optimasi digunakan untuk mencari nilai optimal dalam menjalankan algoritma semut. Travelling salesman problem digunakan sebagai salah satu bentuk permasalahan rute terpendek Terminal Giwangan hingga Bantul Kota dengan menggunakan data berupa jarak antar halte. Data yang didapat dimodelkan ke dalam bentuk graf kemudian diselesaikan dengan metode algoritma semut. A. Teori Graf 1. Definisi Graf Suatu graf dapat dipandang sebagai kumpulan titik yang disebut simpul dan segmen garis yang menghubungkan dua simpul yang disebut dengan rusuk. Definisi 2.1 (Mardiyono, 1996:1) Graf G yang dilambangkan dengan 𝐺 = (𝑉, 𝐸) terdiri atas dua himpunan 𝑉 dan 𝐸 yang saling asing. 𝑉 bukan himpunan kosong dengan unsur-unsurnya disebut simpul,

sedangkan

unsur

himpunan

𝐸

disebut

rusuk.

Setiap

rusuk

menghubungkan dua simpul yang disebut simpul-simpul ujung dari rusuk tersebut. Contoh graf pada gambar 2.1 menunjukkan graf G dengan 𝑉 = {𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 } dan 𝐸 = {𝑒1 , 𝑒2 , 𝑒3 , 𝑒4 , 𝑒5 , 𝑒6 }.

8

𝐺 Gambar 2.1 Contoh Graf 𝐺 2. Keterhubungan Menurut Chartrand & Zang (2005:13), sebuah graf G dikatakan terhubung jika setiap dua simpul graf G terhubung. Dengan kata lain, graf G dikatakan terhubung jika ada suatu lintasan antara sembarang dua simpul. Graf dapat digunakan sebagai model dari suatu sistem, salah satunya yaitu model sistem rute perjalanan. Gambar 2.2 digunakan sebagai ilustrasi untuk membedakan graf berdasarkan rusuk yang dilalui dan simpul yang dituju dan disinggahi.

𝐻 Gambar 2.2 Contoh Graf 𝐻 9

Berikut akan dijelaskan keterhubungan graf yaitu jalan (walk), jejak (trail), lintasan (path), sikel (cycle), dan sirkuit (circuit). a. Jalan (Walk) Definisi 2.2 (Mardiyono, 1996: 41) Misalkan graf G dengan rusuk 𝑉 = {𝑣1, 𝑣2 , 𝑣3 , … , 𝑣𝑘 } dan simpul 𝐸 = {𝑒1, 𝑒2 , 𝑒3 , … , 𝑒𝑘 },

yang

membentuk

barisan

berhingga

𝑊=

{𝑣1 , 𝑒1 , 𝑣2 , 𝑒2 , 𝑣3 , 𝑒3 , … , 𝑣𝑘 , 𝑒𝑘 }. Maka, definisi jalan (walk) adalah suatu barisan yang suku-sukunya berupa simpul dan rusuk yang diurutkan secara bergantian sedemikian hingga rusuk ujung 𝑒𝑖 adalah simpul 𝑣𝑖−1 dan 𝑣𝑖 . Pada gambar 2.2, contoh

suatu

jalan

(walk)

adalah

barisan

berhingga

𝑊=

{𝑣1 , 𝑒2 , 𝑣5 , 𝑒3 , 𝑣4 , 𝑒5 , 𝑣6 , 𝑒6 , 𝑣5 }. b. Jejak (Trail) Definisi 2.3 (Mardiyono, 1996: 41) Jejak (Trail) adalah walk tanpa rusuk berulang. Pada gambar 2.2, contoh jejak adalah 𝑊 = {𝑣1 , 𝑒2 , 𝑣5 , 𝑒3 , 𝑣4 , 𝑒4 , 𝑣2 , 𝑒9 , 𝑣6 , 𝑒6 , 𝑣5 , 𝑒7 , 𝑣3 }. c.

Lintasan (Path)

Definisi 2.4 (Mardiyono, 1996: 41) Lintasan (Path) adalah jejak tanpa simpul berulang. Contoh pada gambar 2.2 ditunjukkan oleh 𝑊 = {𝑣1 , 𝑒1 , 𝑣4 , 𝑒3 , 𝑣5 , 𝑒6 , 𝑣6 , 𝑒9 , 𝑣2 , 𝑒8 , 𝑣3 }.

10

d. Sirkuit (circuit) Definisi 2.5 Sirkuit adalah jalan tertutup (closed walk) dengan rusuk tidak berulang atau dengan kata lain sirkuit adalah jejak (trail) yang tertutup. Contoh sirkuit pada gambar 2.2 adalah 𝑊 = {𝑣1 , 𝑒2 , 𝑣5 , 𝑒6 , 𝑣6 , 𝑒9 , 𝑣2 , 𝑒8 , 𝑣3 , 𝑒7 , 𝑣5 , 𝑒3 , 𝑣4 , 𝑒1 , 𝑣1 } e.

Lintasan Hamilton

Definisi 2.6 Lintasan Hamilton adalah lintasan yang melalui setiap simpul di dalam graf tepat satu kali. f.

Sirkuit Hamilton

Definisi 2.7 Sirkuit Hamilton adalah graf sirkuit yang mengunjungi tiap simpul pada graf terhubung G tepat satu kali, kecuali simpul awal (yang juga merupakan simpul akhir) dilewati dua kali. Contoh Lintasan Hamilton dan Sirkuit Hamilton sebagai berikut:

G1

G2

G3

Gambar 2.3 Contoh Sirkuit Hamilton dan Lintasan Hamilton

11

Pada

gambar

2.3,

graf

G1

merupakan

contoh

lintasan

Hamilton

𝑊 = {𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 }, graf G2 adalah contoh sirkuit hamilton dengan rute 𝑊 = {𝑣4 , 𝑣3 , 𝑣2 , 𝑣1 , 𝑣4 }, sedangkan graf G3 tidak memiliki lintasan Hamilton dan sirkuit Hamilton. 3.

Jenis Graf Graf dapat dibedakan berdasarkan ada tidaknya rusuk ganda, ada tidaknya

loop (gelang), dan ada tidaknya arah (Mardiyono, 1996). Berikut ini dijelaskan beberapa jenis graf, yaitu: a.

Graf Sederhana (Simple Graph)

Definisi 2.8 Graf sederhana adalah graf yang tidak mempunyai rusuk ganda dan tidak mempunyai loop (gelang). Graf sederhana terbagi menjadi beberapa jenis, yaitu: 1) Graf Nol Definisi 2.9 Graf Nol adalah suatu graf yang himpunan rusuknya merupakan himpunan kosong dengan notasi Hn, dengan 𝑛 = jumlah simpul.

H1

H4

Gambar 2.4 Contoh Graf Nol Pada gambar 2.4, Graf H1 dan H4 masing-masing merupakan graf nol dengan banyak simpul 1 dan 4.

12

2) Graf Lengkap Definisi 2.10 Graf lengkap adalah suatu graf yang setiap pasang simpulnya berikatan. Graf lengkap yang dinotasikan dengan n simpul adalah K n . Semua contoh pada gambar 2.5 dibawah ini adalah graf lengkap dan dinotasikan sebagai K1, K2, K3, dan K4.

Gambar 2.5 Contoh Graf Teratur b. Graf Berarah Definisi 2.11 (Mardiyono, 1996: 10) Graf berarah adalah graf yang setiap rusuk mempunyai arah tertentu. Pada gambar 2.6 graf J1 merupakan contoh graf berarah.

J1 Gambar 2.6 Contoh Graf Berarah

13

c.

Graf Tak Berarah

Definisi 2.12 (Mardiyono, 1996: 10) Graf tak berarah adalah graf yang setiap rusuk tidak mempunyai arah tertentu. Pada gambar 2.7 graf J2 merupakan contoh graf tak berarah.

J2 Gambar 2.7 Contoh Graf Tak Berarah

B. Optimasi Optimasi adalah proses pencarian satu atau lebih penyelesaian layak yang berhubungan dengan nilai-nilai ekstrim dari satu atau lebih nilai objektif pada suatu masalah sampai tidak terdapat solusi ekstrim yang dapat ditemukan. (Intan Berlianty & Miftahol Arifin, 2010: 9). Optimal memiliki definisi yaitu nilai terbaik atau paling menguntungkan (Wikipedia: 2013). Pencarian rute optimal pada penelitian ini adalah pencarian rute terpendek. Metode yang digunakan untuk menyelesaikan masalah pencarian jalur terpendek yaitu metode konvensional dan metode heuristik. 1.

Metode Konvensional Metode konvensional adalah metode yang menggunakan perhitungan

matematis biasa. Metode konvensional dilakukan dengan membandingkan jarak 14

masing-masing antar simpul dan kemudian mencari jarak terpendeknya. Ada beberapa metode konvensional yang biasa digunakan untuk melakukan pencarian jalur terpendek, diantaranya : algoritma Djikstra, Algoritma Bellman-Ford, dan algoritma Floyd-Warshall (Iing Mutakhiroh, Indrato, Taufik Hidayat, 2007). 2.

Metode Heuristik Metode heuristik adalah sub-bidang dari kecerdasan buatan yang digunakan

untuk melakukan pencarian dan penentuan jalur terpendek. (Iing Mutakhiroh, Indrato, Taufik Hidayat, 2007). Ada beberapa algoritma pada metode heuristik yang biasa digunakan dalam permasalahan optimasi, diantaranya algoritma genetika, logika fuzzy, jaringan syaraf tiruan, simulated anneling, algoritma semut, dll. Beberapa Jenis Heuristik Searching (Intan Berlianty dan Miftahol Arifin, 2010:15) adalah: a.

Algoritma Immune

b.

Algoritma Koloni Semut

c.

Algoritma Genetika

d.

Logika Fuzzy

e.

Tabu Search

f.

Generate and test

C. Travelling Salesman Problem (TSP) Permasalahan TSP pada awalnya adalah suatu masalah yang ditemukan pedagang ketika berpergian dan singgah di beberapa kota hingga kembali ke kota semula. Selain masalah sarana transportasi, TSP juga mencakup beberapa masalah

15

lainnya, diantaranya masalah efisiensi pengiriman surat atau barang, layanan delivery service dari suatu tempat makan, dan efisiensi petugas bank yang melakukan pengisian Automatic Teller Machine (ATM) di n kota. Penerapan awal Algoritma Semut adalah pada permasalahan TSP. TSP dipilih menjadi kasus rute terpendek pertama yang diterapkan karena TSP merupakan suatu modifikasi perilaku koloni semut buatan yang dengan mudah diadaptasi ke dalam Algoritma Semut. Selain itu, TSP juga mudah dipahami dan penguraian langkah-langkah algoritma tidak dikaburkan dengan banyak istilah teknis (Marco Dorigo & Gianni Di Caro, 1999:146). TSP didefinisikan sebagai suatu permasalahan dalam mencari rute terpendek dengan membangun sebuah perjalanan yang masing-masing simpul dikunjungi tepat satu kali sampai kembali ke simpul awal. Dengan kata lain, TSP bertujuan mencari rute terpendek sebuah graf menggunakan sirkuit Hamilton. TSP hanya memiliki satu salesman dan depot tunggal sebagai simpul awal. TSP digambarkan sebagai graf lengkap berbobot 𝐺 = (𝑉, 𝐸) dengan 𝑉 adalah himpunan simpul, sedangkan 𝐸 adalah himpunan rusuk yang menghubungkan simpul. Setiap rusuk (𝑖, 𝑗) ∈ 𝐸 adalah nilai (jarak) 𝑑𝑖𝑗 yang merupakan jarak dari kota 𝑖 ke kota 𝑗, dengan (𝑖, 𝑗) ∈ 𝑉. Pada TSP simetris, yaitu jarak dari kota 𝑖 ke kota 𝑗 sama dengan jarak dari 𝑗 ke kota 𝑖, berlaku 𝑑𝑖𝑗 = 𝑑𝑗𝑖 untuk semua rusuk (𝑖, 𝑗) ∈ 𝐸. Misalkan dalam graf lengkap G dengan 𝑛 buah simpul (𝑛 > 2), maka graf tersebut mempunyai

(𝑛−1)! 2

buah sirkuit hamilton. Pada teorema lain, jika

terdapat graf lengkap G dengan jumlah simpul 𝑛 > 2 dan n ganjil, maka ada

16

(𝑛−1)! 2

buah Sirkuit Hamilton saling asing, sedangkan untuk jumlah simpul 𝑛 > 3

dan n genap terdapat

(𝑛−1)! 2

buah sirkuit hamilton.

TSP dimodelkan sebagai graf dengan n buah simpul yang mewakili kota-kota yang harus dikunjungi oleh sejumlah m salesman. Misalkan diberikan matriks n x n sebagai berikut.

𝑥𝑖𝑗

1

2

Tabel 2.1 Matriks 𝑥𝑖𝑗 3 …

1

𝑥11

𝑥12

𝑥13

…

2

𝑥21

𝑥22

𝑥23

…

3

𝑥31

𝑥32

𝑥33

…

…

…

… 𝑥𝑛1

n

… 𝑥𝑛2

𝑥1𝑛

𝑥3𝑛 …

𝑥𝑛3

N

…

… 𝑥𝑛𝑛

𝑥𝑖𝑗 adalah variabel biner dari kota i ke kota j yang bernilai sebagai berikut. 𝑥𝑖𝑗 = {

1 , 𝑗𝑖𝑘𝑎 𝑎𝑑𝑎 𝑝𝑒𝑟𝑗𝑎𝑙𝑎𝑛𝑎𝑛 𝑑𝑎𝑟𝑖 𝑘𝑜𝑡𝑎 𝑖 𝑘𝑒 𝑘𝑜𝑡𝑎 𝑗 0, 𝑗𝑖𝑘𝑎 𝑡𝑖𝑑𝑎𝑘 𝑎𝑑𝑎 𝑝𝑒𝑟𝑗𝑎𝑙𝑎𝑛𝑎𝑛 𝑑𝑎𝑟𝑖 𝑘𝑜𝑡𝑎 𝑖 𝑘𝑒 𝑘𝑜𝑡𝑎 𝑗

Selanjutnya, semua sel dalam baris dan kolom dijumlahkan satu persatu. 1. Penjumlahan sel baris pertama. ∑𝑛𝑗=1 𝑥𝑖𝑗 ,

untuk 𝑖 = 1.

2. Penjumlahan sel baris kedua. ∑𝑛𝑗=1 𝑥𝑖𝑗 ,

untuk 𝑖 = 2.

3. Penjumlahan sel baris ketiga. ∑𝑛𝑗=1 𝑥𝑖𝑗 ,

untuk 𝑖 = 3.

17

(2.1)

4. Penjumlahan sel dilakukan seterusnya hingga baris ke-n. Berikut ini penjumlahan sel untuk baris ke-n. ∑𝑛𝑗=1 𝑥𝑖𝑗 ,

untuk 𝑖 = 𝑛.

Persamaan-persamaan hasil penjumlahan sel dalam baris diatas dapat diringkas sebagai berikut 𝑛

∑ 𝑥𝑖𝑗 ,

𝑢𝑛𝑡𝑢𝑘 𝑖 = 1,2,3, … , 𝑛

(2.2)

𝑗=1

Kemudian dilanjutkan penjumlahan sel dalam kolom pertama hingga ke-n. 1. Penjumlahan sel kolom pertama. ∑𝑛𝑖=1 𝑥𝑖𝑗 ,

untuk 𝑗 = 1.

2. Penjumlahan sel kolom kedua. ∑𝑛𝑖=1 𝑥𝑖𝑗 ,

untuk 𝑗 = 2.

3. Penjumlahan sel kolom ketiga. ∑𝑛𝑖=1 𝑥𝑖𝑗 ,

untuk 𝑗 = 3.

4. Penjumlahan sel dilakukan seterusnya hingga sel kolom ke-n. Berikut ini penjumlahan untuk sel kolom ke-n. ∑𝑛𝑖=1 𝑥𝑖𝑗 ,

untuk 𝑗 = 𝑛.

Persamaan-persamaan hasil penjumlahan sel dalam kolom diatas dapat diringkas sebagai berikut. 𝑛

∑ 𝑥𝑖𝑗 ,

𝑢𝑛𝑡𝑢𝑘 𝑗 = 1,2,3, … , 𝑛

(2.3)

𝑖=1

Selanjutnya, untuk menjamin masing-masing kota hanya dikunjungi satu kali maka persamaan ∑𝑛𝑗=1 𝑥𝑖𝑗 diberi nilai 1. Variabel 𝑐𝑖𝑗 dimasukkan dalam 18

persamaan ∑𝑛𝑗=1 𝑥𝑖𝑗 agar dapat diketahui bahwa rute dari i ke j terlewati atau tidak. 𝑐𝑖𝑗 adalah jarak dari kota i ke kota j. Tujuan akhir TSP adalah mencari rute minimal, sehingga persamaan tersebut menjadi: 𝑛

𝑛

𝑍 = 𝑚𝑖𝑛 ∑ ∑ 𝑐𝑖𝑗 𝑥𝑖𝑗 . 𝑢𝑛𝑡𝑢𝑘 𝑖, 𝑗 = 1,2,3, … , 𝑛

(2.4)

𝑖=1 𝑗=1

dengan kendala: ∑𝑛𝑖=1 𝑥𝑖𝑗 = 1

𝑗 = 1,2,3,4, … , 𝑛

(2.5)

∑𝑛𝑗=1 𝑥𝑖𝑗 = 1

𝑖 = 1,2,3,4, … , 𝑛

(2.6)

∑𝑛𝑖=1 𝑥𝑖𝑗 = 0

𝑖=𝑗

(2.7)

Persamaan (2.5) dan Persamaan (2.6) menjamin bahwa setiap kota hanya dikunjungi sekali oleh salesman, sedangkan persamaan (2.7) menyatakan jika jarak dari dan menuju kota yang sama adalah nol. Sebagai contoh kasus TSP yang telah dibentuk ke dalam suatu graf yang terdiri dari 4 kota dan masing-masing kota terhubung satu sama lain dengan jarak tertentu. Jika kasus TSP dibawa ke dalam bentuk graf, maka diperoleh graf seperti pada gambar 2.8, dengan v1 hingga v4 merupakan kota dan bobot merupakan jarak antar kota.

19

Gambar 2.8 Contoh Kasus TSP Dari gambar 2.8 diketahui bahwa graf tersebut adalah graf berbobot dan tidak berarah. Berdasarkan gambar tersebut, akan ditentukan sirkuit Hamilton terpendek (𝐿𝑚𝑖𝑛 ) yang harus dilalui seorang salesman dengan mengunjungi setiap kota tepat satu kali dan kembali lagi ke kota asal. Graf lengkap dengan 𝑛 = 4 simpul seperti yang ditunjukkan pada gambar 2.8 mempunyai

(4−1)! 2

= 3 Sirkuit Hamilton, yaitu:

𝐿1 = (𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝑣1 ) dengan panjang rute 6+8+9+9=32. 𝐿2 = (𝑣1 , 𝑣3 , 𝑣4 , 𝑣2 , 𝑣1 ) dengan panjang rute 5 + 9 + 4 + 6 = 24. 𝐿2 = (𝑣1 , 𝑣3 , 𝑣2 , 𝑣4 , 𝑣1 ) dengan panjang rute 9 + 4 + 8 + 5 = 26. Terlihat, sirkuit Hamilton terpendek dari kasus diatas adalah 𝐿𝑚𝑖𝑛 = 𝐿2 dengan panjang sirkuit 24. D. Algoritma Kata “algoritma” berasal dari nama matematikawan Persia abad kesembilan, Abu Ja’far Mohammed Ibn Musa Al-Khowarizmi. Sampai pada tahun 1950, algoritma selalu diasosiasikan dengan Euclid’s Algorithm, yaitu suatu proses yang menjelaskan cara mencari bilangan pembagi terbesar untuk dua buah bilangan 20

(greatest common divisor). Definisi algoritma yaitu

metode langkah demi

langkah dari pemecahan suatu masalah. Pada Kamus Besar Bahasa Indoonesia (KBBI), definisi algoritma adalah suatu urutan logis pengambilan keputusan untuk pemecahan masalah. Algoritma mempunyai peran penting dalam matematika dan ilmu komputer yang didasarkan pada prinsip-prinsip matematika. Solusi masalah bisa dijalankan oleh komputer apabila solusi diubah penjabarannya menjadi serangkaian langkahlangkah yang tepat (Richard, 1998:134). Algoritma mempunyai ciri khas seperti yang dikutip dari Richard (1998:35) sebagai berikut: 1.

Masukan (Input) Algoritma memerlukan masukan untuk diolah. Pada penelitian ini masukan

adalah jarak tiap halte Bus Trans Jogja. 2.

Keluaran (Output) Setiap algoritma memberikan satu atau beberapa hasil keluaran. Pada

penelitian ini keluaran algoritma berupa jarak optimal. 3.

Presisi (Precision) Ciri algoritma selanjutnya adalah setiap langkah dinyatakan secara jelas

(presisi). 4.

Determinism Hasil intermediate dari tiap langkah eksekusi adalah tunggal dan semata-mata

bergantung pada masukan dan hasil dari langkah selanjutnya.\

21

5.

Terhingga (Finiteness) Algoritma berhenti setelah beberapa instruksi terhingga dilaksanakan.

6.

Kebenaran (Correctness) Produksi keluaran dari algoritma bernilai benar. Dengan kata lain, algoritma

secara tepat menyelesaikan masalah. 7.

Umum (Generality) Algoritma berlaku umum pada himpunan data yang dimasukkan (input).

E.

Algoritma Semut Algoritma semut pertama kali dipublikasikan Marco Dorigo tahun 1992

dalam tesisnya yang termasuk algoritma pertama yang bertujuan untuk mencari jalur optimal dalam graf berdasarkan perilaku semut mencari jalur dari sarang ke sumber makanan. Sesuai namanya, algoritma semut terinspirasi oleh observasi perilaku semut sungguhan. Semut merupakan serangga sosial yang hidup secara berkelompok atau berkoloni dan mempertahankan hidup koloni dengan perilakunya yang khas daripada hidup individu. Perilaku serangga sosial dalam mencari makanan telah menarik minat para ilmuwan karena mereka dapat mencapai

strukturisasi

koloni

yang

tinggi

jika

dibandingkan

dengan

kesederhanaan hubungan individu dalam koloni (Intan Berliyanti dan Miftahol Arifin, 2010: 62). Perilaku penting yang diteliti adalah semut dapat menemukan jalur terpendek dalam mencari makanan dan kembali lagi ke sarangnya. Selama perjalanan, semut meninggalkan jejak berupa feromon, yaitu suatu subtansi kimia

22

yang berasal dari kelenjar endokrin dan digunakan makhluk hidup untuk mengenali sesama spesies, individu lain, kelompok, dan untuk membantu proses reproduksi. Feromon yang tertinggal akan memberikan informasi kepada semutsemut selanjutnya yang akan mengikuti jejak feromon semut pertama. Proses peninggalan feromon disebut stigmergy, yaitu proses lingkungan yang dimodifikasi agar semut dapat mengingat jalan pulang ke sarang sekaligus sebagai sarana komunikasi semut dengan koloninya. Semut dapat menemukan jalur terpendek dalam algoritma semut dengan perilaku yang secara alamiah akan menemukan jalur terpendek dari sarang ke sumber makanan lalu kembali ke sarang. Jejak feromon merupakan media yang digunakan untuk berkomunikasi antar individu tentang informasi jalur dan digunakan untuk memutuskan kemana harus pergi. Seekor semut bergerak dengan meninggalkan seumlah feromon (dalam jumlah bervariasi) di tanah, sehingga menandai jalur yang diikuti jejak dari zat tersebut. Semut yang bergerak secara acak dapat mendeteksi jejak feromon diletakkan sebelumnya dan mengikuti jejak dengan probabilitas tinggi, sehingga memperkuat jejak dengan feromon semut itu sendiri. Perilaku kolektif yang muncul adalah bentuk perilaku di mana semakin banyak semut mengikuti sebuah jejak, maka jejak tersebut menjadi menarik untuk diikuti. Proses ini demikian ditandai dengan umpan balik yang positif, dengan probabilitas semut memilih suatu jalur meningkat bersamaan dengan jumlah semut yang memilih jalan yang sama dalam langkah-langkah sebelumnya.

23

Gambar 2.9 berikut adalah ilustrasi bagaimana semut dapat membangun rute optimal dengan diberi hambatan (obstacle).

Gambar 2.9 Jalur Semut dengan Hambatan (Obstacle) Misalkan ada sebuah jalur dari sumber makanan A ke sarang E seperti pada gambar 2.9 a). Tiba-tiba sebuah hambatan datang dan jalur sebelumnya terputus, sehingga pada posisi B semut-semut berjalan dari E menuju A (atau pada posisi D semut berjalan arah sebaliknya) harus memutuskan berbelok ke kanan atau kiri seperti pada gambar 2.9 b). Disini, pilihan jalur dipengaruhi oleh intensitas jejak feromon yang ditinggalkan semut pendahulunya. Tingkat feromon yang lebih tinggi di jalur kanan memberi stimulus yang lebih kuat, sehingga probabilitas lebih tinggi ke arah kanan, yang artinya semut banyak berjalan ke arah kanan. Semut pertama yang mencapai titik B (atau D) memiiliki probabilitas yang sama dalam memilih berbelok ke kiri atau ke kanan karena tidak ada feromon tertinggal pada dua jalur tersebut. Jalur BCD yang lebih pendek dari BHD menyebabkan

24

semut yang memilih jalur BCD akan mencapai D sebelum semut lain yang menempuh jalur BHD. Hasilnya semut selanjutnya yang datang dari ED akan menemukan jejak kuat di jalur DCB yang disebabkan oleh setengah koloni semut secara tidak sengaja melewati hambatan melalui ABCD yang secara otomatis melewati BCD. Pada akhirnya, semut-semut lebih memilih (dalam probabilitas) jalur DCB daripada jalur DHB. Akibatnya, jumlah semut yang melewati jalur BCD meningkat dalam satuan waktu daripada semut yang melewati jalur BHD. Hal ini menyebabkan jumlah feromon pada jalur yang lebih pendek meningkat lebih cepat daripada jalur lainnya. Oleh karena itu, probabilitas tiap semut memilih jalur dengan cepat jalur yang lebih pendek. Hasil akhir adalah dengan cepat, semutsemut memilih jalur yang lebih pendek seperti yang ditunjukkan gambar 2.9 c). Namun, hasil akhir tersebut tidak deterministik, sehingga memungkinkan eksplorasi rute alternatif. Semakin banyak semut yang melewati suatu lintasan, maka semakin banyak jejak feromon yang ditinggalkan. Akibatnya, jejak yang jarang dilewati akan menguap sehingga semut tidak melewati jejak tersebut lagi. 1.

Langkah-langkah dalam Algoritma Semut Beberapa langkah dalam menjalankan Algoritma Semut dijelaskan sebagai

berikut: a.

Inisialisasi harga parameter algoritma dan Feromon Awal Dalam Algoritma Semut, terdapat beberapa parameter yang perlu

diinisialisasikan, yaitu:

25

1) Intensitas jejak feromon antar simpul (𝜏𝑖𝑗 ) dan perubahannya (∆𝜏𝑖𝑗 ) Penetapan nilai feromon awal dimaksudkan agar tiap-tiap ruas memiliki nilai ketertarikan untuk dikunjungi oleh tiap-tiap semut. 𝜏𝑖𝑗 harus diinisialisasikan sebelum memulai siklus dan digunakan dalam persamaan probabilitas tempat yang akan dikunjungi. Nilai dari semua feromon pada awal perhitungan ditetapkan dengan angka kecil, yaitu 0 ≤ 𝜏𝑖𝑗 ≤ 1. Δ𝜏𝑖𝑗 adalah perubahan harga intensitas jejak semut. ∆𝜏𝑖𝑗 diinisialisasikan setelah selesai satu siklus dan digunakan untuk memperbaharui intensitas jejak semut serta digunakan untuk menentukan 𝜏𝑖𝑗 untuk siklus selanjutnya. 2) Banyak simpul (n) termasuk dij (jarak antar simpul) Banyak simpul (n) merupakan jumlah simpul yang akan dikunjungi semut pada tiap siklus. Nilai n ditentukan oleh pengguna. 3) Penentuan simpul awal dan simpul tujuan Semut yang akan melakukan tur harus memulai perjalanan dari simpul awal ke simpul tujuan. Dalam kasus TSP, simpul tujuan merupakan simpul awal. 4) Tetapan siklus-semut (𝑄) 𝑄 merupakan konstanta yang digunakan dalam persamaan untuk menentukan Δ𝜏𝑖𝑗 dengan nilai 𝑄 ≥ 0. 5) Tetapan pengendali intensitas jejak semut (𝛼) 𝛼 digunakan pada persamaan probabilitas simpul yang akan dikunjungi dan berfungsi sebagai pengendali intensitas jejak semut. Hal tersebut dimaksudkan untuk menghindari akumulasi feromon yang tidak terbatas pada rusuk tersebut. Akumulasi feromon yang tidak terbatas tidak sesuai logika karena tingkat 26

feromon yang ditinggalkan tidak mungkin bertambah kuat tetapi akan terus berkurang. Nilai parameter α diberi nilai 0 ≤ α ≤ 1. 6) Tetapan pengendali visibilitas (β) 𝛽 digunakan dalam persamaan probabilitas simpul yang akan dikunjungi dan berfungsi sebagai pengendali visibilitas dengan nilai 𝛽 ≥ 0. Hal tersebut dimaksudkan untuk menghindari akumulasi yang tidak terbatas pada perhitungan visibilitas. 7) Visibilitas antar simpul (𝜂𝑖𝑗 ) Visibilitas antar simpul (𝜂𝑖𝑗 ) digunakan dalam persamaan probabilitas simpul yang akan dikunjungi. Sebelum memasuki perhitungan probabilitas dalam perhitungan algoritma semut maka terlebih dahulu dilakukan perhitungan awal untuk menghitung visibilitas antar simpul. Visibilitas antar simpul ini bergantung pada jarak antar titik. Nilai 𝜂𝑖𝑗 diperoleh dari persamaan :

𝜂𝑖𝑗 =

1

(2.11)

𝑑𝑖𝑗

dengan :

𝑑𝑖𝑗 = jarak dari simpul awal ke simpul tujuan 8) Jumlah semut (𝑚) Jumlah semut (𝑚) merupakan banyak semut yang akan melakukan siklus dalam Algoritma Semut. Nilai m ditentukan oleh pengguna.

27

9) Tetapan penguapan jejak semut (𝜌) Tetapan penguapan jejak semut (𝜌) digunakan untuk memperbaharui intensitas jejak feromon semut (𝜏𝑖𝑗 ) untuk siklus selanjutnya dan ditetapkan suatu parameter (𝜌) dengan nilai

0 ≥ 𝜌 ≥ 1.

10) Jumlah siklus maksimum (𝑁𝐶𝑚𝑎𝑥) Jumlah siklus maksimum (𝑁𝐶𝑚𝑎𝑥) bersifat tetap selama algoritma dijalankan, sedangkan 𝜏𝑖𝑗 akan selalu diperbaharui. 𝜏𝑖𝑗 diperbaharui pada setiap siklus algoritma mulai dari siklus pertama (NC – 1) sampai tercapai jumlah siklus maksimum (𝑁𝐶 = 𝑁𝐶𝑚𝑎𝑥) atau sampai terjadi konvergensi. b. Pengisian kota pertama ke dalam tabu list Setelah inisialisai 𝜏𝑖𝑗 dilakukan, lalu semut pertama ditempatkan pada simpul pertama dan mulai inisialisasi untuk simpul kedua. Hasil inisialisasi simpul pertama harus diisikan sebagai elemen pertama dalam tabu list. Tabu list digunakan untuk menyimpan simpul-simpul yang telah dilewati. Hasil dari langkah tersebut adalah terisinya elemen pertama setiap semut dengan indeks simpul pertama, yang berarti bahwa setiap 𝑡𝑎𝑏𝑢𝑘 (𝑖) dapat berisi indeks semua simpul. c.

Penyusunan rute kunjungan Penyusunan rute kunjungan dilakukan oleh koloni semut dari simpul pertama

ke simpul kedua. Kemudian masing-masing semut memilih salah satu simpul dari simpul-simpul yang tidak terdapat pada tabuk sebagai simpul tujuan. Perjalanan koloni semut dilanjutkan terus menerus hingga mencapai simpul tujuan. Jika s menyatakan indeks urutan kunjungan, titik asal dinyatakan sebagai tabuk(s), dan 28

titik-titik lainnya dinyatakan sebagai {N-tabuk}, maka untuk menentukan kota tujun digunakan persamaan probabilitas kota untuk dikunjungi sebagai berikut: 𝛼

𝛽

[𝜏𝑖𝑗 ] .[𝜂𝑖𝑗 ]

, untuk 𝑗𝜖{𝑁 − 𝑡𝑎𝑏𝑢 𝑙𝑖𝑠𝑡} 𝑃𝑖𝑗𝑘 = {∑𝑛𝑗=1[𝜏𝑖𝑙]𝛼.[𝜂𝑖𝑙]𝛽 0 , 𝑢𝑛𝑡𝑢𝑘 𝑗 𝑙𝑎𝑖𝑛𝑛𝑦𝑎

(2.12)

dengan 𝑖 sebagai simpul awal dan 𝑗 sebagai simpul tujuan. d. Perhitungan panjang jalur setiap semut, pencarian rute terpendek, dan perhitungan perubahan harga intensitas feromon 1) Perhitungan panjang jalur setiap semut (Lk) Perhitungan panjang tur setiap semut atau 𝐿𝑘 dilakukan setelah semua semut menyelesaikan satu siklus. Perhitungan ini dilakukan berdasarkan tabuk masingmasing dengan persamaan sebagai berikut

L𝑘 = 𝑑𝑡𝑎𝑏𝑢 (𝑛),𝑡𝑎𝑏𝑢(1) + ∑𝑛−1 𝑚=1 𝑑𝑡𝑎𝑏𝑢(𝑠),𝑡𝑎𝑏𝑢(𝑠+1)

(2.13)

dengan ∑𝑛−1 𝑚=1 𝑑𝑡𝑎𝑏𝑢(𝑠),𝑡𝑎𝑏𝑢(𝑠+1) adalah jarak rusuk dari titik s sampai titik s+1 pada tabu list yang ditempati oleh semut k, dan 𝑑𝑡𝑎𝑏𝑢 (𝑛),𝑡𝑎𝑏𝑢(1) merupakan jarak antara simpul n (akhir) dan simpul pertama (awal) pada tabu list yang ditempati oleh semut k. 2) Pencarian rute terpendek Setelah perhitungan 𝐿𝑘 tiap semut selesai, akan diperoleh rute terpendek pada setiap iterasi (𝐿𝑚𝑖𝑛𝑁𝐶 ). Panjang rute terpendek secara keseluruhan disimbolkan dengan 𝐿𝑚𝑖𝑛 . 3) Perhitungan perubahan harga intensitas feromon antar simpul (∆𝜏𝑖𝑗𝑘 )

29

Koloni semut akan meninggalkan jejak feromon pada lintasan antar simpul yang dilaluinya. Adanya penguapan dan perbedaan jumlah semut yang lewat menyebabkan kemungkinan terjadinya perubahan harga intensitas feromon 𝑘 antarsimpul. ∆𝜏𝑖𝑗 adalah perubahan intensitas jejak feromon antar simpul dan 𝑄

adalah tetapan siklus semut. Persamaan ∆𝜏𝑖𝑗𝑘 disajikan sebagai berikut: 𝑘 ∆𝜏𝑖𝑗

e.

=

Q L { k

0,

,

jika semut menggunakan (i,j) dalam perjalanannya

(2.14) lainnya

Perhitungan harga intesitas jejak feromon untuk siklus selanjutnya dan

atur ulang harga perubahan jejak feromon antar simpul. 1) Perhitungan harga intesitas jejak feromon untuk siklus selanjutnya Intensitas jejak feromon semut antar simpul pada semua lintasan antar simpul 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 untuk siklus selanjutnya dihitung dengan persamaan: 𝜏𝑖𝑗 = 𝜌 . 𝜏𝑖𝑗 (𝑎𝑤𝑎𝑙) + ∆𝜏𝑖𝑗

(2.15)

dengan ρ adalah tetapan penguapan jejak semut, 𝜏𝑖𝑗 adalah intensitas jejak feromon antarsimpul, dan ∆𝜏𝑖𝑗 adalah perubahan intensitas jejak feromon. 2) Atur ulang harga perubahan intensitas jejak feromon antar simpul Perubahan harga intensitas feromon antar simpul untuk siklus selanjutnya perlu diatur kembali agar memiliki nilai sama dengan nol.

30

f.

Pengosongan tabu list Langkah berikutnya adalah pengosongan tabu list. Tabu list dikosongkan dan

langkah b diulangi jika NCmax belum tercapai atau belum terjadi konvergensi (semua semut hanya menemukan satu tur yang sama dengan jarak yang sama pula). Tabu list dikosongkan agar dapat diisi lagi dengan urutan simpul yang baru pada siklus selanjutnya. Langkah algoritma diulang lagi dari pengisian kota pertama ke dalam tabu list dengan parameter intensitas jejak feromon yang telah diperbaharui. Perhitungan

akan

dilanjutkan

hingga

semut

telah

menyelesaikan

perjalanannya mengunjungi tiap-tiap simpul. Hal tersebut akan diulangi hingga NCmax tercapai atau telah mencapai konvergensi.

31

2. Flowchart (diagram alir) Algoritma Semut Berikut disajikan langkah-langkah Algoritma Semut dalam bentuk flowchart: Mulai

Inisialisasi parameter

𝑄 , 𝑚, τ𝑖𝑗 , α, β, ρ,NC𝑚𝑎𝑥

Hitung Probabilitas

Tidak

NC𝑚𝑎𝑥 = Siklus + 1

Tempat tujuan tercapai ?

𝑚 = semut+1

Ya Hitung jarak dengan cara menjumlahkan semua node yang dilalui semut

Tidak

Banyak semut = m ? Y a

Perbaharui τ𝑖𝑗 Tidak

Banyak Siklus = NC𝑚𝑎𝑥 ? Ya Hitung jarak jalur terpendek

Selesai

Gambar 2.10 Flowchart Algoritma Semut

32

F. Keadaan Geografis Kabupaten Bantul Keadaan geografis di Kabupaten Bantul berguna untuk mengetahui garis besar tentang daerah yang menjadi obyek penelitian. Penjelasan yang diperlukan antara lain, keadaan alam atau kontur daerah Kabupaten Bantul, kepadatan penduduk, dan profesi masyarakat Bantul. Keadaan alam Kabupaten Bantul terletak di sebelah selatan Provinsi Daerah Istimewa Yogyakarta, berbatasan dengan: Sebelah Utara

: Kota Yogyakarta dan Kab. Sleman

Sebelah Selatan

: Samudera Hindia

Sebelah Timur

: Kab. Gununkidul

Sebelah Barat

: Kab. Kulonprogo

Secara geografis, Kabupaten Bantul terletak antara 07° 44' 04" - 08° 00' 27" Lintang Selatan dan 110° 12' 34" - 110° 31' 08" Bujur Timur. Kabupaten Bantul memiliki luas wilayah 506,85 Km2 (15,90% dari Luas wilayah Propinsi DIY) dengan topografi sebagai dataran rendah 40% dan lebih dari separuhnya (60%) daerah perbukitan yang kurang subur. Secara garis besar, wilayah Kab. Bantul terdiri dari : 1) Bagian Barat, adalah daerah landai yang kurang serta perbukitan yang membujur dari Utara ke Selatan seluas 89,86 km2 (17,73 % dari seluruh wilayah). 2) Bagian Tengah, adalah daerah datar dan landai merupakan daerah pertanian yang subur seluas 210.94 km2 (41,62 %). 3) Bagian Timur, adalah daerah yang landai, miring dan terjal yang keadaannya masih lebih baik dari daerah bagian Barat, seluas 206,05 km2 (40,65%).

33

4) Bagian Selatan, adalah sebenarnya merupakan bagian dari daerah bagian Tengah dengan keadaan alamnya yang berpasir dan sedikir berlagun, terbentang di Pantai Selatan dari Kecamatan Srandakan, Sanden dan Kretek. Tata guna lahan di Kabupaten Bantul adalah sebagai berikut : 1. Pekarangan : 18.327,15 Ha (36,16 %) 2. Sawah : 16.823,84 Ha (33,19 %) 3. Tegalan : 7.554,45 Ha (14,90 %) 4. Tanah Hutan : 1.697,80 Ha ( 3,35 %) Kabupaten Bantul dialiri enam sungai yang mengalir sepanjang tahun dengan panjang 114 km2, yaitu : 1. Sungai Oyo : 35,75 km 2. Sungai Opak : 19,00 km 3. Sungai Code : 7,00 km 4. Sungai Winongo : 18,75 km 5. Sungai Bedog : 9,50 km 6. Sungai Progo : 24,00 km Pemerintahan di Kabupaten Bantul terdiri dari 17 Kecamatan, 75 Desa, dan 933 Dusun. Data hasil registrasi penduduk awal tahun 2012 adalah sebagai berikut: 1.

Total penduduk 1.015.465 jiwa dengan total penduduk laki-laki sebanyak

502.762 jiwa (49,52%) dan total penduduk perempuan adalah 512.703 jiwa (50,48%). 2.

Kepala Keluarga (KK) sebanyak 306.515

34

3.

Mutasi penduduk Bantul tahun 2011 terdiri dari kelahiran (L) sebanyak 9.499

(0,94%), kedatangan (D) sejumlah 14.358 (1,41%), kematian (M) sebanyak 4.578 (0,45%), dam kepergian (P) sejumlah 11.350 (1,12%). 4.

Kepadatan penduduk Kab. Bantul sebesar 2.012,93 jiwa/km2.

35