HEURISTIC SEARCH & GENERATE AND TEST (Implementasi Algoritma Generate And Test Pada Pencarian Rute Terpendek)

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.           

3               4

                                                     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.

       https://www.scribd.com/doc/175475563/Metode-Pencarian-oleh-IsmaiL

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.