Travelling Salesman Problem dengan Algoritma Clonal Selection

Sebenarnya ini tulisan lama, jaman dulu kuliah S2. Lebih spesifiknya, ketika saya mengambil mata kuliah “Intelligent System”. Cerita singkatnya, waktu ambil kuliah itu, dosen pengampu menugaskan mahasiswa untuk membuat implementasi sebuah algoritma (terserah algoritma apa) untuk menyelesaikan Travelling Salesman Problem (TSP), 8-puzzle, atau real world problem lainnya. Waktu itu, saya mengambil topik TSP. Kebetulan, saya menemukan sebuah paper tentang TSP yang berjudul “Optimization of Path Finding Algorithm using Clonal Selection: Application to Travelling Salesperson Problem”. Lebih kebetulan lagi, penjelasan yang diberikan di paper tersebut cukup mudah dipahami, bahkan disertai dengan pseudocode. Mengingat algoritma ini (Clonal Selection) masih relatif baru, saya ingin mencoba mengimplementasikannya.

Bagi yang masih belum familiar dengan TSP, disini, terlebih dahulu saya akan memberikan penjelasan singkat. TSP pertama kali diperkenalkan oleh Rand pada tahun 1948. TSP melibatkan seorang travelling salesman yang harus melakukan kunjungan ke sejumlah kota dalam menjajakan produknya. Rangkaian kota-kota yang dikunjungi harus membentuk suatu jalur sedemikian sehingga kota-kota tersebut hanya boleh dilewati tepat satu kali dan kemudian kembali lagi ke kota awal (untuk setoran ke bosnya, hehe). Maka dari itu, penyelesaian terhadap permasalahan TSP ini membutuhkan optimasi untuk dapat memperoleh jalur terpendek.

Sementara itu, clonal selection merupakan salah satu algoritma yang terinspirasi dari sistem imun (pertahanan) dalam tubuh makhluk hidup. Prinsip umum dari algoritma ini dapat dilihat pada gambar berikut. Gampangannya, ini adalah mekanisme tubuh kita dalam mempertahankan diri dari serangan benda luar seperti bakteri atau virus.

Mekanisme Clonal Selection

Karena sepertinya akan terlalu panjang jika saya jabarkan disini, yang ingin mengetahui penjelasan lengkap tentang algoritma Clonal Selection dapat membaca paper yang saya sebutkan di atas, atau di bab Immune Algorithms – subbab Clonal Selection di e-book “Clever Algorithms” karya Pak Jason Brownlee.

Nah, di bawah ini akan saya tampilkan pemetaan dari algoritma Clonal Selection ke permasalahan TSP.

Immune System TSP
Pathogen Permasalahan (lingkungan antigen), misal: peta kota dimana tiap kotanya merepresentasikan antigen
Respon Kekebalan Solusi, misal: jarak terpendek
B-Cell Agen
Clonal Selection Pembuatan agen baru untuk eksplorasi lingkungan
Seleksi positif/negatif Seleksi agen buruk/ tidak berguna untuk dimusnahkan, misalnya agen yang memiliki cost terlalu besar, agen yang stuck di satu kota dan tidak dapat lagi berpindah ke kota lain, atau agen yang sudah mengunjungi semua kota tapi tidak memiliki jalan kembali ke kota awal

Algoritma umum penyelesaian TSP dengan Clonal Selection ini dapat saya ringkas dengan diagram alir berikut ini.

clonal_bener

Sementara itu, pencarian agen dengan cost minimum dapat saya gambarkan dalam diagram alir berikut. (Kenapa harus ada fungsi ini? Karena mungkin ada beberapa agen yang berhasil melaksanakan “misi”-nya sehingga kita perlu mencari agen mana yang berhasil secara optimal.)

Flowchart Pencarian Agen


Setelah menyusun algoritma, berikutnya saya mengimplementasikan algoritma ini ke dalam sebuah applet. Bagi yang ingin mencoba simulasi algoritma ini, anda dapat membuka link dari applet yang saya sertakan di tulisan sebelumnya. :D

Terakhir, setelah dilakukan pengujian terhadap beberapa input (beberapa input ini dapat dilihat pada applet), ada beberapa kesimpulan yang dapat ditarik, antara lain:

  • Dari segi algoritma, metode Clonal Selection untuk menyelesaikan TSP memberikan hasil yang cukup baik dan lebih efisien jika dibandingkan dengan pendekatan algoritma lain yang mencoba semua kemungkinan. Adapun solusi yang dihasilkan tidak selalu yang terbaik/ optimal, namun masih selalu mendekati optimal. Hal itu juga yang menjadi kekurangan dari algoritma ini.
  • Dari sisi program (applet), tampilannya saya rancang cukup user friendly serta dapat menampilkan Hamiltonian Circuit terbaik hasil dari perhitungan. Namun demikian, penentuan jarak maksimum yang masih manual memungkinkan tidak ditemukannya solusi jika kita memasukkan angka yang terlalu rendah. Selain itu, untuk kasus seperti yang ada pada peta 9 kota yang tidak semua titiknya saling terhubung, solusi juga mungkin tidak ditemukan karena pemilihan kota yang akan dikunjungi selanjutnya dilakukan secara random padahal jumlah Hamiltionian Circuit terbatas. 

Demikian penjelasan singkat dari saya. Semoga bermanfaat. :)

NB:

Feel free to correct, comment, or respond this post. Let’s learn together. \(^o^)/

6 thoughts on “Travelling Salesman Problem dengan Algoritma Clonal Selection

  1. ka saya yg email kk kmrin. saya msh bingung jalan diagram nya. kalo boleh minta contoh manual pengerjaan 5node & 6 node graf lengkap, gmn dia generate agen, gmn jalan agennya, apa smua agen kota yg sudah dikunjunginya sama, saya coba buat 5 node graf lengkap trus mengikuti diagram, agen yg tergenerate cuma 2 dan gk ada solusi -_- mohon bantuannya ka, makasih ka. kalo bisa lewat email aja hehehe

  2. Coba baca papernya disini (ada pseudocode-nya juga):
    http://www.academia.edu/195972/Optimization_of_Path_Finding_Algorithm_using_Clonal_Selection_Application_to_Traveling_Salesperson_Problem

    Step by step dari yang saya kerjakan ya sesuai sama flowchart saya di atas. Mau menggunakan berapa node pun tidak ada bedanya, semua prosesnya sama. Misalnya kalo graphnya kayak gini:

    graph

    Buat satu agen, misalnya agen1. Agen1 punya 2 atribut: kota yang dikunjungi (K) dan cost. Misal dimulai dari A, berarti K = A dan cost = 0. Dari A, dia bisa ke B, bisa juga ke E. Artinya, ada lebih dari 1 kota yang terhubung dengan A yang belum dikunjungi. Agen1 boleh pilih salah satu, random, tidak harus yang costnya lebih kecil. Misalnya milih ke B. Berarti agen1 punya K = A, B dan cost = 5. Sampai disini, pause dulu agen1-nya.

    Karena tadi dari A bisa ke lebih dari 1 kota, duplikasikan agen1. Katakanlah duplikasinya bernama agen2. Fyi, yang diduplikasikan ini agen1 sebelum ke B. Jadi agen2 punya K = A dan cost = 0. Sekarang agen2 boleh pilih kota lain yang belum dikunjungi. Tadi agen1 sudah ke B, berarti agen2 tidak boleh ke B. Di kasus ini, karena cuma ada 2 kemungkinan, ya otomatis agen2 ke E. Berarti sekarang untuk agen2, K = A, E dan cost = 20. Agen2 ini disimpan dulu untuk dievaluasi nanti.

    Lanjut ke agen1. Agen1 ada di B. Dari B cuma bisa ke C, jadi ya agen1 pasti ke C, tanpa perlu ada duplikasi. Berarti sekarang agen1, K = A, B, C dan cost = 5+3 = 8.

    Sekarang dari C, agen1 bisa ke D dan E. Berarti dia harus duplikasi lagi. Katakanlah hasil duplikasinya namanya agen3. Agen3 punya K = A, B, C dan cost = 8. Selanjutnya, agen1 pilih random, misalnya ke D. Berarti sekarang agen1 punya K = A, B, C, D dan cost = 8+5 = 13. Sementara itu, agen3 harus ke E, yang artinya K = A, B, C, E dan cost = 8+5 = 13. Simpan dulu agen3.

    Lanjut agen1 lagi, dari D cuma ada jalan ke C atau E. Kita lihat dari daftar K-nya agen1 = A, B, C, D. Karena C sudah pernah dikunjungi, jadi kemungkinannya sekarang cuma bisa ke E. Tidak perlu duplikasi. Berarti sekarang K = A, B, C, D, E dan cost = 13+10 = 23. Terus agen1 ke E. Dari E bisa A, C, dan D. Tapi berhubung semua sudah pernah dikunjungi, prosesnya berhenti. Nah jika sudah dalam kondisi seperti ini, cek dulu, apakah semua kota sudah dikunjungi? Dalam kasus ini, ya. Apakah ada jalan kembali ke kota awal? Ya. Berarti dapat dikatakan bahwa agen1 berhasil dengan cost 23+20 = 43. Simpan agen1 ke daftar agen berhasil. Proses selesai untuk agen1.

    Selanjutnya agen2 dengan K = A, E dan cost = 20. Dari E, bisa ke A, C, dan D. Ke A tidak mungkin, karena sudah dikunjungi, sisanya ada C dan D. Karena lebih dari 1 kota, duplikasikan (jadi agen4). Misalnya agen2 ke C, berarti K = A, E, C dan cost = 20+5 = 25. Agen4 ke D, jadi nanti K = A, E, D dan cost = 20+10 = 30. Simpan agen4.

    Agen2 dari C bisa ke D dan B (ke E tidak mungkin karena sudah pernah). Duplikasi (jadi agen5). Agen2 ke D sehingga K = A, E, C, D dan cost = 25+5 = 30. Agen5 ke B sehingga K = A, E, C, B dan cost = 25+3 = 28. Simpan agen5.

    Agen2 dari D cuma bisa ke E dan C, padahal semua sudah dikunjung. Evaluasi, apakah semua kota sudah dikunjungi? Belum. Berarti agen2 gagal. Proses selesai untuk agen2.

    Agen3 K = A, B, C, E dan cost = 13. Dari E cuma bisa ke D atau A. Karena A sudah dikunjungi, dia ke D, tanpa duplikasi. Berarti K = A, B, C, E, D dan cost = 13+10 = 23. Dari D, agen3 cuma bisa ke C dan E, tapi ternyata semua sudah dikunjungi. Evaluasi, apakah semua kota sudah dikunjungi? Ya. Apakah ada jalan kembali ke kota awal? Tidak. Berarti disini agen3 gagal. Proses selesai untuk agen3.

    Agen4 K = A, E, D dan cost = 30. Dari D pasti ke C karena E sudah dikunjungi. Jadi, K = A, E, D, C dan cost = 30+5 = 35. Dari C pasti ke B, K = A, E, D, C, B dan cost = 35+3 = 38. Dari B sudah tidak bisa kemana-mana. Evaluasi, apakah semua kota sudah dikunjungi? Ya. Apakah ada jalan kembali ke kota awal? Ya. Tambahkan agen4 ke agen berhasil dengan cost= 38+5 = 43. Proses selesai untuk agen4.

    Agen5 K = A, E, C, B dan cost = 28. Dari B tidak bisa kemana-mana. Evaluasi, apakah semua kota sudah dikunjungi? Belum. Agen5 gagal. Proses selesai untuk agen5.

    Sekarang sudah tidak ada agen lagi. Waktunya mengevaluasi agen-agen yang berhasil. Cari agen yang costnya paling kecil. Di kasus ini, agen1 dan agen4 memiliki cost yang sama, jadi tidak masalah memilih salah satunya untuk dijadikan solusi yang paling optimal. Atau jika kita memiliki patokan cost maksimal, bisa dicek juga disini. Misalnya kita tentukan maksimalnya 40, ternyata walaupun agen1 dan agen4 berhasil, costnya melebihi nilai maksimal yang kita tentukan. Berarti disini, anggapannya tetap tidak ada agen yang berhasil (solusi tidak ditemukan).

    Semoga penjelasan yang panjang lebar ini bisa bikin lebih paham. :)

    NB:
    Tidak ada solusi itu wajar, karena pemilihan kotanya kan random. Jika tidak semua path bisa membentuk Hamiltonian Circuit, bisa jadi solusinya memang tidak akan ditemukan.

    • ok ka makasih. udh paham sekarang setelah di beri contoh. baru td sore saya diskusi sm dosen pembimbing. maaf” ni ka bahasa flowchartnya membingungkan dan dosen saya jg bingung hehehe tp dr contoh ini udh mantep dh. makasih banyak ka doakan cepet selesai ya ka hehehe.

  3. Kalau clonal selection ni di aplikasikan ke channel assignment kira-kira gimana ya ?
    kebetulan topik skripsi ku penyelesaian channel assignment dengan algoritma clonal selection.
    makasih sebelumnya..

    • Mungkin secara algoritma, Clonal Selection ya kurang lebih seperti yang saya tuliskan disini. Tapi mohon maaf mbak, kalau untuk channel assignment mungkin saya kurang bisa menjelaskan. Khawatirnya nanti malah salah, karena problemnya berbeda dengan travelling salesman. :)

      • Makasii sebelumnya.. :)
        kalau ada info tentang channel assignment tolong di share yah..
        makasiii

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s