BAB I
PENDAHULUAN
1.1 Latar
Belakang
Dalam ilmu
komputer, sebuah algoritma pencarian dijelaskan secara luas adalah sebuah
algoritma yang menerima masukan berupa sebuah masalah dan menghasilkan sebuah
solusi untuk masalah tersebut, yang biasanya didapat dari evaluasi beberapa
kemungkinan solusi. Sebagian besar algoritma yang dipelajari oleh ilmuwan
komputer adalah algoritma pencarian. Himpunan semua kemungkinan solusi dari
sebuah masalah disebut ruang pencarian.
Dan
di pembahasan ini Pada umumnya, banyak masyarakat Yogyakarta terutama pendatang
baru tidak memiliki alat transportasi pribadi seperti sepeda motor maupun
mobil. Oleh karena itu, alat transportasi umum menjadi solusi untuk mencari
tempat makan. Salah satu alat transportasi umum adalah busTrans Jogja. Akan
tetapi tidak banyak masyarakat yang menggunakan bus ini dikarenakan tidak mengetahui
rute bus, lokasi halte, serta jalan yang dilalui pada setiap rutenya.
1.2 Landasan Teori
Beberapa dasar
teori yang menjadi landasan penulisan, yaitu heuristic search, algoritma Generate and Test dan , dan bus
Trans Jogja
1.3 Rumusan Masalah
Untuk
membangun sebuah sistem yang mampu menyelesaikan masalah dengan menggunakan
kecerdasan buatan, maka perlu:
§ Mendefinisikan
masalah dengan tepat, mencakup spesifikasi yang tepat mengenai keadaan awal dan
solusi yang diharapkan.
§
Menganalisis
masalah tersebut dan mencari beberapa teknik penyelesaian masalah yang sesuai
§ Merepresentasikan
pengetahuan yang perlu untuk menyelesaikan masalah tersebut.
§ Memilih
teknik penyelesaian masalah yang terbaik.Untuk mendefinisikan suatu masalah
dengan tepat.
BAB II
PEMBAHASAN
2.1. HEURISTIC SEARCH (pencarian
heuristik)
Heuristic search adalah suatu
istilah yang berasal dari bahasa Yunani yang berarti menemukan/menyingkap.
Heuristik adalah suatu perbuatan yang membantu kita menemukan jalan dalam pohon
pelacakan yang menuntut kita kepada suatu solusi masalah. Heuristik dapat
diartikan juga sebagai suatu kaidah yang merupakan metoda/prosedur yang
didasarkan kepada pengalaman dan praktek, syarat, trik atau bantuan lainnya
yang membantu mempersempit dan memfokuskan proses pelacakan kepada suatu tujuan
tertentu.
(heuristic search) yaitu terdapatnya informasi awal
yang digunakan dalam proses pencarian. Pencarian
buta (blind search) tidak selalu
dapat diterapkan dengan baik, disebabkan karena waktu aksesnya yang cukup lama
& besarnya memori yang diperlukan. Untuk masalah dengan ruang masalah yang
besar, teknik pencarian buta (blind search) bukan teknik yang baik untuk digunakan karena
keterbatasan kecepatan komputer dan memori.
Dengan adanya teknik heuristic
search diharapkan bisa menyelesaikan permasalahan yang lebih besar. Fungsi
dari teknik heuristic search menggunakan suatu fungsi yang menghitung
biaya perkiraan (estimasi) dari suatu simpul tertentu menuju ke simpul tujuan. Heuristic search adalah sebuah
teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan
kemungkinan mengorbankan faktor kelengkapan (completeness). Heuristic
search diharapkan bisa menyelesaikan permasalahan yang lebih besar.
Heuristic search menggunakan
suatu fungsi yang menghitung nilai perkiraan(estimasi) dari suatu simpul
tertentu menuju ke simpul tujuan yang disebutsebagai fungsi heuristik
(heuristic function). Fungsi heuristik digunakan untuk mengevaluasi
keadaan-keadaan masalah individual dan menentukan seberapa jauhhal tersebut
dapat digunakan untuk mendapatkan solusi yang diinginkan.
Heuristic search didefinisikan sebagai prosedur untuk
memecahkan masalah matematika yang terdefinisi secara jelas dengan pendekatan
intuitif di mana struktur masalah dapat ditafsirkan dan dimanfaatkan secara
cerdas untuk mendapatkan solusi yang masuk akal (Silver et al., 1980).
Sebuah heuristik yang baik harus memiliki empat sifat berikut:
·
Upaya
komputasi untuk mendapatkan solusi dilakukan serealistis mungkin.
·
Solusi
yang diperoleh harus mendekati nilai optimal rata-rata, dengan katalain kita
inginkan kinerja yang baik pada nilai rata-rata
·
Kemungkinan
munculnya solusi yang sangat buruk (yang jauh dari nilaioptimal) harus ditekan.
·
Heuristik harus sesederhana mungkin agar
memudahkan pengguna memahami dan sebaiknya dijelaskan secara intuitif.
Jenis-jenis
heuristic search, antara lain:
1.Generate
and test
2.Hill
climbing
3.Pencarian
terbaik pertama (best-first search)
4.Reduksi
masalah ( problem reduction)
5.Constraint
satisfaction
6.Means-end-analysis
Contoh;
Pencarian buta tidak selalu dapat
diterapkan dengan baik, hal ini disebabkan waktu aksesnya yang cukup lama serta
besarnya memori yang diperlukan.
Kelemahan ini sebenarnya dapat diatasi
jika ada informasi tambahan dari domain yang bersangkutan.
Misalkan pada kasus 8-puzzle (Gambar
2.11)
Gambar 2.11 Kasus 8-puzzle.
Gambar
2.12 Langkah awal kasus 8-puzzle.
Langkah pertama dari
permainan tersebut seperti terlihat pada Gambar 2.12. Apabila digunakan
pencarian buta, kita tidak perlu mengetahui operasi apa yang akan dikerjakan
(sembarang operasi bisa digunakan).
Pada
pencarian heuristik perlu diberikan informasi khusus dalam domain tersebut.
Informasi
yang bisa diberikan, antara lain:
a. Untuk
jumlah ubin yang menempati posisi yang benar: jumlah yang lebih tinggi adalah
yang lebih diharapkan (lebih baik), Gambar 2.13.
Gambar 2.13 Fungsi heuristik pertama kasus 8-puzzle.
b. Untuk
jumlah ubin yang menempati posisi yang salah: jumlah yang lebih kecil adalah
yang diharapkan (lebih baik), Gambar 2.14.
Gambar
2.14 Fungsi heuristik kedua kasus
8-puzzle.
c. Menghitung
total gerakan yang diperlukan untuk mencapai tujuan; jumlah yang lebih kecil
adalah yang diharapkan (lebih baik), Gambar 2.15.
Gambar 2.15 Fungsi heuristik ketiga kasus 8-puzzle.
3.1 Pembangkitan dan Pengujian (Generate and Test)
Pada prinsipnya metode ini merupakan penggabungan antara
pencarian mendalam pertama (depth-first search) dengan pelacakan mundur
(backtracking), yaitu bergerak
ke belakang menuju pada suatu keadaan awal. Nilai pengujian berupa jawaban
‘ya’ atau ‘tidak’.
Generate
and test adalah teknik penyelesaian masalah dengan cara menyusun daftar
penyelesaian yang mungkin dan menguji satu per satu untuk menentukan solusi
yang tepat.
Kebaikan
dan Keburukan Generate-and-Test
Jika
penurunan solusi yang mungkin dilakukan secara sistematis, maka procedure
diatas akan dapat menemukan solusi suatu saat, jika memang ada. Tapi sayangnya
jika ruang permasalahan sangat luas maka saat ditemukannya solusi akan menjadi
sangat lama.
Cara
terbaik menerapkan generate-and-test yang sistematis adalah pada tree dari
depth-first search dengan backtracking, yaitu kembali ke stata sebelumnya bila
ditemui stata yg sudah pernah di test atau memodifikasi prosedurnya untuk menelusuri
stata pada bentuk graph
A.
Algoritma generate
and test
1.Bangkitkan
suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau lintasan
tertentu dari keadaan awal)
2.Uji
untuk melihat apakah node tersebut benar-benar merupakansolusinya dengan cara
membandingkan node tersebut atau node akhir dari suatu lintasan yang
dipilih dengan kumpulan tujuan yangdiharapkan.
3.Jika
solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah yang pertama.
B. Contoh generate and test
Contoh
penerapan teknik generate and test adalah
pada traveling salesman problem (TSP). Masalah pada traveling salesman
problem digambarkan sebagai masalah dimana seorang salesman ingin mengunjungi kota. Jarak antara tiap-tiap kota
diketahui dan masalah yang timbul adalah bagaimana menentukan ruteterpendek
dimana setiap kota hanya boleh dikunjungi
tepat
1 kali. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti terlihat
pada Gambar 7.
8
7 5
6
6
Gambar
7 Contoh kasus traveling salesman problem
Penyelesaian
dengan menggunakan metode generate & test dilakukan
denganmembangkitkan solusi-solusi yang mungkin dengan menyusun kota-kota
dalamurutan abjad, yaitu:
·
A – B – C – D
·
A – B – D – C
·
A – C – B – D
·
A – C – D – B
·
A – D – C – B
·
A – D – B – C
Demikian
seterusnya untuk simpul B, C dan D, seperti pada Gambar 8.
A B C D
B C D
C D B D
C B
D C D B
B C
Gambar
8 MetodeGenerate and test
Misalkan
pertama-tama kita mulai dari node A. Kita pilih sebagai keadaan awal adalah
lintasan ABCD dengan panjang lintasan = 19. Kemudian kita
lakukan backtracking untuk mendapatkan lintasan ABDC (panjang lintasan =
18).Lintasan ini kita bandingkan dengan lintasan ABCD, ternyata ABDC <
ABCD,sehingga lintasan terpilih adalah ABDC.
Kita lakukan Backtracking lagi untuk mendapatkan lintasan
ACBD (panjanglintasan = 12), ternyata ACBD < ABDC, maka lintasan terpilih
sekarang adalahACBD. Demikian seterusnya hingga kita temukan solusi yang
sebenarnya. Tabel1 menunjukkan proses pencarian tersebut. Dari Tabel 2 dapat
dilihat bahwa padaakhir pencarian, kita peroleh lintasan terpende k adalah
A-C-B-D 
atau D-B-A-Cdengan panjang lintasan sebesar
12.
Salah
satu kelemahan dari metode generate and test ini adalah perlu membangkitkan
semua kemungkinan sebelum dilakukan pengujian, sehingga membutuhkan waktu yang
cukup besar dalam pencariannya.
Tabel 2
Alur pencarian dengan generate and test pada TS
1.
ABCD 19 ABCD 19
2.
ABDC 18 ABDC 18
3.
ACBD 12 ACBD 12
4.
ACDB 13 ACBD 12
5.
ADBC 16 ACBD 12
6.
ADCB 18 ACBD 12
7.
BACD 17 ACBD 12
8.
BADC 21 ACBD 12
9.
BCAD 15 ACBD 12
10.
BCDA 18 ACBD 12
11.
BDAC 14 ACBD 12
12.
BDCA 13 ACBD 12
13.
CABD 15 ACBD 12
14.
CADB 14 ACBD 12
15.
CBAD 20 ACBD 12
16.
CBDA 16 ACBD 12
17.
CDAB 21 ACBD 12
18.
CDBA 18 ACBD 12
19.
DABC 20 ACBD 12
20.
DACB 15 ACBD 12
21.
DBAC 15 ACBD 12
22.
DBCA 12 ACBD atau DBCA 12
23.
DCAB 17 ACBD atau DBCA 12
24.
DCBA 19 ACBD atau DBCA 12
3.2. Bus Trans
Jogja
Bus Trans Jogja resmi beroperasi pada akhir 2007
dengan jam operasi antara pukul 05.30 –21.30 WIB dan berhenti di halte-halte
khusus yang telah disediakan. Sekarang ini, total jumlah halteyang ada dan
tersebar di DIY adalah 108 halte ditambah dengan 4 terminal yang menjadi tempat
singgah dan transit bus Trans Jogja sehingga total seluruhnya adalah 112 tempat
yang dilalui oleh bus Trans Jogja. Trans Jogja memiliki 8 trayek yaitu 1A, 1B,
2A, 2B, 3A, 3B, 4A, dan 4B.
3.3
Hasil dan Pembahasan
Berikut ini akan disajikan gambar implementasi
sistem yang telah dibuat oleh penulis.
Gambar
1 menunjukkan implementasi tampilan awal Form Utama.
Berikut
ini adalah contoh penyelesaian kasus algoritma Generate and Test dengan mengadaptasi
situasi
dan kondisi bus Trans Jogja. Gambar 4 dibawah ini menggambarkan kasus yang akan
diselesaikan.
Pencarian
dilakukan dari titik A menuju titik C dengan daftar trayek :
-
1A melewati halte: A , D, dan C
-
2A melewati halte : A, E, D, dan C
-
1B melewati halte : B dan D
-
2B melewati halte : A dan B
-
3A melewati halte : B, C dan E
Waktu
jeda 1A = 5 menit, 1B = 5 menit, 2A = 7 menit, 2B = 10 menit, dan 3A = 7 menit.
Daftar
waktu yang dibutuhkan adalah :
A
– B = 8 menit B – D = 7 menit
A
– D = 5 menit D – C = 8 menit
A
– E = 5 menit E – B = 3 menit
B
– C = 7 menit E – D = 5 menit
Berikut
ini adalah langkah-langkah penyelesaian kasus di atas adalah :
1.
Menjabarkan satu per satu kemungkinan yang ada. Gambar 5 menggambarkan proses
penjabaran
satu per satu kemungkinan yang ada
2.
Membuat daftar tabel beserta perhitungan jarak dan waktu untuk setiap jalur
yang telah
dilewati.
3.
Dari Tabel 1 ditemukan rute terpendek berdasarkan jarak adalah A – D – C dengan
total jarak
10
km. Rute alternatif 1 adalah A – B – C dengan total jarak 11 km. Rute
alternatif 2 adalah A
–
E – B – C dengan total jarak 11 km.
4.
Dari Tabel 2 ditemukan rute terpendek berdasarkan waktu adalah A – D – C dengan
total waktu 13 menit. Rute alternatif 1 adalah A – B – C dengan total waktu 15
menit. Rute alternatif 2 adalah A – E – B – C dengan total waktu 15 menit.
5.
Setelah melakukan perhitungan jarak dan waktu, langkah selanjutnya adalah
menentukan trayek bus yang digunakan pada masing-masing rute. Tabel 3
menunjukkan penentuan trayek pada masing – masing rute.
Berdasarkan analisis perhitungan yang dilakukan maka
rute terpendek berdasarkan jarak
adalah
A – D – C dengan total jarak tempuh 10 km tanpa perpindahan.
Berdasarkan analisis perhitungan yang dilakukan maka
rute terpendek berdasarkan waktu
adalah
A – D – C dengan total waktu tempuh 13 menit tanpa perpindahan trayek.
3.4.
Analisis Sistem
Analisis
yang dilakukan terdiri dari 3 hal yaitu keberhasilan sistem, waktu proses,
keefektifan
hasil trayek. Keberhasilan sistem dinilai dari keberhasilan sistem dalam
menemukan
rute
terpendek dengan pengujian yang dilakukan terhadap 50 kasus yang berbeda. Waktu
proses
dibedakan
menjadi 2 yaitu waktu proses dengan parameter jarak dan waktu proses dengan
parameter
waktu.
Analisis waktu proses dilakukan dengan pengujian
terhadap 50 kasus. Hasil trayek dinilai
efektif
jika saran trayek yang dihasilkan sistem sesuai dengan kenyataan. Analisis
hasil trayek
dilakukan
dengan pengujian terhadap 25 kasus dengan parameter jarak dan waktu. Oleh
karena itu,
penulis
akan membandingkan hasil trayek tersebut dengan saran trayek yang penulis
dapatkan dari pakar. Pakar tersebut adalah pramugara bus Trans Jogja.
Berikut
ini adalah hasil pengujian yang dilakukan pada masing-masing analisis:
1.
Berdasarkan pengujian terhadap 50 kasus, sistem mampu menemukan rute terpendek,
alternative rute (jika ada), dan saran trayek.
2.
Berdasarkan pengujian terhadap 50 kasus, waktu rata-rata yang diperlukan sistem
untuk
menemukan
rute terpendek dengan parameter jarak adalah 14,88 detik.
3.
Berdasarkan pengujian terhadap 50 kasus, waktu rata-rata yang diperlukan sistem
untuk
menemukan
rute terpendek dengan parameter waktu adalah 14,86 detik.
4.
Pengujian keefektifan hasil trayek dengan parameter jarak pada 25 kasus,
diketahui 3 kasus
tidak
sesuai dengan kenyataan.
5.
Pengujian keefektifan hasil trayek dengan parameter waktu menunjukkan
keberhasilan pada 25 kasus.
BAB III
PENUTUP
4.1 KESIMPULAN
Berdasarkan
pengujian dan analisa sistem serta memperhatikan keseluruhan proses yang
terjadi,
maka dapat diperoleh kesimpulan sebagai berikut :
Ø Sistem
mampu menerapkan algoritma Generate and Test untuk menemukan rute
terpendek rute alternated beserta saran trayek.
Ø Sistem
mampu menampilkan analisis perhitungan jarak atau waktu beserta jumlah
pergantian trayek yang digunakan.
Ø Prosentase
keberhasilan sistem dalam menemukan rute terpendek dengan algoritma Generate
and Test mencapai 100%.
Ø Perbedaan
rata-rata waktu proses yang dibutuhkan sistem dalam menemukan rute terpendek
DAFTAR PUSTAKA
Hasibuan, Z. I. (2013), Metode
Pencarian Dan Pelacakan. Teknik Informatika
Sekolah Tinggi Teknik
Ibnu Sina Batam.
Kusumadewi, Sri.
(2003). Artificial Intelligence: Teknik dan Aplikasinya, Edisi Pertama. Graha
Ilmu.
Luger, G,F.
(2005). Artificial Intelligence : Structures and Strategies for Complex
Problem Solving, .
Addison-Wesley.
Shaffer,C.A.
(1997). A Practical Introduction to Data Structure and Algorithm Analysis.
New Jersey : Prentice Hall, Inc.
Wilson, R. dan Watkins,
J. (1990). Graphs Theory. Toronto : John Willey & Sons, Inc.
