CLONING-BASED ALGORITHM DAN APLIKASINYA DALAM TRAVELLING SALESPERSON PROBLEM
CLONING-BASED ALGORITHM DAN APLIKASINYA DALAM TRAVELLING SALESPERSON PROBLEM
Saat sekarang ini sudah mulai ditemukan algoritma-algoritma baru yang disebut sebagai bio-inspired algorithm yaitu algoritma komputansi yang diinspirasi oleh mekanisme alamiah makhluk hidup. Sebagai salah satu contoh komunikasi antar protokol yang didasari oleh proses penyebaran penyakit. Salah satu metode dalam bio-inspired algorithm yang baru berkembang adalah immune system-based algorithm yaitu algoritma yang diinspirasi dari cara kerja sistem kekebalan tubuh pada manusia.
SISTEM KEKEBALAN TUBUH MANUSIA
Tubuh manusia sistem kekebalan berfungsi untuk mendeteksi masuknya benda asing atau patogen ke dalam tubuh seperti virus, bakteri yang dapat mengganggu kestabilan tubuh. Sistem kekebalan tubuh tidak dapat mendeteksi secara langsung adanya patogen yang masuk ke dalam tubuh, tetapi dapat dideteksi melalui bagian dari patogen yang disebut dengan antigen.
Jika terdeteksi adanya patogen, sistem kekebalan tubuh bertugas untuk mengeleminasinya dari tubuh. Agar proses eliminasi patogen berlangsung dengan baik dan benar, sistim kekebalan tubuh harus mampu untuk membedakan antara antigen pada patogen yang selanjutnya disebut dengan nonself-antigen dengan antigen yang dimiliki sel-sel tubuh yang disebut dengan self-antigen.
ANALISIS CLONING-BASED ALGORITHM UNTUK MENCARI NILAI OPTIMAL
Analogian antara sistem kekebalan tubuh dan masalah optimasi adalah sebagai berikut. Response dari sistem imune merepresentasikan solusi dan antigen merepresentasikan masalah yang harus diselesaikan. Lebih tepatnya, Sel B adalah sebagai agen-agen buatan yang menjelajahi dan mengeksplorasi lingkungan buatan. Patogen adalah sebagai masalah optimasi, dalam kasus ini, masalah optimasi digambarkan oleh antigen pada patogen. Mekanisme seleksi positif dan seleksi negatif digunakan untuk mengontrol perbanyakan agen dengan mengeliminasi solusi yang buruk atau tidak berguna. Jadi, aturan seleksi positif dan seleksi negatif dapat dipertimbangkan sebagai mekanisme yang tidak hanya memilih solusi yang tepat, tetapi juga mengatur jumlah populasi agen yang tumbuh pada proses kloning .
Menggunakan sifat dasar dari sistem kekebalan tubuh yaitu clonal selection melalui mekanisme seleksi positif dan seleksi negatif, jumlah agen di dalam sistem diatur secara dinamik untuk mencari solusi optimal pada masalah yang diberikan. Faktanya, agen yang diprediksi tidak cocok dapat dimatikan sebelum dilakukan kloning pada agen tersebut. Keputusan itu dibuat pada level agen secara lokal, tidak dibutuhkan kontrol secara global.
APLIKASI PADA TSP
Pada Traveling SalesPerson Problem lingkungan buatannya adalah graf kota dimana node merepresentasikan tiap kota, yang dianalogikan sebagai antigen pada patogen. Sel B adalah agen pencari yang bergerak dari satu kota ke kota tetangganya dan dapat mengkloning dirinya atau menghancurkan dirinya sendiri berdasarkan kriteria seleksi positif dan seleksi negatif. Algoritma ini dimulai dengan meletakkan sebuah agen pencari pada kota asal. Dalam setiap siklus algoritma, agen dapat mengkloning dirinya dan hasil kloning-nya ini bergerak ke kota tetangganya. Ketika suatu agen mencapai kota yang sudah pernah dikunjungi, maka akan memicu seleksi positif dan agen hasil kloning tadi dimatikan (solusi tidak berguna).
Untuk menghentikan proses kloning, jalan terbaik adalah untuk mencoba membuat batas bawah dari solusi optimal. Batas bawah ini akan menjadi tanda berhenti untuk agen lain yang masih berusaha mencari solusi lain, karena solusi tercepat sudah ditemukan. Hal ini secara signifikan mengurangi perjalanan yang sia-sia dan mengurangi jumlah populasi agen. Kondisi ini mengabaikan sejumlah jalur pada graf TSP segera ketika jalur ini menjadi tidak mungkin untuk mendapatkan solusi terbaik.
Referensi
Bakhouya M., J. Gaber, “An Immune Inspired- based Optimization Algorithm: Application to the Traveling Salesman Problem” AMO – Advanced Modeling and Optimization.
SMART. 