Mencari Jalur terdekat/terpendek Menggunakan Algoritma Hill Climbing

 

    Pada artikel ini kita akan membahas contoh soal tentang pencarian rute terdekat yang bisa  Salesman tempuh ketitik tujuan yang telah ditentukan. Ada banyak jenis algoritma yang dapat kita gunakan untuk mencari jalan atau rute terdekat dalam perjalanan. Baik itu secara rumit maupun dengan cara yang sederhana.

    Pada kasus kali ini kita akan menggunakan Algoritma Hill Climbing untuk memecahkan masalah yaitu mencari rute terdekat dengan metode hill climbing. 

Tanpa berlama-lama, ayo kita menuju masalah yang akan kita pecahkan. 

• Contoh Kasus

       Seorang salesman ingin mengunjungi n kota. Jarak tiap kota sudah diketahui seperti terlihat pada gambar 2. Bantu salesman untuk menentukan rute terpendek, dimana setiap kota hanya boleh dikunjungi 1 kali. Misal 
ada 4 kota dengan jarak sebagai berikut:

1. Operator yang digunakan adalah operator yang bisa menghasilkan kombinasi lintasan kota yang berbeda, yaitu dengan menukar urutan posisi 2 kota dalam suatu lintasan
3. Bila ada n kota, maka kombinasi lintasan :

            

          

        
          Sehingga kalau ada 4 kota, menjadi:

                    

          

          Keenam kombinasi ini akan dipakai semuanya sebagai operator, yaitu:

                1. (1,2) tukar urutan posisi kota ke-1 dengan kota ke-2

                2. (2,3) tukar urutan posisi kota ke-2 dengan kota ke-3

                3. (3,4) tukar urutan posisi kota ke-3 dengan kota ke-4

                4. (4,1) tukar urutan posisi kota ke-4 dengan kota ke-1

                5. (2,4) tukar urutan posisi kota ke-2 dengan kota ke-4

                6. (1,3) tukar urutan posisi kota ke-1 dengan kota ke-3

    Pencarian dilihat dari anak kiri, bila nilai heuristik anak kiri lebih baik maka dibuka untuk pencarian selanjutnya, bila tidak baru melihat tetangga dari anak kiri tersebut. Pada pencarian ini, penggunaan urutan dari kombinasi harus konsisten, misalnya pada penyelesaian ini urutan sesuai no. 1 sampai dengan 6 seperti yang ada di atas. Urutan kombinasi yang lain juga diperkenankan, yang penting konsisten untuk semua level. Untuk lebih jelasnya bisa dilihat seperti pada Gambar 3.

        Keterangan gambar 3.

      *    Pada Gambar 4.2 terlihat bahwa, pada keadaan awal, lintasan terpilih adalah ABCD (=19).

      *    Pada level pertama, hill climbing akan mengunjungi BACD (=17), BACD memiliki nilai heuristik lebih kecil dibandingkan dengan ABCD (17<19), sehingga BACD menjadi pilihan selanjutnya dengan operator Tukar1,2.

      *    Pada level kedua, hill climbing akan mengunjungi ABCD. Karena operator Tukar1,2 sudah digunakan oleh BACD, maka dipilih node yang lain yaitu BCAD (=15). Karena nilai heuristik BCAD lebih kecil dibanding dengan BACD (15<17), maka node BCAD akan menjadi pilihan selanjutnya dengan operator Tukar2,3.
     *    Kemudian hill climbing akan mengunjungi CBAD (=20). Karena nilai heuristik CBAD lebih besar jika dibanding dengan BCAD (20>17), maka dipilih node lain.
     *    Pencarian menuju ke node BACD, karena operator Tukar2,3 sudah pernah digunakan oleh BCAD, maka dipilih node lain.
     *    Kunjungan berikutnya ke node BCDA (=18). Nilai inipun masih lebih besar dari nilai heuristic BCAD, sehingga dipilih node lain.

     *    Node yang dikunjungi berikutnya adalah DCAB (=19). Nilai heuristik DCAB ternyata juga lebih besar dibanding dengan BCAD, sehingga pencarian dilanjuntukan di node lainnya lagi, yaitu BDAC (=14). Nilai heuristik ini sudah lebih kecil daripada nilai heuristik node BCAD (14<15), maka sekarang node ini yang akan diekplorasi.

     *    Pencarian pertama ditemukan node DBAC (=21), yang lebih besar daripada nilai BDAC. Nilai heuristik yang lebih kecil diperoleh pada node BDCA (=13). Sehingga node BDCA ini akan diekplorasi.

     *    Pencarian pertama sudah mendapatkan node dengan nilai heuristik yang kebih kecil, yaitu DBCA (=12). Sehingga node ini diekplorasi juga.
     *    Dari hasil ekplorasi dengan pemakaian semua operator, ternyata sudah tidak ada node yang memiliki nilai heuristik yang lebih kecil dibanding dengan nilai heuristik DBCA, sehingga sebenarnya node DBCA (=12) inilah lintasan terpendek yang kita cari (SOLUSI).
     *    Misalkan tidak dipergunakan semua operator, melainkan hanya dipergunakan 4 operator pertama saja, yaitu: 
                (a) Tukar 1,2 (menukar urutan posisi kota ke-1 dengan kota ke-2).

                (b) Tukar 2,3 (menukar urutan posisi kota ke-2 dengan kota ke-3).

                (c) Tukar 3,4 (menukar urutan posisi kota ke-3 dengan kota ke-4).

                (d) Tukar 4,1 (menukar urutan posisi kota ke-4 dengan kota ke-1).

    Maka pencarian dengan simple hill climbing ini dapat dilihat pada Gambar 4. Lintasan terpendek yang diperoleh adalah B-C-A-D yaitu sepanjang 15. Di sini kita akan terjebak pada nilai minimum lokal yang disebabkan oleh kurangnya operator yang kita gunakan. Kita tidak dapat memperoleh nilai minimum globalnya yaitu sebesar 12.

   Akhirnya Masalah seorang salesman dapat telah terpecahkan menggunakan algoritma Simple Hill Climbing. Mudah bukan? Disamping mudahnya penggunaan metode ini, ada beberapa kekurang jika kita menggunakan algoritma Hill Climbing.

    Adapun Kekurang ataupun kelemahan Algoritma Simple Hill Climbing ialah:

        1. Tidak semua solusi dapat ditentukan. Itu dikarenakan jika menemukan jalur yang pendek di tingkatan pertama maka itu yang akan di seleksi tanpa memeriksa jalur lainnya

        2. Pembatasan kombinasi operator --> Penemuan solusi yang tidak maksimal

    Demikianlah tulisan admin pada artikel ini, semoga isi artikel ini bisa bermanfaat bagi kita semua. Jika ada kekurangan dalam tulisan ini, kami segenap admin mohon maaf

- Good Luck n See you next post -